6 #include <ccan/tal/tal.h>
7 #include <ccan/tap/tap.h>
8 #include <ccan/array_size/array_size.h>
9 #include <ccan/ptrint/ptrint.h>
11 #include <ccan/agar/agar.h>
13 #include "simple-graphr.h"
15 #define test_bfs_partial(sr, first, ...) \
17 int cmp[] = { __VA_ARGS__ }; \
18 bool stillok = true; \
21 agar_bfs(node, (sr), int2ptr(first)) { \
22 int index = ptr2int(node); \
23 diag("Visited %d\n", index); \
24 if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \
31 #define test_bfs(gr, first, ...) \
33 struct agar_state *sr; \
34 ok1((sr = agar_bfs_new(NULL, (gr)))); \
35 test_bfs_partial(sr, first, __VA_ARGS__); \
41 struct parallel_graphr pgr;
42 struct full_graphr fgr;
43 struct chain_graphr cgr;
44 struct grid_graphr ggr1, ggr2;
45 struct agar_state *sr;
48 plan_tests(2 * 13 + 12 + 10 + 6);
50 test_bfs(&trivial_graphr.gr, 1, 1);
52 parallel_graphr_init(&pgr, 3, 0);
53 test_bfs(&pgr.gr, 1, 1, 2);
55 full_graphr_init(&fgr, 5);
56 test_bfs(&fgr.gr, 1, 1, 2, 3, 4, 5);
57 test_bfs(&fgr.gr, 3, 3, 1, 2, 4, 5);
59 chain_graphr_init(&cgr, 8);
60 test_bfs(&cgr.fgr.gr, 1, 1, 2, 3, 4, 5, 6, 7, 8);
61 test_bfs(&cgr.fgr.gr, 8, 8, 7, 6, 5, 4, 3, 2, 1);
62 test_bfs(&cgr.fgr.gr, 5, 5, 4, 6, 3, 7, 2, 8, 1);
64 grid_graphr_init(&ggr1, 3, 3, true, true, false, false);
65 test_bfs(&ggr1.gr, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
66 test_bfs(&ggr1.gr, 5, 5, 6, 8, 9);
67 test_bfs(&ggr1.gr, 9, 9);
69 grid_graphr_init(&ggr2, 3, 3, true, true, true, true);
70 test_bfs(&ggr2.gr, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
71 test_bfs(&ggr2.gr, 5, 5, 6, 8, 4, 2, 9, 3, 7, 1);
72 test_bfs(&ggr2.gr, 9, 9, 8, 6, 7, 5, 3, 4, 2, 1);
74 test_bfs(&error_graphr.gr, 1, 1, 2);
75 ok((sr = agar_bfs_new(NULL, &error_graphr.gr)),
76 "started error traversal");
77 ok1(agar_bfs_explore(sr, int2ptr(3), &nr));
78 ok(ptr2int(nr) == 3, "Expected node #3, actually #%ld", ptr2int(nr));
79 ok1(agar_bfs_explore(sr, nr, &nr));
80 ok(ptr2int(nr) == 4, "Expected node #4, actually #%ld", ptr2int(nr));
81 ok1(!agar_bfs_explore(sr, nr, &nr));
82 ok1(agar_error(sr) == -1);
83 ok1(!agar_bfs_explore(sr, nr, &nr));
85 test_bfs(&error_graphr.gr, 1, 1, 2);
87 test_bfs(&traversal1_graphr.gr, 1, 1, 2, 3, 4, 5, 6);
88 test_bfs(&traversal1_graphr.gr, 9, 9, 8, 7, 6, 5, 4);
90 ok1((sr = agar_bfs_new(NULL, &traversal1_graphr.gr)));
91 test_bfs_partial(sr, 1, 1, 2, 3, 4, 5, 6);
92 test_bfs_partial(sr, 9, 9, 8, 7);
95 ok1((sr = agar_bfs_new(NULL, &traversal1_graphr.gr)));
96 test_bfs_partial(sr, 9, 9, 8, 7, 6, 5, 4);
97 test_bfs_partial(sr, 1, 1, 2, 3);
100 test_bfs(&negacycle_graphr.gr, 1, 1, 2, 3);
101 test_bfs(&negacycle_graphr.gr, 2, 2, 3, 1);
102 test_bfs(&negacycle_graphr.gr, 3, 3, 1, 2);
104 return exit_status();