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 trivial_graphr tgr;
18 struct agar_state *sr;
22 trivial_graphr_init(&tgr);
24 ok1(sr = agar_dijkstra_new(NULL, &tgr.gr, int2ptr(1)));
25 ok1(agar_dijkstra_step(sr, &node));
26 ok1(ptr2int(node) == 1);
27 ok1(!agar_dijkstra_step(sr, &node));
28 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
33 static void test_parallel(void)
35 struct parallel_graphr pgr;
36 struct agar_state *sr;
38 const void *node, *edge;
40 parallel_graphr_init(&pgr, 3, 0);
42 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
43 ok1(agar_dijkstra_step(sr, &node));
44 ok1(ptr2int(node) == 1);
45 ok1(agar_dijkstra_step(sr, &node));
46 ok1(ptr2int(node) == 2);
47 ok1(!agar_dijkstra_step(sr, &node));
48 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
50 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
52 ok1(node == int2ptr(1));
55 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(2)));
56 ok1(agar_dijkstra_step(sr, &node));
57 ok1(ptr2int(node) == 2);
58 ok1(!agar_dijkstra_step(sr, &node));
59 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
61 ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
64 parallel_graphr_init(&pgr, 3, 2);
65 ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
66 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
68 ok1(ptr2int(node) == 1);
69 ok1(ptr2int(edge) == 2);
75 static void test_full(void)
77 struct full_graphr fgr;
80 full_graphr_init(&fgr, FULL_LEN);
82 for (i = 1; i <= FULL_LEN; i++) {
83 struct agar_state *sr;
85 ok1(sr = agar_dijkstra_new(NULL, &fgr.gr, int2ptr(i)));
87 for (j = 1; j <= FULL_LEN; j++) {
89 const void *node, *edge;
91 ok1(agar_dijkstra_path(sr, int2ptr(j),
92 &cost, &node, &edge));
97 ok1(node == int2ptr(i));
98 ok1(edge == int2ptr(j));
108 static void test_chain(void)
110 struct chain_graphr cgr;
113 chain_graphr_init(&cgr, CHAIN_LEN);
115 for (i = 1; i <= CHAIN_LEN; i++) {
116 struct agar_state *sr;
118 ok1(sr = agar_dijkstra_new(NULL, &cgr.fgr.gr, int2ptr(i)));
120 for (j = 1; j <= CHAIN_LEN; j++) {
123 ok1(agar_dijkstra_path(sr, int2ptr(j),
125 ok1(cost == labs(i - j));
132 static void test_error(void)
134 struct error_graphr egr;
135 struct agar_state *sr;
138 error_graphr_init(&egr);
140 ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(1)));
141 ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
143 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
145 ok1(!agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
146 ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
149 ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(3)));
150 ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
152 ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
153 ok1(agar_error(sr) == -1);
157 static void test_traversal1(void)
159 struct traversal1_graphr t1gr;
160 struct agar_state *sr;
163 /* This is mostly about testing we correctly handle
164 * non-reachable nodes */
165 traversal1_graphr_init(&t1gr);
167 ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(1)));
168 ok1(agar_dijkstra_path(sr, int2ptr(1),
171 ok1(agar_dijkstra_path(sr, int2ptr(2),
174 ok1(agar_dijkstra_path(sr, int2ptr(3),
177 ok1(agar_dijkstra_path(sr, int2ptr(4),
180 ok1(agar_dijkstra_path(sr, int2ptr(5),
183 ok1(agar_dijkstra_path(sr, int2ptr(6),
186 ok1(!agar_dijkstra_path(sr, int2ptr(7),
188 ok1(!agar_dijkstra_path(sr, int2ptr(8),
190 ok1(!agar_dijkstra_path(sr, int2ptr(9),
194 ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(9)));
195 ok1(agar_dijkstra_path(sr, int2ptr(9),
198 ok1(agar_dijkstra_path(sr, int2ptr(8),
201 ok1(agar_dijkstra_path(sr, int2ptr(7),
204 ok1(agar_dijkstra_path(sr, int2ptr(6),
207 ok1(agar_dijkstra_path(sr, int2ptr(5),
210 ok1(agar_dijkstra_path(sr, int2ptr(4),
213 ok1(!agar_dijkstra_path(sr, int2ptr(3),
215 ok1(!agar_dijkstra_path(sr, int2ptr(2),
217 ok1(!agar_dijkstra_path(sr, int2ptr(1),
222 static void test_shortcut1(void)
224 struct shortcut1_graphr s1gr;
225 struct agar_state *sr;
229 shortcut1_graphr_init(&s1gr);
231 ok1(sr = agar_dijkstra_new(NULL, &s1gr.gr, int2ptr(1)));
232 ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
234 ok1(node == int2ptr(2));
235 ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
237 ok1(node == int2ptr(1));
244 + FULL_LEN * (FULL_LEN*4 - 1)
245 + CHAIN_LEN * (1 + CHAIN_LEN*2)
256 return exit_status();