X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Faga%2Ftest%2Fsimple-graph.h;h=5808993ac2c203364c73b6ffdbbf8f09ebfc95fd;hb=318edb2466a24a2eadcfd05fa83ae29c0e8aae03;hp=77ba2a64898dd27661cd7694d6e83e027fb4200a;hpb=13430d4e252edbe0c202237e5a956670da1efe0b;p=ccan

diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 77ba2a64..5808993a 100644
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -235,4 +235,44 @@ static const struct adjacency_list shortcut1_adjacency[] = {
 	{},
 };
 
+/* 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, {}},
+	{},
+};
+
+/* Negacycle graph
+ *
+ *  A <---- (-3) ----- C
+ *   \                 ^
+ *    (1)->  B -- (1)-/
+ *
+ * Graph with a negative length cycle, and so lacking well-defined shortest paths.
+ */
+struct negacycle_graph {
+	struct simple_graph sg;
+};
+void negacycle_graph_init(struct negacycle_graph *ng);
+static const struct adjacency_list negacycle_adjacency[] = {
+	{1, {2}},
+	{2, {3}},
+	{3, {1}},
+	{},
+};
+
 #endif /* _TEST_GRAPHS_H */