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