aga,agar: Negative weight cycle testcase

[ccan] / ccan / agar / test / api-dijkstra.c

diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 4b03bc6b8fcd9c44b7508b98fcfacae1c3a63ba4..19980919bd7ca059db2a4287ac8aaf318f407148 100644 (file)
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -14,14 +14,11 @@
 
 static void test_trivial(void)
 {
-       struct trivial_graphr tgr;
        struct agar_state *sr;
        aga_icost_t cost;
        const void *node;
 
-       trivial_graphr_init(&tgr);
-
-       ok1(sr = agar_dijkstra_new(NULL, &tgr.gr, int2ptr(1)));
+       ok1(sr = agar_dijkstra_new(NULL, &trivial_graphr.gr, int2ptr(1)));
        ok1(agar_dijkstra_step(sr, &node));
        ok1(ptr2int(node) == 1);
        ok1(!agar_dijkstra_step(sr, &node));
@@ -35,9 +32,9 @@ static void test_parallel(void)
        struct parallel_graphr pgr;
        struct agar_state *sr;
        aga_icost_t cost;
-       const void *node;
+       const void *node, *edge;
 
-       parallel_graphr_init(&pgr, 3);
+       parallel_graphr_init(&pgr, 3, 0);
 
        ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
        ok1(agar_dijkstra_step(sr, &node));
@@ -48,7 +45,7 @@ static void test_parallel(void)
        ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
-       ok1(cost == 1);
+       ok1(cost == 2);
        ok1(node == int2ptr(1));
        tal_free(sr);
 
@@ -60,6 +57,14 @@ static void test_parallel(void)
        ok1(cost == 0);
        ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
        tal_free(sr);
+
+       parallel_graphr_init(&pgr, 3, 2);
+       ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
+       ok1(agar_dijkstra_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
@@ -123,13 +128,10 @@ static void test_chain(void)
 
 static void test_error(void)
 {
-       struct error_graphr egr;
        struct agar_state *sr;
        aga_icost_t cost;
 
-       error_graphr_init(&egr);
-
-       ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(1)));
+       ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(1)));
        ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
@@ -138,7 +140,7 @@ static void test_error(void)
        ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
        tal_free(sr);
 
-       ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(3)));
+       ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(3)));
        ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
@@ -148,15 +150,12 @@ static void test_error(void)
 
 static void test_traversal1(void)
 {
-       struct traversal1_graphr t1gr;
        struct agar_state *sr;
        aga_icost_t cost;
 
        /* This is mostly about testing we correctly handle
         * non-reachable nodes */
-       traversal1_graphr_init(&t1gr);
-
-       ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(1)));
+       ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(1)));
        ok1(agar_dijkstra_path(sr, int2ptr(1),
                              &cost, NULL, NULL));
        ok1(cost == 0);
@@ -183,7 +182,7 @@ static void test_traversal1(void)
                               NULL, NULL, NULL));
        tal_free(sr);
 
-       ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(9)));
+       ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(9)));
        ok1(agar_dijkstra_path(sr, int2ptr(9),
                              &cost, NULL, NULL));
        ok1(cost == 0);
@@ -211,12 +210,48 @@ static void test_traversal1(void)
        tal_free(sr);
 }
 
+static void test_shortcut1(void)
+{
+       struct agar_state *sr;
+       aga_icost_t cost;
+       const void *node;
+
+       ok1(sr = agar_dijkstra_new(NULL, &shortcut1_graphr.gr, int2ptr(1)));
+       ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
+       ok1(cost == 2);
+       ok1(node == int2ptr(2));
+       ok1(agar_dijkstra_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;
+
+       ok1(sr = agar_dijkstra_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
+       agar_dijkstra_complete(sr);
+       ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
+       tal_free(sr);
+}
+
+static void test_negacycle(void)
+{
+       struct agar_state *sr;
+
+       ok1(sr = agar_dijkstra_new(NULL, &negacycle_graphr.gr, int2ptr(1)));
+       agar_dijkstra_complete(sr);
+       ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
+       tal_free(sr);
+}
+
 int main(void)
 {
-       plan_tests(6 + 18
+       plan_tests(6 + 23
                   + FULL_LEN * (FULL_LEN*4 - 1)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32);
+                  + 12 + 32 + 7 + 2 + 2);
 
        test_trivial();
        test_parallel();
@@ -224,6 +259,9 @@ int main(void)
        test_chain();
        test_error();
        test_traversal1();
+       test_shortcut1();
+       test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }