aga,agar: New shortcut2 sample graph and testcases based on it

[ccan] / ccan / agar / test / simple-graphr.h

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index de48ff68fe744f037117c01913016d83adabfd28..2fe98a48776c9c2ddbc8bdd9a85100ad0a9b0685 100644 (file)
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -37,9 +37,11 @@ static const struct adjacency_listr trivial_adjacencyr[] = {
  */
 struct parallel_graphr {
        int nlinks;
+       int cheaplink;
        struct agar_graph gr;
 };
-void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
+                         int cheaplink);
 static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
        {1, {2, 2, 2}},
        {2, {}},
@@ -197,4 +199,45 @@ static const struct adjacency_listr traversal1_adjacency[] = {
        {},
 };
 
+/* Shortcut-1 graph
+ *
+ *   A ---- (3) -----> C
+ *    \             /
+ *     (1)-> B  --(1)
+ *
+ * This provides an example of a graph where the lowest cost path from
+ * (A) to (C) is not the path with the smallest number od edges.
+ */
+struct shortcut1_graphr {
+       struct agar_graph gr;
+};
+void shortcut1_graphr_init(struct shortcut1_graphr *s1gr);
+static const struct adjacency_listr shortcut1_adjacencyr[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+
+/* Shortcut-2 graph
+ *
+ *   A ---- (2) -----> C
+ *    \             /
+ *     (2)-> B  --(-1)
+ *
+ * This provides an example of a graph with a negative edge cost, but
+ * no negative cost cycles (and so still with well defined shortest
+ * paths).
+ */
+struct shortcut2_graphr {
+       struct agar_graph gr;
+};
+void shortcut2_graphr_init(struct shortcut2_graphr *s2gr);
+static const struct adjacency_listr shortcut2_adjacencyr[] = {
+       {1, {3, 2}},
+       {2, {3}},
+       {3, {}},
+       {},
+};
+
 #endif /* _SIMPLE_GRAPHR_H */