From: David Gibson Date: Sat, 11 Jun 2016 08:30:08 +0000 (+1000) Subject: aga,agar: The Bellman-Ford algorithm X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=eedf1079f38efb2b8dc4fd3f516cce8ac1272c06 aga,agar: The Bellman-Ford algorithm This adds the Bellman-Ford single-source shortest path algorithm to the aga and agar modules. The Bellman-Ford algorithm is (usually) slower than Dijkstra's algorithm, but unlike Dijkstra's is able to cope with negative edge costs, unless they form a negative cost cycle. Signed-off-by: David Gibson --- diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h index aa60bcc9..239d36c3 100644 --- a/ccan/aga/aga.h +++ b/ccan/aga/aga.h @@ -165,6 +165,12 @@ struct aga_node { bool complete; struct lpq_link pqlink; } dijkstra; + struct { + aga_icost_t distance; + struct aga_node *prev; + const void *prevedge; + struct aga_node *list; + } bellman_ford; } u; }; @@ -177,6 +183,11 @@ struct aga_graph { aga_edge_info_fn edge_info; union { LPQ(struct aga_node, u.dijkstra.pqlink) dijkstra; + struct { + struct aga_node *nodelist; + int nnodes; + int npasses; + } bellman_ford; } state; }; @@ -427,4 +438,63 @@ bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest, */ void aga_dijkstra_complete(struct aga_graph *g); +/* + * Bellman-Ford algorithm + */ + +/** + * aga_bellman_ford_start - Start Bellman-Ford algorithm + * @g: graph + * @source: source node + * + * Start's the Bellman-Ford algorithm on @g to find shortest paths + * from node @source, to other nodes in @g. + */ +int aga_bellman_ford_start(struct aga_graph *g, struct aga_node *source); + +/** + * aga_bellman_ford_path - Find the shortest path to a node + * @g: graph + * @dest: destination node + * @prev: Second last node in the path *output) + * @prevedge: Last edge in the path + * + * Finds the shortest path from the source node (specified in + * aga_bellman_ford_start() to @dest using Bellman_Ford's algorithm. + * + * If no path exists, return false. + * + * If a path does exist, returns true. Additionally if @total_cost is + * non-NULL, store the total cost of the path in *@total_cost, if + * @prev is non-NULL, store the node in the path immediately before + * @dest in *@prev and if @prevedge is non-NULL stores the edge which + * leads from *@prev to @dest in *@prevedge. + * + * If @dest is the same as source, 0 will be stored in @cost, and NULL + * will be stored in *@prev and *@prevedge. + * + * The full path from source to @dest can be determined by repeatedly + * calling aga_bellman_ford_path() on *@prev. + * + * NOTE: Bellman_Ford's algorithm will not work correctly on a graph + * which contains a cycle with (total) negative cost. If aga detects + * this case, it will set aga_error() to AGA_ERR_NEGATIVE_COST. + */ +bool aga_bellman_ford_path(struct aga_graph *g, struct aga_node *dest, + aga_icost_t *total_cost, + struct aga_node **prev, const void **prevedge); + +/** + * aga_bellman_ford_complete - Run Bellman-Ford algorithm to completion + * @g: graph + * + * Finds shortest paths from the source node (specified in + * aga_bellman_ford_start()) to all other reachable nodes in @g. No + * results are returned directly, but between calling + * aga_bellman_ford_complete() and aga_finish(), + * aga_bellman_ford_path() is guaranteed to complete in O(1) time for + * all destinations. + */ +void aga_bellman_ford_complete(struct aga_graph *g); + #endif /* CCAN_AGA_H */ diff --git a/ccan/aga/bellman_ford.c b/ccan/aga/bellman_ford.c new file mode 100644 index 00000000..18204831 --- /dev/null +++ b/ccan/aga/bellman_ford.c @@ -0,0 +1,141 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include "config.h" + +#include +#include +#include + +#include +#include +#include + +#include +#include "private.h" + +/* + * The Bellman-Ford algorithm + */ + +static bool candidate_path(struct aga_graph *g, struct aga_node *node, + aga_icost_t distance, + struct aga_node *prev, const void *prevedge) +{ + if (aga_update_node(g, node)) { + /* New node, treat as having infinite distance */ + node->u.bellman_ford.distance = distance; + node->u.bellman_ford.prev = prev; + node->u.bellman_ford.prevedge = prevedge; + + node->u.bellman_ford.list = g->state.bellman_ford.nodelist; + g->state.bellman_ford.nodelist = node; + g->state.bellman_ford.nnodes++; + + return true; + } else if (distance < node->u.bellman_ford.distance) { + node->u.bellman_ford.distance = distance; + node->u.bellman_ford.prev = prev; + node->u.bellman_ford.prevedge = prevedge; + } + return false; +} + +int aga_bellman_ford_start(struct aga_graph *g, struct aga_node *source) +{ + int rc; + + /* Make sure we're actually using the right ordering for + * aga_icost_t */ + BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0); + + rc = aga_start(g); + if (rc < 0) + return rc; + + g->state.bellman_ford.nodelist = NULL; + g->state.bellman_ford.nnodes = 0; + g->state.bellman_ford.npasses = 0; + + candidate_path(g, source, 0, NULL, NULL); + + return 0; +} + +static bool aga_bellman_ford_step(struct aga_graph *g) +{ + struct aga_node *n; + const void *e; + struct aga_edge_info ei; + int err; + bool newnode = false; + + if (!aga_check_state(g)) + return false; + + for (n = g->state.bellman_ford.nodelist; + n; n = n->u.bellman_ford.list) { + aga_for_each_edge_info(e, ei, err, g, n) { + aga_icost_t dist = n->u.bellman_ford.distance + + ei.icost; + newnode = newnode || candidate_path(g, ei.to, dist, n, e); + } + if (err) { + aga_fail(g, err); + return false; + } + } + g->state.bellman_ford.npasses++; + return newnode || (g->state.bellman_ford.npasses + < g->state.bellman_ford.nnodes); +} + +void aga_bellman_ford_complete(struct aga_graph *g) +{ + struct aga_node *n; + const void *e; + struct aga_edge_info ei; + int err; + + if (!aga_check_state(g)) + return; + + while (aga_bellman_ford_step(g)) + ; + + /* Check for negative cycles */ + for (n = g->state.bellman_ford.nodelist; + n; n = n->u.bellman_ford.list) { + aga_for_each_edge_info(e, ei, err, g, n) { + if ((n->u.bellman_ford.distance + ei.icost) + < ei.to->u.bellman_ford.distance) { + aga_fail(g, AGA_ERR_NEGATIVE_COST); + return; + } + } + if (err) { + aga_fail(g, err); + return; + } + } +} + +bool aga_bellman_ford_path(struct aga_graph *g, struct aga_node *node, + aga_icost_t *total_cost, + struct aga_node **prev, const void **prevedge) +{ + aga_bellman_ford_complete(g); + + if (!aga_check_state(g)) + return false; + + if (aga_node_needs_update(g, node)) + return false; + + if (total_cost) + *total_cost = node->u.bellman_ford.distance; + if (prev) + *prev = node->u.bellman_ford.prev; + if (prevedge) + *prevedge = node->u.bellman_ford.prevedge; + + return true; +} diff --git a/ccan/aga/test/api-bellman_ford.c b/ccan/aga/test/api-bellman_ford.c new file mode 100644 index 00000000..e0ce1a06 --- /dev/null +++ b/ccan/aga/test/api-bellman_ford.c @@ -0,0 +1,266 @@ +#include "config.h" + +#include +#include +#include + +#include +#include + +#include + +#include "simple-graph.h" + +static void test_trivial(void) +{ + struct trivial_graph tg; + aga_icost_t cost; + struct aga_node *node; + const void *edge; + + trivial_graph_init(&tg); + + ok1(aga_bellman_ford_start(&tg.sg.g, &tg.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge)); + ok1(cost == 0); + ok1(node == NULL); + ok1(edge == NULL); + aga_finish(&tg.sg.g); +} + +static void test_parallel(void) +{ + struct parallel_graph pg; + aga_icost_t cost; + struct aga_node *node; + const void *edge; + + parallel_graph_init(&pg, 3, 0); + + ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == &pg.sg.nodes[1]); + aga_finish(&pg.sg.g); + + ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[2]) == 0); + ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(!aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL)); + aga_finish(&pg.sg.g); + + + parallel_graph_init(&pg, 3, 2); + ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge)); + ok1(cost == 1); + ok1(node == &pg.sg.nodes[1]); + ok1(ptr2int(edge) == 2); + aga_finish(&pg.sg.g); +} + +#define FULL_LEN 4 + +static void test_full(void) +{ + struct full_graph fg; + int i, j; + + full_graph_init(&fg, FULL_LEN); + + for (i = 1; i <= FULL_LEN; i++) { + ok1(aga_bellman_ford_start(&fg.sg.g, &fg.sg.nodes[i]) == 0); + + for (j = 1; j <= FULL_LEN; j++) { + aga_icost_t cost; + struct aga_node *node; + const void *edge; + + ok1(aga_bellman_ford_path(&fg.sg.g, &fg.sg.nodes[j], + &cost, &node, &edge)); + if (i == j) { + ok1(cost == 0); + ok1(node == NULL); + ok1(edge == NULL); + } else { + ok1(cost == 1); + ok1(node == &fg.sg.nodes[i]); + ok1(edge == &fg.sg.nodes[j]); + } + } + + aga_finish(&fg.sg.g); + } +} + +#define CHAIN_LEN 8 + +static void test_chain(void) +{ + struct chain_graph cg; + int i, j; + + chain_graph_init(&cg, CHAIN_LEN); + + for (i = 1; i <= CHAIN_LEN; i++) { + ok1(aga_bellman_ford_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0); + + for (j = 1; j <= CHAIN_LEN; j++) { + aga_icost_t cost; + + ok1(aga_bellman_ford_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j], + &cost, NULL, NULL)); + ok1(cost == labs(i - j)); + } + + aga_finish(&cg.fg.sg.g); + } +} + +static void test_error(void) +{ + struct error_graph eg; + aga_icost_t cost; + + error_graph_init(&eg); + + ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL)); + ok1(cost == 1); + ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL)); + ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL)); + aga_finish(&eg.sg.g); + + ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[3]) == 0); + aga_bellman_ford_complete(&eg.sg.g); + ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL)); + ok1(aga_error(&eg.sg.g) == -1); + aga_finish(&eg.sg.g); +} + +static void test_traversal1(void) +{ + struct traversal1_graph t1g; + aga_icost_t cost; + + /* This is mostly about testing we correctly handle + * non-reachable nodes */ + traversal1_graph_init(&t1g); + + ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1], + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7], + NULL, NULL, NULL)); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8], + NULL, NULL, NULL)); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9], + NULL, NULL, NULL)); + aga_finish(&t1g.sg.g); + + ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9], + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7], + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4], + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3], + NULL, NULL, NULL)); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2], + NULL, NULL, NULL)); + ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1], + NULL, NULL, NULL)); + 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_bellman_ford_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[3], + &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == &s1g.sg.nodes[2]); + ok1(aga_bellman_ford_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); +} + +static void test_shortcut2(void) +{ + struct shortcut2_graph s2g; + aga_icost_t cost; + struct aga_node *node; + + shortcut2_graph_init(&s2g); + + ok1(aga_bellman_ford_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0); + ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[3], + &cost, &node, NULL)); + ok1(cost == 1); + ok1(node == &s2g.sg.nodes[2]); + ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[2], + &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == &s2g.sg.nodes[1]); + aga_finish(&s2g.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); + + test_trivial(); + test_parallel(); + test_full(); + test_chain(); + test_error(); + test_traversal1(); + test_shortcut1(); + test_shortcut2(); + + return exit_status(); +} diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c index 0ee34e9a..aa462840 100644 --- a/ccan/agar/agar.c +++ b/ccan/agar/agar.c @@ -291,3 +291,48 @@ void agar_dijkstra_complete(struct agar_state *sr) aga_dijkstra_complete(&sr->g); } + +/* + * Bellman-Ford algorithm + */ + +struct agar_state *agar_bellman_ford_new(void *ctx, struct agar_graph *gr, + const void *nr) +{ + struct agar_state *sr = agar_new(ctx, gr); + + if (aga_bellman_ford_start(&sr->g, nr_to_n(sr, nr)) < 0) { + tal_free(sr); + return NULL; + } + + return sr; +} + +bool agar_bellman_ford_path(struct agar_state *sr, const void *destr, + aga_icost_t *total_cost, + const void **prevr, const void **prevedge) +{ + struct aga_node *dest = nr_to_n(sr, destr); + struct aga_node *prev; + + if (!aga_bellman_ford_path(&sr->g, dest, total_cost, &prev, prevedge)) + return false; + + /* + * When destr is the same as the source node, there obviously + * isn't a previous node or edge. In that case aga sets them + * to NULL. But for agar, NULL could be a valid node + * references (particularly if using ptrint). So we don't + * have much choice here but to leave *prevr as undefined when + * destr is the source node. */ + if (prevr && prev) + *prevr = n_to_nr(sr, prev); + + return true; +} + +void agar_bellman_ford_complete(struct agar_state *sr) +{ + aga_bellman_ford_complete(&sr->g); +} diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h index 274c9cc1..f65b4e37 100644 --- a/ccan/agar/agar.h +++ b/ccan/agar/agar.h @@ -86,4 +86,16 @@ bool agar_dijkstra_path(struct agar_state *sr, const void *destr, const void **prevr, const void **prevedge); void agar_dijkstra_complete(struct agar_state *sr); +/* + * Bellman-Ford algorithm + */ + +struct agar_state *agar_bellman_ford_new(void *ctx, struct agar_graph *gr, + const void *nr); + +bool agar_bellman_ford_path(struct agar_state *sr, const void *destr, + aga_icost_t *total_cost, + const void **prevr, const void **prevedge); +void agar_bellman_ford_complete(struct agar_state *sr); + #endif /* CCAN_AGAR_H */ diff --git a/ccan/agar/test/api-bellman_ford.c b/ccan/agar/test/api-bellman_ford.c new file mode 100644 index 00000000..960cf399 --- /dev/null +++ b/ccan/agar/test/api-bellman_ford.c @@ -0,0 +1,249 @@ +#include "config.h" + +#include +#include +#include + +#include +#include +#include + +#include + +#include "simple-graphr.h" + +static void test_trivial(void) +{ + struct agar_state *sr; + aga_icost_t cost; + + ok1(sr = agar_bellman_ford_new(NULL, &trivial_graphr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL)); + ok1(cost == 0); + tal_free(sr); +} + +static void test_parallel(void) +{ + struct parallel_graphr pgr; + struct agar_state *sr; + aga_icost_t cost; + const void *node, *edge; + + parallel_graphr_init(&pgr, 3, 0); + + ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL)); + ok1(cost == 0); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == int2ptr(1)); + tal_free(sr); + + ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(2))); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL)); + ok1(cost == 0); + ok1(!agar_bellman_ford_path(sr, int2ptr(1), NULL, NULL, NULL)); + tal_free(sr); + + parallel_graphr_init(&pgr, 3, 2); + ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, &edge)); + ok1(cost == 1); + ok1(ptr2int(node) == 1); + ok1(ptr2int(edge) == 2); + tal_free(sr); +} + +#define FULL_LEN 4 + +static void test_full(void) +{ + struct full_graphr fgr; + int i, j; + + full_graphr_init(&fgr, FULL_LEN); + + for (i = 1; i <= FULL_LEN; i++) { + struct agar_state *sr; + + ok1(sr = agar_bellman_ford_new(NULL, &fgr.gr, int2ptr(i))); + + for (j = 1; j <= FULL_LEN; j++) { + aga_icost_t cost; + const void *node, *edge; + + ok1(agar_bellman_ford_path(sr, int2ptr(j), + &cost, &node, &edge)); + if (i == j) { + ok1(cost == 0); + } else { + ok1(cost == 1); + ok1(node == int2ptr(i)); + ok1(edge == int2ptr(j)); + } + } + + tal_free(sr); + } +} + +#define CHAIN_LEN 8 + +static void test_chain(void) +{ + struct chain_graphr cgr; + int i, j; + + chain_graphr_init(&cgr, CHAIN_LEN); + + for (i = 1; i <= CHAIN_LEN; i++) { + struct agar_state *sr; + + ok1(sr = agar_bellman_ford_new(NULL, &cgr.fgr.gr, int2ptr(i))); + + for (j = 1; j <= CHAIN_LEN; j++) { + aga_icost_t cost; + + ok1(agar_bellman_ford_path(sr, int2ptr(j), + &cost, NULL, NULL)); + ok1(cost == labs(i - j)); + } + + tal_free(sr); + } +} + +static void test_error(void) +{ + struct agar_state *sr; + aga_icost_t cost; + + ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL)); + ok1(cost == 0); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL)); + ok1(cost == 1); + ok1(!agar_bellman_ford_path(sr, int2ptr(3), &cost, NULL, NULL)); + ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL)); + tal_free(sr); + + ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(3))); + agar_bellman_ford_complete(sr); + ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL)); + ok1(agar_error(sr) == -1); + tal_free(sr); +} + +static void test_traversal1(void) +{ + struct agar_state *sr; + aga_icost_t cost; + + /* This is mostly about testing we correctly handle + * non-reachable nodes */ + ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(1), + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(agar_bellman_ford_path(sr, int2ptr(2), + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(agar_bellman_ford_path(sr, int2ptr(3), + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(agar_bellman_ford_path(sr, int2ptr(4), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(agar_bellman_ford_path(sr, int2ptr(5), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(agar_bellman_ford_path(sr, int2ptr(6), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!agar_bellman_ford_path(sr, int2ptr(7), + NULL, NULL, NULL)); + ok1(!agar_bellman_ford_path(sr, int2ptr(8), + NULL, NULL, NULL)); + ok1(!agar_bellman_ford_path(sr, int2ptr(9), + NULL, NULL, NULL)); + tal_free(sr); + + ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(9))); + ok1(agar_bellman_ford_path(sr, int2ptr(9), + &cost, NULL, NULL)); + ok1(cost == 0); + ok1(agar_bellman_ford_path(sr, int2ptr(8), + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(agar_bellman_ford_path(sr, int2ptr(7), + &cost, NULL, NULL)); + ok1(cost == 1); + ok1(agar_bellman_ford_path(sr, int2ptr(6), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(agar_bellman_ford_path(sr, int2ptr(5), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(agar_bellman_ford_path(sr, int2ptr(4), + &cost, NULL, NULL)); + ok1(cost == 2); + ok1(!agar_bellman_ford_path(sr, int2ptr(3), + NULL, NULL, NULL)); + ok1(!agar_bellman_ford_path(sr, int2ptr(2), + NULL, NULL, NULL)); + ok1(!agar_bellman_ford_path(sr, int2ptr(1), + NULL, NULL, NULL)); + tal_free(sr); +} + +static void test_shortcut1(void) +{ + struct agar_state *sr; + aga_icost_t cost; + const void *node; + + ok1(sr = agar_bellman_ford_new(NULL, &shortcut1_graphr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == int2ptr(2)); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL)); + ok1(cost == 1); + ok1(node == int2ptr(1)); + tal_free(sr); +} + +static void test_shortcut2(void) +{ + struct agar_state *sr; + aga_icost_t cost; + const void *node; + + ok1(sr = agar_bellman_ford_new(NULL, &shortcut2_graphr.gr, int2ptr(1))); + ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL)); + ok1(cost == 1); + ok1(node == int2ptr(2)); + ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL)); + ok1(cost == 2); + ok1(node == int2ptr(1)); + 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); + + test_trivial(); + test_parallel(); + test_full(); + test_chain(); + test_error(); + test_traversal1(); + test_shortcut1(); + test_shortcut2(); + + return exit_status(); +}