end
end
+ # Build a path (or circuit) from the vertex `start` that visits every edge exactly once.
+ #
+ # ~~~
+ # var g = new HashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.eulerian_path(1) == [1, 2, 3, 4]
+ # ~~~
+ fun eulerian_path(start: V): Array[V]
+ do
+ var visited = new HashDigraph[V]
+ visited.add_graph(self)
+ return visited.remove_eulerian_path(start)
+ end
+
# Returns the distance between `u` and `v`
#
# If no path exists between `u` and `v`, it returns null. It is not
do
for a in arcs do add_arc(a[0], a[1])
end
+
+ # Add all vertices and arcs from the `other` graph.
+ #
+ # ~~~
+ # var g1 = new HashDigraph[Int]
+ # var arcs1 = [[0,1], [1,2]]
+ # g1.add_arcs(arcs1)
+ # g1.add_arcs(arcs1)
+ # g1.add_vertex(3)
+ # var g2 = new HashDigraph[Int]
+ # var arcs2 = [[0,1], [1,4]]
+ # g2.add_arcs(arcs2)
+ # g2.add_vertex(5)
+ # g2.add_graph(g1)
+ # assert g2.vertices.has_exactly([0, 1, 2, 3, 4, 5])
+ # var arcs3 = [[0,1], [1,2], [1,4]]
+ # assert g2.arcs.has_exactly(arcs3)
+ # ~~~
+ fun add_graph(other: Digraph[V])
+ do
+ for v in other.vertices do
+ add_vertex(v)
+ for w in other.successors(v) do
+ add_arc(v, w)
+ end
+ end
+ end
+
+ # Build a path (or circuit) that removes every edge exactly once.
+ #
+ # See `eulerian_path` for details
+ fun remove_eulerian_path(start: V): Array[V]
+ do
+ var stack = new Array[V]
+ var path = new Array[V]
+ var current = start
+ loop
+ if out_degree(current) == 0 then
+ path.unshift current
+ if stack.is_empty then break
+ current = stack.pop
+ else
+ stack.add current
+ var n = successors(current).first
+ remove_arc(current, n)
+ current = n
+ end
+ end
+ return path
+ end
end
# A directed graph represented by hash maps
class HashDigraph[V: Object]