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