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 {
55 struct simple_graph sg;
57 void parallel_graph_init(struct parallel_graph *pg, int nlinks);
58 static const struct adjacency_list parallel_adjacency_nlinks3[] = {
66 * n nodes with an edge from every node to every other node (including
71 struct simple_graph sg;
73 void full_graph_init(struct full_graph *fg, int nnodes);
74 static const struct adjacency_list full_adjacency_5[] = {
82 struct aga_node *full_first_edge(const struct aga_graph *g,
83 const struct aga_node *node);
84 struct aga_node *full_next_edge(const struct aga_graph *g,
85 const struct aga_node *node,
86 struct aga_node *edge);
95 * nnodes nodes arranged in a linear sequence, edges from each node to
96 * the previous and next
101 void chain_graph_init(struct chain_graph *cg, int nnodes);
102 static const struct adjacency_list chain_adjacency_8[] = {
125 * nx * ny nodes arranged in an nx * ny grid. Depending on
126 * parameters, edges to the node to the right / down / left / up of
131 bool right, down, left, up;
132 struct simple_graph sg;
134 void grid_graph_init(struct grid_graph *gg, int nx, int ny,
135 bool right, bool down, bool left, bool up);
136 static const struct adjacency_list grid_adjacency_3x3_rightdown[] = {
148 static const struct adjacency_list grid_adjacency_3x3_all[] = {
167 * This is for testing reporting of errors by the edge_info function.
168 * 5 nodes are arranged as above, with the link from D always
169 * returning an error.
172 struct simple_graph sg;
174 void error_graph_init(struct error_graph *eg);
175 static const struct adjacency_list error_adjacency[] = {
195 * This provides an example of a graph which can't be traversed (with
196 * DFS or BFS) from a single starting node. It can be traversed with
197 * two starting points, but several nodes can be reached from either,
198 * complicating the logic to avoid double-traversal.
200 struct traversal1_graph {
201 struct simple_graph sg;
203 void traversal1_graph_init(struct traversal1_graph *t1g);
204 static const struct adjacency_list traversal1_adjacency[] = {
217 #endif /* _TEST_GRAPHS_H */