aga,agar: Rename aga_dijkstra_all_paths()
[ccan] / ccan / agar / 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/tal/tal.h>
9 #include <ccan/array_size/array_size.h>
10
11 #include <ccan/agar/agar.h>
12
13 #include "simple-graphr.h"
14
15 static void test_trivial(void)
16 {
17         struct agar_state *sr;
18         aga_icost_t cost;
19         const void *node;
20
21         ok1(sr = agar_dijkstra_new(NULL, &trivial_graphr.gr, int2ptr(1)));
22         ok1(agar_dijkstra_step(sr, &node));
23         ok1(ptr2int(node) == 1);
24         ok1(!agar_dijkstra_step(sr, &node));
25         ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
26         ok1(cost == 0);
27         tal_free(sr);
28 }
29
30 static void test_parallel(void)
31 {
32         struct parallel_graphr pgr;
33         struct agar_state *sr;
34         aga_icost_t cost;
35         const void *node, *edge;
36
37         parallel_graphr_init(&pgr, 3, 0);
38
39         ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
40         ok1(agar_dijkstra_step(sr, &node));
41         ok1(ptr2int(node) == 1);
42         ok1(agar_dijkstra_step(sr, &node));
43         ok1(ptr2int(node) == 2);
44         ok1(!agar_dijkstra_step(sr, &node));
45         ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
46         ok1(cost == 0);
47         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
48         ok1(cost == 2);
49         ok1(node == int2ptr(1));
50         tal_free(sr);
51
52         ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(2)));
53         ok1(agar_dijkstra_step(sr, &node));
54         ok1(ptr2int(node) == 2);
55         ok1(!agar_dijkstra_step(sr, &node));
56         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
57         ok1(cost == 0);
58         ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
59         tal_free(sr);
60
61         parallel_graphr_init(&pgr, 3, 2);
62         ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
63         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
64         ok1(cost == 1);
65         ok1(ptr2int(node) == 1);
66         ok1(ptr2int(edge) == 2);
67         tal_free(sr);
68 }
69
70 #define FULL_LEN        4
71
72 static void test_full(void)
73 {
74         struct full_graphr fgr;
75         int i, j;
76
77         full_graphr_init(&fgr, FULL_LEN);
78
79         for (i = 1; i <= FULL_LEN; i++) {
80                 struct agar_state *sr;
81
82                 ok1(sr = agar_dijkstra_new(NULL, &fgr.gr, int2ptr(i)));
83
84                 for (j = 1; j <= FULL_LEN; j++) {
85                         aga_icost_t cost;
86                         const void *node, *edge;
87
88                         ok1(agar_dijkstra_path(sr, int2ptr(j),
89                                               &cost, &node, &edge));
90                         if (i == j) {
91                                 ok1(cost == 0);
92                         } else {
93                                 ok1(cost == 1);
94                                 ok1(node == int2ptr(i));
95                                 ok1(edge == int2ptr(j));
96                         }
97                 }
98
99                 tal_free(sr);
100         }
101 }
102
103 #define CHAIN_LEN       8
104
105 static void test_chain(void)
106 {
107         struct chain_graphr cgr;
108         int i, j;
109
110         chain_graphr_init(&cgr, CHAIN_LEN);
111
112         for (i = 1; i <= CHAIN_LEN; i++) {
113                 struct agar_state *sr;
114
115                 ok1(sr = agar_dijkstra_new(NULL, &cgr.fgr.gr, int2ptr(i)));
116
117                 for (j = 1; j <= CHAIN_LEN; j++) {
118                         aga_icost_t cost;
119
120                         ok1(agar_dijkstra_path(sr, int2ptr(j),
121                                               &cost, NULL, NULL));
122                         ok1(cost == labs(i - j));
123                 }
124
125                 tal_free(sr);
126         }
127 }
128
129 static void test_error(void)
130 {
131         struct agar_state *sr;
132         aga_icost_t cost;
133
134         ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(1)));
135         ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
136         ok1(cost == 0);
137         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
138         ok1(cost == 1);
139         ok1(!agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
140         ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
141         tal_free(sr);
142
143         ok1(sr = agar_dijkstra_new(NULL, &error_graphr.gr, int2ptr(3)));
144         ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
145         ok1(cost == 0);
146         ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
147         ok1(agar_error(sr) == -1);
148         tal_free(sr);
149 }
150
151 static void test_traversal1(void)
152 {
153         struct agar_state *sr;
154         aga_icost_t cost;
155
156         /* This is mostly about testing we correctly handle
157          * non-reachable nodes */
158         ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(1)));
159         ok1(agar_dijkstra_path(sr, int2ptr(1),
160                               &cost, NULL, NULL));
161         ok1(cost == 0);
162         ok1(agar_dijkstra_path(sr, int2ptr(2),
163                               &cost, NULL, NULL));
164         ok1(cost == 1);
165         ok1(agar_dijkstra_path(sr, int2ptr(3),
166                               &cost, NULL, NULL));
167         ok1(cost == 1);
168         ok1(agar_dijkstra_path(sr, int2ptr(4),
169                               &cost, NULL, NULL));
170         ok1(cost == 2);
171         ok1(agar_dijkstra_path(sr, int2ptr(5),
172                               &cost, NULL, NULL));
173         ok1(cost == 2);
174         ok1(agar_dijkstra_path(sr, int2ptr(6),
175                               &cost, NULL, NULL));
176         ok1(cost == 2);
177         ok1(!agar_dijkstra_path(sr, int2ptr(7),
178                                NULL, NULL, NULL));
179         ok1(!agar_dijkstra_path(sr, int2ptr(8),
180                                NULL, NULL, NULL));
181         ok1(!agar_dijkstra_path(sr, int2ptr(9),
182                                NULL, NULL, NULL));
183         tal_free(sr);
184
185         ok1(sr = agar_dijkstra_new(NULL, &traversal1_graphr.gr, int2ptr(9)));
186         ok1(agar_dijkstra_path(sr, int2ptr(9),
187                               &cost, NULL, NULL));
188         ok1(cost == 0);
189         ok1(agar_dijkstra_path(sr, int2ptr(8),
190                               &cost, NULL, NULL));
191         ok1(cost == 1);
192         ok1(agar_dijkstra_path(sr, int2ptr(7),
193                               &cost, NULL, NULL));
194         ok1(cost == 1);
195         ok1(agar_dijkstra_path(sr, int2ptr(6),
196                               &cost, NULL, NULL));
197         ok1(cost == 2);
198         ok1(agar_dijkstra_path(sr, int2ptr(5),
199                               &cost, NULL, NULL));
200         ok1(cost == 2);
201         ok1(agar_dijkstra_path(sr, int2ptr(4),
202                               &cost, NULL, NULL));
203         ok1(cost == 2);
204         ok1(!agar_dijkstra_path(sr, int2ptr(3),
205                                NULL, NULL, NULL));
206         ok1(!agar_dijkstra_path(sr, int2ptr(2),
207                                NULL, NULL, NULL));
208         ok1(!agar_dijkstra_path(sr, int2ptr(1),
209                                NULL, NULL, NULL));
210         tal_free(sr);
211 }
212
213 static void test_shortcut1(void)
214 {
215         struct agar_state *sr;
216         aga_icost_t cost;
217         const void *node;
218
219         ok1(sr = agar_dijkstra_new(NULL, &shortcut1_graphr.gr, int2ptr(1)));
220         ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
221         ok1(cost == 2);
222         ok1(node == int2ptr(2));
223         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
224         ok1(cost == 1);
225         ok1(node == int2ptr(1));
226         tal_free(sr);
227 }
228
229 static void test_shortcut2(void)
230 {
231         struct agar_state *sr;
232
233         ok1(sr = agar_dijkstra_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
234         agar_dijkstra_complete(sr);
235         ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
236         tal_free(sr);
237 }
238
239 int main(void)
240 {
241         plan_tests(6 + 23
242                    + FULL_LEN * (FULL_LEN*4 - 1)
243                    + CHAIN_LEN * (1 + CHAIN_LEN*2)
244                    + 12 + 32 + 7 + 2);
245
246         test_trivial();
247         test_parallel();
248         test_full();
249         test_chain();
250         test_error();
251         test_traversal1();
252         test_shortcut1();
253         test_shortcut2();
254         
255         return exit_status();
256 }