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
  39         parallel_graph_init(&pg, 3);
  40
  41         ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
  42         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
  43         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
  44         ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
  45         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
  46         ok1(cost == 0);
  47         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
  48         ok1(cost == 1);
  49         ok1(node == &pg.sg.nodes[1]);
  50         aga_finish(&pg.sg.g);
  51
  52         ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
  53         ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
  54         ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
  55         ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
  56         ok1(cost == 0);
  57         ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
  58         aga_finish(&pg.sg.g);
  59 }
  60
  61 #define FULL_LEN        4
  62
  63 static void test_full(void)
  64 {
  65         struct full_graph fg;
  66         int i, j;
  67
  68         full_graph_init(&fg, FULL_LEN);
  69
  70         for (i = 1; i <= FULL_LEN; i++) {
  71                 ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
  72
  73                 for (j = 1; j <= FULL_LEN; j++) {
  74                         aga_icost_t cost;
  75                         struct aga_node *node;
  76                         const void *edge;
  77
  78                         ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j],
  79                                               &cost, &node, &edge));
  80                         if (i == j) {
  81                                 ok1(cost == 0);
  82                                 ok1(node == NULL);
  83                                 ok1(edge == NULL);
  84                         } else {
  85                                 ok1(cost == 1);
  86                                 ok1(node == &fg.sg.nodes[i]);
  87                                 ok1(edge == &fg.sg.nodes[j]);
  88                         }
  89                 }
  90
  91                 aga_finish(&fg.sg.g);
  92         }
  93 }
  94
  95 #define CHAIN_LEN       8
  96
  97 static void test_chain(void)
  98 {
  99         struct chain_graph cg;
 100         int i, j;
 101
 102         chain_graph_init(&cg, CHAIN_LEN);
 103
 104         for (i = 1; i <= CHAIN_LEN; i++) {
 105                 ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
 106
 107                 for (j = 1; j <= CHAIN_LEN; j++) {
 108                         aga_icost_t cost;
 109
 110                         ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
 111                                               &cost, NULL, NULL));
 112                         ok1(cost == labs(i - j));
 113                 }
 114
 115                 aga_finish(&cg.fg.sg.g);
 116         }
 117 }
 118
 119 static void test_error(void)
 120 {
 121         struct error_graph eg;
 122         aga_icost_t cost;
 123
 124         error_graph_init(&eg);
 125
 126         ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
 127         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
 128         ok1(cost == 0);
 129         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
 130         ok1(cost == 1);
 131         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
 132         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
 133         aga_finish(&eg.sg.g);
 134
 135         ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
 136         ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
 137         ok1(cost == 0);
 138         ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
 139         ok1(aga_error(&eg.sg.g) == -1);
 140         aga_finish(&eg.sg.g);
 141 }
 142
 143 static void test_traversal1(void)
 144 {
 145         struct traversal1_graph t1g;
 146         aga_icost_t cost;
 147
 148         /* This is mostly about testing we correctly handle
 149          * non-reachable nodes */
 150         traversal1_graph_init(&t1g);
 151
 152         ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
 153         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
 154                               &cost, NULL, NULL));
 155         ok1(cost == 0);
 156         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
 157                               &cost, NULL, NULL));
 158         ok1(cost == 1);
 159         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
 160                               &cost, NULL, NULL));
 161         ok1(cost == 1);
 162         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
 163                               &cost, NULL, NULL));
 164         ok1(cost == 2);
 165         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
 166                               &cost, NULL, NULL));
 167         ok1(cost == 2);
 168         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
 169                               &cost, NULL, NULL));
 170         ok1(cost == 2);
 171         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
 172                                NULL, NULL, NULL));
 173         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
 174                                NULL, NULL, NULL));
 175         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
 176                                NULL, NULL, NULL));
 177         aga_finish(&t1g.sg.g);
 178
 179         ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
 180         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
 181                               &cost, NULL, NULL));
 182         ok1(cost == 0);
 183         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
 184                               &cost, NULL, NULL));
 185         ok1(cost == 1);
 186         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
 187                               &cost, NULL, NULL));
 188         ok1(cost == 1);
 189         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
 190                               &cost, NULL, NULL));
 191         ok1(cost == 2);
 192         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
 193                               &cost, NULL, NULL));
 194         ok1(cost == 2);
 195         ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
 196                               &cost, NULL, NULL));
 197         ok1(cost == 2);
 198         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
 199                                NULL, NULL, NULL));
 200         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
 201                                NULL, NULL, NULL));
 202         ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
 203                                NULL, NULL, NULL));
 204         aga_finish(&t1g.sg.g);
 205 }
 206
 207 int main(void)
 208 {
 209         plan_tests(7 + 15
 210                    + FULL_LEN * (1 + FULL_LEN*4)
 211                    + CHAIN_LEN * (1 + CHAIN_LEN*2)
 212                    + 12 + 32);
 213
 214         test_trivial();
 215         test_parallel();
 216         test_full();
 217         test_chain();
 218         test_error();
 219         test_traversal1();
 220
 221         return exit_status();
 222 }