X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Ftest%2Fsimple-graph.h;h=b8da3ad999045bc9207b59871a56fae691a13120;hb=c82067334270187ef77d50715a838e3dbbdfea3c;hp=57f87a881cc38961b28d2eccfb9787aa76752956;hpb=a2eaae42b58a44d6f88f5e20e4a7d7cdbde9edae;p=ccan

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 57f87a88..b8da3ad9 100644
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -215,4 +215,45 @@ static const struct adjacency_list 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_graph {
+	struct simple_graph sg;
+};
+void shortcut1_graph_init(struct shortcut1_graph *s1g);
+static const struct adjacency_list shortcut1_adjacency[] = {
+	{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_graph {
+	struct simple_graph sg;
+};
+void shortcut2_graph_init(struct shortcut2_graph *s2g);
+static const struct adjacency_list shortcut2_adjacency[] = {
+	{1, {3, 2}},
+	{2, {3}},
+	{3, {}},
+	{},
+};
+
 #endif /* _TEST_GRAPHS_H */