[ccan] [PATCH 2/2] aga,agar: The Bellman-Ford algorithm
David Gibson
david at gibson.dropbear.id.au
Sun Jun 12 23:17:00 AEST 2016
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 <david at gibson.dropbear.id.au>
---
ccan/aga/aga.h | 70 ++++++++++
ccan/aga/bellman_ford.c | 121 +++++++++++++++++
ccan/aga/test/api-bellman_ford.c | 266 ++++++++++++++++++++++++++++++++++++++
ccan/agar/agar.c | 45 +++++++
ccan/agar/agar.h | 12 ++
ccan/agar/test/api-bellman_ford.c | 249 +++++++++++++++++++++++++++++++++++
6 files changed, 763 insertions(+)
create mode 100644 ccan/aga/bellman_ford.c
create mode 100644 ccan/aga/test/api-bellman_ford.c
create mode 100644 ccan/agar/test/api-bellman_ford.c
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index 62e03e7..53829e3 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 0000000..c3ba270
--- /dev/null
+++ b/ccan/aga/bellman_ford.c
@@ -0,0 +1,121 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/check_type/check_type.h>
+#include <ccan/order/order.h>
+
+#include <ccan/aga/aga.h>
+#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 true;
+ }
+ 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 update = 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;
+ update = update || candidate_path(g, ei.to, dist, n, e);
+ }
+ if (err) {
+ aga_fail(g, err);
+ return false;
+ }
+ }
+ g->state.bellman_ford.npasses++;
+ return update;
+}
+
+void aga_bellman_ford_complete(struct aga_graph *g)
+{
+ if (!aga_check_state(g))
+ return;
+
+ while (aga_bellman_ford_step(g))
+ ;
+}
+
+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 0000000..e0ce1a0
--- /dev/null
+++ b/ccan/aga/test/api-bellman_ford.c
@@ -0,0 +1,266 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/aga/aga.h>
+
+#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 0ee34e9..aa46284 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 274c9cc..f65b4e3 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 0000000..960cf39
--- /dev/null
+++ b/ccan/agar/test/api-bellman_ford.c
@@ -0,0 +1,249 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/tal/tal.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/agar/agar.h>
+
+#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();
+}
--
2.5.5
More information about the ccan
mailing list