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, {}},
{},
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, {}},
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}},
struct shortcut1_graphr {
struct agar_graph gr;
};
-void shortcut1_graphr_init(struct shortcut1_graphr *s1gr);
+extern struct shortcut1_graphr shortcut1_graphr;
static const struct adjacency_listr shortcut1_adjacencyr[] = {
{1, {3, 2}},
{2, {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 */