aga,agar: New shortcut2 sample graph and testcases based on it

This patch adds a new test graph "shortcut2" which includes a negative cost
edge.  Along with that we add a testcase for Dijkstra's algorithm checking
that it gracefully fails in this case.

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 8f6c6d55c7f18de9cb25afaa0b6631076814081c..6e5043017788272e6aa8f2b07163e49277d71c34 100644 (file)
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -62,8 +62,9 @@ int main(void)
        struct error_graph eg;
        struct traversal1_graph t1g;
        struct shortcut1_graph s1g;
        struct error_graph eg;
        struct traversal1_graph t1g;
        struct shortcut1_graph s1g;

+       struct shortcut2_graph s2g;

 
 

-       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9);
+       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9);

 
        trivial_graph_init(&tg);
        test_adjacency("trivial", &tg.sg, trivial_adjacency);
 
        trivial_graph_init(&tg);
        test_adjacency("trivial", &tg.sg, trivial_adjacency);


@@ -95,5 +96,8 @@ int main(void)
        shortcut1_graph_init(&s1g);
        test_adjacency("shortcut1 graph", &s1g.sg, shortcut1_adjacency);
 
        shortcut1_graph_init(&s1g);
        test_adjacency("shortcut1 graph", &s1g.sg, shortcut1_adjacency);
 

+       shortcut2_graph_init(&s2g);
+       test_adjacency("shortcut2 graph", &s2g.sg, shortcut2_adjacency);
+

        return exit_status();
 }
        return exit_status();
 }

diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 9b94c988834da5a71a2484d6a9a5c9679dbc4560..f9b8d764a7d6e198d23797afa404882b0009e8d6 100644 (file)
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -234,12 +234,24 @@ static void test_shortcut1(void)
        aga_finish(&s1g.sg.g);
 }
 
        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_all_paths(&s2g.sg.g);
+       ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
+       aga_finish(&s2g.sg.g);
+}
+

 int main(void)
 {
        plan_tests(7 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
 int main(void)
 {
        plan_tests(7 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)

-                  + 12 + 32 + 7);
+                  + 12 + 32 + 7 + 2);

 
        test_trivial();
        test_parallel();
 
        test_trivial();
        test_parallel();


@@ -248,6 +260,7 @@ int main(void)
        test_error();
        test_traversal1();
        test_shortcut1();
        test_error();
        test_traversal1();
        test_shortcut1();

+       test_shortcut2();

        
        return exit_status();
 }
        
        return exit_status();
 }

diff --git a/ccan/aga/test/shortcut2.c b/ccan/aga/test/shortcut2.c
new file mode 100644 (file)
index 0000000..33eee0a
--- /dev/null
+++ b/ccan/aga/test/shortcut2.c
@@ -0,0 +1,94 @@
+#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 *shortcut2_first_edge(const struct aga_graph *g,
+                                     const struct aga_node *n)
+{
+       struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+                                                  sg.g);
+       int ni = n - s1g->sg.nodes;
+
+       switch (ni) {
+       case 1:
+       case 2:
+               return int2ptr(1);
+
+       case 3:
+               return NULL;
+
+       default:
+               assert(0);
+       }
+}
+
+static ptrint_t *shortcut2_next_edge(const struct aga_graph *g,
+                                    const struct aga_node *n,
+                                    ptrint_t *e)
+{
+       struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+                                                  sg.g);
+       int ni = n - s1g->sg.nodes;
+       int index = ptr2int(e);
+
+       switch (ni) {
+       case 1:
+               if (index == 1)
+                       return int2ptr(2);
+               assert(index == 2);
+               return NULL;
+
+       case 2:
+               assert(index == 1);
+               return NULL;
+
+       default:
+               assert(0);
+       }
+}
+
+static int shortcut2_edge_info(const struct aga_graph *g,
+                              const struct aga_node *n,
+                              ptrint_t *e, struct aga_edge_info *ei)
+{
+       struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+                                                  sg.g);
+       int ni = n - s1g->sg.nodes;
+       int index = ptr2int(e);
+
+       switch (ni) {
+       case 1:
+               if (index == 1) {
+                       ei->to = &s1g->sg.nodes[3];
+               } else {
+                       assert(index == 2);
+                       ei->to = &s1g->sg.nodes[2];
+               }
+               ei->icost = 2;
+               break;
+
+       case 2:
+               assert(index == 1);
+               ei->to = &s1g->sg.nodes[3];
+               ei->icost = -1;
+               break;
+
+       default:
+               assert(0);
+       }
+       return 0;
+}
+
+void shortcut2_graph_init(struct shortcut2_graph *s1g)
+{
+       simple_graph_init(&s1g->sg, shortcut2_first_edge,
+                         shortcut2_next_edge,
+                         shortcut2_edge_info);
+}

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 77ba2a64898dd27661cd7694d6e83e027fb4200a..b8da3ad999045bc9207b59871a56fae691a13120 100644 (file)
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -235,4 +235,25 @@ static const struct adjacency_list shortcut1_adjacency[] = {
        {},
 };
 
        {},
 };
 

