From 318edb2466a24a2eadcfd05fa83ae29c0e8aae03 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Thu, 3 Nov 2016 21:49:55 +1100 Subject: [PATCH] aga,agar: Negative weight cycle testcase Adds a new test graph which includes a negative weight cycle. This means that shortest paths are not well defined, and both Dijkstra's algorithm and the Bellman-Ford algorithm (which can handle some negative edge weights) will fail. Signed-off-by: David Gibson --- ccan/aga/test/api-adjacency.c | 6 +++- ccan/aga/test/api-bellman_ford.c | 15 +++++++++- ccan/aga/test/api-bfs.c | 8 +++++- ccan/aga/test/api-dfs.c | 8 +++++- ccan/aga/test/api-dijkstra.c | 15 +++++++++- ccan/aga/test/negacycle.c | 46 +++++++++++++++++++++++++++++++ ccan/aga/test/simple-graph.h | 19 +++++++++++++ ccan/agar/test/api-bellman_ford.c | 13 ++++++++- ccan/agar/test/api-bfs.c | 6 +++- ccan/agar/test/api-dfs.c | 6 +++- ccan/agar/test/api-dijkstra.c | 13 ++++++++- ccan/agar/test/negacycle.c | 42 ++++++++++++++++++++++++++++ ccan/agar/test/simple-graphr.h | 19 +++++++++++++ 13 files changed, 207 insertions(+), 9 deletions(-) create mode 100644 ccan/aga/test/negacycle.c create mode 100644 ccan/agar/test/negacycle.c diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c index 6e504301..31685224 100644 --- a/ccan/aga/test/api-adjacency.c +++ b/ccan/aga/test/api-adjacency.c @@ -63,8 +63,9 @@ int main(void) struct traversal1_graph t1g; struct shortcut1_graph s1g; struct shortcut2_graph s2g; + struct negacycle_graph ng; - plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9); + plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9 + 9); trivial_graph_init(&tg); test_adjacency("trivial", &tg.sg, trivial_adjacency); @@ -99,5 +100,8 @@ int main(void) shortcut2_graph_init(&s2g); test_adjacency("shortcut2 graph", &s2g.sg, shortcut2_adjacency); + negacycle_graph_init(&ng); + test_adjacency("negacycle graph", &ng.sg, negacycle_adjacency); + return exit_status(); } diff --git a/ccan/aga/test/api-bellman_ford.c b/ccan/aga/test/api-bellman_ford.c index e0ce1a06..5dc032a7 100644 --- a/ccan/aga/test/api-bellman_ford.c +++ b/ccan/aga/test/api-bellman_ford.c @@ -246,12 +246,24 @@ static void test_shortcut2(void) aga_finish(&s2g.sg.g); } +static void test_negacycle(void) +{ + struct negacycle_graph ng; + + negacycle_graph_init(&ng); + + ok1(aga_bellman_ford_start(&ng.sg.g, &ng.sg.nodes[1]) == 0); + aga_bellman_ford_complete(&ng.sg.g); + ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST); + aga_finish(&ng.sg.g); +} + int main(void) { plan_tests(5 + 15 + FULL_LEN * (1 + FULL_LEN * 4) + CHAIN_LEN * (1 + CHAIN_LEN * 2) - + 10 + 32 + 7 + 7); + + 10 + 32 + 7 + 7 + 2); test_trivial(); test_parallel(); @@ -261,6 +273,7 @@ int main(void) test_traversal1(); test_shortcut1(); test_shortcut2(); + test_negacycle(); return exit_status(); } diff --git a/ccan/aga/test/api-bfs.c b/ccan/aga/test/api-bfs.c index 90fcc628..1a3e1411 100644 --- a/ccan/aga/test/api-bfs.c +++ b/ccan/aga/test/api-bfs.c @@ -42,9 +42,10 @@ int main(void) struct grid_graph gg1, gg2; struct error_graph eg; struct traversal1_graph t1g; + struct negacycle_graph ng; struct aga_node *node; - plan_tests(2 * 13 + 10 + 10); + plan_tests(2 * 13 + 10 + 10 + 6); trivial_graph_init(&tg); test_bfs(&tg.sg, 1, 1); @@ -100,5 +101,10 @@ int main(void) test_bfs_partial(&t1g.sg, 1, 1, 2, 3); aga_finish(&t1g.sg.g); + negacycle_graph_init(&ng); + test_bfs(&ng.sg, 1, 1, 2, 3); + test_bfs(&ng.sg, 2, 2, 3, 1); + test_bfs(&ng.sg, 3, 3, 1, 2); + return exit_status(); } diff --git a/ccan/aga/test/api-dfs.c b/ccan/aga/test/api-dfs.c index 24d1a4f9..c28097a6 100644 --- a/ccan/aga/test/api-dfs.c +++ b/ccan/aga/test/api-dfs.c @@ -42,9 +42,10 @@ int main(void) struct grid_graph gg1, gg2; struct error_graph eg; struct traversal1_graph t1g; + struct negacycle_graph ng; struct aga_node *node; - plan_tests(2 * 13 + 10 + 10); + plan_tests(2 * 13 + 10 + 10 + 6); trivial_graph_init(&tg); test_dfs(&tg.sg, 1, 1); @@ -100,5 +101,10 @@ int main(void) test_dfs_partial(&t1g.sg, 1, 1, 2, 3); aga_finish(&t1g.sg.g); + negacycle_graph_init(&ng); + test_dfs(&ng.sg, 1, 1, 2, 3); + test_dfs(&ng.sg, 2, 2, 3, 1); + test_dfs(&ng.sg, 3, 3, 1, 2); + return exit_status(); } diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c index 74875fbc..01bb5aa4 100644 --- a/ccan/aga/test/api-dijkstra.c +++ b/ccan/aga/test/api-dijkstra.c @@ -246,12 +246,24 @@ static void test_shortcut2(void) aga_finish(&s2g.sg.g); } +static void test_negacycle(void) +{ + struct negacycle_graph ng; + + negacycle_graph_init(&ng); + + ok1(aga_dijkstra_start(&ng.sg.g, &ng.sg.nodes[1]) == 0); + aga_dijkstra_complete(&ng.sg.g); + ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST); + aga_finish(&ng.sg.g); +} + int main(void) { plan_tests(7 + 20 + FULL_LEN * (1 + FULL_LEN*4) + CHAIN_LEN * (1 + CHAIN_LEN*2) - + 12 + 32 + 7 + 2); + + 12 + 32 + 7 + 2 + 2); test_trivial(); test_parallel(); @@ -261,6 +273,7 @@ int main(void) test_traversal1(); test_shortcut1(); test_shortcut2(); + test_negacycle(); return exit_status(); } diff --git a/ccan/aga/test/negacycle.c b/ccan/aga/test/negacycle.c new file mode 100644 index 00000000..8eae4bf0 --- /dev/null +++ b/ccan/aga/test/negacycle.c @@ -0,0 +1,46 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graph.h" + +static ptrint_t *negacycle_first_edge(const struct aga_graph *g, + const struct aga_node *n) +{ + return int2ptr(1); +} + +static ptrint_t *negacycle_next_edge(const struct aga_graph *g, + const struct aga_node *n, + ptrint_t *e) +{ + assert(ptr2int(e) == 1); + return NULL; +} + +static int negacycle_edge_info(const struct aga_graph *g, + const struct aga_node *n, + ptrint_t *e, struct aga_edge_info *ei) +{ + struct negacycle_graph *ng = container_of(g, struct negacycle_graph, + sg.g); + int ni = n - ng->sg.nodes; + + assert(ptr2int(e) == 1); + ei->to = &ng->sg.nodes[(ni % 3) + 1]; + if (ni == 3) + ei->icost = -3; + return 0; +} + +void negacycle_graph_init(struct negacycle_graph *ng) +{ + simple_graph_init(&ng->sg, negacycle_first_edge, + negacycle_next_edge, + negacycle_edge_info); +} diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h index b8da3ad9..5808993a 100644 --- a/ccan/aga/test/simple-graph.h +++ b/ccan/aga/test/simple-graph.h @@ -256,4 +256,23 @@ static const struct adjacency_list shortcut2_adjacency[] = { {}, }; +/* Negacycle graph + * + * A <---- (-3) ----- C + * \ ^ + * (1)-> B -- (1)-/ + * + * Graph with a negative length cycle, and so lacking well-defined shortest paths. + */ +struct negacycle_graph { + struct simple_graph sg; +}; +void negacycle_graph_init(struct negacycle_graph *ng); +static const struct adjacency_list negacycle_adjacency[] = { + {1, {2}}, + {2, {3}}, + {3, {1}}, + {}, +}; + #endif /* _TEST_GRAPHS_H */ diff --git a/ccan/agar/test/api-bellman_ford.c b/ccan/agar/test/api-bellman_ford.c index 960cf399..a161b0ca 100644 --- a/ccan/agar/test/api-bellman_ford.c +++ b/ccan/agar/test/api-bellman_ford.c @@ -229,12 +229,22 @@ static void test_shortcut2(void) tal_free(sr); } +static void test_negacycle(void) +{ + struct agar_state *sr; + + ok1(sr = agar_bellman_ford_new(NULL, &negacycle_graphr.gr, int2ptr(1))); + agar_bellman_ford_complete(sr); + ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST); + tal_free(sr); +} + int main(void) { plan_tests(3 + 15 + FULL_LEN * (FULL_LEN*4 - 1) + CHAIN_LEN * (1 + CHAIN_LEN*2) - + 10 + 32 + 7 + 7); + + 10 + 32 + 7 + 7 + 2); test_trivial(); test_parallel(); @@ -244,6 +254,7 @@ int main(void) test_traversal1(); test_shortcut1(); test_shortcut2(); + test_negacycle(); return exit_status(); } diff --git a/ccan/agar/test/api-bfs.c b/ccan/agar/test/api-bfs.c index 27369b6e..79ea21ad 100644 --- a/ccan/agar/test/api-bfs.c +++ b/ccan/agar/test/api-bfs.c @@ -45,7 +45,7 @@ int main(void) struct agar_state *sr; const void *nr; - plan_tests(2 * 13 + 12 + 10); + plan_tests(2 * 13 + 12 + 10 + 6); test_bfs(&trivial_graphr.gr, 1, 1); @@ -97,5 +97,9 @@ int main(void) test_bfs_partial(sr, 1, 1, 2, 3); tal_free(sr); + test_bfs(&negacycle_graphr.gr, 1, 1, 2, 3); + test_bfs(&negacycle_graphr.gr, 2, 2, 3, 1); + test_bfs(&negacycle_graphr.gr, 3, 3, 1, 2); + return exit_status(); } diff --git a/ccan/agar/test/api-dfs.c b/ccan/agar/test/api-dfs.c index 625e825c..65be2e18 100644 --- a/ccan/agar/test/api-dfs.c +++ b/ccan/agar/test/api-dfs.c @@ -45,7 +45,7 @@ int main(void) struct agar_state *sr; const void *nr; - plan_tests(2 * 13 + 12 + 10); + plan_tests(2 * 13 + 12 + 10 + 6); test_dfs(&trivial_graphr.gr, 1, 1); @@ -97,5 +97,9 @@ int main(void) test_dfs_partial(sr, 1, 1, 2, 3); tal_free(sr); + test_dfs(&negacycle_graphr.gr, 1, 1, 2, 3); + test_dfs(&negacycle_graphr.gr, 2, 2, 3, 1); + test_dfs(&negacycle_graphr.gr, 3, 3, 1, 2); + return exit_status(); } diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c index a5de2ea6..19980919 100644 --- a/ccan/agar/test/api-dijkstra.c +++ b/ccan/agar/test/api-dijkstra.c @@ -236,12 +236,22 @@ static void test_shortcut2(void) tal_free(sr); } +static void test_negacycle(void) +{ + struct agar_state *sr; + + ok1(sr = agar_dijkstra_new(NULL, &negacycle_graphr.gr, int2ptr(1))); + agar_dijkstra_complete(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 + 2); + + 12 + 32 + 7 + 2 + 2); test_trivial(); test_parallel(); @@ -251,6 +261,7 @@ int main(void) test_traversal1(); test_shortcut1(); test_shortcut2(); + test_negacycle(); return exit_status(); } diff --git a/ccan/agar/test/negacycle.c b/ccan/agar/test/negacycle.c new file mode 100644 index 00000000..7d3daa96 --- /dev/null +++ b/ccan/agar/test/negacycle.c @@ -0,0 +1,42 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static const void *negacycle_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + return int2ptr(1); +} + +static const void *negacycle_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e) +{ + assert(ptr2int(e) == 1); + return NULL; +} + +static int negacycle_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *e, + struct agar_edge_info *eir) +{ + int ni = ptr2int(nr); + + assert(ptr2int(e) == 1); + eir->to = int2ptr((ni % 3) + 1); + if (ni == 3) + eir->icost = -3; + return 0; +} + +struct negacycle_graphr negacycle_graphr = { + AGAR_INIT_GRAPH(negacycle_first_edge_r, + negacycle_next_edge_r, + negacycle_edge_info_r), +}; diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h index ddb1edbc..21cae6a3 100644 --- a/ccan/agar/test/simple-graphr.h +++ b/ccan/agar/test/simple-graphr.h @@ -240,4 +240,23 @@ static const struct adjacency_listr shortcut2_adjacencyr[] = { {}, }; +/* Negacycle graph + * + * A <---- (-3) ----- C + * \ ^ + * (1)-> B -- (1)-/ + * + * Graph with a negative length cycle, and so lacking well-defined shortest paths. + */ +struct negacycle_graphr { + struct agar_graph gr; +}; +extern struct negacycle_graphr negacycle_graphr; +static const struct adjacency_listr negacycle_adjacencyr[] = { + {1, {2}}, + {2, {3}}, + {3, {1}}, + {}, +}; + #endif /* _SIMPLE_GRAPHR_H */ -- 2.39.2