git.ozlabs.org Git - ccan/blob - ccan/aga/test/api-bfs.c

   1 #include "config.h"
   2
   3 #include <stddef.h>
   4 #include <assert.h>
   5
   6 #include <ccan/tap/tap.h>
   7 #include <ccan/array_size/array_size.h>
   8
   9 #include <ccan/aga/aga.h>
  10
  11 #include "simple-graph.h"
  12
  13 #define test_bfs_partial(sg, first, ...)                                \
  14         do {                                                            \
  15                 int cmp[] = { __VA_ARGS__ };                            \
  16                 bool stillok = true;                                    \
  17                 struct aga_node *node;                                  \
  18                 int i = 0;                                              \
  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]))  \
  23                                 stillok = false;                        \
  24                         i++;                                            \
  25                 }                                                       \
  26                 ok1(stillok);                                           \
  27         } while (0)
  28
  29 #define test_bfs(sg, first, ...)                                        \
  30         do {                                                            \
  31                 ok1(aga_bfs_start(&(sg)->g) == 0);                      \
  32                 test_bfs_partial(sg, first, __VA_ARGS__);               \
  33                 aga_finish(&(sg)->g);                                   \
  34         } while (0)
  35
  36 int main(void)
  37 {
  38         struct trivial_graph tg;
  39         struct parallel_graph pg;
  40         struct full_graph fg;
  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;
  47
  48         plan_tests(2 * 13 + 10 + 10 + 6);
  49
  50         trivial_graph_init(&tg);
  51         test_bfs(&tg.sg, 1, 1);
  52
  53         parallel_graph_init(&pg, 3, 0);
  54         test_bfs(&pg.sg, 1, 1, 2);
  55
  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);
  59
  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);
  64
  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);
  69
  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);
  74
  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);
  87         aga_finish(&eg.sg.g);
  88         test_bfs(&eg.sg, 1, 1, 2);
  89
  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);
  93
  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);
  98
  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);
 103
 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);
 108
 109         return exit_status();
 110 }