7 #include <ccan/tap/tap.h>
8 #include <ccan/tal/tal.h>
9 #include <ccan/array_size/array_size.h>
11 #include <ccan/agar/agar.h>
13 #include "simple-graphr.h"
15 static void test_trivial(void)
17 struct agar_state *sr;
21 ok1(sr = agar_dijkstra_new(NULL, &trivial_graphr.gr, int2ptr(1)));
22 ok1(agar_dijkstra_step(sr, &node));
23 ok1(ptr2int(node) == 1);
24 ok1(!agar_dijkstra_step(sr, &node));
25 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
30 static void test_parallel(void)
32 struct parallel_graphr pgr;
33 struct agar_state *sr;
35 const void *node, *edge;
37 parallel_graphr_init(&pgr, 3, 0);
39 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
40 ok1(agar_dijkstra_step(sr, &node));
41 ok1(ptr2int(node) == 1);
42 ok1(agar_dijkstra_step(sr, &node));
43 ok1(ptr2int(node) == 2);
44 ok1(!agar_dijkstra_step(sr, &node));
45 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
47 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
49 ok1(node == int2ptr(1));
52 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(2)));
53 ok1(agar_dijkstra_step(sr, &node));
54 ok1(ptr2int(node) == 2);
55 ok1(!agar_dijkstra_step(sr, &node));
56 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
58 ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
61 parallel_graphr_init(&pgr, 3, 2);
62 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
63 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
65 ok1(ptr2int(node) == 1);
66 ok1(ptr2int(edge) == 2);
72 static void test_full(void)
74 struct full_graphr fgr;
77 full_graphr_init(&fgr, FULL_LEN);
79 for (i = 1; i <= FULL_LEN; i++) {
80 struct agar_state *sr;
82 ok1(sr = agar_dijkstra_new(NULL, &fgr.gr, int2ptr(i)));
84 for (j = 1; j <= FULL_LEN; j++) {
86 const void *node, *edge;
88 ok1(agar_dijkstra_path(sr, int2ptr(j),
89 &cost, &node, &edge));
94 ok1(node == int2ptr(i));
95 ok1(edge == int2ptr(j));
105 static void test_chain(void)
107 struct chain_graphr cgr;
110 chain_graphr_init(&cgr, CHAIN_LEN);
112 for (i = 1; i <= CHAIN_LEN; i++) {
113 struct agar_state *sr;
115 ok1(sr = agar_dijkstra_new(NULL, &cgr.fgr.gr, int2ptr(i)));
117 for (j = 1; j <= CHAIN_LEN; j++) {
120 ok1(agar_dijkstra_path(sr, int2ptr(j),
122 ok1(cost == labs(i - j));
129 static void test_error(void)
131 struct agar_state *sr;
134 ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(1)));
135 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
137 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
139 ok1(!agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
140 ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
143 ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(3)));
144 ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
146 ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
147 ok1(agar_error(sr) == -1);
151 static void test_traversal1(void)
153 struct agar_state *sr;
156 /* This is mostly about testing we correctly handle
157 * non-reachable nodes */
158 ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(1)));
159 ok1(agar_dijkstra_path(sr, int2ptr(1),
162 ok1(agar_dijkstra_path(sr, int2ptr(2),
165 ok1(agar_dijkstra_path(sr, int2ptr(3),
168 ok1(agar_dijkstra_path(sr, int2ptr(4),
171 ok1(agar_dijkstra_path(sr, int2ptr(5),
174 ok1(agar_dijkstra_path(sr, int2ptr(6),
177 ok1(!agar_dijkstra_path(sr, int2ptr(7),
179 ok1(!agar_dijkstra_path(sr, int2ptr(8),
181 ok1(!agar_dijkstra_path(sr, int2ptr(9),
185 ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(9)));
186 ok1(agar_dijkstra_path(sr, int2ptr(9),
189 ok1(agar_dijkstra_path(sr, int2ptr(8),
192 ok1(agar_dijkstra_path(sr, int2ptr(7),
195 ok1(agar_dijkstra_path(sr, int2ptr(6),
198 ok1(agar_dijkstra_path(sr, int2ptr(5),
201 ok1(agar_dijkstra_path(sr, int2ptr(4),
204 ok1(!agar_dijkstra_path(sr, int2ptr(3),
206 ok1(!agar_dijkstra_path(sr, int2ptr(2),
208 ok1(!agar_dijkstra_path(sr, int2ptr(1),
213 static void test_shortcut1(void)
215 struct agar_state *sr;
219 ok1(sr = agar_dijkstra_new(NULL, &shortcut1_graphr.gr, int2ptr(1)));
220 ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
222 ok1(node == int2ptr(2));
223 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
225 ok1(node == int2ptr(1));
229 static void test_shortcut2(void)
231 struct agar_state *sr;
233 ok1(sr = agar_dijkstra_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
234 agar_dijkstra_complete(sr);
235 ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
239 static void test_negacycle(void)
241 struct agar_state *sr;
243 ok1(sr = agar_dijkstra_new(NULL, &negacycle_graphr.gr, int2ptr(1)));
244 agar_dijkstra_complete(sr);
245 ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
252 + FULL_LEN * (FULL_LEN*4 - 1)
253 + CHAIN_LEN * (1 + CHAIN_LEN*2)
254 + 12 + 32 + 7 + 2 + 2);
266 return exit_status();