1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
#ifndef _TEST_GRAPHS_H
#define _TEST_GRAPHS_H
#include <stdbool.h>
#define MAX_NODES 16
#define MAX_EDGES 16 /* Max edges per node */
struct simple_graph {
struct aga_graph g;
/* We don't use nodes[0] just to avoid awkward -1 and +1 in
* the code */
struct aga_node nodes[MAX_NODES + 1];
};
void simple_graph_init_(struct simple_graph *sg);
#define simple_graph_init(sg_, fefn_, nefn_, eifn_) \
do { \
simple_graph_init_((sg_)); \
aga_init_graph(&(sg_)->g, (fefn_), (nefn_), (eifn_)); \
} while (0)
struct adjacency_list {
int from;
int to[MAX_EDGES];
};
/* Trivial graph
*
* (A)
*
* The simplest possible graph: one node, no edges
*/
struct trivial_graph {
struct simple_graph sg;
};
void trivial_graph_init(struct trivial_graph *tg);
static const struct adjacency_list trivial_adjacency[] = {
{1, {}},
{},
};
/* Parallel graph
*
* --
* / \
* (A) => (B)
* \ /
* --
*
* Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
*/
struct parallel_graph {
int nlinks;
struct simple_graph sg;
};
void parallel_graph_init(struct parallel_graph *pg, int nlinks);
static const struct adjacency_list parallel_adjacency_nlinks3[] = {
{1, {2, 2, 2}},
{2, {}},
{},
};
/* Full graph
*
* n nodes with an edge from every node to every other node (including
* itself)
*/
struct full_graph {
int nnodes;
struct simple_graph sg;
};
void full_graph_init(struct full_graph *fg, int nnodes);
static const struct adjacency_list full_adjacency_5[] = {
{1, {1, 2, 3, 4, 5}},
{2, {1, 2, 3, 4, 5}},
{3, {1, 2, 3, 4, 5}},
{4, {1, 2, 3, 4, 5}},
{5, {1, 2, 3, 4, 5}},
{},
};
struct aga_node *full_first_edge(const struct aga_graph *g,
const struct aga_node *node);
struct aga_node *full_next_edge(const struct aga_graph *g,
const struct aga_node *node,
struct aga_node *edge);
/* Chain graph
*
* --> --> -->
* A B C D
* <-- <-- <--
*
* nnodes nodes arranged in a linear sequence, edges from each node to
* the previous and next
*/
struct chain_graph {
struct full_graph fg;
};
void chain_graph_init(struct chain_graph *cg, int nnodes);
static const struct adjacency_list chain_adjacency_8[] = {
{1, {2}},
{2, {1, 3}},
{3, {2, 4}},
{4, {3, 5}},
{5, {4, 6}},
{6, {5, 7}},
{7, {6, 8}},
{8, {7}},
{},
};
/* Grid graph(s)
*
* A -> B -> C
* | | |
* v v v
* D -> E -> F
* | | |
* v v v
* G -> H -> I
*
* nx * ny nodes arranged in an nx * ny grid. Depending on
* parameters, edges to the node to the right / down / left / up of
* each node
*/
struct grid_graph {
int nx, ny;
bool right, down, left, up;
struct simple_graph sg;
};
void grid_graph_init(struct grid_graph *gg, int nx, int ny,
bool right, bool down, bool left, bool up);
static const struct adjacency_list grid_adjacency_3x3_rightdown[] = {
{1, {2, 4}},
{2, {3, 5}},
{3, {6}},
{4, {5, 7}},
{5, {6, 8}},
{6, {9}},
{7, {8}},
{8, {9}},
{9, {}},
{},
};
static const struct adjacency_list grid_adjacency_3x3_all[] = {
{1, {2, 4}},
{2, {3, 5, 1}},
{3, {6, 2}},
{4, {5, 7, 1}},
{5, {6, 8, 4, 2}},
{6, {9, 5, 3}},
{7, {8, 4}},
{8, {9, 7, 5}},
{9, {8, 6}},
{},
};
/* Error graph
*
* A -> B
*
* C -> D -> ???
*
* This is for testing reporting of errors by the edge_info function.
* 5 nodes are arranged as above, with the link from D always
* returning an error.
*/
struct error_graph {
struct simple_graph sg;
};
void error_graph_init(struct error_graph *eg);
static const struct adjacency_list error_adjacency[] = {
{1, {2}},
{2, {}},
{3, {4}},
{4, {-1}},
{},
};
/* Traversal-1 graph
*
* -> D <-
* / \
* -> B G <-
* / \ / \
* A => E <= I
* \ / \ /
* -> C H <-
* \ /
* -> F <-
*
* This provides an example of a graph which can't be traversed (with
* DFS or BFS) from a single starting node. It can be traversed with
* two starting points, but several nodes can be reached from either,
* complicating the logic to avoid double-traversal.
*/
struct traversal1_graph {
struct simple_graph sg;
};
void traversal1_graph_init(struct traversal1_graph *t1g);
static const struct adjacency_list traversal1_adjacency[] = {
{1, {2, 3}},
{2, {4, 5}},
{3, {5, 6}},
{4, {}},
{5, {}},
{6, {}},
{7, {5, 4}},
{8, {6, 5}},
{9, {8, 7}},
{},
};
#endif /* _TEST_GRAPHS_H */
|
