git.ozlabs.org Git - ccan/blob - ccan/agar/test/simple-graphr.h

   1 #ifndef _SIMPLE_GRAPHR_H
   2 #define _SIMPLE_GRAPHR_H
   3
   4 #include <stdbool.h>
   5
   6 #define MAX_EDGES       16 /* Max edges per node */
   7
   8 struct adjacency_listr {
   9         int from;
  10         int to[MAX_EDGES];
  11 };
  12
  13 /* Trivial graph
  14  *
  15  *      (A)
  16  *
  17  * The simplest possible graph: one node, no edges
  18  */
  19 struct trivial_graphr {
  20         struct agar_graph gr;
  21 };
  22 void trivial_graphr_init(struct trivial_graphr *tgr);
  23 static const struct adjacency_listr trivial_adjacencyr[] = {
  24         {1, {}},
  25         {},
  26 };
  27
  28 /* Parallel graph
  29  *
  30  *          --
  31  *         /  \
  32  *      (A)    => (B)
  33  *         \  /
  34  *          --
  35  *
  36  * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
  37  */
  38 struct parallel_graphr {
  39         int nlinks;
  40         struct agar_graph gr;
  41 };
  42 void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
  43 static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
  44         {1, {2, 2, 2}},
  45         {2, {}},
  46         {},
  47 };
  48
  49 /* Full graph
  50  *
  51  * n nodes with an edge from every node to every other node (including
  52  * itself)
  53  */
  54 struct full_graphr {
  55         int nnodes;
  56         struct agar_graph gr;
  57 };
  58 void full_graphr_init(struct full_graphr *fgr, int nnodes);
  59 static const struct adjacency_listr full_adjacencyr_5[] = {
  60         {1, {1, 2, 3, 4, 5}},
  61         {2, {1, 2, 3, 4, 5}},
  62         {3, {1, 2, 3, 4, 5}},
  63         {4, {1, 2, 3, 4, 5}},
  64         {5, {1, 2, 3, 4, 5}},
  65         {},
  66 };
  67 const void *full_first_edge_r(const struct agar_graph *gr, const void *nr);
  68 const void *full_next_edge_r(const struct agar_graph *gr,
  69                              const void *nr, const void *e);
  70
  71
  72 /* Chain graph
  73  *
  74  *  --> --> -->
  75  * A   B   C   D
  76  *  <-- <-- <--
  77  *
  78  * nnodes nodes arranged in a linear sequence, edges from each node to
  79  * the previous and next
  80  */
  81 struct chain_graphr {
  82         struct full_graphr fgr;
  83 };
  84 void chain_graphr_init(struct chain_graphr *cgr, int nnodes);
  85 static const struct adjacency_listr chain_adjacencyr_8[] = {
  86         {1, {2}},
  87         {2, {1, 3}},
  88         {3, {2, 4}},
  89         {4, {3, 5}},
  90         {5, {4, 6}},
  91         {6, {5, 7}},
  92         {7, {6, 8}},
  93         {8, {7}},
  94         {},
  95 };
  96
  97
  98 /* Grid graph(s)
  99  *
 100  * A -> B -> C
 101  * |    |    |
 102  * v    v    v
 103  * D -> E -> F
 104  * |    |    |
 105  * v    v    v
 106  * G -> H -> I
 107  *
 108  * nx * ny nodes arranged in an nx * ny grid.  Depending on
 109  * parameters, edges to the node to the right / down / left / up of
 110  * each node
 111  */
 112 struct grid_graphr {
 113         int nx, ny;
 114         bool right, down, left, up;
 115         struct agar_graph gr;
 116 };
 117 void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny,
 118                      bool right, bool down, bool left, bool up);
 119 static const struct adjacency_listr grid_adjacencyr_3x3_rightdown[] = {
 120         {1, {2, 4}},
 121         {2, {3, 5}},
 122         {3, {6}},
 123         {4, {5, 7}},
 124         {5, {6, 8}},
 125         {6, {9}},
 126         {7, {8}},
 127         {8, {9}},
 128         {9, {}},
 129         {},
 130 };
 131 static const struct adjacency_listr grid_adjacencyr_3x3_all[] = {
 132         {1, {2, 4}},
 133         {2, {3, 5, 1}},
 134         {3, {6, 2}},
 135         {4, {5, 7, 1}},
 136         {5, {6, 8, 4, 2}},
 137         {6, {9, 5, 3}},
 138         {7, {8, 4}},
 139         {8, {9, 7, 5}},
 140         {9, {8, 6}},
 141         {},
 142 };
 143
 144 /* Error graph
 145  *
 146  * A -> B
 147  *
 148  * C -> D -> ???
 149  *
 150  * This is for testing reporting of errors by the edge_info function.
 151  * 5 nodes are arranged as above, with the link from D always
 152  * returning an error.
 153  */
 154 struct error_graphr {
 155         struct agar_graph gr;
 156 };
 157 void error_graphr_init(struct error_graphr *eg);
 158 static const struct adjacency_listr error_adjacencyr[] = {
 159         {1, {2}},
 160         {2, {}},
 161         {3, {4}},
 162         {4, {-1}},
 163         {},
 164 };
 165
 166 /* Traversal-1 graph
 167  *
 168  *        -> D <-
 169  *       /       \
 170  *   -> B         G <-
 171  *  /    \       /    \
 172  * A      => E <=      I
 173  *  \    /       \    /
 174  *   -> C         H <-
 175  *       \       /
 176  *        -> F <-
 177  *
 178  * This provides an example of a graph which can't be traversed (with
 179  * DFS or BFS) from a single starting node.  It can be traversed with
 180  * two starting points, but several nodes can be reached from either,
 181  * complicating the logic to avoid double-traversal.
 182  */
 183 struct traversal1_graphr {
 184         struct agar_graph gr;
 185 };
 186 void traversal1_graphr_init(struct traversal1_graphr *t1gr);
 187 static const struct adjacency_listr traversal1_adjacency[] = {
 188         {1, {2, 3}},
 189         {2, {4, 5}},
 190         {3, {5, 6}},
 191         {4, {}},
 192         {5, {}},
 193         {6, {}},
 194         {7, {5, 4}},
 195         {8, {6, 5}},
 196         {9, {8, 7}},
 197         {},
 198 };
 199
 200 #endif /* _SIMPLE_GRAPHR_H */