7 #define MAX_EDGES 16 /* Max edges per node */
11 /* We don't use nodes[0] just to avoid awkward -1 and +1 in
13 struct aga_node nodes[MAX_NODES + 1];
16 void simple_graph_init_(struct simple_graph *sg);
17 #define simple_graph_init(sg_, fefn_, nefn_, eifn_) \
19 simple_graph_init_((sg_)); \
20 aga_init_graph(&(sg_)->g, (fefn_), (nefn_), (eifn_)); \
23 struct adjacency_list {
32 * The simplest possible graph: one node, no edges
34 struct trivial_graph {
35 struct simple_graph sg;
37 void trivial_graph_init(struct trivial_graph *tg);
38 static const struct adjacency_list trivial_adjacency[] = {
51 * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
53 struct parallel_graph {
56 struct simple_graph sg;
58 void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink);
59 static const struct adjacency_list parallel_adjacency_nlinks3[] = {
67 * n nodes with an edge from every node to every other node (including
72 struct simple_graph sg;
74 void full_graph_init(struct full_graph *fg, int nnodes);
75 static const struct adjacency_list full_adjacency_5[] = {
83 struct aga_node *full_first_edge(const struct aga_graph *g,
84 const struct aga_node *node);
85 struct aga_node *full_next_edge(const struct aga_graph *g,
86 const struct aga_node *node,
87 struct aga_node *edge);
96 * nnodes nodes arranged in a linear sequence, edges from each node to
97 * the previous and next
100 struct full_graph fg;
102 void chain_graph_init(struct chain_graph *cg, int nnodes);
103 static const struct adjacency_list chain_adjacency_8[] = {
126 * nx * ny nodes arranged in an nx * ny grid. Depending on
127 * parameters, edges to the node to the right / down / left / up of
132 bool right, down, left, up;
133 struct simple_graph sg;
135 void grid_graph_init(struct grid_graph *gg, int nx, int ny,
136 bool right, bool down, bool left, bool up);
137 static const struct adjacency_list grid_adjacency_3x3_rightdown[] = {
149 static const struct adjacency_list grid_adjacency_3x3_all[] = {
168 * This is for testing reporting of errors by the edge_info function.
169 * 5 nodes are arranged as above, with the link from D always
170 * returning an error.
173 struct simple_graph sg;
175 void error_graph_init(struct error_graph *eg);
176 static const struct adjacency_list error_adjacency[] = {
196 * This provides an example of a graph which can't be traversed (with
197 * DFS or BFS) from a single starting node. It can be traversed with
198 * two starting points, but several nodes can be reached from either,
199 * complicating the logic to avoid double-traversal.
201 struct traversal1_graph {
202 struct simple_graph sg;
204 void traversal1_graph_init(struct traversal1_graph *t1g);
205 static const struct adjacency_list traversal1_adjacency[] = {
220 * A ---- (3) -----> C
224 * This provides an example of a graph where the lowest cost path from
225 * (A) to (C) is not the path with the smallest number od edges.
227 struct shortcut1_graph {
228 struct simple_graph sg;
230 void shortcut1_graph_init(struct shortcut1_graph *s1g);
231 static const struct adjacency_list shortcut1_adjacency[] = {
240 * A ---- (2) -----> C
244 * This provides an example of a graph with a negative edge cost, but
245 * no negative cost cycles (and so still with well defined shortest
248 struct shortcut2_graph {
249 struct simple_graph sg;
251 void shortcut2_graph_init(struct shortcut2_graph *s2g);
252 static const struct adjacency_list shortcut2_adjacency[] = {
261 * A <---- (-3) ----- C
265 * Graph with a negative length cycle, and so lacking well-defined shortest paths.
267 struct negacycle_graph {
268 struct simple_graph sg;
270 void negacycle_graph_init(struct negacycle_graph *ng);
271 static const struct adjacency_list negacycle_adjacency[] = {
278 #endif /* _TEST_GRAPHS_H */