*/
struct parallel_graph {
int nlinks;
+ int cheaplink;
struct simple_graph sg;
};
-void parallel_graph_init(struct parallel_graph *pg, int nlinks);
+void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink);
static const struct adjacency_list parallel_adjacency_nlinks3[] = {
{1, {2, 2, 2}},
{2, {}},
{},
};
+/* 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, {}},
+ {},
+};
+
+/* 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 */