git.ozlabs.org Git - ccan/blob - ccan/aga/test/simple-graph.h

   1 #ifndef _TEST_GRAPHS_H
   2 #define _TEST_GRAPHS_H
   3
   4 #include <stdbool.h>
   5
   6 #define MAX_NODES       16
   7 #define MAX_EDGES       16 /* Max edges per node */
   8
   9 struct simple_graph {
  10         struct aga_graph g;
  11         /* We don't use nodes[0] just to avoid awkward -1 and +1 in
  12          * the code */
  13         struct aga_node nodes[MAX_NODES + 1];
  14 };
  15
  16 void simple_graph_init_(struct simple_graph *sg);
  17 #define simple_graph_init(sg_, fefn_, nefn_, eifn_)                     \
  18         do {                                                            \
  19                 simple_graph_init_((sg_));                              \
  20                 aga_init_graph(&(sg_)->g, (fefn_), (nefn_), (eifn_));   \
  21         } while (0)
  22
  23 struct adjacency_list {
  24         int from;
  25         int to[MAX_EDGES];
  26 };
  27
  28 /* Trivial graph
  29  *
  30  *      (A)
  31  *
  32  * The simplest possible graph: one node, no edges
  33  */
  34 struct trivial_graph {
  35         struct simple_graph sg;
  36 };
  37 void trivial_graph_init(struct trivial_graph *tg);
  38 static const struct adjacency_list trivial_adjacency[] = {
  39         {1, {}},
  40         {},
  41 };
  42
  43 /* Parallel graph
  44  *
  45  *          --
  46  *         /  \
  47  *      (A)    => (B)
  48  *         \  /
  49  *          --
  50  *
  51  * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
  52  */
  53 struct parallel_graph {
  54         int nlinks;
  55         int cheaplink;
  56         struct simple_graph sg;
  57 };
  58 void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink);
  59 static const struct adjacency_list parallel_adjacency_nlinks3[] = {
  60         {1, {2, 2, 2}},
  61         {2, {}},
  62         {},
  63 };
  64
  65 /* Full graph
  66  *
  67  * n nodes with an edge from every node to every other node (including
  68  * itself)
  69  */
  70 struct full_graph {
  71         int nnodes;
  72         struct simple_graph sg;
  73 };
  74 void full_graph_init(struct full_graph *fg, int nnodes);
  75 static const struct adjacency_list full_adjacency_5[] = {
  76         {1, {1, 2, 3, 4, 5}},
  77         {2, {1, 2, 3, 4, 5}},
  78         {3, {1, 2, 3, 4, 5}},
  79         {4, {1, 2, 3, 4, 5}},
  80         {5, {1, 2, 3, 4, 5}},
  81         {},
  82 };
  83 struct aga_node *full_first_edge(const struct aga_graph *g,
  84                                  const struct aga_node *node);
  85 struct aga_node *full_next_edge(const struct aga_graph *g,
  86                                 const struct aga_node *node,
  87                                 struct aga_node *edge);
  88
  89
  90 /* Chain graph
  91  *
  92  *  --> --> -->
  93  * A   B   C   D
  94  *  <-- <-- <--
  95  *
  96  * nnodes nodes arranged in a linear sequence, edges from each node to
  97  * the previous and next
  98  */
  99 struct chain_graph {
 100         struct full_graph fg;
 101 };
 102 void chain_graph_init(struct chain_graph *cg, int nnodes);
 103 static const struct adjacency_list chain_adjacency_8[] = {
 104         {1, {2}},
 105         {2, {1, 3}},
 106         {3, {2, 4}},
 107         {4, {3, 5}},
 108         {5, {4, 6}},
 109         {6, {5, 7}},
 110         {7, {6, 8}},
 111         {8, {7}},
 112         {},
 113 };
 114
 115
 116 /* Grid graph(s)
 117  *
 118  * A -> B -> C
 119  * |    |    |
 120  * v    v    v
 121  * D -> E -> F
 122  * |    |    |
 123  * v    v    v
 124  * G -> H -> I
 125  *
 126  * nx * ny nodes arranged in an nx * ny grid.  Depending on
 127  * parameters, edges to the node to the right / down / left / up of
 128  * each node
 129  */
 130 struct grid_graph {
 131         int nx, ny;
 132         bool right, down, left, up;
 133         struct simple_graph sg;
 134 };
 135 void grid_graph_init(struct grid_graph *gg, int nx, int ny,
 136                      bool right, bool down, bool left, bool up);
 137 static const struct adjacency_list grid_adjacency_3x3_rightdown[] = {
 138         {1, {2, 4}},
 139         {2, {3, 5}},
 140         {3, {6}},
 141         {4, {5, 7}},
 142         {5, {6, 8}},
 143         {6, {9}},
 144         {7, {8}},
 145         {8, {9}},
 146         {9, {}},
 147         {},
 148 };
 149 static const struct adjacency_list grid_adjacency_3x3_all[] = {
 150         {1, {2, 4}},
 151         {2, {3, 5, 1}},
 152         {3, {6, 2}},
 153         {4, {5, 7, 1}},
 154         {5, {6, 8, 4, 2}},
 155         {6, {9, 5, 3}},
 156         {7, {8, 4}},
 157         {8, {9, 7, 5}},
 158         {9, {8, 6}},
 159         {},
 160 };
 161
 162 /* Error graph
 163  *
 164  * A -> B
 165  *
 166  * C -> D -> ???
 167  *
 168  * This is for testing reporting of errors by the edge_info function.
 169  * 5 nodes are arranged as above, with the link from D always
 170  * returning an error.
 171  */
 172 struct error_graph {
 173         struct simple_graph sg;
 174 };
 175 void error_graph_init(struct error_graph *eg);
 176 static const struct adjacency_list error_adjacency[] = {
 177         {1, {2}},
 178         {2, {}},
 179         {3, {4}},
 180         {4, {-1}},
 181         {},
 182 };
 183
 184 /* Traversal-1 graph
 185  *
 186  *        -> D <-
 187  *       /       \
 188  *   -> B         G <-
 189  *  /    \       /    \
 190  * A      => E <=      I
 191  *  \    /       \    /
 192  *   -> C         H <-
 193  *       \       /
 194  *        -> F <-
 195  *
 196  * This provides an example of a graph which can't be traversed (with
 197  * DFS or BFS) from a single starting node.  It can be traversed with
 198  * two starting points, but several nodes can be reached from either,
 199  * complicating the logic to avoid double-traversal.
 200  */
 201 struct traversal1_graph {
 202         struct simple_graph sg;
 203 };
 204 void traversal1_graph_init(struct traversal1_graph *t1g);
 205 static const struct adjacency_list traversal1_adjacency[] = {
 206         {1, {2, 3}},
 207         {2, {4, 5}},
 208         {3, {5, 6}},
 209         {4, {}},
 210         {5, {}},
 211         {6, {}},
 212         {7, {5, 4}},
 213         {8, {6, 5}},
 214         {9, {8, 7}},
 215         {},
 216 };
 217
 218 /* Shortcut-1 graph
 219  *
 220  *   A ---- (3) -----> C
 221  *    \             /
 222  *     (1)-> B  --(1)
 223  *
 224  * This provides an example of a graph where the lowest cost path from
 225  * (A) to (C) is not the path with the smallest number od edges.
 226  */
 227 struct shortcut1_graph {
 228         struct simple_graph sg;
 229 };
 230 void shortcut1_graph_init(struct shortcut1_graph *s1g);
 231 static const struct adjacency_list shortcut1_adjacency[] = {
 232         {1, {3, 2}},
 233         {2, {3}},
 234         {3, {}},
 235         {},
 236 };
 237
 238 /* Shortcut-2 graph
 239  *
 240  *   A ---- (2) -----> C
 241  *    \             /
 242  *     (2)-> B  --(-1)
 243  *
 244  * This provides an example of a graph with a negative edge cost, but
 245  * no negative cost cycles (and so still with well defined shortest
 246  * paths).
 247  */
 248 struct shortcut2_graph {
 249         struct simple_graph sg;
 250 };
 251 void shortcut2_graph_init(struct shortcut2_graph *s2g);
 252 static const struct adjacency_list shortcut2_adjacency[] = {
 253         {1, {3, 2}},
 254         {2, {3}},
 255         {3, {}},
 256         {},
 257 };
 258
 259 /* Negacycle graph
 260  *
 261  *  A <---- (-3) ----- C
 262  *   \                 ^
 263  *    (1)->  B -- (1)-/
 264  *
 265  * Graph with a negative length cycle, and so lacking well-defined shortest paths.
 266  */
 267 struct negacycle_graph {
 268         struct simple_graph sg;
 269 };
 270 void negacycle_graph_init(struct negacycle_graph *ng);
 271 static const struct adjacency_list negacycle_adjacency[] = {
 272         {1, {2}},
 273         {2, {3}},
 274         {3, {1}},
 275         {},
 276 };
 277
 278 #endif /* _TEST_GRAPHS_H */