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_bellman_ford_start(&tg.sg.g, &tg.sg.nodes[1]) == 0);
24 ok1(aga_bellman_ford_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge));
31 static void test_parallel(void)
33 struct parallel_graph pg;
35 struct aga_node *node;
38 parallel_graph_init(&pg, 3, 0);
40 ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
41 ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
43 ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
45 ok1(node == &pg.sg.nodes[1]);
48 ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
49 ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
51 ok1(!aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
55 parallel_graph_init(&pg, 3, 2);
56 ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
57 ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
59 ok1(node == &pg.sg.nodes[1]);
60 ok1(ptr2int(edge) == 2);
66 static void test_full(void)
71 full_graph_init(&fg, FULL_LEN);
73 for (i = 1; i <= FULL_LEN; i++) {
74 ok1(aga_bellman_ford_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
76 for (j = 1; j <= FULL_LEN; j++) {
78 struct aga_node *node;
81 ok1(aga_bellman_ford_path(&fg.sg.g, &fg.sg.nodes[j],
82 &cost, &node, &edge));
89 ok1(node == &fg.sg.nodes[i]);
90 ok1(edge == &fg.sg.nodes[j]);
100 static void test_chain(void)
102 struct chain_graph cg;
105 chain_graph_init(&cg, CHAIN_LEN);
107 for (i = 1; i <= CHAIN_LEN; i++) {
108 ok1(aga_bellman_ford_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
110 for (j = 1; j <= CHAIN_LEN; j++) {
113 ok1(aga_bellman_ford_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
115 ok1(cost == labs(i - j));
118 aga_finish(&cg.fg.sg.g);
122 static void test_error(void)
124 struct error_graph eg;
127 error_graph_init(&eg);
129 ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
130 ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
132 ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
134 ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
135 ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
136 aga_finish(&eg.sg.g);
138 ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
139 aga_bellman_ford_complete(&eg.sg.g);
140 ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
141 ok1(aga_error(&eg.sg.g) == -1);
142 aga_finish(&eg.sg.g);
145 static void test_traversal1(void)
147 struct traversal1_graph t1g;
150 /* This is mostly about testing we correctly handle
151 * non-reachable nodes */
152 traversal1_graph_init(&t1g);
154 ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
155 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
158 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
161 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
164 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
167 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
170 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
173 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
175 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
177 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
179 aga_finish(&t1g.sg.g);
181 ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
182 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
185 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
188 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
191 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
194 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
197 ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
200 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
202 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
204 ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
206 aga_finish(&t1g.sg.g);
209 static void test_shortcut1(void)
211 struct shortcut1_graph s1g;
213 struct aga_node *node;
215 shortcut1_graph_init(&s1g);
217 ok1(aga_bellman_ford_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
218 ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[3],
219 &cost, &node, NULL));
221 ok1(node == &s1g.sg.nodes[2]);
222 ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[2],
223 &cost, &node, NULL));
225 ok1(node == &s1g.sg.nodes[1]);
226 aga_finish(&s1g.sg.g);
229 static void test_shortcut2(void)
231 struct shortcut2_graph s2g;
233 struct aga_node *node;
235 shortcut2_graph_init(&s2g);
237 ok1(aga_bellman_ford_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
238 ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[3],
239 &cost, &node, NULL));
241 ok1(node == &s2g.sg.nodes[2]);
242 ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[2],
243 &cost, &node, NULL));
245 ok1(node == &s2g.sg.nodes[1]);
246 aga_finish(&s2g.sg.g);
252 + FULL_LEN * (1 + FULL_LEN * 4)
253 + CHAIN_LEN * (1 + CHAIN_LEN * 2)
265 return exit_status();