X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Faga.h;h=239d36c339ee7bebc73d03ba1b1e4419fb1e0b76;hb=9d2d2c49f053018724bcc6e37029da10b7c3d60d;hp=aa4126a79768d5afe55e9ada39c71b34b684c1b6;hpb=2ab26c629fcad393fd3da70e1bd26ed29048c950;p=ccan

diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index aa4126a7..239d36c3 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -72,6 +72,10 @@
  *   reference to that node by the edge callback for *any* node and
  *   index MUST use the same pointer.
  *
+ * - The ei->icost field MAY be set by the edge_info callback to
+ *   indicate the edge's cost / length represented as an integer (of
+ *   type aga_icost_t),  Otherwise the cost defaults to 1.
+ *
  * Concurrency
  * ===========
  *
@@ -114,6 +118,7 @@
 #include <ccan/check_type/check_type.h>
 #include <ccan/lstack/lstack.h>
 #include <ccan/lqueue/lqueue.h>
+#include <ccan/lpq/lpq.h>
 
 struct aga_graph;
 struct aga_node;
@@ -127,9 +132,13 @@ typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
 					const struct aga_node *n,
 					const void *e);
 
+typedef long aga_icost_t;
+
 struct aga_edge_info {
 	struct aga_node *to;
+	aga_icost_t icost; /* integer edge cost */
 };
+
 typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
 				const struct aga_node *n,
 				const void *e, struct aga_edge_info *ei);
@@ -149,6 +158,19 @@ struct aga_node {
 			struct lqueue_link next;
 			const void *edge;
 		} bfs;
+		struct {
+			aga_icost_t distance;
+			struct aga_node *prev;
+			const void *prevedge;
+			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;
 };
 
@@ -159,6 +181,14 @@ struct aga_graph {
 	aga_first_edge_fn first_edge;
 	aga_next_edge_fn next_edge;
 	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;
 };
 
 /*
@@ -195,6 +225,20 @@ void aga_init_graph_(struct aga_graph *g,
 				(aga_edge_info_fn)(eifn_));		\
 	} while (0)
 
+/**
+ * enum aga_error - Error codes for aga routines
+ *
+ * These error codes are returned by aga_error() for errors detected
+ * within aga itself (rather than errors reported by supplied
+ * callbacks, which should be negative
+ */
+enum aga_error {
+	/* No error */
+	AGA_ERR_NONE = 0,
+	/* Negative edge cost (in a context where it's not valid) */
+	AGA_ERR_NEGATIVE_COST = 1,
+};
+
 /**
  * aga_error - Determine error state of a graph
  * @g: the graph
@@ -314,11 +358,143 @@ struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
  *
  * Performs a breadth first search.  The block following this macro is
  * executed with @_n set first to @_start, then to each node reachable
- * from @_start in depth first search order.
+ * from @_start in breadth-first search order.
  *
  * aga_bfs_start() must be called before this macro is used.
  */
 #define aga_bfs(_n, _g, _start)					\
 	for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
 
+/*
+ * Dijkstra's algorithm
+ */
+
+/**
+ * aga_dijkstra_start - Start Dijkstra's algorithm
+ * @g: graph
+ * @source: source node
+ *
+ * Start's Dijkstra's algorithm on @g to find shortest paths from node
+ * @source, to other nodes in @g.
+ */
+int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source);
+
+
+/**
+ * aga_dijkstra_step - Find the node with the next shortest path
+ * @g: graph
+ *
+ * The first call to this function returns the source node specified
+ * in aga_dijkstra_start().  Subsequent calls return the next closest
+ * node to source by shortest path cost.  Returns NULL if no further
+ * nodes are reachable from source.
+ */
+struct aga_node *aga_dijkstra_step(struct aga_graph *g);
+
+/**
+ * aga_dijkstra_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_dijkstra_start() to @dest using Dijkstra'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_dijkstra_path() on *@prev.
+ *
+ * NOTE: Dijkstra's algorithm will not work correctly on a graph which
+ * has negative costs on some edges.  If aga detects this case, it
+ * will set aga_error() to AGA_ERR_NEGATIVE_COST.  However,
+ * aga_dijkstra_path() may produce incorrect results without detecting
+ * this situation.  aga_dijkstra_all_paths() *is* guaranteed to
+ * discover any negative cost edge reachable from the starting node.
+ */
+bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
+		       aga_icost_t *total_cost,
+		       struct aga_node **prev, const void **prevedge);
+
+/**
+ * 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
+ * guaranteed to complete in O(1) time for all destinations.
+ */
+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 */