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, *edge;
  39
  40         parallel_graphr_init(&pgr, 3, 0);
  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 == 2);
  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         parallel_graphr_init(&pgr, 3, 2);
  65         ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
  66         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
  67         ok1(cost == 1);
  68         ok1(ptr2int(node) == 1);
  69         ok1(ptr2int(edge) == 2);
  70         tal_free(sr);
  71 }
  72
  73 #define FULL_LEN        4
  74
  75 static void test_full(void)
  76 {
  77         struct full_graphr fgr;
  78         int i, j;
  79
  80         full_graphr_init(&fgr, FULL_LEN);
  81
  82         for (i = 1; i <= FULL_LEN; i++) {
  83                 struct agar_state *sr;
  84
  85                 ok1(sr = agar_dijkstra_new(NULL, &fgr.gr, int2ptr(i)));
  86
  87                 for (j = 1; j <= FULL_LEN; j++) {
  88                         aga_icost_t cost;
  89                         const void *node, *edge;
  90
  91                         ok1(agar_dijkstra_path(sr, int2ptr(j),
  92                                               &cost, &node, &edge));
  93                         if (i == j) {
  94                                 ok1(cost == 0);
  95                         } else {
  96                                 ok1(cost == 1);
  97                                 ok1(node == int2ptr(i));
  98                                 ok1(edge == int2ptr(j));
  99                         }
 100                 }
 101
 102                 tal_free(sr);
 103         }
 104 }
 105
 106 #define CHAIN_LEN       8
 107
 108 static void test_chain(void)
 109 {
 110         struct chain_graphr cgr;
 111         int i, j;
 112
 113         chain_graphr_init(&cgr, CHAIN_LEN);
 114
 115         for (i = 1; i <= CHAIN_LEN; i++) {
 116                 struct agar_state *sr;
 117
 118                 ok1(sr = agar_dijkstra_new(NULL, &cgr.fgr.gr, int2ptr(i)));
 119
 120                 for (j = 1; j <= CHAIN_LEN; j++) {
 121                         aga_icost_t cost;
 122
 123                         ok1(agar_dijkstra_path(sr, int2ptr(j),
 124                                               &cost, NULL, NULL));
 125                         ok1(cost == labs(i - j));
 126                 }
 127
 128                 tal_free(sr);
 129         }
 130 }
 131
 132 static void test_error(void)
 133 {
 134         struct error_graphr egr;
 135         struct agar_state *sr;
 136         aga_icost_t cost;
 137
 138         error_graphr_init(&egr);
 139
 140         ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(1)));
 141         ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
 142         ok1(cost == 0);
 143         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
 144         ok1(cost == 1);
 145         ok1(!agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
 146         ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
 147         tal_free(sr);
 148
 149         ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(3)));
 150         ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
 151         ok1(cost == 0);
 152         ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
 153         ok1(agar_error(sr) == -1);
 154         tal_free(sr);
 155 }
 156
 157 static void test_traversal1(void)
 158 {
 159         struct traversal1_graphr t1gr;
 160         struct agar_state *sr;
 161         aga_icost_t cost;
 162
 163         /* This is mostly about testing we correctly handle
 164          * non-reachable nodes */
 165         traversal1_graphr_init(&t1gr);
 166
 167         ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(1)));
 168         ok1(agar_dijkstra_path(sr, int2ptr(1),
 169                               &cost, NULL, NULL));
 170         ok1(cost == 0);
 171         ok1(agar_dijkstra_path(sr, int2ptr(2),
 172                               &cost, NULL, NULL));
 173         ok1(cost == 1);
 174         ok1(agar_dijkstra_path(sr, int2ptr(3),
 175                               &cost, NULL, NULL));
 176         ok1(cost == 1);
 177         ok1(agar_dijkstra_path(sr, int2ptr(4),
 178                               &cost, NULL, NULL));
 179         ok1(cost == 2);
 180         ok1(agar_dijkstra_path(sr, int2ptr(5),
 181                               &cost, NULL, NULL));
 182         ok1(cost == 2);
 183         ok1(agar_dijkstra_path(sr, int2ptr(6),
 184                               &cost, NULL, NULL));
 185         ok1(cost == 2);
 186         ok1(!agar_dijkstra_path(sr, int2ptr(7),
 187                                NULL, NULL, NULL));
 188         ok1(!agar_dijkstra_path(sr, int2ptr(8),
 189                                NULL, NULL, NULL));
 190         ok1(!agar_dijkstra_path(sr, int2ptr(9),
 191                                NULL, NULL, NULL));
 192         tal_free(sr);
 193
 194         ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(9)));
 195         ok1(agar_dijkstra_path(sr, int2ptr(9),
 196                               &cost, NULL, NULL));
 197         ok1(cost == 0);
 198         ok1(agar_dijkstra_path(sr, int2ptr(8),
 199                               &cost, NULL, NULL));
 200         ok1(cost == 1);
 201         ok1(agar_dijkstra_path(sr, int2ptr(7),
 202                               &cost, NULL, NULL));
 203         ok1(cost == 1);
 204         ok1(agar_dijkstra_path(sr, int2ptr(6),
 205                               &cost, NULL, NULL));
 206         ok1(cost == 2);
 207         ok1(agar_dijkstra_path(sr, int2ptr(5),
 208                               &cost, NULL, NULL));
 209         ok1(cost == 2);
 210         ok1(agar_dijkstra_path(sr, int2ptr(4),
 211                               &cost, NULL, NULL));
 212         ok1(cost == 2);
 213         ok1(!agar_dijkstra_path(sr, int2ptr(3),
 214                                NULL, NULL, NULL));
 215         ok1(!agar_dijkstra_path(sr, int2ptr(2),
 216                                NULL, NULL, NULL));
 217         ok1(!agar_dijkstra_path(sr, int2ptr(1),
 218                                NULL, NULL, NULL));
 219         tal_free(sr);
 220 }
 221
 222 static void test_shortcut1(void)
 223 {
 224         struct shortcut1_graphr s1gr;
 225         struct agar_state *sr;
 226         aga_icost_t cost;
 227         const void *node;
 228
 229         shortcut1_graphr_init(&s1gr);
 230
 231         ok1(sr = agar_dijkstra_new(NULL, &s1gr.gr, int2ptr(1)));
 232         ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
 233         ok1(cost == 2);
 234         ok1(node == int2ptr(2));
 235         ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
 236         ok1(cost == 1);
 237         ok1(node == int2ptr(1));
 238         tal_free(sr);
 239 }
 240
 241 int main(void)
 242 {
 243         plan_tests(6 + 23
 244                    + FULL_LEN * (FULL_LEN*4 - 1)
 245                    + CHAIN_LEN * (1 + CHAIN_LEN*2)
 246                    + 12 + 32 + 7);
 247
 248         test_trivial();
 249         test_parallel();
 250         test_full();
 251         test_chain();
 252         test_error();
 253         test_traversal1();
 254         test_shortcut1();
 255
 256         return exit_status();
 257 }