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
nitlanguage / nit.git / blobdiff