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