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;
20 ok1(sr = agar_bellman_ford_new(NULL, &trivial_graphr.gr, int2ptr(1)));
21 ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
26 static void test_parallel(void)
28 struct parallel_graphr pgr;
29 struct agar_state *sr;
31 const void *node, *edge;
33 parallel_graphr_init(&pgr, 3, 0);
35 ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1)));
36 ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
38 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
40 ok1(node == int2ptr(1));
43 ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(2)));
44 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL));
46 ok1(!agar_bellman_ford_path(sr, int2ptr(1), NULL, NULL, NULL));
49 parallel_graphr_init(&pgr, 3, 2);
50 ok1(sr = agar_bellman_ford_new(NULL, &pgr.gr, int2ptr(1)));
51 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, &edge));
53 ok1(ptr2int(node) == 1);
54 ok1(ptr2int(edge) == 2);
60 static void test_full(void)
62 struct full_graphr fgr;
65 full_graphr_init(&fgr, FULL_LEN);
67 for (i = 1; i <= FULL_LEN; i++) {
68 struct agar_state *sr;
70 ok1(sr = agar_bellman_ford_new(NULL, &fgr.gr, int2ptr(i)));
72 for (j = 1; j <= FULL_LEN; j++) {
74 const void *node, *edge;
76 ok1(agar_bellman_ford_path(sr, int2ptr(j),
77 &cost, &node, &edge));
82 ok1(node == int2ptr(i));
83 ok1(edge == int2ptr(j));
93 static void test_chain(void)
95 struct chain_graphr cgr;
98 chain_graphr_init(&cgr, CHAIN_LEN);
100 for (i = 1; i <= CHAIN_LEN; i++) {
101 struct agar_state *sr;
103 ok1(sr = agar_bellman_ford_new(NULL, &cgr.fgr.gr, int2ptr(i)));
105 for (j = 1; j <= CHAIN_LEN; j++) {
108 ok1(agar_bellman_ford_path(sr, int2ptr(j),
110 ok1(cost == labs(i - j));
117 static void test_error(void)
119 struct agar_state *sr;
122 ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(1)));
123 ok1(agar_bellman_ford_path(sr, int2ptr(1), &cost, NULL, NULL));
125 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, NULL, NULL));
127 ok1(!agar_bellman_ford_path(sr, int2ptr(3), &cost, NULL, NULL));
128 ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL));
131 ok1(sr = agar_bellman_ford_new(NULL, &error_graphr.gr, int2ptr(3)));
132 agar_bellman_ford_complete(sr);
133 ok1(!agar_bellman_ford_path(sr, int2ptr(4), &cost, NULL, NULL));
134 ok1(agar_error(sr) == -1);
138 static void test_traversal1(void)
140 struct agar_state *sr;
143 /* This is mostly about testing we correctly handle
144 * non-reachable nodes */
145 ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(1)));
146 ok1(agar_bellman_ford_path(sr, int2ptr(1),
149 ok1(agar_bellman_ford_path(sr, int2ptr(2),
152 ok1(agar_bellman_ford_path(sr, int2ptr(3),
155 ok1(agar_bellman_ford_path(sr, int2ptr(4),
158 ok1(agar_bellman_ford_path(sr, int2ptr(5),
161 ok1(agar_bellman_ford_path(sr, int2ptr(6),
164 ok1(!agar_bellman_ford_path(sr, int2ptr(7),
166 ok1(!agar_bellman_ford_path(sr, int2ptr(8),
168 ok1(!agar_bellman_ford_path(sr, int2ptr(9),
172 ok1(sr = agar_bellman_ford_new(NULL, &traversal1_graphr.gr, int2ptr(9)));
173 ok1(agar_bellman_ford_path(sr, int2ptr(9),
176 ok1(agar_bellman_ford_path(sr, int2ptr(8),
179 ok1(agar_bellman_ford_path(sr, int2ptr(7),
182 ok1(agar_bellman_ford_path(sr, int2ptr(6),
185 ok1(agar_bellman_ford_path(sr, int2ptr(5),
188 ok1(agar_bellman_ford_path(sr, int2ptr(4),
191 ok1(!agar_bellman_ford_path(sr, int2ptr(3),
193 ok1(!agar_bellman_ford_path(sr, int2ptr(2),
195 ok1(!agar_bellman_ford_path(sr, int2ptr(1),
200 static void test_shortcut1(void)
202 struct agar_state *sr;
206 ok1(sr = agar_bellman_ford_new(NULL, &shortcut1_graphr.gr, int2ptr(1)));
207 ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL));
209 ok1(node == int2ptr(2));
210 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
212 ok1(node == int2ptr(1));
216 static void test_shortcut2(void)
218 struct agar_state *sr;
222 ok1(sr = agar_bellman_ford_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
223 ok1(agar_bellman_ford_path(sr, int2ptr(3), &cost, &node, NULL));
225 ok1(node == int2ptr(2));
226 ok1(agar_bellman_ford_path(sr, int2ptr(2), &cost, &node, NULL));
228 ok1(node == int2ptr(1));
232 static void test_negacycle(void)
234 struct agar_state *sr;
236 ok1(sr = agar_bellman_ford_new(NULL, &negacycle_graphr.gr, int2ptr(1)));
237 agar_bellman_ford_complete(sr);
238 ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
245 + FULL_LEN * (FULL_LEN*4 - 1)
246 + CHAIN_LEN * (1 + CHAIN_LEN*2)
247 + 10 + 32 + 7 + 7 + 2);
259 return exit_status();