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