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;
39 parallel_graph_init(&pg, 3);
41 ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
42 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
43 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
44 ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
45 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
47 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
49 ok1(node == &pg.sg.nodes[1]);
52 ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
53 ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
54 ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
55 ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
57 ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
63 static void test_full(void)
68 full_graph_init(&fg, FULL_LEN);
70 for (i = 1; i <= FULL_LEN; i++) {
71 ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
73 for (j = 1; j <= FULL_LEN; j++) {
75 struct aga_node *node;
78 ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j],
79 &cost, &node, &edge));
86 ok1(node == &fg.sg.nodes[i]);
87 ok1(edge == &fg.sg.nodes[j]);
97 static void test_chain(void)
99 struct chain_graph cg;
102 chain_graph_init(&cg, CHAIN_LEN);
104 for (i = 1; i <= CHAIN_LEN; i++) {
105 ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
107 for (j = 1; j <= CHAIN_LEN; j++) {
110 ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
112 ok1(cost == labs(i - j));
115 aga_finish(&cg.fg.sg.g);
119 static void test_error(void)
121 struct error_graph eg;
124 error_graph_init(&eg);
126 ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
127 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
129 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
131 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
132 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
133 aga_finish(&eg.sg.g);
135 ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
136 ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
138 ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
139 ok1(aga_error(&eg.sg.g) == -1);
140 aga_finish(&eg.sg.g);
143 static void test_traversal1(void)
145 struct traversal1_graph t1g;
148 /* This is mostly about testing we correctly handle
149 * non-reachable nodes */
150 traversal1_graph_init(&t1g);
152 ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
153 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
156 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
159 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
162 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
165 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
168 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
171 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
173 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
175 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
177 aga_finish(&t1g.sg.g);
179 ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
180 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
183 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
186 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
189 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
192 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
195 ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
198 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
200 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
202 ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
204 aga_finish(&t1g.sg.g);
210 + FULL_LEN * (1 + FULL_LEN*4)
211 + CHAIN_LEN * (1 + CHAIN_LEN*2)
221 return exit_status();