X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Faga%2Ftest%2Fapi-bellman_ford.c;fp=ccan%2Faga%2Ftest%2Fapi-bellman_ford.c;h=e0ce1a067822bad31e32377e110e8a39f06eb5d1;hp=0000000000000000000000000000000000000000;hb=eedf1079f38efb2b8dc4fd3f516cce8ac1272c06;hpb=fd96a212810bff1574b047c9079e3e050feb8a28

diff --git a/ccan/aga/test/api-bellman_ford.c b/ccan/aga/test/api-bellman_ford.c
new file mode 100644
index 00000000..e0ce1a06
--- /dev/null
+++ b/ccan/aga/test/api-bellman_ford.c
@@ -0,0 +1,266 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static void test_trivial(void)
+{
+	struct trivial_graph tg;
+	aga_icost_t cost;
+	struct aga_node *node;
+	const void *edge;
+
+	trivial_graph_init(&tg);
+
+	ok1(aga_bellman_ford_start(&tg.sg.g, &tg.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge));
+	ok1(cost == 0);
+	ok1(node == NULL);
+	ok1(edge == NULL);
+	aga_finish(&tg.sg.g);
+}
+
+static void test_parallel(void)
+{
+	struct parallel_graph pg;
+	aga_icost_t cost;
+	struct aga_node *node;
+	const void *edge;
+
+	parallel_graph_init(&pg, 3, 0);
+
+	ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == &pg.sg.nodes[1]);
+	aga_finish(&pg.sg.g);
+
+	ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
+	ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(!aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
+	aga_finish(&pg.sg.g);
+
+
+	parallel_graph_init(&pg, 3, 2);
+	ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
+	ok1(cost == 1);
+	ok1(node == &pg.sg.nodes[1]);
+	ok1(ptr2int(edge) == 2);
+	aga_finish(&pg.sg.g);
+}
+
+#define FULL_LEN	4
+
+static void test_full(void)
+{
+	struct full_graph fg;
+	int i, j;
+
+	full_graph_init(&fg, FULL_LEN);
+
+	for (i = 1; i <= FULL_LEN; i++) {
+		ok1(aga_bellman_ford_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
+
+		for (j = 1; j <= FULL_LEN; j++) {
+			aga_icost_t cost;
+			struct aga_node *node;
+			const void *edge;
+
+			ok1(aga_bellman_ford_path(&fg.sg.g, &fg.sg.nodes[j],
+					      &cost, &node, &edge));
+			if (i == j) {
+				ok1(cost == 0);
+				ok1(node == NULL);
+				ok1(edge == NULL);
+			} else {
+				ok1(cost == 1);
+				ok1(node == &fg.sg.nodes[i]);
+				ok1(edge == &fg.sg.nodes[j]);
+			}
+		}
+
+		aga_finish(&fg.sg.g);
+	}
+}
+
+#define CHAIN_LEN	8
+
+static void test_chain(void)
+{
+	struct chain_graph cg;
+	int i, j;
+
+	chain_graph_init(&cg, CHAIN_LEN);
+
+	for (i = 1; i <= CHAIN_LEN; i++) {
+		ok1(aga_bellman_ford_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
+
+		for (j = 1; j <= CHAIN_LEN; j++) {
+			aga_icost_t cost;
+
+			ok1(aga_bellman_ford_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
+					      &cost, NULL, NULL));
+			ok1(cost == labs(i - j));
+		}
+
+		aga_finish(&cg.fg.sg.g);
+	}
+}
+
+static void test_error(void)
+{
+	struct error_graph eg;
+	aga_icost_t cost;
+
+	error_graph_init(&eg);
+
+	ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
+	ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
+	aga_finish(&eg.sg.g);
+
+	ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
+	aga_bellman_ford_complete(&eg.sg.g);
+	ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
+	ok1(aga_error(&eg.sg.g) == -1);
+	aga_finish(&eg.sg.g);
+}
+
+static void test_traversal1(void)
+{
+	struct traversal1_graph t1g;
+	aga_icost_t cost;
+
+	/* This is mostly about testing we correctly handle
+	 * non-reachable nodes */
+	traversal1_graph_init(&t1g);
+
+	ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
+			      &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
+			       NULL, NULL, NULL));
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
+			       NULL, NULL, NULL));
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
+			       NULL, NULL, NULL));
+	aga_finish(&t1g.sg.g);
+
+	ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
+			      &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
+			       NULL, NULL, NULL));
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
+			       NULL, NULL, NULL));
+	ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
+			       NULL, NULL, NULL));
+	aga_finish(&t1g.sg.g);
+}
+
+static void test_shortcut1(void)
+{
+	struct shortcut1_graph s1g;
+	aga_icost_t cost;
+	struct aga_node *node;
+
+	shortcut1_graph_init(&s1g);
+
+	ok1(aga_bellman_ford_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[3],
+			      &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == &s1g.sg.nodes[2]);
+	ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[2],
+			      &cost, &node, NULL));
+	ok1(cost == 1);
+	ok1(node == &s1g.sg.nodes[1]);
+	aga_finish(&s1g.sg.g);
+}
+
+static void test_shortcut2(void)
+{
+	struct shortcut2_graph s2g;
+	aga_icost_t cost;
+	struct aga_node *node;
+
+	shortcut2_graph_init(&s2g);
+
+	ok1(aga_bellman_ford_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
+	ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[3],
+				  &cost, &node, NULL));
+	ok1(cost == 1);
+	ok1(node == &s2g.sg.nodes[2]);
+	ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[2],
+			      &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == &s2g.sg.nodes[1]);
+	aga_finish(&s2g.sg.g);
+}
+
+int main(void)
+{
+	plan_tests(5 + 15
+		   + FULL_LEN * (1 + FULL_LEN * 4)
+		   + CHAIN_LEN * (1 + CHAIN_LEN * 2)
+		   + 10 + 32 + 7 + 7);
+
+	test_trivial();
+	test_parallel();
+	test_full();
+	test_chain();
+	test_error();
+	test_traversal1();
+	test_shortcut1();
+	test_shortcut2();
+	
+	return exit_status();
+}