git.ozlabs.org Git - ccan/blob - ccan/aga/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/array_size/array_size.h>
   9
  10 #include <ccan/aga/aga.h>
  11
  12 #include "simple-graph.h"
  13
  14 static void test_trivial(void)
  15 {
  16         struct trivial_graph tg;
  17         aga_icost_t cost;
  18         struct aga_node *node;
  19         const void *edge;
  20
  21         trivial_graph_init(&tg);
  22
  23         ok1(aga_bellman_ford_start(&tg.sg.g, &tg.sg.nodes[1]) == 0);
  24         ok1(aga_bellman_ford_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge));
  25         ok1(cost == 0);
  26         ok1(node == NULL);
  27         ok1(edge == NULL);
  28         aga_finish(&tg.sg.g);
  29 }
  30
  31 static void test_parallel(void)
  32 {
  33         struct parallel_graph pg;
  34         aga_icost_t cost;
  35         struct aga_node *node;
  36         const void *edge;
  37
  38         parallel_graph_init(&pg, 3, 0);
  39
  40         ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
  41         ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
  42         ok1(cost == 0);
  43         ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
  44         ok1(cost == 2);
  45         ok1(node == &pg.sg.nodes[1]);
  46         aga_finish(&pg.sg.g);
  47
  48         ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
  49         ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
  50         ok1(cost == 0);
  51         ok1(!aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
  52         aga_finish(&pg.sg.g);
  53
  54
  55         parallel_graph_init(&pg, 3, 2);
  56         ok1(aga_bellman_ford_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
  57         ok1(aga_bellman_ford_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
  58         ok1(cost == 1);
  59         ok1(node == &pg.sg.nodes[1]);
  60         ok1(ptr2int(edge) == 2);
  61         aga_finish(&pg.sg.g);
  62 }
  63
  64 #define FULL_LEN        4
  65
  66 static void test_full(void)
  67 {
  68         struct full_graph fg;
  69         int i, j;
  70
  71         full_graph_init(&fg, FULL_LEN);
  72
  73         for (i = 1; i <= FULL_LEN; i++) {
  74                 ok1(aga_bellman_ford_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
  75
  76                 for (j = 1; j <= FULL_LEN; j++) {
  77                         aga_icost_t cost;
  78                         struct aga_node *node;
  79                         const void *edge;
  80
  81                         ok1(aga_bellman_ford_path(&fg.sg.g, &fg.sg.nodes[j],
  82                                               &cost, &node, &edge));
  83                         if (i == j) {
  84                                 ok1(cost == 0);
  85                                 ok1(node == NULL);
  86                                 ok1(edge == NULL);
  87                         } else {
  88                                 ok1(cost == 1);
  89                                 ok1(node == &fg.sg.nodes[i]);
  90                                 ok1(edge == &fg.sg.nodes[j]);
  91                         }
  92                 }
  93
  94                 aga_finish(&fg.sg.g);
  95         }
  96 }
  97
  98 #define CHAIN_LEN       8
  99
 100 static void test_chain(void)
 101 {
 102         struct chain_graph cg;
 103         int i, j;
 104
 105         chain_graph_init(&cg, CHAIN_LEN);
 106
 107         for (i = 1; i <= CHAIN_LEN; i++) {
 108                 ok1(aga_bellman_ford_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
 109
 110                 for (j = 1; j <= CHAIN_LEN; j++) {
 111                         aga_icost_t cost;
 112
 113                         ok1(aga_bellman_ford_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
 114                                               &cost, NULL, NULL));
 115                         ok1(cost == labs(i - j));
 116                 }
 117
 118                 aga_finish(&cg.fg.sg.g);
 119         }
 120 }
 121
 122 static void test_error(void)
 123 {
 124         struct error_graph eg;
 125         aga_icost_t cost;
 126
 127         error_graph_init(&eg);
 128
 129         ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
 130         ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
 131         ok1(cost == 0);
 132         ok1(aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
 133         ok1(cost == 1);
 134         ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
 135         ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
 136         aga_finish(&eg.sg.g);
 137
 138         ok1(aga_bellman_ford_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
 139         aga_bellman_ford_complete(&eg.sg.g);
 140         ok1(!aga_bellman_ford_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
 141         ok1(aga_error(&eg.sg.g) == -1);
 142         aga_finish(&eg.sg.g);
 143 }
 144
 145 static void test_traversal1(void)
 146 {
 147         struct traversal1_graph t1g;
 148         aga_icost_t cost;
 149
 150         /* This is mostly about testing we correctly handle
 151          * non-reachable nodes */
 152         traversal1_graph_init(&t1g);
 153
 154         ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
 155         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
 156                               &cost, NULL, NULL));
 157         ok1(cost == 0);
 158         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
 159                               &cost, NULL, NULL));
 160         ok1(cost == 1);
 161         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
 162                               &cost, NULL, NULL));
 163         ok1(cost == 1);
 164         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
 165                               &cost, NULL, NULL));
 166         ok1(cost == 2);
 167         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
 168                               &cost, NULL, NULL));
 169         ok1(cost == 2);
 170         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
 171                               &cost, NULL, NULL));
 172         ok1(cost == 2);
 173         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
 174                                NULL, NULL, NULL));
 175         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
 176                                NULL, NULL, NULL));
 177         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
 178                                NULL, NULL, NULL));
 179         aga_finish(&t1g.sg.g);
 180
 181         ok1(aga_bellman_ford_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
 182         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[9],
 183                               &cost, NULL, NULL));
 184         ok1(cost == 0);
 185         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[8],
 186                               &cost, NULL, NULL));
 187         ok1(cost == 1);
 188         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[7],
 189                               &cost, NULL, NULL));
 190         ok1(cost == 1);
 191         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[6],
 192                               &cost, NULL, NULL));
 193         ok1(cost == 2);
 194         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[5],
 195                               &cost, NULL, NULL));
 196         ok1(cost == 2);
 197         ok1(aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[4],
 198                               &cost, NULL, NULL));
 199         ok1(cost == 2);
 200         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[3],
 201                                NULL, NULL, NULL));
 202         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[2],
 203                                NULL, NULL, NULL));
 204         ok1(!aga_bellman_ford_path(&t1g.sg.g, &t1g.sg.nodes[1],
 205                                NULL, NULL, NULL));
 206         aga_finish(&t1g.sg.g);
 207 }
 208
 209 static void test_shortcut1(void)
 210 {
 211         struct shortcut1_graph s1g;
 212         aga_icost_t cost;
 213         struct aga_node *node;
 214
 215         shortcut1_graph_init(&s1g);
 216
 217         ok1(aga_bellman_ford_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
 218         ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[3],
 219                               &cost, &node, NULL));
 220         ok1(cost == 2);
 221         ok1(node == &s1g.sg.nodes[2]);
 222         ok1(aga_bellman_ford_path(&s1g.sg.g, &s1g.sg.nodes[2],
 223                               &cost, &node, NULL));
 224         ok1(cost == 1);
 225         ok1(node == &s1g.sg.nodes[1]);
 226         aga_finish(&s1g.sg.g);
 227 }
 228
 229 static void test_shortcut2(void)
 230 {
 231         struct shortcut2_graph s2g;
 232         aga_icost_t cost;
 233         struct aga_node *node;
 234
 235         shortcut2_graph_init(&s2g);
 236
 237         ok1(aga_bellman_ford_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
 238         ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[3],
 239                                   &cost, &node, NULL));
 240         ok1(cost == 1);
 241         ok1(node == &s2g.sg.nodes[2]);
 242         ok1(aga_bellman_ford_path(&s2g.sg.g, &s2g.sg.nodes[2],
 243                               &cost, &node, NULL));
 244         ok1(cost == 2);
 245         ok1(node == &s2g.sg.nodes[1]);
 246         aga_finish(&s2g.sg.g);
 247 }
 248
 249 static void test_negacycle(void)
 250 {
 251         struct negacycle_graph ng;
 252
 253         negacycle_graph_init(&ng);
 254
 255         ok1(aga_bellman_ford_start(&ng.sg.g, &ng.sg.nodes[1]) == 0);
 256         aga_bellman_ford_complete(&ng.sg.g);
 257         ok1(aga_error(&ng.sg.g) == AGA_ERR_NEGATIVE_COST);
 258         aga_finish(&ng.sg.g);
 259 }
 260
 261 int main(void)
 262 {
 263         plan_tests(5 + 15
 264                    + FULL_LEN * (1 + FULL_LEN * 4)
 265                    + CHAIN_LEN * (1 + CHAIN_LEN * 2)
 266                    + 10 + 32 + 7 + 7 + 2);
 267
 268         test_trivial();
 269         test_parallel();
 270         test_full();
 271         test_chain();
 272         test_error();
 273         test_traversal1();
 274         test_shortcut1();
 275         test_shortcut2();
 276         test_negacycle();
 277
 278         return exit_status();
 279 }