X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fagar%2Ftest%2Fsimple-graphr.h;h=21cae6a3497c9900ba010dd445f4acdd6203f649;hb=318edb2466a24a2eadcfd05fa83ae29c0e8aae03;hp=de48ff68fe744f037117c01913016d83adabfd28;hpb=c2966d1879c825cfaf0e7d6848a5da052ee4a038;p=ccan

diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index de48ff68..21cae6a3 100644
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -19,7 +19,7 @@ struct adjacency_listr {
 struct trivial_graphr {
 	struct agar_graph gr;
 };
-void trivial_graphr_init(struct trivial_graphr *tgr);
+extern struct trivial_graphr trivial_graphr;
 static const struct adjacency_listr trivial_adjacencyr[] = {
 	{1, {}},
 	{},
@@ -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, {}},
@@ -154,7 +156,7 @@ static const struct adjacency_listr grid_adjacencyr_3x3_all[] = {
 struct error_graphr {
 	struct agar_graph gr;
 };
-void error_graphr_init(struct error_graphr *eg);
+extern struct error_graphr error_graphr;
 static const struct adjacency_listr error_adjacencyr[] = {
 	{1, {2}},
 	{2, {}},
@@ -183,7 +185,7 @@ static const struct adjacency_listr error_adjacencyr[] = {
 struct traversal1_graphr {
 	struct agar_graph gr;
 };
-void traversal1_graphr_init(struct traversal1_graphr *t1gr);
+extern struct traversal1_graphr traversal1_graphr;
 static const struct adjacency_listr traversal1_adjacency[] = {
 	{1, {2, 3}},
 	{2, {4, 5}},
@@ -197,4 +199,64 @@ 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;
+};
+extern struct shortcut1_graphr shortcut1_graphr;
+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;
+};
+extern struct shortcut2_graphr shortcut2_graphr;
+static const struct adjacency_listr shortcut2_adjacencyr[] = {
+	{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_graphr {
+	struct agar_graph gr;
+};
+extern struct negacycle_graphr negacycle_graphr;
+static const struct adjacency_listr negacycle_adjacencyr[] = {
+	{1, {2}},
+	{2, {3}},
+	{3, {1}},
+	{},
+};
+
 #endif /* _SIMPLE_GRAPHR_H */