[PATCH 0/2] Bellman-Ford

[PATCH 0/2] Bellman-Ford

[David Gibson]

A Bellman-Ford algorithm implementation for aga.  Sending this out in
case anyone cares to review it.  I'll commit it shortly if there
aren't screams.

Doesn't yet have some of the extensions we discussed, Rusty, but I
hope to add at least some of them gradually.

David Gibson (2):
  aga,agar: Rename aga_dijkstra_all_paths()
  aga,agar: The Bellman-Ford algorithm

 ccan/aga/aga.h                    |  76 ++++++++++-
 ccan/aga/bellman_ford.c           | 121 +++++++++++++++++
 ccan/aga/dijkstra.c               |   2 +-
 ccan/aga/test/api-bellman_ford.c  | 266 ++++++++++++++++++++++++++++++++++++++
 ccan/aga/test/api-dijkstra.c      |   2 +-
 ccan/agar/agar.c                  |  49 ++++++-
 ccan/agar/agar.h                  |  14 +-
 ccan/agar/test/api-bellman_ford.c | 249 +++++++++++++++++++++++++++++++++++
 ccan/agar/test/api-dijkstra.c     |   2 +-
 9 files changed, 772 insertions(+), 9 deletions(-)
 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

-- 
2.5.5

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

[PATCH 1/2] aga,agar: Rename aga_dijkstra_all_paths()

[David Gibson]

aga_dijkstra_all_paths() runs Dijkstra's algorithm to completion (as
opposed to aga_dijkstra_path(), which operates lazily).  In effect this
computes the shortest path to all (reachable) nodes from the start node.

So, in this context the name makes sense.  But for an analogous function
for future algorithms (e.g. Bellman-Ford), the name doesn't make sense.

So, in the interests of consistency with those future extensions, change
the name of this to aga_dijkstra_complete().

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 ccan/aga/aga.h                | 6 +++---
 ccan/aga/dijkstra.c           | 2 +-
 ccan/aga/test/api-dijkstra.c  | 2 +-
 ccan/agar/agar.c              | 4 ++--
 ccan/agar/agar.h              | 2 +-
 ccan/agar/test/api-dijkstra.c | 2 +-
 6 files changed, 9 insertions(+), 9 deletions(-)

diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index d09d4c7..62e03e7 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -416,15 +416,15 @@ bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
 		       struct aga_node **prev, const void **prevedge);
 
 /**
- * aga_dijkstra_all_paths - Find shortest paths to all reachable nodes
+ * aga_dijkstra_complete - Find shortest paths to all reachable nodes
  * @g: graph
  *
  * Finds shortest paths from the source node (specified in
  * aga_dijkstra_start()) to all other reachable nodes in @g.  No
  * results are returned directly, but between calling
- * aga_dijkstra_all_paths() and aga_finish, aga_dijkstra_path() is
+ * aga_dijkstra_all_paths() and aga_finish(), aga_dijkstra_path() is
  * guaranteed to complete in O(1) time for all destinations.
  */
-void aga_dijkstra_all_paths(struct aga_graph *g);
+void aga_dijkstra_complete(struct aga_graph *g);
 
 #endif /* CCAN_AGA_H */
diff --git a/ccan/aga/dijkstra.c b/ccan/aga/dijkstra.c
index 02177fb..cbb79b9 100644
--- a/ccan/aga/dijkstra.c
+++ b/ccan/aga/dijkstra.c
@@ -114,7 +114,7 @@ bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *node,
 	return true;
 }
 
-void aga_dijkstra_all_paths(struct aga_graph *g)
+void aga_dijkstra_complete(struct aga_graph *g)
 {
 	if (!aga_check_state(g))
 		return;
diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index f9b8d76..74875fb 100644
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -241,7 +241,7 @@ static void test_shortcut2(void)
 	shortcut2_graph_init(&s2g);
 
 	ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
-	aga_dijkstra_all_paths(&s2g.sg.g);
+	aga_dijkstra_complete(&s2g.sg.g);
 	ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
 	aga_finish(&s2g.sg.g);
 }
diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c
index e930d7a..0ee34e9 100644
--- a/ccan/agar/agar.c
+++ b/ccan/agar/agar.c
@@ -286,8 +286,8 @@ bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
 	return true;
 }
 
-void agar_dijkstra_all_paths(struct agar_state *sr)
+void agar_dijkstra_complete(struct agar_state *sr)
 {
-	aga_dijkstra_all_paths(&sr->g);
+	aga_dijkstra_complete(&sr->g);
 }
 
diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h
index abd1130..274c9cc 100644
--- a/ccan/agar/agar.h
+++ b/ccan/agar/agar.h
@@ -84,6 +84,6 @@ bool agar_dijkstra_step(struct agar_state *sr, const void **nextr);
 bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
 			aga_icost_t *total_cost,
 			const void **prevr, const void **prevedge);
-void agar_dijkstra_all_paths(struct agar_state *sr);
+void agar_dijkstra_complete(struct agar_state *sr);
 
 #endif /* CCAN_AGAR_H */
diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index ebdbf42..a5de2ea 100644
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -231,7 +231,7 @@ static void test_shortcut2(void)
 	struct agar_state *sr;
 
 	ok1(sr = agar_dijkstra_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
-	agar_dijkstra_all_paths(sr);
+	agar_dijkstra_complete(sr);
 	ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
 	tal_free(sr);
 }
-- 
2.5.5

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan

[PATCH 2/2] aga,agar: The Bellman-Ford algorithm

[David Gibson]

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                    |  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

_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan