X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Faga.h;h=239d36c339ee7bebc73d03ba1b1e4419fb1e0b76;hb=9d2d2c49f053018724bcc6e37029da10b7c3d60d;hp=7d6016ff70606765145fa9f90be5014ba918c757;hpb=be32f4df1263ad0d323d6d401f037a37a19d580f;p=ccan diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h index 7d6016ff..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 * =========== * @@ -107,13 +111,14 @@ * * - Errors are cleared on aga_finish(). */ - #include "config.h" #include #include #include #include +#include +#include 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); @@ -145,6 +154,23 @@ struct aga_node { struct lstack_link parent; const void *edge; } dfs; + struct { + 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; }; @@ -155,12 +181,30 @@ 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; }; /* * 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, @@ -181,13 +225,51 @@ 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 + * + * 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); @@ -201,7 +283,7 @@ 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) @@ -210,10 +292,209 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n, * 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 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 */