[ccan] [PATCH 4/5] aga, agar: New shortcut1 sample graph and testcases based on it
David Gibson
david at gibson.dropbear.id.au
Thu Nov 12 22:42:47 AEDT 2015
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 at gibson.dropbear.id.au>
---
ccan/aga/test/api-adjacency.c | 6 ++-
ccan/aga/test/api-dijkstra.c | 23 ++++++++++-
ccan/aga/test/shortcut1.c | 93 ++++++++++++++++++++++++++++++++++++++++++
ccan/aga/test/simple-graph.h | 20 +++++++++
ccan/agar/test/api-adjacency.c | 6 ++-
ccan/agar/test/api-dijkstra.c | 22 +++++++++-
ccan/agar/test/shortcut1.c | 86 ++++++++++++++++++++++++++++++++++++++
ccan/agar/test/simple-graphr.h | 20 +++++++++
8 files changed, 272 insertions(+), 4 deletions(-)
create mode 100644 ccan/aga/test/shortcut1.c
create mode 100644 ccan/agar/test/shortcut1.c
diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 2212600..8f6c6d5 100644
--- 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 9be747d..9b94c98 100644
--- 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
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 57f87a8..77ba2a6 100644
--- 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 469cd83..9482bba 100644
--- 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 5edccd7..3ade158 100644
--- 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
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 2abe72d..168ee29 100644
--- 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 */
--
2.5.0
More information about the ccan
mailing list