aga,agar: Negative weight cycle testcase

Adds a new test graph which includes a negative weight cycle.  This means
that shortest paths are not well defined, and both Dijkstra's algorithm and
the Bellman-Ford algorithm (which can handle some negative edge weights)
will fail.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 6e5043017788272e6aa8f2b07163e49277d71c34..3168522401018b751eb5b2daa70792d863af2963 100644 (file)
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -63,8 +63,9 @@ int main(void)
        struct traversal1_graph t1g;
        struct shortcut1_graph s1g;
        struct shortcut2_graph s2g;
+       struct negacycle_graph ng;
 
-       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9);
+       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9 + 9);
 
        trivial_graph_init(&tg);
        test_adjacency("trivial", &tg.sg, trivial_adjacency);
@@ -99,5 +100,8 @@ int main(void)
        shortcut2_graph_init(&s2g);
        test_adjacency("shortcut2 graph", &s2g.sg, shortcut2_adjacency);
 
+       negacycle_graph_init(&ng);
+       test_adjacency("negacycle graph", &ng.sg, negacycle_adjacency);
+
        return exit_status();
 }

diff --git a/ccan/aga/test/api-bellman_ford.c b/ccan/aga/test/api-bellman_ford.c
index e0ce1a067822bad31e32377e110e8a39f06eb5d1..5dc032a77bbf7c7d5960465c26d01caea2a27b8d 100644 (file)
--- a/ccan/aga/test/api-bellman_ford.c
+++ b/ccan/aga/test/api-bellman_ford.c
@@ -246,12 +246,24 @@ static void test_shortcut2(void)
        aga_finish(&s2g.sg.g);
 }
 
+static void test_negacycle(void)
+{
+       struct negacycle_graph ng;
+
+       negacycle_graph_init(&ng);
+
+       ok1(aga_bellman_ford_start(&ng.sg.g, &ng.sg.nodes[1]) == 0);
+       aga_bellman_ford_complete(&ng.sg.g);
+       ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST);
+       aga_finish(&ng.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);
+                  + 10 + 32 + 7 + 7 + 2);
 
        test_trivial();
        test_parallel();
@@ -261,6 +273,7 @@ int main(void)
        test_traversal1();
        test_shortcut1();
        test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }

diff --git a/ccan/aga/test/api-bfs.c b/ccan/aga/test/api-bfs.c
index 90fcc62853887595093ce9fff22cc055124d2f23..1a3e1411a229f1ea2b90ba96cea568136b57e565 100644 (file)
--- a/ccan/aga/test/api-bfs.c
+++ b/ccan/aga/test/api-bfs.c
@@ -42,9 +42,10 @@ int main(void)
        struct grid_graph gg1, gg2;
        struct error_graph eg;
        struct traversal1_graph t1g;
+       struct negacycle_graph ng;
        struct aga_node *node;
        
-       plan_tests(2 * 13 + 10 + 10);
+       plan_tests(2 * 13 + 10 + 10 + 6);
 
        trivial_graph_init(&tg);
        test_bfs(&tg.sg, 1, 1);
@@ -100,5 +101,10 @@ int main(void)
        test_bfs_partial(&t1g.sg, 1, 1, 2, 3);
        aga_finish(&t1g.sg.g);
 
+       negacycle_graph_init(&ng);
+       test_bfs(&ng.sg, 1, 1, 2, 3);
+       test_bfs(&ng.sg, 2, 2, 3, 1);
+       test_bfs(&ng.sg, 3, 3, 1, 2);
+       
        return exit_status();
 }

diff --git a/ccan/aga/test/api-dfs.c b/ccan/aga/test/api-dfs.c
index 24d1a4f912078551fbb9faa0161e047fc88f2ef5..c28097a690dcc1687f9273837bd61e6591134527 100644 (file)
--- a/ccan/aga/test/api-dfs.c
+++ b/ccan/aga/test/api-dfs.c
@@ -42,9 +42,10 @@ int main(void)
        struct grid_graph gg1, gg2;
        struct error_graph eg;
        struct traversal1_graph t1g;
+       struct negacycle_graph ng;
        struct aga_node *node;
        
-       plan_tests(2 * 13 + 10 + 10);
+       plan_tests(2 * 13 + 10 + 10 + 6);
 
        trivial_graph_init(&tg);
        test_dfs(&tg.sg, 1, 1);
@@ -100,5 +101,10 @@ int main(void)
        test_dfs_partial(&t1g.sg, 1, 1, 2, 3);
        aga_finish(&t1g.sg.g);
 
