1 #ifndef _SIMPLE_GRAPHR_H
2 #define _SIMPLE_GRAPHR_H
6 #define MAX_EDGES 16 /* Max edges per node */
8 struct adjacency_listr {
17 * The simplest possible graph: one node, no edges
19 struct trivial_graphr {
22 extern struct trivial_graphr trivial_graphr;
23 static const struct adjacency_listr trivial_adjacencyr[] = {
36 * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
38 struct parallel_graphr {
43 void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
45 static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
53 * n nodes with an edge from every node to every other node (including
60 void full_graphr_init(struct full_graphr *fgr, int nnodes);
61 static const struct adjacency_listr full_adjacencyr_5[] = {
69 const void *full_first_edge_r(const struct agar_graph *gr, const void *nr);
70 const void *full_next_edge_r(const struct agar_graph *gr,
71 const void *nr, const void *e);
80 * nnodes nodes arranged in a linear sequence, edges from each node to
81 * the previous and next
84 struct full_graphr fgr;
86 void chain_graphr_init(struct chain_graphr *cgr, int nnodes);
87 static const struct adjacency_listr chain_adjacencyr_8[] = {
110 * nx * ny nodes arranged in an nx * ny grid. Depending on
111 * parameters, edges to the node to the right / down / left / up of
116 bool right, down, left, up;
117 struct agar_graph gr;
119 void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny,
120 bool right, bool down, bool left, bool up);
121 static const struct adjacency_listr grid_adjacencyr_3x3_rightdown[] = {
133 static const struct adjacency_listr grid_adjacencyr_3x3_all[] = {
152 * This is for testing reporting of errors by the edge_info function.
153 * 5 nodes are arranged as above, with the link from D always
154 * returning an error.
156 struct error_graphr {
157 struct agar_graph gr;
159 extern struct error_graphr error_graphr;
160 static const struct adjacency_listr error_adjacencyr[] = {
180 * This provides an example of a graph which can't be traversed (with
181 * DFS or BFS) from a single starting node. It can be traversed with
182 * two starting points, but several nodes can be reached from either,
183 * complicating the logic to avoid double-traversal.
185 struct traversal1_graphr {
186 struct agar_graph gr;
188 extern struct traversal1_graphr traversal1_graphr;
189 static const struct adjacency_listr traversal1_adjacency[] = {
204 * A ---- (3) -----> C
208 * This provides an example of a graph where the lowest cost path from
209 * (A) to (C) is not the path with the smallest number od edges.
211 struct shortcut1_graphr {
212 struct agar_graph gr;
214 extern struct shortcut1_graphr shortcut1_graphr;
215 static const struct adjacency_listr shortcut1_adjacencyr[] = {
224 * A ---- (2) -----> C
228 * This provides an example of a graph with a negative edge cost, but
229 * no negative cost cycles (and so still with well defined shortest
232 struct shortcut2_graphr {
233 struct agar_graph gr;
235 extern struct shortcut2_graphr shortcut2_graphr;
236 static const struct adjacency_listr shortcut2_adjacencyr[] = {
243 #endif /* _SIMPLE_GRAPHR_H */