6 #include <ccan/tap/tap.h>
7 #include <ccan/array_size/array_size.h>
9 #include <ccan/aga/aga.h>
11 #include "simple-graph.h"
13 #define test_bfs_partial(sg, first, ...) \
15 int cmp[] = { __VA_ARGS__ }; \
16 bool stillok = true; \
17 struct aga_node *node; \
19 aga_bfs(node, &(sg)->g, &(sg)->nodes[first]) { \
20 int index = node - (sg)->nodes; \
21 diag("Visited %d\n", index); \
22 if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \
29 #define test_bfs(sg, first, ...) \
31 ok1(aga_bfs_start(&(sg)->g) == 0); \
32 test_bfs_partial(sg, first, __VA_ARGS__); \
33 aga_finish(&(sg)->g); \
38 struct trivial_graph tg;
39 struct parallel_graph pg;
41 struct chain_graph cg;
42 struct grid_graph gg1, gg2;
43 struct error_graph eg;
44 struct traversal1_graph t1g;
45 struct negacycle_graph ng;
46 struct aga_node *node;
48 plan_tests(2 * 13 + 10 + 10 + 6);
50 trivial_graph_init(&tg);
51 test_bfs(&tg.sg, 1, 1);
53 parallel_graph_init(&pg, 3, 0);
54 test_bfs(&pg.sg, 1, 1, 2);
56 full_graph_init(&fg, 5);
57 test_bfs(&fg.sg, 1, 1, 2, 3, 4, 5);
58 test_bfs(&fg.sg, 3, 3, 1, 2, 4, 5);
60 chain_graph_init(&cg, 8);
61 test_bfs(&cg.fg.sg, 1, 1, 2, 3, 4, 5, 6, 7, 8);
62 test_bfs(&cg.fg.sg, 8, 8, 7, 6, 5, 4, 3, 2, 1);
63 test_bfs(&cg.fg.sg, 5, 5, 4, 6, 3, 7, 2, 8, 1);
65 grid_graph_init(&gg1, 3, 3, true, true, false, false);
66 test_bfs(&gg1.sg, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
67 test_bfs(&gg1.sg, 5, 5, 6, 8, 9);
68 test_bfs(&gg1.sg, 9, 9);
70 grid_graph_init(&gg2, 3, 3, true, true, true, true);
71 test_bfs(&gg2.sg, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9);
72 test_bfs(&gg2.sg, 5, 5, 6, 8, 4, 2, 9, 3, 7, 1);
73 test_bfs(&gg2.sg, 9, 9, 8, 6, 7, 5, 3, 4, 2, 1);
75 error_graph_init(&eg);
76 test_bfs(&eg.sg, 1, 1, 2);
77 ok(aga_bfs_start(&eg.sg.g) == 0, "started error traversal");
78 node = aga_bfs_explore(&eg.sg.g, &eg.sg.nodes[3]);
79 ok(node == &eg.sg.nodes[3], "Expected node #3 (%p), actually #%ld (%p)",
80 &eg.sg.nodes[3], node - eg.sg.nodes, node);
81 node = aga_bfs_explore(&eg.sg.g, node);
82 ok(node == &eg.sg.nodes[4], "Expected node #4 (%p), actually #%ld (%p)",
83 &eg.sg.nodes[4], node - eg.sg.nodes, node);
84 ok1(aga_bfs_explore(&eg.sg.g, node) == NULL);
85 ok1(aga_error(&eg.sg.g) == -1);
86 ok1(aga_bfs_explore(&eg.sg.g, node) == NULL);
88 test_bfs(&eg.sg, 1, 1, 2);
90 traversal1_graph_init(&t1g);
91 test_bfs(&t1g.sg, 1, 1, 2, 3, 4, 5, 6);
92 test_bfs(&t1g.sg, 9, 9, 8, 7, 6, 5, 4);
94 ok1(aga_bfs_start(&t1g.sg.g) == 0);
95 test_bfs_partial(&t1g.sg, 1, 1, 2, 3, 4, 5, 6);
96 test_bfs_partial(&t1g.sg, 9, 9, 8, 7);
97 aga_finish(&t1g.sg.g);
99 ok1(aga_bfs_start(&t1g.sg.g) == 0);
100 test_bfs_partial(&t1g.sg, 9, 9, 8, 7, 6, 5, 4);
101 test_bfs_partial(&t1g.sg, 1, 1, 2, 3);
102 aga_finish(&t1g.sg.g);
104 negacycle_graph_init(&ng);
105 test_bfs(&ng.sg, 1, 1, 2, 3);
106 test_bfs(&ng.sg, 2, 2, 3, 1);
107 test_bfs(&ng.sg, 3, 3, 1, 2);
109 return exit_status();