git.ozlabs.org Git - ccan/blob - 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                 struct {
 169                         aga_icost_t distance;
 170                         struct aga_node *prev;
 171                         const void *prevedge;
 172                         struct aga_node *list;
 173                 } bellman_ford;
 174         } u;
 175 };
 176
 177 struct aga_graph {
 178         int sequence;
 179         int error;
 180
 181         aga_first_edge_fn first_edge;
 182         aga_next_edge_fn next_edge;
 183         aga_edge_info_fn edge_info;
 184         union {
 185                 LPQ(struct aga_node, u.dijkstra.pqlink) dijkstra;
 186                 struct {
 187                         struct aga_node *nodelist;
 188                         int nnodes;
 189                         int npasses;
 190                 } bellman_ford;
 191         } state;
 192 };
 193
 194 /*
 195  * Core functions
 196  */
 197
 198 /**
 199  * aga_init_graph - Initialize a new abstract graph
 200  * @g: graph structure to initialize
 201  * @first_edge: first edge callback
 202  * @next_edge: next edge callback
 203  * @edge_into: edge info callback
 204  *
 205  * Initialize @g to represent an abstract graph defined by the
 206  * supplied edge callbacks
 207  */
 208 void aga_init_graph_(struct aga_graph *g,
 209                      aga_first_edge_fn first_edge,
 210                      aga_next_edge_fn next_edge,
 211                      aga_edge_info_fn edge_info);
 212 #define aga_init_graph(g_, fefn_, nefn_, eifn_)                         \
 213         do {                                                            \
 214                 struct aga_node *n_;                                    \
 215                 struct aga_edge_info *ei_;                              \
 216                 BUILD_ASSERT(check_types_match((fefn_)((g_), n_),       \
 217                                                (nefn_)((g_), n_,        \
 218                                                        (fefn_)((g_), n_))) \
 219                              == 0);                                     \
 220                 BUILD_ASSERT(check_type((eifn_)((g_), n_,               \
 221                                                 (fefn_)((g_), n_), ei_), \
 222                                         int) == 0);                     \
 223                 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_),       \
 224                                 (aga_next_edge_fn)(nefn_),              \
 225                                 (aga_edge_info_fn)(eifn_));             \
 226         } while (0)
 227
 228 /**
 229  * enum aga_error - Error codes for aga routines
 230  *
 231  * These error codes are returned by aga_error() for errors detected
 232  * within aga itself (rather than errors reported by supplied
 233  * callbacks, which should be negative
 234  */
 235 enum aga_error {
 236         /* No error */
 237         AGA_ERR_NONE = 0,
 238         /* Negative edge cost (in a context where it's not valid) */
 239         AGA_ERR_NEGATIVE_COST = 1,
 240 };
 241
 242 /**
 243  * aga_error - Determine error state of a graph
 244  * @g: the graph
 245  *
 246  * Returns 0 if the graph is not in an error state, negative values
 247  * for error states reported by one of the edge callbacks and
 248  * postitive values for errors detected by aga itself.
 249  */
 250 int aga_error(const struct aga_graph *g);
 251
 252 /**
 253  * aga_node_init - Initialize a graph node
 254  * @node: a graph node
 255  *
 256  * Initialize @node as a new graph node.  This must be called before
 257  * @node is passed to any aga function, or returned from an edge_info
 258  * callback (in the ei->to field)
 259  */
 260 static inline void aga_node_init(struct aga_node *node)
 261 {
 262         memset(node, 0, sizeof(*node));
 263 }
 264
 265 /**
 266  * aga_finish - Finish an aga algorithm
 267  * @g: graph
 268  *
 269  * Wraps up the aga algorithm currently running on @g.  This will
 270  * clear any error conditions.  After this is called it is an error to
 271  * call aga functions on @g apart from aga_*_start() and aga_error.
 272  */
 273 void aga_finish(struct aga_graph *g);
 274
 275 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
 276 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
 277                           const void *e);
 278 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
 279                   const void *e, struct aga_edge_info *ei);
 280
 281 #define aga_for_each_edge(_e, _g, _n)                                   \
 282         for ((_e) = aga_first_edge((_g), (_n)); (_e);                   \
 283              (_e) = aga_next_edge((_g), (_n), (_e)))
 284
 285 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n)                   \
 286         for ((_err) = 0, (_e) = aga_first_edge((_g), (_n));             \
 287              (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
 288              (_e) = aga_next_edge((_g), (_n), (_e)))                    \
 289                 if ((_ei).to)
 290
 291 /*
 292  * Depth first search
 293  */
 294
 295 /**
 296  * aga_dfs_start - Start a depth-first search
 297  * @g: graph to search
 298  *
 299  * Begins the depth-first search algorithm on @g
 300  */
 301 int aga_dfs_start(struct aga_graph *g);
 302
 303 /**
 304  * aga_dfs_explore - One step of depth-first search
 305  * @g: graph to search
 306  * @n: node to start exploration from
 307  *
 308  * If @n has not yet been explored since aga_dfs_start(), returns @n.
 309  * Otherwise returns the next node after @n in depth-first search
 310  * order.  Marks the returned node as explored.
 311  */
 312 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
 313
 314 /**
 315  * aga_dfs - Depth-first search
 316  * @_n: pointer to current node (output)
 317  * @_g: graph to search
 318  * @_start: node to start from
 319  *
 320  * Performs a depth first search.  The block following this macro is
 321  * executed with @_n set first to @_start, then to each node reachable
 322  * from @_start in depth first search order.
 323  *
 324  * aga_dfs_start() must be called before this macro is used.
 325  */
 326 #define aga_dfs(_n, _g, _start)                                 \
 327         for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
 328
 329
 330 /*
 331  * Breadth first search
 332  */
 333
 334 /**
 335  * aga_bfs_start - Start a breadth-first search
 336  * @g: graph to search
 337  *
 338  * Begins the breadth-first search algorithm on @g
 339  */
 340 int aga_bfs_start(struct aga_graph *g);
 341
 342 /**
 343  * aga_bfs_explore - One step of breadth-first search
 344  * @g: graph to search
 345  * @n: node to start exploration from
 346  *
 347  * If @n has not yet been explored since aga_bfs_start(), returns @n.
 348  * Otherwise returns the next node after @n in breadth-first search
 349  * order.  Marks the returned node as explored.
 350  */
 351 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
 352
 353 /**
 354  * aga_bfs - Breadth-first search
 355  * @_n: pointer to current node (output)
 356  * @_g: graph to search
 357  * @_start: node to start from
 358  *
 359  * Performs a breadth first search.  The block following this macro is
 360  * executed with @_n set first to @_start, then to each node reachable
 361  * from @_start in breadth-first search order.
 362  *
 363  * aga_bfs_start() must be called before this macro is used.
 364  */
 365 #define aga_bfs(_n, _g, _start)                                 \
 366         for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
 367
 368 /*
 369  * Dijkstra's algorithm
 370  */
 371
 372 /**
 373  * aga_dijkstra_start - Start Dijkstra's algorithm
 374  * @g: graph
 375  * @source: source node
 376  *
 377  * Start's Dijkstra's algorithm on @g to find shortest paths from node
 378  * @source, to other nodes in @g.
 379  */
 380 int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source);
 381
 382
 383 /**
 384  * aga_dijkstra_step - Find the node with the next shortest path
 385  * @g: graph
 386  *
 387  * The first call to this function returns the source node specified
 388  * in aga_dijkstra_start().  Subsequent calls return the next closest
 389  * node to source by shortest path cost.  Returns NULL if no further
 390  * nodes are reachable from source.
 391  */
 392 struct aga_node *aga_dijkstra_step(struct aga_graph *g);
 393
 394 /**
 395  * aga_dijkstra_path - Find the shortest path to a node
 396  * @g: graph
 397  * @dest: destination node
 398  * @prev: Second last node in the path *output)
 399  * @prevedge: Last edge in the path
 400  *
 401  * Finds the shortest path from the source node (specified in
 402  * aga_dijkstra_start() to @dest using Dijkstra's algorithm.
 403  *
 404  * If no path exists, return false.
 405  *
 406  * If a path does exist, returns true.  Additionally if @total_cost is
 407  * non-NULL, store the total cost of the path in *@total_cost, if
 408  * @prev is non-NULL, store the node in the path immediately before
 409  * @dest in *@prev and if @prevedge is non-NULL stores the edge which
 410  * leads from *@prev to @dest in *@prevedge.
 411  *
 412  * If @dest is the same as source, 0 will be stored in @cost, and NULL
 413  * will be stored in *@prev and *@prevedge.
 414  *
 415  * The full path from source to @dest can be determined by repeatedly
 416  * calling aga_dijkstra_path() on *@prev.
 417  *
 418  * NOTE: Dijkstra's algorithm will not work correctly on a graph which
 419  * has negative costs on some edges.  If aga detects this case, it
 420  * will set aga_error() to AGA_ERR_NEGATIVE_COST.  However,
 421  * aga_dijkstra_path() may produce incorrect results without detecting
 422  * this situation.  aga_dijkstra_all_paths() *is* guaranteed to
 423  * discover any negative cost edge reachable from the starting node.
 424  */
 425 bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
 426                        aga_icost_t *total_cost,
 427                        struct aga_node **prev, const void **prevedge);
 428
 429 /**
 430  * aga_dijkstra_complete - Find shortest paths to all reachable nodes
 431  * @g: graph
 432  *
 433  * Finds shortest paths from the source node (specified in
 434  * aga_dijkstra_start()) to all other reachable nodes in @g.  No
 435  * results are returned directly, but between calling
 436  * aga_dijkstra_all_paths() and aga_finish(), aga_dijkstra_path() is
 437  * guaranteed to complete in O(1) time for all destinations.
 438  */
 439 void aga_dijkstra_complete(struct aga_graph *g);
 440
 441 /*
 442  * Bellman-Ford algorithm
 443  */
 444
 445 /**
 446  * aga_bellman_ford_start - Start Bellman-Ford algorithm
 447  * @g: graph
 448  * @source: source node
 449  *
 450  * Start's the Bellman-Ford algorithm on @g to find shortest paths
 451  * from node @source, to other nodes in @g.
 452  */
 453 int aga_bellman_ford_start(struct aga_graph *g, struct aga_node *source);
 454
 455 /**
 456  * aga_bellman_ford_path - Find the shortest path to a node
 457  * @g: graph
 458  * @dest: destination node
 459  * @prev: Second last node in the path *output)
 460  * @prevedge: Last edge in the path
 461  *
 462  * Finds the shortest path from the source node (specified in
 463  * aga_bellman_ford_start() to @dest using Bellman_Ford's algorithm.
 464  *
 465  * If no path exists, return false.
 466  *
 467  * If a path does exist, returns true.  Additionally if @total_cost is
 468  * non-NULL, store the total cost of the path in *@total_cost, if
 469  * @prev is non-NULL, store the node in the path immediately before
 470  * @dest in *@prev and if @prevedge is non-NULL stores the edge which
 471  * leads from *@prev to @dest in *@prevedge.
 472  *
 473  * If @dest is the same as source, 0 will be stored in @cost, and NULL
 474  * will be stored in *@prev and *@prevedge.
 475  *
 476  * The full path from source to @dest can be determined by repeatedly
 477  * calling aga_bellman_ford_path() on *@prev.
 478  *
 479  * NOTE: Bellman_Ford's algorithm will not work correctly on a graph
 480  * which contains a cycle with (total) negative cost.  If aga detects
 481  * this case, it will set aga_error() to AGA_ERR_NEGATIVE_COST.
 482  */
 483 bool aga_bellman_ford_path(struct aga_graph *g, struct aga_node *dest,
 484                            aga_icost_t *total_cost,
 485                            struct aga_node **prev, const void **prevedge);
 486
 487 /**
 488  * aga_bellman_ford_complete - Run Bellman-Ford algorithm to completion
 489  * @g: graph
 490  *
 491  * Finds shortest paths from the source node (specified in
 492  * aga_bellman_ford_start()) to all other reachable nodes in @g.  No
 493  * results are returned directly, but between calling
 494  * aga_bellman_ford_complete() and aga_finish(),
 495  * aga_bellman_ford_path() is guaranteed to complete in O(1) time for
 496  * all destinations.
 497  */
 498 void aga_bellman_ford_complete(struct aga_graph *g);
 499
 500 #endif /* CCAN_AGA_H */