aga,agar: The Bellman-Ford algorithm
authorDavid Gibson <david@gibson.dropbear.id.au>
Sat, 11 Jun 2016 08:30:08 +0000 (18:30 +1000)
committerDavid Gibson <david@gibson.dropbear.id.au>
Fri, 4 Nov 2016 12:38:47 +0000 (23:38 +1100)
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@gibson.dropbear.id.au>
ccan/aga/aga.h
ccan/aga/bellman_ford.c [new file with mode: 0644]
ccan/aga/test/api-bellman_ford.c [new file with mode: 0644]
ccan/agar/agar.c
ccan/agar/agar.h
ccan/agar/test/api-bellman_ford.c [new file with mode: 0644]

index aa60bcc96a4404bd518b4d82120e7bc9f48e4db3..239d36c339ee7bebc73d03ba1b1e4419fb1e0b76 100644 (file)
@@ -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 (file)
index 0000000..1820483
--- /dev/null
@@ -0,0 +1,141 @@
+/* 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 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 (file)
index 0000000..e0ce1a0
--- /dev/null
@@ -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();
+}
index 0ee34e9ab94c63cd7c765870c43dd85531a44115..aa4628404864affe29578122fb69f729f1a059c8 100644 (file)
@@ -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);
+}
index 274c9cc1f9a308136bfd982612c519c0412a0d91..f65b4e371f456d7b6bca8208dd5e7f53260874c2 100644 (file)
@@ -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 (file)
index 0000000..960cf39
--- /dev/null
@@ -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();
+}