X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Faga.h;h=a8a888be1a9d584045e99659bb465459e01af895;hb=f9274cce2171d919d72fe9ec186320f85174b7e5;hp=d5cc434b50ccb33ee0d5c3f7204d67ffeeb76cfa;hpb=3b7409ea08a7d1643bc7de31ece63e20b89f319b;p=ccan diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h index d5cc434b..a8a888be 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 * =========== * @@ -107,12 +111,13 @@ * * - Errors are cleared on aga_finish(). */ - #include "config.h" #include #include #include +#include +#include struct aga_graph; struct aga_node; @@ -126,9 +131,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); @@ -140,7 +149,14 @@ typedef int (*aga_edge_info_fn)(const struct aga_graph *g, struct aga_node { int sequence; union { - /* Per-algorithm state here */ + struct { + struct lstack_link parent; + const void *edge; + } dfs; + struct { + struct lqueue_link next; + const void *edge; + } bfs; } u; }; @@ -157,6 +173,16 @@ struct aga_graph { * Core functions */ +/** + * aga_init_graph - Initialize a new abstract graph + * @g: graph structure to initialize + * @first_edge: first edge callback + * @next_edge: next edge callback + * @edge_into: edge info callback + * + * Initialize @g to represent an abstract graph defined by the + * supplied edge callbacks + */ void aga_init_graph_(struct aga_graph *g, aga_first_edge_fn first_edge, aga_next_edge_fn next_edge, @@ -177,13 +203,49 @@ 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, +}; + +/** + * aga_error - Determine error state of a graph + * @g: the graph + * + * Returns 0 if the graph is not in an error state, negative values + * for error states reported by one of the edge callbacks and + * postitive values for errors detected by aga itself. + */ int aga_error(const struct aga_graph *g); +/** + * aga_node_init - Initialize a graph node + * @node: a graph node + * + * Initialize @node as a new graph node. This must be called before + * @node is passed to any aga function, or returned from an edge_info + * callback (in the ei->to field) + */ static inline void aga_node_init(struct aga_node *node) { memset(node, 0, sizeof(*node)); } +/** + * aga_finish - Finish an aga algorithm + * @g: graph + * + * Wraps up the aga algorithm currently running on @g. This will + * clear any error conditions. After this is called it is an error to + * call aga functions on @g apart from aga_*_start() and aga_error. + */ void aga_finish(struct aga_graph *g); const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n); @@ -197,9 +259,86 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n, (_e) = aga_next_edge((_g), (_n), (_e))) #define aga_for_each_edge_info(_e, _ei, _err, _g, _n) \ - for ((_e) = aga_first_edge((_g), (_n)); \ + for ((_err) = 0, (_e) = aga_first_edge((_g), (_n)); \ (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \ (_e) = aga_next_edge((_g), (_n), (_e))) \ if ((_ei).to) +/* + * Depth first search + */ + +/** + * aga_dfs_start - Start a depth-first search + * @g: graph to search + * + * Begins the depth-first search algorithm on @g + */ +int aga_dfs_start(struct aga_graph *g); + +/** + * aga_dfs_explore - One step of depth-first search + * @g: graph to search + * @n: node to start exploration from + * + * If @n has not yet been explored since aga_dfs_start(), returns @n. + * Otherwise returns the next node after @n in depth-first search + * order. Marks the returned node as explored. + */ +struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n); + +/** + * aga_dfs - Depth-first search + * @_n: pointer to current node (output) + * @_g: graph to search + * @_start: node to start from + * + * Performs a depth 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. + * + * aga_dfs_start() must be called before this macro is used. + */ +#define aga_dfs(_n, _g, _start) \ + for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; ) + + +/* + * Breadth first search + */ + +/** + * aga_bfs_start - Start a breadth-first search + * @g: graph to search + * + * Begins the breadth-first search algorithm on @g + */ +int aga_bfs_start(struct aga_graph *g); + +/** + * aga_bfs_explore - One step of breadth-first search + * @g: graph to search + * @n: node to start exploration from + * + * If @n has not yet been explored since aga_bfs_start(), returns @n. + * Otherwise returns the next node after @n in breadth-first search + * order. Marks the returned node as explored. + */ +struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n); + +/** + * aga_bfs - Breadth-first search + * @_n: pointer to current node (output) + * @_g: graph to search + * @_start: node to start from + * + * 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. + * + * 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; ) + #endif /* CCAN_AGA_H */