X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fagar%2Ftest%2Fsimple-graphr.h;fp=ccan%2Fagar%2Ftest%2Fsimple-graphr.h;h=de48ff68fe744f037117c01913016d83adabfd28;hb=c2966d1879c825cfaf0e7d6848a5da052ee4a038;hp=0000000000000000000000000000000000000000;hpb=06162212353c882249d7e207756ea81ea645fc30;p=ccan

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
new file mode 100644
index 00000000..de48ff68
--- /dev/null
+++ b/ccan/agar/test/simple-graphr.h
@@ -0,0 +1,200 @@
+#ifndef _SIMPLE_GRAPHR_H
+#define _SIMPLE_GRAPHR_H
+
+#include <stdbool.h>
+
+#define MAX_EDGES	16 /* Max edges per node */
+
+struct adjacency_listr {
+	int from;
+	int to[MAX_EDGES];
+};
+
+/* Trivial graph
+ *
+ *	(A)
+ *
+ * The simplest possible graph: one node, no edges
+ */
+struct trivial_graphr {
+	struct agar_graph gr;
+};
+void trivial_graphr_init(struct trivial_graphr *tgr);
+static const struct adjacency_listr trivial_adjacencyr[] = {
+	{1, {}},
+	{},
+};
+
+/* Parallel graph
+ *
+ *          --
+ *         /  \
+ *      (A)    => (B)
+ *         \  /
+ *          --
+ *
+ * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
+ */
+struct parallel_graphr {
+	int nlinks;
+	struct agar_graph gr;
+};
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
+static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
+	{1, {2, 2, 2}},
+	{2, {}},
+	{},
+};
+
+/* Full graph
+ *
+ * n nodes with an edge from every node to every other node (including
+ * itself)
+ */
+struct full_graphr {
+	int nnodes;
+	struct agar_graph gr;
+};
+void full_graphr_init(struct full_graphr *fgr, int nnodes);
+static const struct adjacency_listr full_adjacencyr_5[] = {
+	{1, {1, 2, 3, 4, 5}},
+	{2, {1, 2, 3, 4, 5}},
+	{3, {1, 2, 3, 4, 5}},
+	{4, {1, 2, 3, 4, 5}},
+	{5, {1, 2, 3, 4, 5}},
+	{},
+};
+const void *full_first_edge_r(const struct agar_graph *gr, const void *nr);
+const void *full_next_edge_r(const struct agar_graph *gr,
+			     const void *nr, const void *e);
+
+
+/* Chain graph
+ *
+ *  --> --> -->
+ * A   B   C   D
+ *  <-- <-- <--
+ *
+ * nnodes nodes arranged in a linear sequence, edges from each node to
+ * the previous and next
+ */
+struct chain_graphr {
+	struct full_graphr fgr;
+};
+void chain_graphr_init(struct chain_graphr *cgr, int nnodes);
+static const struct adjacency_listr chain_adjacencyr_8[] = {
+	{1, {2}},
+	{2, {1, 3}},
+	{3, {2, 4}},
+	{4, {3, 5}},
+	{5, {4, 6}},
+	{6, {5, 7}},
+	{7, {6, 8}},
+	{8, {7}},
+	{},
+};
+
+
+/* Grid graph(s)
+ *
+ * A -> B -> C
+ * |    |    |
+ * v    v    v
+ * D -> E -> F
+ * |    |    |
+ * v    v    v
+ * G -> H -> I
+ *
+ * nx * ny nodes arranged in an nx * ny grid.  Depending on
+ * parameters, edges to the node to the right / down / left / up of
+ * each node
+ */
+struct grid_graphr {
+	int nx, ny;
+	bool right, down, left, up;
+	struct agar_graph gr;
+};
+void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny,
+		     bool right, bool down, bool left, bool up);
+static const struct adjacency_listr grid_adjacencyr_3x3_rightdown[] = {
+	{1, {2, 4}},
+	{2, {3, 5}},
+	{3, {6}},
+	{4, {5, 7}},
+	{5, {6, 8}},
+	{6, {9}},
+	{7, {8}},
+	{8, {9}},
+	{9, {}},
+	{},
+};
+static const struct adjacency_listr grid_adjacencyr_3x3_all[] = {
+	{1, {2, 4}},
+	{2, {3, 5, 1}},
+	{3, {6, 2}},
+	{4, {5, 7, 1}},
+	{5, {6, 8, 4, 2}},
+	{6, {9, 5, 3}},
+	{7, {8, 4}},
+	{8, {9, 7, 5}},
+	{9, {8, 6}},
+	{},
+};
+
+/* Error graph
+ *
+ * A -> B
+ *
+ * C -> D -> ???
+ *
+ * This is for testing reporting of errors by the edge_info function.
+ * 5 nodes are arranged as above, with the link from D always
+ * returning an error.
+ */
+struct error_graphr {
+	struct agar_graph gr;
+};
+void error_graphr_init(struct error_graphr *eg);
+static const struct adjacency_listr error_adjacencyr[] = {
+	{1, {2}},
+	{2, {}},
+	{3, {4}},
+	{4, {-1}},
+	{},
+};
+
+/* Traversal-1 graph
+ *
+ *        -> D <-
+ *       /       \
+ *   -> B         G <-
+ *  /    \       /    \
+ * A      => E <=      I
+ *  \    /       \    /
+ *   -> C         H <-
+ *       \       /
+ *        -> F <-
+ *
+ * This provides an example of a graph which can't be traversed (with
+ * DFS or BFS) from a single starting node.  It can be traversed with
+ * two starting points, but several nodes can be reached from either,
+ * complicating the logic to avoid double-traversal.
+ */
+struct traversal1_graphr {
+	struct agar_graph gr;
+};
+void traversal1_graphr_init(struct traversal1_graphr *t1gr);
+static const struct adjacency_listr traversal1_adjacency[] = {
+	{1, {2, 3}},
+	{2, {4, 5}},
+	{3, {5, 6}},
+	{4, {}},
+	{5, {}},
+	{6, {}},
+	{7, {5, 4}},
+	{8, {6, 5}},
+	{9, {8, 7}},
+	{},
+};
+
+#endif /* _SIMPLE_GRAPHR_H */