f9b8d764a7d6e198d23797afa404882b0009e8d6
[ccan] / ccan / aga / test / api-dijkstra.c
1 #include "config.h"
2
3 #include <stddef.h>
4 #include <assert.h>
5 #include <stdlib.h>
6
7 #include <ccan/tap/tap.h>
8 #include <ccan/array_size/array_size.h>
9
10 #include <ccan/aga/aga.h>
11
12 #include "simple-graph.h"
13
14 static void test_trivial(void)
15 {
16         struct trivial_graph tg;
17         aga_icost_t cost;
18         struct aga_node *node;
19         const void *edge;
20
21         trivial_graph_init(&tg);
22
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));
27         ok1(cost == 0);
28         ok1(node == NULL);
29         ok1(edge == NULL);
30         aga_finish(&tg.sg.g);
31 }
32
33 static void test_parallel(void)
34 {
35         struct parallel_graph pg;
36         aga_icost_t cost;
37         struct aga_node *node;
38         const void *edge;
39
40         parallel_graph_init(&pg, 3, 0);
41
42         ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
43         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
44         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
45         ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
46         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
47         ok1(cost == 0);
48         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
49         ok1(cost == 2);
50         ok1(node == &pg.sg.nodes[1]);
51         aga_finish(&pg.sg.g);
52
53         ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
54         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
55         ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
56         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
57         ok1(cost == 0);
58         ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
59         aga_finish(&pg.sg.g);
60
61
62         parallel_graph_init(&pg, 3, 2);
63         ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
64         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
65         ok1(cost == 1);
66         ok1(node == &pg.sg.nodes[1]);
67         ok1(ptr2int(edge) == 2);
68         aga_finish(&pg.sg.g);
69 }
70
71 #define FULL_LEN        4
72
73 static void test_full(void)
74 {
75         struct full_graph fg;
76         int i, j;
77
78         full_graph_init(&fg, FULL_LEN);
79
80         for (i = 1; i <= FULL_LEN; i++) {
81                 ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
82
83                 for (j = 1; j <= FULL_LEN; j++) {
84                         aga_icost_t cost;
85                         struct aga_node *node;
86                         const void *edge;
87
88                         ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j],
89                                               &cost, &node, &edge));
90                         if (i == j) {
91                                 ok1(cost == 0);
92                                 ok1(node == NULL);
93                                 ok1(edge == NULL);
94                         } else {
95                                 ok1(cost == 1);
96                                 ok1(node == &fg.sg.nodes[i]);
97                                 ok1(edge == &fg.sg.nodes[j]);
98                         }
99                 }
100
101                 aga_finish(&fg.sg.g);
102         }
103 }
104
105 #define CHAIN_LEN       8
106
107 static void test_chain(void)
108 {
109         struct chain_graph cg;
110         int i, j;
111
112         chain_graph_init(&cg, CHAIN_LEN);
113
114         for (i = 1; i <= CHAIN_LEN; i++) {
115                 ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
116
117                 for (j = 1; j <= CHAIN_LEN; j++) {
118                         aga_icost_t cost;
119
120                         ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
121                                               &cost, NULL, NULL));
122                         ok1(cost == labs(i - j));
123                 }
124
125                 aga_finish(&cg.fg.sg.g);
126         }
127 }
128
129 static void test_error(void)
130 {
131         struct error_graph eg;
132         aga_icost_t cost;
133
134         error_graph_init(&eg);
135
136         ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
137         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
138         ok1(cost == 0);
139         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
140         ok1(cost == 1);
141         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
142         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
143         aga_finish(&eg.sg.g);
144
145         ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
146         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
147         ok1(cost == 0);
148         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
149         ok1(aga_error(&eg.sg.g) == -1);
150         aga_finish(&eg.sg.g);
151 }
152
153 static void test_traversal1(void)
154 {
155         struct traversal1_graph t1g;
156         aga_icost_t cost;
157
158         /* This is mostly about testing we correctly handle
159          * non-reachable nodes */
160         traversal1_graph_init(&t1g);
161
162         ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
163         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
164                               &cost, NULL, NULL));
165         ok1(cost == 0);
166         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
167                               &cost, NULL, NULL));
168         ok1(cost == 1);
169         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
170                               &cost, NULL, NULL));
171         ok1(cost == 1);
172         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
173                               &cost, NULL, NULL));
174         ok1(cost == 2);
175         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
176                               &cost, NULL, NULL));
177         ok1(cost == 2);
178         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
179                               &cost, NULL, NULL));
180         ok1(cost == 2);
181         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
182                                NULL, NULL, NULL));
183         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
184                                NULL, NULL, NULL));
185         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
186                                NULL, NULL, NULL));
187         aga_finish(&t1g.sg.g);
188
189         ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
190         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
191                               &cost, NULL, NULL));
192         ok1(cost == 0);
193         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
194                               &cost, NULL, NULL));
195         ok1(cost == 1);
196         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
197                               &cost, NULL, NULL));
198         ok1(cost == 1);
199         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
200                               &cost, NULL, NULL));
201         ok1(cost == 2);
202         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
203                               &cost, NULL, NULL));
204         ok1(cost == 2);
205         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
206                               &cost, NULL, NULL));
207         ok1(cost == 2);
208         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
209                                NULL, NULL, NULL));
210         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
211                                NULL, NULL, NULL));
212         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
213                                NULL, NULL, NULL));
214         aga_finish(&t1g.sg.g);
215 }
216
217 static void test_shortcut1(void)
218 {
219         struct shortcut1_graph s1g;
220         aga_icost_t cost;
221         struct aga_node *node;
222
223         shortcut1_graph_init(&s1g);
224
225         ok1(aga_dijkstra_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
226         ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[3],
227                               &cost, &node, NULL));
228         ok1(cost == 2);
229         ok1(node == &s1g.sg.nodes[2]);
230         ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[2],
231                               &cost, &node, NULL));
232         ok1(cost == 1);
233         ok1(node == &s1g.sg.nodes[1]);
234         aga_finish(&s1g.sg.g);
235 }
236
237 static void test_shortcut2(void)
238 {
239         struct shortcut2_graph s2g;
240
241         shortcut2_graph_init(&s2g);
242
243         ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
244         aga_dijkstra_all_paths(&s2g.sg.g);
245         ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
246         aga_finish(&s2g.sg.g);
247 }
248
249 int main(void)
250 {
251         plan_tests(7 + 20
252                    + FULL_LEN * (1 + FULL_LEN*4)
253                    + CHAIN_LEN * (1 + CHAIN_LEN*2)
254                    + 12 + 32 + 7 + 2);
255
256         test_trivial();
257         test_parallel();
258         test_full();
259         test_chain();
260         test_error();
261         test_traversal1();
262         test_shortcut1();
263         test_shortcut2();
264         
265         return exit_status();
266 }