git.ozlabs.org Git - ccan/blob - ccan/agar/agar.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_AGAR_H
   3 #define CCAN_AGAR_H
   4 #include "config.h"
   5 #include <string.h>
   6 #include <stdbool.h>
   7
   8 #include <ccan/aga/aga.h>
   9
  10 struct agar_edge_info {
  11         const void *to;
  12         aga_icost_t icost; /* integer edge cost */
  13 };
  14
  15 struct agar_graph;
  16 struct agar_state;
  17
  18 typedef int (*agar_edge_info_fn)(const struct agar_graph *gr,
  19                                  const void *nr,
  20                                  const void *e,
  21                                  struct agar_edge_info *ei);
  22 typedef const void *(*agar_first_edge_fn)(const struct agar_graph *gr,
  23                                           const void *nr);
  24 typedef const void *(*agar_next_edge_fn)(const struct agar_graph *gr,
  25                                          const void *nr,
  26                                          const void *e);
  27
  28 struct agar_graph {
  29         agar_edge_info_fn edge_info;
  30         agar_first_edge_fn first_edge;
  31         agar_next_edge_fn next_edge;
  32 };
  33
  34 #define AGAR_INIT_GRAPH(fe, ne, ei) \
  35         { (ei), (fe), (ne), }
  36
  37 void agar_init_graph(struct agar_graph *gr,
  38                      agar_first_edge_fn first_edge,
  39                      agar_next_edge_fn next_edge,
  40                      agar_edge_info_fn edge_info);
  41 int agar_error(struct agar_state *sr);
  42
  43 const void *agar_first_edge(const struct agar_graph *g, const void *nr);
  44 const void *agar_next_edge(const struct agar_graph *g, const void *nr,
  45                            const void *e);
  46 int agar_edge_info(const struct agar_graph *g, const void *nr, const void *e,
  47                    struct agar_edge_info *eir);
  48
  49 #define agar_for_each_edge(_e, _gr, _nr)                                \
  50         for ((_e) = agar_first_edge((_gr), (_nr)); (_e);                \
  51              (_e) = aga_next_edge((_gr), (_nr), (_e)))
  52
  53 #define agar_for_each_edge_info(_e, _eir, _err, _gr, _nr)               \
  54         for ((_e) = agar_first_edge((_gr), (_nr));                      \
  55              (_e) && ((((_err) = agar_edge_info((_gr), (_nr), (_e), &(_eir)))) == 0); \
  56              (_e) = agar_next_edge((_gr), (_nr), (_e)))                 \
  57                 if ((_eir).to)
  58
  59 /*
  60  * Depth first search
  61  */
  62 struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr);
  63 bool agar_dfs_explore(struct agar_state *sr, const void *nr,
  64                       const void **nextr);
  65 #define agar_dfs(_nr, _sr, _startr)                                     \
  66         for ((_nr) = (_startr); agar_dfs_explore((_sr), (_nr), &(_nr)); )
  67
  68 /*
  69  * Breadth first search
  70  */
  71 struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr);
  72 bool agar_bfs_explore(struct agar_state *sr, const void *nr,
  73                       const void **nextr);
  74 #define agar_bfs(_nr, _sr, _startr)                                     \
  75         for ((_nr) = (_startr); agar_bfs_explore((_sr), (_nr), &(_nr)); )
  76
  77 /*
  78  * Dijkstra's algorithm
  79  */
  80
  81 struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
  82                                      const void *nr);
  83 bool agar_dijkstra_step(struct agar_state *sr, const void **nextr);
  84 bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
  85                         aga_icost_t *total_cost,
  86                         const void **prevr, const void **prevedge);
  87 void agar_dijkstra_all_paths(struct agar_state *sr);
  88
  89 #endif /* CCAN_AGAR_H */