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

For all the existing test graphs, the shortest path by cost is also the
shortest path by number of edges.  This patch adds a new test graph where
that is not the case, in order to test that the Dijkstra's algorithm
implementation correctly handles that 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 22126003f13cfa62781806a3ef0be71cfee9e54a..8f6c6d55c7f18de9cb25afaa0b6631076814081c 100644 (file)
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -61,8 +61,9 @@ int main(void)
        struct grid_graph gg1, gg2;
        struct error_graph eg;
        struct traversal1_graph t1g;
+       struct shortcut1_graph s1g;
 
-       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30);
+       plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9);
 
        trivial_graph_init(&tg);
        test_adjacency("trivial", &tg.sg, trivial_adjacency);
@@ -91,5 +92,8 @@ int main(void)
        traversal1_graph_init(&t1g);
        test_adjacency("traversal1 graph", &t1g.sg, traversal1_adjacency);
 
+       shortcut1_graph_init(&s1g);
+       test_adjacency("shortcut1 graph", &s1g.sg, shortcut1_adjacency);
+
        return exit_status();
 }

diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 9be747d976e9f671b3fb5865f77c98c3e6884ff4..9b94c988834da5a71a2484d6a9a5c9679dbc4560 100644 (file)
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -214,12 +214,32 @@ 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);
+}
+
 int main(void)
 {
        plan_tests(7 + 20
                   + FULL_LEN * (1 + FULL_LEN*4)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32);
+                  + 12 + 32 + 7);
 
        test_trivial();
        test_parallel();
@@ -227,6 +247,7 @@ int main(void)
        test_chain();
        test_error();
        test_traversal1();
+       test_shortcut1();
        
        return exit_status();
 }

diff --git a/ccan/aga/test/shortcut1.c b/ccan/aga/test/shortcut1.c
new file mode 100644 (file)
index 0000000..bea05a6
--- /dev/null
+++ b/ccan/aga/test/shortcut1.c
@@ -0,0 +1,93 @@
+#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 *shortcut1_first_edge(const struct aga_graph *g,
+                                     const struct aga_node *n)
+{
+       struct shortcut1_graph *s1g = container_of(g, struct shortcut1_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 *shortcut1_next_edge(const struct aga_graph *g,
+                                    const struct aga_node *n,
+                                    ptrint_t *e)
+{
+       struct shortcut1_graph *s1g = container_of(g, struct shortcut1_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 shortcut1_edge_info(const struct aga_graph *g,
+                              const struct aga_node *n,
+                              ptrint_t *e, struct aga_edge_info *ei)
+{
+       struct shortcut1_graph *s1g = container_of(g, struct shortcut1_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];
+                       ei->icost = 3;
+               } else {
+                       assert(index == 2);
+                       ei->to = &s1g->sg.nodes[2];
+               }
+               break;
+
+       case 2:
+               assert(index == 1);
+               ei->to = &s1g->sg.nodes[3];
+               break;
+
+       default:
+               assert(0);
+       }
+       return 0;
+}
+
+void shortcut1_graph_init(struct shortcut1_graph *s1g)
+{
+       simple_graph_init(&s1g->sg, shortcut1_first_edge,
+                         shortcut1_next_edge,
+                         shortcut1_edge_info);
+}

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 57f87a881cc38961b28d2eccfb9787aa76752956..77ba2a64898dd27661cd7694d6e83e027fb4200a 100644 (file)
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -215,4 +215,24 @@ static const struct adjacency_list traversal1_adjacency[] = {
        {},
 };
 
+/* Shortcut-1 graph
+ *
+ *   A ---- (3) -----> C
+ *    \             /
+ *     (1)-> B  --(1)
+ *
+ * This provides an example of a graph where the lowest cost path from
+ * (A) to (C) is not the path with the smallest number od edges.
+ */
+struct shortcut1_graph {
+       struct simple_graph sg;
+};
+void shortcut1_graph_init(struct shortcut1_graph *s1g);
+static const struct adjacency_list shortcut1_adjacency[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+
 #endif /* _TEST_GRAPHS_H */

diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index 469cd83e443e29e0d08f940a64781f8ef95ddfee..9482bbacb424068d3d87d955bbfaf5afd1f95bff 100644 (file)
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -55,8 +55,9 @@ int main(void)
        struct chain_graphr cgr;
        struct grid_graphr ggr1, ggr2;
        struct error_graphr egr;
+       struct shortcut1_graphr s1gr;
 
-       plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6);
+       plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6);
 
        trivial_graphr_init(&tgr);
        test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
@@ -82,5 +83,8 @@ int main(void)
        error_graphr_init(&egr);
        test_adjacency("error graph", &egr.gr, error_adjacencyr);
 
+       shortcut1_graphr_init(&s1gr);
+       test_adjacency("shortcut1 graph", &s1gr.gr, shortcut1_adjacencyr);
+
        return exit_status();
 }

diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 5edccd7032bbcfd23ae3ca5da4d34c5f597b4356..3ade1580d2a11f4bb079fb8421cdf0e33209cb27 100644 (file)
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -219,12 +219,31 @@ static void test_traversal1(void)
        tal_free(sr);
 }
 
+static void test_shortcut1(void)
+{
+       struct shortcut1_graphr s1gr;
+       struct agar_state *sr;
+       aga_icost_t cost;
+       const void *node;
+
+       shortcut1_graphr_init(&s1gr);
+
+       ok1(sr = agar_dijkstra_new(NULL, &s1gr.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);
+}
+
 int main(void)
 {
        plan_tests(6 + 23
                   + FULL_LEN * (FULL_LEN*4 - 1)
                   + CHAIN_LEN * (1 + CHAIN_LEN*2)
-                  + 12 + 32);
+                  + 12 + 32 + 7);
 
        test_trivial();
        test_parallel();
@@ -232,6 +251,7 @@ int main(void)
        test_chain();
        test_error();
        test_traversal1();
+       test_shortcut1();
        
        return exit_status();
 }

diff --git a/ccan/agar/test/shortcut1.c b/ccan/agar/test/shortcut1.c
new file mode 100644 (file)
index 0000000..efae316
--- /dev/null
+++ b/ccan/agar/test/shortcut1.c
@@ -0,0 +1,86 @@
+#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 *shortcut1_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 *shortcut1_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 shortcut1_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);
+                       eir->icost = 3;
+               } else {
+                       assert(index == 2);
+                       eir->to = int2ptr(2);
+               }
+               break;
+
+       case 2:
+               assert(index == 1);
+               eir->to = int2ptr(3);
+               break;
+
+       default:
+               assert(0);
+       }
+       return 0;
+}
+
+void shortcut1_graphr_init(struct shortcut1_graphr *s1gr)
+{
+       agar_init_graph(&s1gr->gr, shortcut1_first_edge_r,
+                       shortcut1_next_edge_r,
+                       shortcut1_edge_info_r);
+}

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index 2abe72dcb6903989fafa71d46b5c5f3715b95ab2..168ee2902a9a3941b94712785b3d8a84869b58ca 100644 (file)
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -199,4 +199,24 @@ static const struct adjacency_listr traversal1_adjacency[] = {
        {},
 };
 
+/* Shortcut-1 graph
+ *
+ *   A ---- (3) -----> C
+ *    \             /
+ *     (1)-> B  --(1)
+ *
+ * This provides an example of a graph where the lowest cost path from
+ * (A) to (C) is not the path with the smallest number od edges.
+ */
+struct shortcut1_graphr {
+       struct agar_graph gr;
+};
+void shortcut1_graphr_init(struct shortcut1_graphr *s1gr);
+static const struct adjacency_listr shortcut1_adjacencyr[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+
 #endif /* _SIMPLE_GRAPHR_H */