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
|
#ifndef _SIMPLE_GRAPHR_H
#define _SIMPLE_GRAPHR_H
#include <stdbool.h>
#define MAX_EDGES 16 /* Max edges per node */
struct adjacency_listr {
int from;
int to[MAX_EDGES];
};
/* Trivial graph
*
* (A)
*
* The simplest possible graph: one node, no edges
*/
struct trivial_graphr {
struct agar_graph gr;
};
void trivial_graphr_init(struct trivial_graphr *tgr);
static const struct adjacency_listr trivial_adjacencyr[] = {
{1, {}},
{},
};
/* Parallel graph
*
* --
* / \
* (A) => (B)
* \ /
* --
*
* Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
*/
struct parallel_graphr {
int nlinks;
struct agar_graph gr;
};
void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
{1, {2, 2, 2}},
{2, {}},
{},
};
/* Full graph
*
* n nodes with an edge from every node to every other node (including
* itself)
*/
struct full_graphr {
int nnodes;
struct agar_graph gr;
};
void full_graphr_init(struct full_graphr *fgr, int nnodes);
static const struct adjacency_listr full_adjacencyr_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}},
{},
};
const void *full_first_edge_r(const struct agar_graph *gr, const void *nr);
const void *full_next_edge_r(const struct agar_graph *gr,
const void *nr, const void *e);
/* Chain graph
*
* --> --> -->
* A B C D
* <-- <-- <--
*
* nnodes nodes arranged in a linear sequence, edges from each node to
* the previous and next
*/
struct chain_graphr {
struct full_graphr fgr;
};
void chain_graphr_init(struct chain_graphr *cgr, int nnodes);
static const struct adjacency_listr chain_adjacencyr_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_graphr {
int nx, ny;
bool right, down, left, up;
struct agar_graph gr;
};
void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny,
bool right, bool down, bool left, bool up);
static const struct adjacency_listr grid_adjacencyr_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_listr grid_adjacencyr_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_graphr {
struct agar_graph gr;
};
void error_graphr_init(struct error_graphr *eg);
static const struct adjacency_listr error_adjacencyr[] = {
{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_graphr {
struct agar_graph gr;
};
void traversal1_graphr_init(struct traversal1_graphr *t1gr);
static const struct adjacency_listr traversal1_adjacency[] = {
{1, {2, 3}},
{2, {4, 5}},
{3, {5, 6}},
{4, {}},
{5, {}},
{6, {}},
{7, {5, 4}},
{8, {6, 5}},
{9, {8, 7}},
{},
};
#endif /* _SIMPLE_GRAPHR_H */
|
