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         struct simple_graph sg;
  56 };
  57 void parallel_graph_init(struct parallel_graph *pg, int nlinks);
  58 static const struct adjacency_list parallel_adjacency_nlinks3[] = {
  59         {1, {2, 2, 2}},
  60         {2, {}},
  61         {},
  62 };
  63
  64 /* Full graph
  65  *
  66  * n nodes with an edge from every node to every other node (including
  67  * itself)
  68  */
  69 struct full_graph {
  70         int nnodes;
  71         struct simple_graph sg;
  72 };
  73 void full_graph_init(struct full_graph *fg, int nnodes);
  74 static const struct adjacency_list full_adjacency_5[] = {
  75         {1, {1, 2, 3, 4, 5}},
  76         {2, {1, 2, 3, 4, 5}},
  77         {3, {1, 2, 3, 4, 5}},
  78         {4, {1, 2, 3, 4, 5}},
  79         {5, {1, 2, 3, 4, 5}},
  80         {},
  81 };
  82 struct aga_node *full_first_edge(const struct aga_graph *g,
  83                                  const struct aga_node *node);
  84 struct aga_node *full_next_edge(const struct aga_graph *g,
  85                                 const struct aga_node *node,
  86                                 struct aga_node *edge);
  87
  88
  89 /* Chain graph
  90  *
  91  *  --> --> -->
  92  * A   B   C   D
  93  *  <-- <-- <--
  94  *
  95  * nnodes nodes arranged in a linear sequence, edges from each node to
  96  * the previous and next
  97  */
  98 struct chain_graph {
  99         struct full_graph fg;
 100 };
 101 void chain_graph_init(struct chain_graph *cg, int nnodes);
 102 static const struct adjacency_list chain_adjacency_8[] = {
 103         {1, {2}},
 104         {2, {1, 3}},
 105         {3, {2, 4}},
 106         {4, {3, 5}},
 107         {5, {4, 6}},
 108         {6, {5, 7}},
 109         {7, {6, 8}},
 110         {8, {7}},
 111         {},
 112 };
 113
 114
 115 /* Grid graph(s)
 116  *
 117  * A -> B -> C
 118  * |    |    |
 119  * v    v    v
 120  * D -> E -> F
 121  * |    |    |
 122  * v    v    v
 123  * G -> H -> I
 124  *
 125  * nx * ny nodes arranged in an nx * ny grid.  Depending on
 126  * parameters, edges to the node to the right / down / left / up of
 127  * each node
 128  */
 129 struct grid_graph {
 130         int nx, ny;
 131         bool right, down, left, up;
 132         struct simple_graph sg;
 133 };
 134 void grid_graph_init(struct grid_graph *gg, int nx, int ny,
 135                      bool right, bool down, bool left, bool up);
 136 static const struct adjacency_list grid_adjacency_3x3_rightdown[] = {
 137         {1, {2, 4}},
 138         {2, {3, 5}},
 139         {3, {6}},
 140         {4, {5, 7}},
 141         {5, {6, 8}},
 142         {6, {9}},
 143         {7, {8}},
 144         {8, {9}},
 145         {9, {}},
 146         {},
 147 };
 148 static const struct adjacency_list grid_adjacency_3x3_all[] = {
 149         {1, {2, 4}},
 150         {2, {3, 5, 1}},
 151         {3, {6, 2}},
 152         {4, {5, 7, 1}},
 153         {5, {6, 8, 4, 2}},
 154         {6, {9, 5, 3}},
 155         {7, {8, 4}},
 156         {8, {9, 7, 5}},
 157         {9, {8, 6}},
 158         {},
 159 };
 160
 161 /* Error graph
 162  *
 163  * A -> B
 164  *
 165  * C -> D -> ???
 166  *
 167  * This is for testing reporting of errors by the edge_info function.
 168  * 5 nodes are arranged as above, with the link from D always
 169  * returning an error.
 170  */
 171 struct error_graph {
 172         struct simple_graph sg;
 173 };
 174 void error_graph_init(struct error_graph *eg);
 175 static const struct adjacency_list error_adjacency[] = {
 176         {1, {2}},
 177         {2, {}},
 178         {3, {4}},
 179         {4, {-1}},
 180         {},
 181 };
 182
 183 /* Traversal-1 graph
 184  *
 185  *        -> D <-
 186  *       /       \
 187  *   -> B         G <-
 188  *  /    \       /    \
 189  * A      => E <=      I
 190  *  \    /       \    /
 191  *   -> C         H <-
 192  *       \       /
 193  *        -> F <-
 194  *
 195  * This provides an example of a graph which can't be traversed (with
 196  * DFS or BFS) from a single starting node.  It can be traversed with
 197  * two starting points, but several nodes can be reached from either,
 198  * complicating the logic to avoid double-traversal.
 199  */
 200 struct traversal1_graph {
 201         struct simple_graph sg;
 202 };
 203 void traversal1_graph_init(struct traversal1_graph *t1g);
 204 static const struct adjacency_list traversal1_adjacency[] = {
 205         {1, {2, 3}},
 206         {2, {4, 5}},
 207         {3, {5, 6}},
 208         {4, {}},
 209         {5, {}},
 210         {6, {}},
 211         {7, {5, 4}},
 212         {8, {6, 5}},
 213         {9, {8, 7}},
 214         {},
 215 };
 216
 217 #endif /* _TEST_GRAPHS_H */