aga,agar: Dijkstra's algorithm
[ccan] / 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 void agar_init_graph(struct agar_graph *gr,
35                      agar_first_edge_fn first_edge,
36                      agar_next_edge_fn next_edge,
37                      agar_edge_info_fn edge_info);
38 int agar_error(struct agar_state *sr);
39
40 const void *agar_first_edge(const struct agar_graph *g, const void *nr);
41 const void *agar_next_edge(const struct agar_graph *g, const void *nr,
42                            const void *e);
43 int agar_edge_info(const struct agar_graph *g, const void *nr, const void *e,
44                    struct agar_edge_info *eir);
45
46 #define agar_for_each_edge(_e, _gr, _nr)                                \
47         for ((_e) = agar_first_edge((_gr), (_nr)); (_e);                \
48              (_e) = aga_next_edge((_gr), (_nr), (_e)))
49
50 #define agar_for_each_edge_info(_e, _eir, _err, _gr, _nr)               \
51         for ((_e) = agar_first_edge((_gr), (_nr));                      \
52              (_e) && ((((_err) = agar_edge_info((_gr), (_nr), (_e), &(_eir)))) == 0); \
53              (_e) = agar_next_edge((_gr), (_nr), (_e)))                 \
54                 if ((_eir).to)
55
56 /*
57  * Depth first search
58  */
59 struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr);
60 bool agar_dfs_explore(struct agar_state *sr, const void *nr,
61                       const void **nextr);
62 #define agar_dfs(_nr, _sr, _startr)                                     \
63         for ((_nr) = (_startr); agar_dfs_explore((_sr), (_nr), &(_nr)); )
64
65 /*
66  * Breadth first search
67  */
68 struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr);
69 bool agar_bfs_explore(struct agar_state *sr, const void *nr,
70                       const void **nextr);
71 #define agar_bfs(_nr, _sr, _startr)                                     \
72         for ((_nr) = (_startr); agar_bfs_explore((_sr), (_nr), &(_nr)); )
73
74 /*
75  * Dijkstra's algorithm
76  */
77
78 struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
79                                      const void *nr);
80 bool agar_dijkstra_step(struct agar_state *sr, const void **nextr);
81 bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
82                         aga_icost_t *total_cost,
83                         const void **prevr, const void **prevedge);
84 void agar_dijkstra_all_paths(struct agar_state *sr);
85
86 #endif /* CCAN_AGAR_H */