+/* Shortcut-2 graph
+ *
+ *   A ---- (2) -----> C
+ *    \             /
+ *     (2)-> B  --(-1)
+ *
+ * This provides an example of a graph with a negative edge cost, but
+ * no negative cost cycles (and so still with well defined shortest
+ * paths).
+ */
+struct shortcut2_graph {
+       struct simple_graph sg;
+};
+void shortcut2_graph_init(struct shortcut2_graph *s2g);
+static const struct adjacency_list shortcut2_adjacency[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+

 #endif /* _TEST_GRAPHS_H */
 #endif /* _TEST_GRAPHS_H */

diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index 9482bbacb424068d3d87d955bbfaf5afd1f95bff..2b2637d277f2fc41dd8ca298a098234059bd3b87 100644 (file)
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -56,8 +56,9 @@ int main(void)
        struct grid_graphr ggr1, ggr2;
        struct error_graphr egr;
        struct shortcut1_graphr s1gr;
        struct grid_graphr ggr1, ggr2;
        struct error_graphr egr;
        struct shortcut1_graphr s1gr;

+       struct shortcut2_graphr s2gr;

 
 

-       plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6);
+       plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6 + 6);

 
        trivial_graphr_init(&tgr);
        test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
 
        trivial_graphr_init(&tgr);
        test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);


@@ -86,5 +87,8 @@ int main(void)
        shortcut1_graphr_init(&s1gr);
        test_adjacency("shortcut1 graph", &s1gr.gr, shortcut1_adjacencyr);
 
        shortcut1_graphr_init(&s1gr);
        test_adjacency("shortcut1 graph", &s1gr.gr, shortcut1_adjacencyr);
 

+       shortcut2_graphr_init(&s2gr);
+       test_adjacency("shortcut2 graph", &s2gr.gr, shortcut2_adjacencyr);
+       

        return exit_status();
 }
        return exit_status();
 }

diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 3ade1580d2a11f4bb079fb8421cdf0e33209cb27..1321e26f75404927ec4f7bd483d5be4bce228b36 100644 (file)
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -238,12 +238,25 @@ static void test_shortcut1(void)
        tal_free(sr);
 }
 
        tal_free(sr);
 }
 

+static void test_shortcut2(void)
+{
+       struct shortcut2_graphr s2gr;
+       struct agar_state *sr;
+
+       shortcut2_graphr_init(&s2gr);
+
+       ok1(sr = agar_dijkstra_new(NULL, &s2gr.gr, int2ptr(1)));
+       agar_dijkstra_all_paths(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)
 int main(void)
 {
        plan_tests(6 + 23
                   + FULL_LEN * (FULL_LEN*4 - 1)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)

-                  + 12 + 32 + 7);
+                  + 12 + 32 + 7 + 2);

 
        test_trivial();
        test_parallel();
 
        test_trivial();
        test_parallel();


@@ -252,6 +265,7 @@ int main(void)
        test_error();
        test_traversal1();
        test_shortcut1();
        test_error();
        test_traversal1();
        test_shortcut1();

+       test_shortcut2();

        
        return exit_status();
 }
        
        return exit_status();
 }

diff --git a/ccan/agar/test/shortcut2.c b/ccan/agar/test/shortcut2.c
new file mode 100644 (file)
index 0000000..aff89a6
--- /dev/null
+++ b/ccan/agar/test/shortcut2.c
@@ -0,0 +1,87 @@
+#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 *shortcut2_first_edge_r(const struct agar_graph *gr,
+                                         const void *nr)
+{
+       int ni = ptr2int(nr);
+
+       switch (ni) {
+       case 1:
+       case 2:
+               return int2ptr(1);
+
+       case 3:
+               return NULL;
+
+       default:
+               assert(0);
+       }
+}
+
+static const void *shortcut2_next_edge_r(const struct agar_graph *gr,
+                                        const void *nr, const void *e)
+{
+       int ni = ptr2int(nr);
+       int index = ptr2int(e);
+
+       switch (ni) {
+       case 1:
+               if (index == 1)
+                       return int2ptr(2);
+               assert(index == 2);
+               return NULL;
+
+       case 2:
+               assert(index == 1);
+               return NULL;
+
+       default:
+               assert(0);
+       }
+}
+
+static int shortcut2_edge_info_r(const struct agar_graph *gr,
+                                const void *nr, const void *e,
+                                struct agar_edge_info *eir)
+{
+       int ni = ptr2int(nr);
+       int index = ptr2int(e);
+
+       switch (ni) {
+       case 1:
+               if (index == 1) {
+                       eir->to = int2ptr(3);
+               } else {
+                       assert(index == 2);
+                       eir->to = int2ptr(2);
+               }
+               eir->icost = 2;
+               break;
+
+       case 2:
+               assert(index == 1);
+               eir->to = int2ptr(3);
+               eir->icost = -1;
+               break;
+
+       default:
+               assert(0);
+       }
+       return 0;
+}
+
+void shortcut2_graphr_init(struct shortcut2_graphr *s1gr)
+{
+       agar_init_graph(&s1gr->gr, shortcut2_first_edge_r,
+                       shortcut2_next_edge_r,
+                       shortcut2_edge_info_r);
+}

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index 168ee2902a9a3941b94712785b3d8a84869b58ca..2fe98a48776c9c2ddbc8bdd9a85100ad0a9b0685 100644 (file)
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -219,4 +219,25 @@ static const struct adjacency_listr shortcut1_adjacencyr[] = {
        {},
 };
 
        {},
 };
 

+/* Shortcut-2 graph
+ *
+ *   A ---- (2) -----> C
+ *    \             /
+ *     (2)-> B  --(-1)
+ *
+ * This provides an example of a graph with a negative edge cost, but
+ * no negative cost cycles (and so still with well defined shortest
+ * paths).
+ */
+struct shortcut2_graphr {
+       struct agar_graph gr;
+};
+void shortcut2_graphr_init(struct shortcut2_graphr *s2gr);
+static const struct adjacency_listr shortcut2_adjacencyr[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+

 #endif /* _SIMPLE_GRAPHR_H */
 #endif /* _SIMPLE_GRAPHR_H */