+       negacycle_graph_init(&ng);
+       test_dfs(&ng.sg, 1, 1, 2, 3);
+       test_dfs(&ng.sg, 2, 2, 3, 1);
+       test_dfs(&ng.sg, 3, 3, 1, 2);
+
        return exit_status();
 }

diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 74875fbc88f7de672acfb9be7a1cf6ea9e3f7eba..01bb5aa4d880f579ea4c60dd3f51a64a14a9657d 100644 (file)
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -246,12 +246,24 @@ static void test_shortcut2(void)
        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 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32 + 7 + 2);
+                  + 12 + 32 + 7 + 2 + 2);
 
        test_trivial();
        test_parallel();
@@ -261,6 +273,7 @@ int main(void)
        test_traversal1();
        test_shortcut1();
        test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }

diff --git a/ccan/aga/test/negacycle.c b/ccan/aga/test/negacycle.c
new file mode 100644 (file)
index 0000000..8eae4bf
--- /dev/null
+++ b/ccan/aga/test/negacycle.c
@@ -0,0 +1,46 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static ptrint_t *negacycle_first_edge(const struct aga_graph *g,
+                                     const struct aga_node *n)
+{
+       return int2ptr(1);
+}
+
+static ptrint_t *negacycle_next_edge(const struct aga_graph *g,
+                                    const struct aga_node *n,
+                                    ptrint_t *e)
+{
+       assert(ptr2int(e) == 1);
+       return NULL;
+}
+
+static int negacycle_edge_info(const struct aga_graph *g,
+                              const struct aga_node *n,
+                              ptrint_t *e, struct aga_edge_info *ei)
+{
+       struct negacycle_graph *ng = container_of(g, struct negacycle_graph,
+                                                  sg.g);
+       int ni = n - ng->sg.nodes;
+
+       assert(ptr2int(e) == 1);
+       ei->to = &ng->sg.nodes[(ni % 3) + 1];
+       if (ni == 3)
+               ei->icost = -3;
+       return 0;
+}
+
+void negacycle_graph_init(struct negacycle_graph *ng)
+{
+       simple_graph_init(&ng->sg, negacycle_first_edge,
+                         negacycle_next_edge,
+                         negacycle_edge_info);
+}

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index b8da3ad999045bc9207b59871a56fae691a13120..5808993ac2c203364c73b6ffdbbf8f09ebfc95fd 100644 (file)
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -256,4 +256,23 @@ static const struct adjacency_list shortcut2_adjacency[] = {
        {},
 };
 
+/* Negacycle graph
+ *
+ *  A <---- (-3) ----- C
+ *   \                 ^
+ *    (1)->  B -- (1)-/
+ *
+ * Graph with a negative length cycle, and so lacking well-defined shortest paths.
+ */
+struct negacycle_graph {
+       struct simple_graph sg;
+};
+void negacycle_graph_init(struct negacycle_graph *ng);
+static const struct adjacency_list negacycle_adjacency[] = {
+       {1, {2}},
+       {2, {3}},
+       {3, {1}},
+       {},
+};
+
 #endif /* _TEST_GRAPHS_H */

diff --git a/ccan/agar/test/api-bellman_ford.c b/ccan/agar/test/api-bellman_ford.c
index 960cf3994f0109f17b0466fe25a38f0cb0326c00..a161b0ca63d9b3f398bb4e0b068d925e18b63dd2 100644 (file)
--- a/ccan/agar/test/api-bellman_ford.c
+++ b/ccan/agar/test/api-bellman_ford.c
@@ -229,12 +229,22 @@ static void test_shortcut2(void)
        tal_free(sr);   
 }
 
+static void test_negacycle(void)
+{
+       struct agar_state *sr;
+
+       ok1(sr = agar_bellman_ford_new(NULL, &negacycle_graphr.gr, int2ptr(1)));
+       agar_bellman_ford_complete(sr);
+       ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
+       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);
+                  + 10 + 32 + 7 + 7 + 2);
 
        test_trivial();
        test_parallel();
@@ -244,6 +254,7 @@ int main(void)
        test_traversal1();
        test_shortcut1();
        test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }

diff --git a/ccan/agar/test/api-bfs.c b/ccan/agar/test/api-bfs.c
index 27369b6e76f19b73e83ac1ec681beec53935b28e..79ea21ad71ee041a5a31ea0fab3729d52a7997f8 100644 (file)
--- a/ccan/agar/test/api-bfs.c
+++ b/ccan/agar/test/api-bfs.c
@@ -45,7 +45,7 @@ int main(void)
        struct agar_state *sr;
        const void *nr;
        
-       plan_tests(2 * 13 + 12 + 10);
+       plan_tests(2 * 13 + 12 + 10 + 6);
 
        test_bfs(&trivial_graphr.gr, 1, 1);
 
@@ -97,5 +97,9 @@ int main(void)
        test_bfs_partial(sr, 1, 1, 2, 3);
        tal_free(sr);
 
+       test_bfs(&negacycle_graphr.gr, 1, 1, 2, 3);
+       test_bfs(&negacycle_graphr.gr, 2, 2, 3, 1);
+       test_bfs(&negacycle_graphr.gr, 3, 3, 1, 2);
+
        return exit_status();
 }

diff --git a/ccan/agar/test/api-dfs.c b/ccan/agar/test/api-dfs.c
index 625e825c3fac07f63c75001f9795a186b531a6d2..65be2e18353f4ee39eb31442da9a1f202d2b0007 100644 (file)
--- a/ccan/agar/test/api-dfs.c
+++ b/ccan/agar/test/api-dfs.c
@@ -45,7 +45,7 @@ int main(void)
        struct agar_state *sr;
        const void *nr;
        
-       plan_tests(2 * 13 + 12 + 10);
+       plan_tests(2 * 13 + 12 + 10 + 6);
 
        test_dfs(&trivial_graphr.gr, 1, 1);
 
@@ -97,5 +97,9 @@ int main(void)
        test_dfs_partial(sr, 1, 1, 2, 3);
        tal_free(sr);
 
+       test_dfs(&negacycle_graphr.gr, 1, 1, 2, 3);
+       test_dfs(&negacycle_graphr.gr, 2, 2, 3, 1);
+       test_dfs(&negacycle_graphr.gr, 3, 3, 1, 2);
+
        return exit_status();
 }

diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index a5de2ea6b31b9e4074d871749293be4405151408..19980919bd7ca059db2a4287ac8aaf318f407148 100644 (file)
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -236,12 +236,22 @@ static void test_shortcut2(void)
        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 + 23
                   + FULL_LEN * (FULL_LEN*4 - 1)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32 + 7 + 2);
+                  + 12 + 32 + 7 + 2 + 2);
 
        test_trivial();
        test_parallel();
@@ -251,6 +261,7 @@ int main(void)
        test_traversal1();
        test_shortcut1();
        test_shortcut2();
+       test_negacycle();
        
        return exit_status();
 }

diff --git a/ccan/agar/test/negacycle.c b/ccan/agar/test/negacycle.c
new file mode 100644 (file)
index 0000000..7d3daa9
--- /dev/null
+++ b/ccan/agar/test/negacycle.c
@@ -0,0 +1,42 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#include "simple-graphr.h"
+
+static const void *negacycle_first_edge_r(const struct agar_graph *gr,
+                                         const void *nr)
+{
+       return int2ptr(1);
+}
+
+static const void *negacycle_next_edge_r(const struct agar_graph *gr,
+                                        const void *nr, const void *e)
+{
+       assert(ptr2int(e) == 1);
+       return NULL;
+}
+
+static int negacycle_edge_info_r(const struct agar_graph *gr,
+                                const void *nr, const void *e,
+                                struct agar_edge_info *eir)
+{
+       int ni = ptr2int(nr);
+
+       assert(ptr2int(e) == 1);
+       eir->to = int2ptr((ni % 3) + 1);
+       if (ni == 3)
+               eir->icost = -3;
+       return 0;
+}
+
+struct negacycle_graphr negacycle_graphr = {
+       AGAR_INIT_GRAPH(negacycle_first_edge_r,
+                       negacycle_next_edge_r,
+                       negacycle_edge_info_r),
+};

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index ddb1edbcbd58a5603d9858d36a62671d2f4fcc6a..21cae6a3497c9900ba010dd445f4acdd6203f649 100644 (file)
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -240,4 +240,23 @@ static const struct adjacency_listr shortcut2_adjacencyr[] = {
        {},
 };
 
+/* Negacycle graph
+ *
+ *  A <---- (-3) ----- C
+ *   \                 ^
+ *    (1)->  B -- (1)-/
+ *
+ * Graph with a negative length cycle, and so lacking well-defined shortest paths.
+ */
+struct negacycle_graphr {
+       struct agar_graph gr;
+};
+extern struct negacycle_graphr negacycle_graphr;
+static const struct adjacency_listr negacycle_adjacencyr[] = {
+       {1, {2}},
+       {2, {3}},
+       {3, {1}},
+       {},
+};
+
 #endif /* _SIMPLE_GRAPHR_H */