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

diff --git a/ccan/agar/test/api-bellman_ford.c b/ccan/agar/test/api-bellman_ford.c
new file mode 100644
index 00000000..960cf399
--- /dev/null
+++ b/ccan/agar/test/api-bellman_ford.c
@@ -0,0 +1,249 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/tal/tal.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/agar/agar.h>
+
+#include "simple-graphr.h"
+
+static void test_trivial(void)
+{
+	struct agar_state *sr;
+	aga_icost_t cost;
+
+	ok1(sr = agar_bellman_ford_new(NULL, &trivial_graphr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
+	ok1(cost == 0);
+	tal_free(sr);
+}
+
+static void test_parallel(void)
+{
+	struct parallel_graphr pgr;
+	struct agar_state *sr;
+	aga_icost_t cost;
+	const void *node, *edge;
+
+	parallel_graphr_init(&pgr, 3, 0);
+
+	ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == int2ptr(1));
+	tal_free(sr);
+
+	ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(2)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(!agar_bellman_ford_path(sr, int2ptr(1), NULL, NULL, NULL));
+	tal_free(sr);
+
+	parallel_graphr_init(&pgr, 3, 2);
+	ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, &edge));
+	ok1(cost == 1);
+	ok1(ptr2int(node) == 1);
+	ok1(ptr2int(edge) == 2);
+	tal_free(sr);
+}
+
+#define FULL_LEN	4
+
+static void test_full(void)
+{
+	struct full_graphr fgr;
+	int i, j;
+
+	full_graphr_init(&fgr, FULL_LEN);
+
+	for (i = 1; i <= FULL_LEN; i++) {
+		struct agar_state *sr;
+
+		ok1(sr = agar_bellman_ford_new(NULL, &fgr.gr, int2ptr(i)));
+
+		for (j = 1; j <= FULL_LEN; j++) {
+			aga_icost_t cost;
+			const void *node, *edge;
+
+			ok1(agar_bellman_ford_path(sr, int2ptr(j),
+					      &cost, &node, &edge));
+			if (i == j) {
+				ok1(cost == 0);
+			} else {
+				ok1(cost == 1);
+				ok1(node == int2ptr(i));
+				ok1(edge == int2ptr(j));
+			}
+		}
+
+		tal_free(sr);
+	}
+}
+
+#define CHAIN_LEN	8
+
+static void test_chain(void)
+{
+	struct chain_graphr cgr;
+	int i, j;
+
+	chain_graphr_init(&cgr, CHAIN_LEN);
+
+	for (i = 1; i <= CHAIN_LEN; i++) {
+		struct agar_state *sr;
+
+		ok1(sr = agar_bellman_ford_new(NULL, &cgr.fgr.gr, int2ptr(i)));
+
+		for (j = 1; j <= CHAIN_LEN; j++) {
+			aga_icost_t cost;
+
+			ok1(agar_bellman_ford_path(sr, int2ptr(j),
+					      &cost, NULL, NULL));
+			ok1(cost == labs(i - j));
+		}
+
+		tal_free(sr);
+	}
+}
+
+static void test_error(void)
+{
+	struct agar_state *sr;
+	aga_icost_t cost;
+
+	ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(!agar_bellman_ford_path(sr, int2ptr(3), &cost, NULL, NULL));
+	ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL));
+	tal_free(sr);
+
+	ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(3)));
+	agar_bellman_ford_complete(sr);
+	ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL));
+	ok1(agar_error(sr) == -1);
+	tal_free(sr);
+}
+
+static void test_traversal1(void)
+{
+	struct agar_state *sr;
+	aga_icost_t cost;
+
+	/* This is mostly about testing we correctly handle
+	 * non-reachable nodes */
+	ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(1),
+			      &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(agar_bellman_ford_path(sr, int2ptr(2),
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(agar_bellman_ford_path(sr, int2ptr(3),
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(agar_bellman_ford_path(sr, int2ptr(4),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(agar_bellman_ford_path(sr, int2ptr(5),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(agar_bellman_ford_path(sr, int2ptr(6),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(!agar_bellman_ford_path(sr, int2ptr(7),
+			       NULL, NULL, NULL));
+	ok1(!agar_bellman_ford_path(sr, int2ptr(8),
+			       NULL, NULL, NULL));
+	ok1(!agar_bellman_ford_path(sr, int2ptr(9),
+			       NULL, NULL, NULL));
+	tal_free(sr);
+
+	ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(9)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(9),
+			      &cost, NULL, NULL));
+	ok1(cost == 0);
+	ok1(agar_bellman_ford_path(sr, int2ptr(8),
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(agar_bellman_ford_path(sr, int2ptr(7),
+			      &cost, NULL, NULL));
+	ok1(cost == 1);
+	ok1(agar_bellman_ford_path(sr, int2ptr(6),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(agar_bellman_ford_path(sr, int2ptr(5),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(agar_bellman_ford_path(sr, int2ptr(4),
+			      &cost, NULL, NULL));
+	ok1(cost == 2);
+	ok1(!agar_bellman_ford_path(sr, int2ptr(3),
+			       NULL, NULL, NULL));
+	ok1(!agar_bellman_ford_path(sr, int2ptr(2),
+			       NULL, NULL, NULL));
+	ok1(!agar_bellman_ford_path(sr, int2ptr(1),
+			       NULL, NULL, NULL));
+	tal_free(sr);
+}
+
+static void test_shortcut1(void)
+{
+	struct agar_state *sr;
+	aga_icost_t cost;
+	const void *node;
+
+	ok1(sr = agar_bellman_ford_new(NULL, &shortcut1_graphr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == int2ptr(2));
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
+	ok1(cost == 1);
+	ok1(node == int2ptr(1));
+	tal_free(sr);
+}
+
+static void test_shortcut2(void)
+{
+	struct agar_state *sr;
+	aga_icost_t cost;
+	const void *node;
+
+	ok1(sr = agar_bellman_ford_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
+	ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL));
+	ok1(cost == 1);
+	ok1(node == int2ptr(2));
+	ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
+	ok1(cost == 2);
+	ok1(node == int2ptr(1));
+	tal_free(sr);	
+}
+
+int main(void)
+{
+	plan_tests(3 + 15
+		   + FULL_LEN * (FULL_LEN*4 - 1)
+		   + 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();
+}