aga,agar: Negative weight cycle testcase

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

diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 08b472884728904fb99d53606cc6479d3451b1fa..01bb5aa4d880f579ea4c60dd3f51a64a14a9657d 100644 (file)
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -35,8 +35,9 @@ 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);
+       parallel_graph_init(&pg, 3, 0);
 
        ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
        ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
@@ -45,7 +46,7 @@ static void test_parallel(void)
        ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
        ok1(cost == 0);
        ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
-       ok1(cost == 1);
+       ok1(cost == 2);
        ok1(node == &pg.sg.nodes[1]);
        aga_finish(&pg.sg.g);
 
@@ -56,6 +57,15 @@ static void test_parallel(void)
        ok1(cost == 0);
        ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
        aga_finish(&pg.sg.g);
+
+
+       parallel_graph_init(&pg, 3, 2);
+       ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+       ok1(aga_dijkstra_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
@@ -204,12 +214,56 @@ static void test_traversal1(void)
        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_dijkstra_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
+       ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[3],
+                             &cost, &node, NULL));
+       ok1(cost == 2);
+       ok1(node == &s1g.sg.nodes[2]);
+       ok1(aga_dijkstra_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;
+
+       shortcut2_graph_init(&s2g);
+
+       ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
+       aga_dijkstra_complete(&s2g.sg.g);
+       ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
+       aga_finish(&s2g.sg.g);
+}
+
+static void test_negacycle(void)
+{
+       struct negacycle_graph ng;
+
+       negacycle_graph_init(&ng);
+
+       ok1(aga_dijkstra_start(&ng.sg.g, &ng.sg.nodes[1]) == 0);
+       aga_dijkstra_complete(&ng.sg.g);
+       ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST);
+       aga_finish(&ng.sg.g);
+}
+
 int main(void)
 {
-       plan_tests(7 + 15
+       plan_tests(7 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32);
+                  + 12 + 32 + 7 + 2 + 2);
 
        test_trivial();
        test_parallel();
@@ -217,6 +271,9 @@ int main(void)
        test_chain();
        test_error();
        test_traversal1();
+       test_shortcut1();
+       test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }