]> git.ozlabs.org Git - ccan/blob - ccan/aga/aga.h
tlist: Place tlists last in structures
[ccan] / ccan / aga / aga.h
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef CCAN_AGA_H
3 #define CCAN_AGA_H
4 /*
5  * Abstract Graph Algorithms
6  *
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.
11  *
12  *
13  * Node representation
14  * ===================
15  *
16  * Graph nodes are represented by 'struct aga_node'
17  *
18  * - These will often be embedded in a caller-specific structure
19  *   (calling code can then locate its own structures using
20  *   container_of)
21  *
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
25  *   algorithm.
26  *
27  * - Nodes must be initialized with aga_node_init(), either up front,
28  *   or as they are constructed on the fly.
29  *
30  * - The contents of the structure should be treated as opaque by the
31  *   caller.
32  *
33  *
34  * Edge representation
35  * ===================
36  *
37  * Graph edges are reported by three caller supplied functions,
38  * 'first_edge', 'next_edge' and 'edge_info'.
39  *
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
44  *   (void *) identifier
45  * - NULL has a special meaning (indicating there are no more edges
46  *   from a given node).
47  * - Otherwise, edge identifiers are treated as opaque by aga
48  *
49  * - Calling first_edge, followed by next_edge repeatedly must iterate
50  *   through all the edges leading from node n.
51  *
52  * - Either first_edge or next_edge may return NULL indicating there
53  *   are no further edges from this node
54  *
55  * - edge_info MAY return a negative value in case of error.  This
56  *   will generally abort any aga algorithm which encounters it.
57  *
58  * - Otherwise edge_info must return 0.  Any other return value will
59  *   cause an abort().
60  *
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
65  *
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.
70  *
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.
74  *
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.
78  *
79  * Concurrency
80  * ===========
81  *
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.
85  *
86  * - When you start an algorithm (aga_*_start()) the graph is marked
87  *   as in-use.
88  *
89  * - Subsequent attempts to start an algorithm will fail;
90  *   aga_*_start() will return -1.
91  *
92  * - To release the graph for another algorithm, use aga_finish().
93  *
94  * - Calling functions associated with one algorithm while another is
95  *   running has undefined results.
96  *
97  * Errors
98  * ======
99  *
100  * - Errors may be reported by the edge_info callback, or may be
101  *   detected internally by algorithms.
102  *
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.
106  *
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.
111  *
112  * - Errors are cleared on aga_finish().
113  */
114 #include "config.h"
115 #include <string.h>
116
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>
122
123 struct aga_graph;
124 struct aga_node;
125
126 /*
127  * Callbacks
128  */
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,
133                                         const void *e);
134
135 typedef long aga_icost_t;
136
137 struct aga_edge_info {
138         struct aga_node *to;
139         aga_icost_t icost; /* integer edge cost */
140 };
141
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);
145
146 /*
147  * Internal data structures
148  */
149
150 struct aga_node {
151         int sequence;
152         union {
153                 struct {
154                         struct lstack_link parent;
155                         const void *edge;
156                 } dfs;
157                 struct {
158                         struct lqueue_link next;
159                         const void *edge;
160                 } bfs;
161                 struct {
162                         aga_icost_t distance;
163                         struct aga_node *prev;
164                         const void *prevedge;
165                         bool complete;
166                         struct lpq_link pqlink;
167                 } dijkstra;
168         } u;
169 };
170
171 struct aga_graph {
172         int sequence;
173         int error;
174
175         aga_first_edge_fn first_edge;
176         aga_next_edge_fn next_edge;
177         aga_edge_info_fn edge_info;
178         union {
179                 LPQ(struct aga_node, u.dijkstra.pqlink) dijkstra;
180         } state;
181 };
182
183 /*
184  * Core functions
185  */
186
187 /**
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
193  *
194  * Initialize @g to represent an abstract graph defined by the
195  * supplied edge callbacks
196  */
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_)                         \
202         do {                                                            \
203                 struct aga_node *n_;                                    \
204                 struct aga_edge_info *ei_;                              \
205                 BUILD_ASSERT(check_types_match((fefn_)((g_), n_),       \
206                                                (nefn_)((g_), n_,        \
207                                                        (fefn_)((g_), n_))) \
208                              == 0);                                     \
209                 BUILD_ASSERT(check_type((eifn_)((g_), n_,               \
210                                                 (fefn_)((g_), n_), ei_), \
211                                         int) == 0);                     \
212                 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_),       \
213                                 (aga_next_edge_fn)(nefn_),              \
214                                 (aga_edge_info_fn)(eifn_));             \
215         } while (0)
216
217 /**
218  * enum aga_error - Error codes for aga routines
219  *
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
223  */
224 enum aga_error {
225         /* No error */
226         AGA_ERR_NONE = 0,
227         /* Negative edge cost (in a context where it's not valid) */
228         AGA_ERR_NEGATIVE_COST = 1,
229 };
230
231 /**
232  * aga_error - Determine error state of a graph
233  * @g: the graph
234  *
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.
238  */
239 int aga_error(const struct aga_graph *g);
240
241 /**
242  * aga_node_init - Initialize a graph node
243  * @node: a graph node
244  *
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)
248  */
249 static inline void aga_node_init(struct aga_node *node)
250 {
251         memset(node, 0, sizeof(*node));
252 }
253
254 /**
255  * aga_finish - Finish an aga algorithm
256  * @g: graph
257  *
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.
261  */
262 void aga_finish(struct aga_graph *g);
263
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,
266                           const void *e);
267 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
268                   const void *e, struct aga_edge_info *ei);
269
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)))
273
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)))                    \
278                 if ((_ei).to)
279
280 /*
281  * Depth first search
282  */
283
284 /**
285  * aga_dfs_start - Start a depth-first search
286  * @g: graph to search
287  *
288  * Begins the depth-first search algorithm on @g
289  */
290 int aga_dfs_start(struct aga_graph *g);
291
292 /**
293  * aga_dfs_explore - One step of depth-first search
294  * @g: graph to search
295  * @n: node to start exploration from
296  *
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.
300  */
301 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
302
303 /**
304  * aga_dfs - Depth-first search
305  * @_n: pointer to current node (output)
306  * @_g: graph to search
307  * @_start: node to start from
308  *
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.
312  *
313  * aga_dfs_start() must be called before this macro is used.
314  */
315 #define aga_dfs(_n, _g, _start)                                 \
316         for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
317
318
319 /*
320  * Breadth first search
321  */
322
323 /**
324  * aga_bfs_start - Start a breadth-first search
325  * @g: graph to search
326  *
327  * Begins the breadth-first search algorithm on @g
328  */
329 int aga_bfs_start(struct aga_graph *g);
330
331 /**
332  * aga_bfs_explore - One step of breadth-first search
333  * @g: graph to search
334  * @n: node to start exploration from
335  *
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.
339  */
340 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
341
342 /**
343  * aga_bfs - Breadth-first search
344  * @_n: pointer to current node (output)
345  * @_g: graph to search
346  * @_start: node to start from
347  *
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.
351  *
352  * aga_bfs_start() must be called before this macro is used.
353  */
354 #define aga_bfs(_n, _g, _start)                                 \
355         for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
356
357 /*
358  * Dijkstra's algorithm
359  */
360
361 /**
362  * aga_dijkstra_start - Start Dijkstra's algorithm
363  * @g: graph
364  * @source: source node
365  *
366  * Start's Dijkstra's algorithm on @g to find shortest paths from node
367  * @source, to other nodes in @g.
368  */
369 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source);
370
371
372 /**
373  * aga_dijkstra_step - Find the node with the next shortest path
374  * @g: graph
375  *
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.
380  */
381 struct aga_node *aga_dijkstra_step(struct aga_graph *g);
382
383 /**
384  * aga_dijkstra_path - Find the shortest path to a node
385  * @g: graph
386  * @dest: destination node
387  * @prev: Second last node in the path *output)
388  * @prevedge: Last edge in the path
389  *
390  * Finds the shortest path from the source node (specified in
391  * aga_dijkstra_start() to @dest using Dijkstra's algorithm.
392  *
393  * If no path exists, return false.
394  *
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.
400  *
401  * If @dest is the same as source, 0 will be stored in @cost, and NULL
402  * will be stored in *@prev and *@prevedge.
403  *
404  * The full path from source to @dest can be determined by repeatedly
405  * calling aga_dijkstra_path() on *@prev.
406  *
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.
413  */
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);
417
418 /**
419  * aga_dijkstra_all_paths - Find shortest paths to all reachable nodes
420  * @g: graph
421  *
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.
427  */
428 void aga_dijkstra_all_paths(struct aga_graph *g);
429
430 #endif /* CCAN_AGA_H */