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
+
+ # Cache of all predecessors for each vertex.
+ # This attribute are lazy to compute the list use `get_all_predecessors` for each needed vertexe.
+ # Warning the cache must be invalidated after `add_arc`
+ private var cache_all_predecessors = new HashMap[V, Set[V]]
+
+ # Cache of all successors for each vertex.
+ # This attribute are lazy to compute the list use `get_all_successors` for each needed vertexe.
+ # Warning the cache must be invalidated after `add_arc`
+ private var cache_all_successors = new HashMap[V, Set[V]]
+
+ # Invalid all cache `cache_all_predecessors` and `cache_all_successors`
+ private fun invalidated_all_cache
+ do
+ if not cache_all_successors.is_empty then cache_all_successors = new HashMap[V, Set[V]]
+ if not cache_all_predecessors.is_empty then cache_all_predecessors = new HashMap[V, Set[V]]
+ end
+
+ # Returns the all predecessors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # Returns an empty Array is the `u` does not exist
+ # ~~~
+ # var g = new HashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.get_all_predecessors(4).has(4)
+ # assert g.get_all_predecessors(4).has(3)
+ # assert g.get_all_predecessors(4).has(2)
+ # assert g.get_all_predecessors(4).has(1)
+ # ~~~
+ fun get_all_predecessors(u: V): Array[V]
+ do
+ if not vertices.has(u) then return new Array[V]
+ if not cache_all_predecessors.has_key(u) then compute_all_link(u)
+ return cache_all_predecessors[u].clone.to_a
+ end
+
+ # Returns the all successors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # Returns an empty Array is the `u` does not exist
+ # ~~~
+ # var g = new HashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.get_all_successors(2).has(3)
+ # assert g.get_all_successors(2).has(4)
+ # assert g.get_all_successors(2).has(2)
+ # ~~~
+ fun get_all_successors(u: V): Array[V]
+ do
+ if not vertices.has(u) then return new Array[V]
+ if not cache_all_successors.has_key(u) then compute_all_link(u)
+ return cache_all_successors[u].clone.to_a
+ end
+
+ # Compute all succesors and all predecessors for the given `u`
+ # The result is stocked in `cache_all_predecessors` and `cache_all_predecessors`
+ private fun compute_all_link(u: V)
+ do
+ if not vertices.has(u) then return
+ if not cache_all_predecessors.has_key(u) then cache_all_predecessors[u] = new Set[V]
+ if not cache_all_successors.has_key(u) then cache_all_successors[u] = new Set[V]
+ for v in vertices do
+ if distance(v, u) != null then cache_all_predecessors[u].add(v)
+ if distance(u, v) != null then cache_all_successors[u].add(v)
+ end
+ end
end
# A directed graph represented by hash maps
class HashDigraph[V: Object]
if not has_arc(u, v) then
incoming_vertices_map[v].add(u)
outgoing_vertices_map[u].add(v)
+ invalidated_all_cache
number_of_arcs += 1
end
end
redef fun vertices_iterator: Iterator[V] do return outgoing_vertices_map.keys.iterator
end
+
+# A reflexive directed graph
+# i.e an element is in relation with itself (ie is implies `self.has_arc(u,u)`))
+# This class avoids manually adding the reflexive vertices and at the same time it's avoids adding useless data to the hashmap.
+class ReflexiveHashDigraph[V: Object]
+ super HashDigraph[V]
+
+ # Adds the arc (u,v) to this graph.
+ # if `u` is the same as `v` do nothing
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(3, 1)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(1,2)
+ # assert g.has_arc(3,1)
+ # ~~~
+ redef fun add_arc(u, v)
+ do
+ # Check `u` is the same as `v`
+ if u != v then
+ super
+ end
+ end
+
+ # Is (u,v) an arc in this graph?
+ # If `u` is the same as `v` return true
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(3, 1)
+ # g.add_vertex(4)
+ # assert g.has_arc(1,1)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(2,2)
+ # assert g.has_arc(3,2) == false
+ # assert g.has_arc(4,4)
+ # ~~~
+ redef fun has_arc(u, v)
+ do
+ return u == v or super
+ end
+
+ redef fun show_dot
+ do
+ var f = new ProcessWriter("dot", "-Txlib")
+ f.write to_dot
+ f.close
+ f.wait
+ end
+
+ # Returns a shortest path from vertex `u` to `v`.
+ #
+ # If `u` is the same as `v` return `[u]`
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.a_shortest_path(1, 4).length == 4
+ # assert g.a_shortest_path(1, 1).length == 1
+ # ~~~
+ redef fun a_shortest_path(u, v)
+ do
+ if u == v then
+ var path = new List[V]
+ path.add(u)
+ return path
+ end
+ return super
+ end
+
+ # Returns the distance between `u` and `v`
+ #
+ # If `u` is the same as `v` return `1`
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 4)
+ # assert g.distance(1, 1) == 1
+ # assert g.distance(2, 2) == 1
+ # ~~~
+ redef fun distance(u, v)
+ do
+ if has_arc(u, v) and u == v then return 1
+ return super
+ end
+
+ # Returns the predecessors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 1)
+ # assert g.predecessors(2).has(1)
+ # assert g.predecessors(2).has(2)
+ # ~~~
+ redef fun predecessors(u)
+ do
+ var super_predecessors = super
+ if incoming_vertices_map.has_key(u) then super_predecessors.add(u)
+ return super_predecessors
+ end
+
+ # Returns the successors of `u`.
+ #
+ # `u` is include in the returned collection
+ #
+ # ~~~
+ # var g = new ReflexiveHashDigraph[Int]
+ # g.add_arc(1, 2)
+ # g.add_arc(2, 3)
+ # g.add_arc(3, 1)
+ # assert g.successors(2).has(3)
+ # assert g.successors(2).has(2)
+ # ~~~
+ redef fun successors(u: V)
+ do
+ var super_successors = super
+ if outgoing_vertices_map.has_key(u) then super_successors.add(u)
+ return super_successors
+ end
+end