From 13430d4e252edbe0c202237e5a956670da1efe0b Mon Sep 17 00:00:00 2001 From: David Gibson Date: Fri, 6 Nov 2015 12:26:03 +1100 Subject: [PATCH] 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 --- 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 22126003..8f6c6d55 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 9be747d9..9b94c988 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 00000000..bea05a64 --- /dev/null +++ b/ccan/aga/test/shortcut1.c @@ -0,0 +1,93 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#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 57f87a88..77ba2a64 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 469cd83e..9482bbac 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 5edccd70..3ade1580 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 00000000..efae3164 --- /dev/null +++ b/ccan/agar/test/shortcut1.c @@ -0,0 +1,86 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#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 2abe72dc..168ee290 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.39.2