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 <[email protected]> --- 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 _______________________________________________ ccan mailing list [email protected] https://lists.ozlabs.org/listinfo/ccan
