git.ozlabs.org Git - ccan/blob - ccan/agar/test/api-dfs.c

   1 #include "config.h"
   2
   3 #include <stddef.h>
   4 #include <assert.h>
   5
   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>
  10
  11 #include <ccan/agar/agar.h>
  12
  13 #include "simple-graphr.h"
  14
  15 #define test_dfs_partial(sr, first, ...)                                \
  16         do {                                                            \
  17                 int cmp[] = { __VA_ARGS__ };                            \
  18                 bool stillok = true;                                    \
  19                 const void *node;                                       \
  20                 int i = 0;                                              \
  21                 agar_dfs(node, (sr), int2ptr(first)) {                  \
  22                         int index = ptr2int(node);                      \
  23                         diag("Visited %d\n", index);                    \
  24                         if (i >= ARRAY_SIZE(cmp) || (index != cmp[i]))  \
  25                                 stillok = false;                        \
  26                         i++;                                            \
  27                 }                                                       \
  28                 ok1(stillok);                                           \
  29         } while (0)
  30
  31 #define test_dfs(gr, first, ...)                                        \
  32         do {                                                            \
  33                 struct agar_state *sr;                                  \
  34                 ok1((sr = agar_dfs_new(NULL, (gr))));                   \
  35                 test_dfs_partial(sr, first, __VA_ARGS__);               \
  36                 tal_free(sr);                                           \
  37         } while (0)
  38
  39 int main(void)
  40 {
  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;
  46         const void *nr;
  47
  48         plan_tests(2 * 13 + 12 + 10 + 6);
  49
  50         test_dfs(&trivial_graphr.gr, 1, 1);
  51
  52         parallel_graphr_init(&pgr, 3, 0);
  53         test_dfs(&pgr.gr, 1, 1, 2);
  54
  55         full_graphr_init(&fgr, 5);
  56         test_dfs(&fgr.gr, 1, 1, 2, 3, 4, 5);
  57         test_dfs(&fgr.gr, 3, 3, 1, 2, 4, 5);
  58
  59         chain_graphr_init(&cgr, 8);
  60         test_dfs(&cgr.fgr.gr, 1, 1, 2, 3, 4, 5, 6, 7, 8);
  61         test_dfs(&cgr.fgr.gr, 8, 8, 7, 6, 5, 4, 3, 2, 1);
  62         test_dfs(&cgr.fgr.gr, 5, 5, 4, 3, 2, 1, 6, 7, 8);
  63
  64         grid_graphr_init(&ggr1, 3, 3, true, true, false, false);
  65         test_dfs(&ggr1.gr, 1, 1, 2, 3, 6, 9, 5, 8, 4, 7);
  66         test_dfs(&ggr1.gr, 5, 5, 6, 9, 8);
  67         test_dfs(&ggr1.gr, 9, 9);
  68
  69         grid_graphr_init(&ggr2, 3, 3, true, true, true, true);
  70         test_dfs(&ggr2.gr, 1, 1, 2, 3, 6, 9, 8, 7, 4, 5);
  71         test_dfs(&ggr2.gr, 5, 5, 6, 9, 8, 7, 4, 1, 2, 3);
  72         test_dfs(&ggr2.gr, 9, 9, 8, 7, 4, 5, 6, 3, 2, 1);
  73
  74         test_dfs(&error_graphr.gr, 1, 1, 2);
  75         ok((sr = agar_dfs_new(NULL, &error_graphr.gr)),
  76            "started error traversal");
  77         ok1(agar_dfs_explore(sr, int2ptr(3), &nr));
  78         ok(ptr2int(nr) == 3, "Expected node #3, actually #%ld", ptr2int(nr));
  79         ok1(agar_dfs_explore(sr, nr, &nr));
  80         ok(ptr2int(nr) == 4, "Expected node #4, actually #%ld", ptr2int(nr));
  81         ok1(!agar_dfs_explore(sr, nr, &nr));
  82         ok(agar_error(sr) == -1, "Error is %d (expected -1)", agar_error(sr));
  83         ok1(!agar_dfs_explore(sr, nr, &nr));
  84         tal_free(sr);
  85         test_dfs(&error_graphr.gr, 1, 1, 2);
  86
  87         test_dfs(&traversal1_graphr.gr, 1, 1, 2, 4, 5, 3, 6);
  88         test_dfs(&traversal1_graphr.gr, 9, 9, 8, 6, 5, 7, 4);
  89
  90         ok1((sr = agar_dfs_new(NULL, &traversal1_graphr.gr)));
  91         test_dfs_partial(sr, 1, 1, 2, 4, 5, 3, 6);
  92         test_dfs_partial(sr, 9, 9, 8, 7);
  93         tal_free(sr);
  94
  95         ok1((sr = agar_dfs_new(NULL, &traversal1_graphr.gr)));
  96         test_dfs_partial(sr, 9, 9, 8, 6, 5, 7, 4);
  97         test_dfs_partial(sr, 1, 1, 2, 3);
  98         tal_free(sr);
  99
 100         test_dfs(&negacycle_graphr.gr, 1, 1, 2, 3);
 101         test_dfs(&negacycle_graphr.gr, 2, 2, 3, 1);
 102         test_dfs(&negacycle_graphr.gr, 3, 3, 1, 2);
 103
 104         return exit_status();
 105 }