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.
78 * - Because the algorithms implemented here keep state in the
79 * aga_node structures, only one algorithm can run at a time.
80 * Global state for algorithms is stored in the aga_graph structure.
82 * - When you start an algorithm (aga_*_start()) the graph is marked
85 * - Subsequent attempts to start an algorithm will fail;
86 * aga_*_start() will return -1.
88 * - To release the graph for another algorithm, use aga_finish().
90 * - Calling functions associated with one algorithm while another is
91 * running has undefined results.
96 * - Errors may be reported by the edge_info callback, or may be
97 * detected internally by algorithms.
99 * - Algorithms will generally stop running when they encounter an
100 * error; the call which detects the error and subsequent calls will
101 * return a "safe", but otherwise meaningless value.
103 * - After an error is encountered aga_error() will return a non-zero
104 * value. Negative values are reserved for errors reported by the
105 * user supplied edge callback. Positive values are reserved for
106 * errors detected interally by aga.
108 * - Errors are cleared on aga_finish().
113 #include <ccan/build_assert/build_assert.h>
114 #include <ccan/check_type/check_type.h>
115 #include <ccan/lstack/lstack.h>
116 #include <ccan/lqueue/lqueue.h>
124 typedef const void *(*aga_first_edge_fn)(const struct aga_graph *g,
125 const struct aga_node *n);
126 typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
127 const struct aga_node *n,
130 struct aga_edge_info {
133 typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
134 const struct aga_node *n,
135 const void *e, struct aga_edge_info *ei);
138 * Internal data structures
145 struct lstack_link parent;
149 struct lqueue_link next;
159 aga_first_edge_fn first_edge;
160 aga_next_edge_fn next_edge;
161 aga_edge_info_fn edge_info;
168 void aga_init_graph_(struct aga_graph *g,
169 aga_first_edge_fn first_edge,
170 aga_next_edge_fn next_edge,
171 aga_edge_info_fn edge_info);
172 #define aga_init_graph(g_, fefn_, nefn_, eifn_) \
174 struct aga_node *n_; \
175 struct aga_edge_info *ei_; \
176 BUILD_ASSERT(check_types_match((fefn_)((g_), n_), \
178 (fefn_)((g_), n_))) \
180 BUILD_ASSERT(check_type((eifn_)((g_), n_, \
181 (fefn_)((g_), n_), ei_), \
183 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_), \
184 (aga_next_edge_fn)(nefn_), \
185 (aga_edge_info_fn)(eifn_)); \
188 int aga_error(const struct aga_graph *g);
190 static inline void aga_node_init(struct aga_node *node)
192 memset(node, 0, sizeof(*node));
195 void aga_finish(struct aga_graph *g);
197 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
198 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
200 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
201 const void *e, struct aga_edge_info *ei);
203 #define aga_for_each_edge(_e, _g, _n) \
204 for ((_e) = aga_first_edge((_g), (_n)); (_e); \
205 (_e) = aga_next_edge((_g), (_n), (_e)))
207 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n) \
208 for ((_e) = aga_first_edge((_g), (_n)); \
209 (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
210 (_e) = aga_next_edge((_g), (_n), (_e))) \
217 int aga_dfs_start(struct aga_graph *g);
218 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
220 #define aga_dfs(_n, _g, _start) \
221 for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
225 * Breadth first search
228 int aga_bfs_start(struct aga_graph *g);
229 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
231 #define aga_bfs(_n, _g, _start) \
232 for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
234 #endif /* CCAN_AGA_H */