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 extern struct trivial_graphr trivial_graphr;
  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         int cheaplink;
  41         struct agar_graph gr;
  42 };
  43 void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
  44                           int cheaplink);
  45 static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
  46         {1, {2, 2, 2}},
  47         {2, {}},
  48         {},
  49 };
  50
  51 /* Full graph
  52  *
  53  * n nodes with an edge from every node to every other node (including
  54  * itself)
  55  */
  56 struct full_graphr {
  57         int nnodes;
  58         struct agar_graph gr;
  59 };
  60 void full_graphr_init(struct full_graphr *fgr, int nnodes);
  61 static const struct adjacency_listr full_adjacencyr_5[] = {
  62         {1, {1, 2, 3, 4, 5}},
  63         {2, {1, 2, 3, 4, 5}},
  64         {3, {1, 2, 3, 4, 5}},
  65         {4, {1, 2, 3, 4, 5}},
  66         {5, {1, 2, 3, 4, 5}},
  67         {},
  68 };
  69 const void *full_first_edge_r(const struct agar_graph *gr, const void *nr);
  70 const void *full_next_edge_r(const struct agar_graph *gr,
  71                              const void *nr, const void *e);
  72
  73
  74 /* Chain graph
  75  *
  76  *  --> --> -->
  77  * A   B   C   D
  78  *  <-- <-- <--
  79  *
  80  * nnodes nodes arranged in a linear sequence, edges from each node to
  81  * the previous and next
  82  */
  83 struct chain_graphr {
  84         struct full_graphr fgr;
  85 };
  86 void chain_graphr_init(struct chain_graphr *cgr, int nnodes);
  87 static const struct adjacency_listr chain_adjacencyr_8[] = {
  88         {1, {2}},
  89         {2, {1, 3}},
  90         {3, {2, 4}},
  91         {4, {3, 5}},
  92         {5, {4, 6}},
  93         {6, {5, 7}},
  94         {7, {6, 8}},
  95         {8, {7}},
  96         {},
  97 };
  98
  99
 100 /* Grid graph(s)
 101  *
 102  * A -> B -> C
 103  * |    |    |
 104  * v    v    v
 105  * D -> E -> F
 106  * |    |    |
 107  * v    v    v
 108  * G -> H -> I
 109  *
 110  * nx * ny nodes arranged in an nx * ny grid.  Depending on
 111  * parameters, edges to the node to the right / down / left / up of
 112  * each node
 113  */
 114 struct grid_graphr {
 115         int nx, ny;
 116         bool right, down, left, up;
 117         struct agar_graph gr;
 118 };
 119 void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny,
 120                      bool right, bool down, bool left, bool up);
 121 static const struct adjacency_listr grid_adjacencyr_3x3_rightdown[] = {
 122         {1, {2, 4}},
 123         {2, {3, 5}},
 124         {3, {6}},
 125         {4, {5, 7}},
 126         {5, {6, 8}},
 127         {6, {9}},
 128         {7, {8}},
 129         {8, {9}},
 130         {9, {}},
 131         {},
 132 };
 133 static const struct adjacency_listr grid_adjacencyr_3x3_all[] = {
 134         {1, {2, 4}},
 135         {2, {3, 5, 1}},
 136         {3, {6, 2}},
 137         {4, {5, 7, 1}},
 138         {5, {6, 8, 4, 2}},
 139         {6, {9, 5, 3}},
 140         {7, {8, 4}},
 141         {8, {9, 7, 5}},
 142         {9, {8, 6}},
 143         {},
 144 };
 145
 146 /* Error graph
 147  *
 148  * A -> B
 149  *
 150  * C -> D -> ???
 151  *
 152  * This is for testing reporting of errors by the edge_info function.
 153  * 5 nodes are arranged as above, with the link from D always
 154  * returning an error.
 155  */
 156 struct error_graphr {
 157         struct agar_graph gr;
 158 };
 159 extern struct error_graphr error_graphr;
 160 static const struct adjacency_listr error_adjacencyr[] = {
 161         {1, {2}},
 162         {2, {}},
 163         {3, {4}},
 164         {4, {-1}},
 165         {},
 166 };
 167
 168 /* Traversal-1 graph
 169  *
 170  *        -> D <-
 171  *       /       \
 172  *   -> B         G <-
 173  *  /    \       /    \
 174  * A      => E <=      I
 175  *  \    /       \    /
 176  *   -> C         H <-
 177  *       \       /
 178  *        -> F <-
 179  *
 180  * This provides an example of a graph which can't be traversed (with
 181  * DFS or BFS) from a single starting node.  It can be traversed with
 182  * two starting points, but several nodes can be reached from either,
 183  * complicating the logic to avoid double-traversal.
 184  */
 185 struct traversal1_graphr {
 186         struct agar_graph gr;
 187 };
 188 extern struct traversal1_graphr traversal1_graphr;
 189 static const struct adjacency_listr traversal1_adjacency[] = {
 190         {1, {2, 3}},
 191         {2, {4, 5}},
 192         {3, {5, 6}},
 193         {4, {}},
 194         {5, {}},
 195         {6, {}},
 196         {7, {5, 4}},
 197         {8, {6, 5}},
 198         {9, {8, 7}},
 199         {},
 200 };
 201
 202 /* Shortcut-1 graph
 203  *
 204  *   A ---- (3) -----> C
 205  *    \             /
 206  *     (1)-> B  --(1)
 207  *
 208  * This provides an example of a graph where the lowest cost path from
 209  * (A) to (C) is not the path with the smallest number od edges.
 210  */
 211 struct shortcut1_graphr {
 212         struct agar_graph gr;
 213 };
 214 extern struct shortcut1_graphr shortcut1_graphr;
 215 static const struct adjacency_listr shortcut1_adjacencyr[] = {
 216         {1, {3, 2}},
 217         {2, {3}},
 218         {3, {}},
 219         {},
 220 };
 221
 222 /* Shortcut-2 graph
 223  *
 224  *   A ---- (2) -----> C
 225  *    \             /
 226  *     (2)-> B  --(-1)
 227  *
 228  * This provides an example of a graph with a negative edge cost, but
 229  * no negative cost cycles (and so still with well defined shortest
 230  * paths).
 231  */
 232 struct shortcut2_graphr {
 233         struct agar_graph gr;
 234 };
 235 extern struct shortcut2_graphr shortcut2_graphr;
 236 static const struct adjacency_listr shortcut2_adjacencyr[] = {
 237         {1, {3, 2}},
 238         {2, {3}},
 239         {3, {}},
 240         {},
 241 };
 242
 243 #endif /* _SIMPLE_GRAPHR_H */