1 /* Licensed under LGPLv2+ - see LICENSE file for details */
5 * Abstract Graph Algorithms
7 * This module implements several standard algorithms on "abstract"
8 * (directed) graphs. That is to say rather than requiring a specific
9 * concrete representation of the graph, user-supplied callbacks allow
10 * the graph to be constructed as it is explored.
16 * Graph nodes are represented by 'struct aga_node'
18 * - These will often be embedded in a caller-specific structure
19 * (calling code can then locate its own structures using
22 * - Nodes are semi-persistent - they MAY be constructed on the fly by
23 * the edge_info callback (see below), but MUST then remain in place
24 * at least as long as the completion of the current graph
27 * - Nodes must be initialized with aga_node_init(), either up front,
28 * or as they are constructed on the fly.
30 * - The contents of the structure should be treated as opaque by the
37 * Graph edges are reported by three caller supplied functions,
38 * 'first_edge', 'next_edge' and 'edge_info'.
40 * - Edges are identified by a (void *)
41 * - The combination of a graph, a node and this (void *) MUST
42 * uniquely identify an edge
43 * - Different edges leading from different nodes MAY have the same
45 * - NULL has a special meaning (indicating there are no more edges
47 * - Otherwise, edge identifiers are treated as opaque by aga
49 * - Calling first_edge, followed by next_edge repeatedly must iterate
50 * through all the edges leading from node n.
52 * - Either first_edge or next_edge may return NULL indicating there
53 * are no further edges from this node
55 * - edge_info MAY return a negative value in case of error. This
56 * will generally abort any aga algorithm which encounters it.
58 * - Otherwise edge_info must return 0. Any other return value will
61 * - edge_info MAY set ei->to to NULL, indicating a "missing" edge,
62 * thus there MAY be more edge identifiers than actual edges from a
63 * given node. Otherwise, edge_info MUST fill in the ei->to field
64 * with a pointer to the destination node of the given edge
66 * - The ei->to field for a returned edge MAY point to an existing
67 * struct aga_node, or it MAY have just been allocated by the edge
68 * callback itself. If the latter, it MUST have been initialized
69 * with aga_node_init() before the edge callback returns.
71 * - If a node is contructed by the edge callback, any subsequent
72 * reference to that node by the edge callback for *any* node and
73 * index MUST use the same pointer.
75 * - The ei->icost field MAY be set by the edge_info callback to
76 * indicate the edge's cost / length represented as an integer (of
77 * type aga_icost_t), Otherwise the cost defaults to 1.
82 * - Because the algorithms implemented here keep state in the
83 * aga_node structures, only one algorithm can run at a time.
84 * Global state for algorithms is stored in the aga_graph structure.
86 * - When you start an algorithm (aga_*_start()) the graph is marked
89 * - Subsequent attempts to start an algorithm will fail;
90 * aga_*_start() will return -1.
92 * - To release the graph for another algorithm, use aga_finish().
94 * - Calling functions associated with one algorithm while another is
95 * running has undefined results.
100 * - Errors may be reported by the edge_info callback, or may be
101 * detected internally by algorithms.
103 * - Algorithms will generally stop running when they encounter an
104 * error; the call which detects the error and subsequent calls will
105 * return a "safe", but otherwise meaningless value.
107 * - After an error is encountered aga_error() will return a non-zero
108 * value. Negative values are reserved for errors reported by the
109 * user supplied edge callback. Positive values are reserved for
110 * errors detected interally by aga.
112 * - Errors are cleared on aga_finish().
117 #include <ccan/build_assert/build_assert.h>
118 #include <ccan/check_type/check_type.h>
119 #include <ccan/lstack/lstack.h>
120 #include <ccan/lqueue/lqueue.h>
121 #include <ccan/lpq/lpq.h>
129 typedef const void *(*aga_first_edge_fn)(const struct aga_graph *g,
130 const struct aga_node *n);
131 typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
132 const struct aga_node *n,
135 typedef long aga_icost_t;
137 struct aga_edge_info {
139 aga_icost_t icost; /* integer edge cost */
142 typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
143 const struct aga_node *n,
144 const void *e, struct aga_edge_info *ei);
147 * Internal data structures
154 struct lstack_link parent;
158 struct lqueue_link next;
162 aga_icost_t distance;
163 struct aga_node *prev;
164 const void *prevedge;
166 struct lpq_link pqlink;
175 aga_first_edge_fn first_edge;
176 aga_next_edge_fn next_edge;
177 aga_edge_info_fn edge_info;
179 LPQ(struct aga_node, u.dijkstra.pqlink) dijkstra;
188 * aga_init_graph - Initialize a new abstract graph
189 * @g: graph structure to initialize
190 * @first_edge: first edge callback
191 * @next_edge: next edge callback
192 * @edge_into: edge info callback
194 * Initialize @g to represent an abstract graph defined by the
195 * supplied edge callbacks
197 void aga_init_graph_(struct aga_graph *g,
198 aga_first_edge_fn first_edge,
199 aga_next_edge_fn next_edge,
200 aga_edge_info_fn edge_info);
201 #define aga_init_graph(g_, fefn_, nefn_, eifn_) \
203 struct aga_node *n_; \
204 struct aga_edge_info *ei_; \
205 BUILD_ASSERT(check_types_match((fefn_)((g_), n_), \
207 (fefn_)((g_), n_))) \
209 BUILD_ASSERT(check_type((eifn_)((g_), n_, \
210 (fefn_)((g_), n_), ei_), \
212 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_), \
213 (aga_next_edge_fn)(nefn_), \
214 (aga_edge_info_fn)(eifn_)); \
218 * enum aga_error - Error codes for aga routines
220 * These error codes are returned by aga_error() for errors detected
221 * within aga itself (rather than errors reported by supplied
222 * callbacks, which should be negative
227 /* Negative edge cost (in a context where it's not valid) */
228 AGA_ERR_NEGATIVE_COST = 1,
232 * aga_error - Determine error state of a graph
235 * Returns 0 if the graph is not in an error state, negative values
236 * for error states reported by one of the edge callbacks and
237 * postitive values for errors detected by aga itself.
239 int aga_error(const struct aga_graph *g);
242 * aga_node_init - Initialize a graph node
243 * @node: a graph node
245 * Initialize @node as a new graph node. This must be called before
246 * @node is passed to any aga function, or returned from an edge_info
247 * callback (in the ei->to field)
249 static inline void aga_node_init(struct aga_node *node)
251 memset(node, 0, sizeof(*node));
255 * aga_finish - Finish an aga algorithm
258 * Wraps up the aga algorithm currently running on @g. This will
259 * clear any error conditions. After this is called it is an error to
260 * call aga functions on @g apart from aga_*_start() and aga_error.
262 void aga_finish(struct aga_graph *g);
264 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
265 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
267 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
268 const void *e, struct aga_edge_info *ei);
270 #define aga_for_each_edge(_e, _g, _n) \
271 for ((_e) = aga_first_edge((_g), (_n)); (_e); \
272 (_e) = aga_next_edge((_g), (_n), (_e)))
274 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n) \
275 for ((_err) = 0, (_e) = aga_first_edge((_g), (_n)); \
276 (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
277 (_e) = aga_next_edge((_g), (_n), (_e))) \
285 * aga_dfs_start - Start a depth-first search
286 * @g: graph to search
288 * Begins the depth-first search algorithm on @g
290 int aga_dfs_start(struct aga_graph *g);
293 * aga_dfs_explore - One step of depth-first search
294 * @g: graph to search
295 * @n: node to start exploration from
297 * If @n has not yet been explored since aga_dfs_start(), returns @n.
298 * Otherwise returns the next node after @n in depth-first search
299 * order. Marks the returned node as explored.
301 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
304 * aga_dfs - Depth-first search
305 * @_n: pointer to current node (output)
306 * @_g: graph to search
307 * @_start: node to start from
309 * Performs a depth first search. The block following this macro is
310 * executed with @_n set first to @_start, then to each node reachable
311 * from @_start in depth first search order.
313 * aga_dfs_start() must be called before this macro is used.
315 #define aga_dfs(_n, _g, _start) \
316 for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
320 * Breadth first search
324 * aga_bfs_start - Start a breadth-first search
325 * @g: graph to search
327 * Begins the breadth-first search algorithm on @g
329 int aga_bfs_start(struct aga_graph *g);
332 * aga_bfs_explore - One step of breadth-first search
333 * @g: graph to search
334 * @n: node to start exploration from
336 * If @n has not yet been explored since aga_bfs_start(), returns @n.
337 * Otherwise returns the next node after @n in breadth-first search
338 * order. Marks the returned node as explored.
340 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
343 * aga_bfs - Breadth-first search
344 * @_n: pointer to current node (output)
345 * @_g: graph to search
346 * @_start: node to start from
348 * Performs a breadth first search. The block following this macro is
349 * executed with @_n set first to @_start, then to each node reachable
350 * from @_start in depth first search order.
352 * aga_bfs_start() must be called before this macro is used.
354 #define aga_bfs(_n, _g, _start) \
355 for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
358 * Dijkstra's algorithm
362 * aga_dijkstra_start - Start Dijkstra's algorithm
364 * @source: source node
366 * Start's Dijkstra's algorithm on @g to find shortest paths from node
367 * @source, to other nodes in @g.
369 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source);
373 * aga_dijkstra_step - Find the node with the next shortest path
376 * The first call to this function returns the source node specified
377 * in aga_dijkstra_start(). Subsequent calls return the next closest
378 * node to source by shortest path cost. Returns NULL if no further
379 * nodes are reachable from source.
381 struct aga_node *aga_dijkstra_step(struct aga_graph *g);
384 * aga_dijkstra_path - Find the shortest path to a node
386 * @dest: destination node
387 * @prev: Second last node in the path *output)
388 * @prevedge: Last edge in the path
390 * Finds the shortest path from the source node (specified in
391 * aga_dijkstra_start() to @dest using Dijkstra's algorithm.
393 * If no path exists, return false.
395 * If a path does exist, returns true. Additionally if @total_cost is
396 * non-NULL, store the total cost of the path in *@total_cost, if
397 * @prev is non-NULL, store the node in the path immediately before
398 * @dest in *@prev and if @prevedge is non-NULL stores the edge which
399 * leads from *@prev to @dest in *@prevedge.
401 * If @dest is the same as source, 0 will be stored in @cost, and NULL
402 * will be stored in *@prev and *@prevedge.
404 * The full path from source to @dest can be determined by repeatedly
405 * calling aga_dijkstra_path() on *@prev.
407 * NOTE: Dijkstra's algorithm will not work correctly on a graph which
408 * has negative costs on some edges. If aga detects this case, it
409 * will set aga_error() to AGA_ERR_NEGATIVE_COST. However,
410 * aga_dijkstra_path() may produce incorrect results without detecting
411 * this situation. aga_dijkstra_all_paths() *is* guaranteed to
412 * discover any negative cost edge reachable from the starting node.
414 bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
415 aga_icost_t *total_cost,
416 struct aga_node **prev, const void **prevedge);
419 * aga_dijkstra_all_paths - Find shortest paths to all reachable nodes
422 * Finds shortest paths from the source node (specified in
423 * aga_dijkstra_start()) to all other reachable nodes in @g. No
424 * results are returned directly, but between calling
425 * aga_dijkstra_all_paths() and aga_finish, aga_dijkstra_path() is
426 * guaranteed to complete in O(1) time for all destinations.
428 void aga_dijkstra_all_paths(struct aga_graph *g);
430 #endif /* CCAN_AGA_H */