From: David Gibson Date: Fri, 6 Nov 2015 01:26:17 +0000 (+1100) Subject: aga,agar: New shortcut2 sample graph and testcases based on it X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=09378088f7f49f30cb61435712a8dc2e52a32f69;hp=13430d4e252edbe0c202237e5a956670da1efe0b 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 --- diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c index 8f6c6d55..6e504301 100644 --- 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 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); @@ -95,5 +96,8 @@ int main(void) 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(); } diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c index 9b94c988..f9b8d764 100644 --- 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); } +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) - + 12 + 32 + 7); + + 12 + 32 + 7 + 2); test_trivial(); test_parallel(); @@ -248,6 +260,7 @@ int main(void) test_error(); test_traversal1(); test_shortcut1(); + test_shortcut2(); return exit_status(); } diff --git a/ccan/aga/test/shortcut2.c b/ccan/aga/test/shortcut2.c new file mode 100644 index 00000000..33eee0a9 --- /dev/null +++ b/ccan/aga/test/shortcut2.c @@ -0,0 +1,94 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#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 77ba2a64..b8da3ad9 100644 --- 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 */ diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c index 9482bbac..2b2637d2 100644 --- 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 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); @@ -86,5 +87,8 @@ int main(void) 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(); } diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c index 3ade1580..1321e26f 100644 --- 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); } +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) - + 12 + 32 + 7); + + 12 + 32 + 7 + 2); test_trivial(); test_parallel(); @@ -252,6 +265,7 @@ int main(void) test_error(); test_traversal1(); test_shortcut1(); + test_shortcut2(); return exit_status(); } diff --git a/ccan/agar/test/shortcut2.c b/ccan/agar/test/shortcut2.c new file mode 100644 index 00000000..aff89a61 --- /dev/null +++ b/ccan/agar/test/shortcut2.c @@ -0,0 +1,87 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#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 168ee290..2fe98a48 100644 --- 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 */