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 void trivial_graphr_init(struct trivial_graphr *tgr);
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 void error_graphr_init(struct error_graphr *eg);
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 void traversal1_graphr_init(struct traversal1_graphr *t1gr);
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 void shortcut1_graphr_init(struct shortcut1_graphr *s1gr);
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 void shortcut2_graphr_init(struct shortcut2_graphr *s2gr);
236 static const struct adjacency_listr shortcut2_adjacencyr[] = {
243 #endif /* _SIMPLE_GRAPHR_H */