7 #include <ccan/tap/tap.h>
8 #include <ccan/array_size/array_size.h>
10 #include <ccan/aga/aga.h>
12 #include "simple-graph.h"
14 static void test_trivial(void)
16 struct trivial_graph tg;
18 struct aga_node *node;
21 trivial_graph_init(&tg);
23 ok1(aga_dijkstra_start(&tg.sg.g, &tg.sg.nodes[1]) == 0);
24 ok1(aga_dijkstra_step(&tg.sg.g) == &tg.sg.nodes[1]);
25 ok1(aga_dijkstra_step(&tg.sg.g) == NULL);
26 ok1(aga_dijkstra_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge));
33 static void test_parallel(void)
35 struct parallel_graph pg;
37 struct aga_node *node;
40 parallel_graph_init(&pg, 3, 0);
42 ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
43 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
44 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
45 ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
46 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
48 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
50 ok1(node == &pg.sg.nodes[1]);
53 ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
54 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
55 ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
56 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
58 ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
62 parallel_graph_init(&pg, 3, 2);
63 ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
64 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
66 ok1(node == &pg.sg.nodes[1]);
67 ok1(ptr2int(edge) == 2);
73 static void test_full(void)
78 full_graph_init(&fg, FULL_LEN);
80 for (i = 1; i <= FULL_LEN; i++) {
81 ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
83 for (j = 1; j <= FULL_LEN; j++) {
85 struct aga_node *node;
88 ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j],
89 &cost, &node, &edge));
96 ok1(node == &fg.sg.nodes[i]);
97 ok1(edge == &fg.sg.nodes[j]);
101 aga_finish(&fg.sg.g);
107 static void test_chain(void)
109 struct chain_graph cg;
112 chain_graph_init(&cg, CHAIN_LEN);
114 for (i = 1; i <= CHAIN_LEN; i++) {
115 ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
117 for (j = 1; j <= CHAIN_LEN; j++) {
120 ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
122 ok1(cost == labs(i - j));
125 aga_finish(&cg.fg.sg.g);
129 static void test_error(void)
131 struct error_graph eg;
134 error_graph_init(&eg);
136 ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
137 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
139 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
141 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
142 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
143 aga_finish(&eg.sg.g);
145 ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
146 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
148 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
149 ok1(aga_error(&eg.sg.g) == -1);
150 aga_finish(&eg.sg.g);
153 static void test_traversal1(void)
155 struct traversal1_graph t1g;
158 /* This is mostly about testing we correctly handle
159 * non-reachable nodes */
160 traversal1_graph_init(&t1g);
162 ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
163 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
166 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
169 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
172 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
175 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
178 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
181 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
183 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
185 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
187 aga_finish(&t1g.sg.g);
189 ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
190 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
193 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
196 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
199 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
202 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
205 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
208 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
210 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
212 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
214 aga_finish(&t1g.sg.g);
217 static void test_shortcut1(void)
219 struct shortcut1_graph s1g;
221 struct aga_node *node;
223 shortcut1_graph_init(&s1g);
225 ok1(aga_dijkstra_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
226 ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[3],
227 &cost, &node, NULL));
229 ok1(node == &s1g.sg.nodes[2]);
230 ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[2],
231 &cost, &node, NULL));
233 ok1(node == &s1g.sg.nodes[1]);
234 aga_finish(&s1g.sg.g);
237 static void test_shortcut2(void)
239 struct shortcut2_graph s2g;
241 shortcut2_graph_init(&s2g);
243 ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
244 aga_dijkstra_complete(&s2g.sg.g);
245 ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
246 aga_finish(&s2g.sg.g);
249 static void test_negacycle(void)
251 struct negacycle_graph ng;
253 negacycle_graph_init(&ng);
255 ok1(aga_dijkstra_start(&ng.sg.g, &ng.sg.nodes[1]) == 0);
256 aga_dijkstra_complete(&ng.sg.g);
257 ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST);
258 aga_finish(&ng.sg.g);
264 + FULL_LEN * (1 + FULL_LEN*4)
265 + CHAIN_LEN * (1 + CHAIN_LEN*2)
266 + 12 + 32 + 7 + 2 + 2);
278 return exit_status();