Module: Plexus::StrongComponents
 Included in:
 DirectedGraphBuilder::Algorithms
 Defined in:
 lib/plexus/strong_components.rb
Instance Method Summary (collapse)

 (Object) condensation
Returns a condensation graph of the strongly connected components Each node is an array of nodes from the original graph.

 (Object) plexus_inner_transitive_closure!
:nodoc:.

 (Object) strong_components
strong_components computes the strongly connected components of a graph using Tarjan's algorithm based on DFS.

 (Object) transitive_closure
This returns the transitive closure of a graph.

 (Object) transitive_closure!
Compute transitive closure of a graph.
Instance Method Details
 (Object) condensation
Returns a condensation graph of the strongly connected components Each node is an array of nodes from the original graph
54 55 56 57 58 59 60 61 62 63 64 65 66 
# File 'lib/plexus/strong_components.rb', line 54 def condensation sc = strong_components cg = DirectedMultiGraph.new map = sc.inject({}) do a,c c.each {v a[v] = c }; a end sc.each do c c.each do v adjacent(v).each {v1 cg.add_edge!(c, map[v1]) unless cg.edge?(c, map[v1]) } end end; cg end 
 (Object) plexus_inner_transitive_closure!
:nodoc:
85 86 87 88 89 90 91 
# File 'lib/plexus/strong_components.rb', line 85 def plexus_inner_transitive_closure! # :nodoc: sort.reverse.each do u adjacent(u).each do v adjacent(v).each {w add_edge!(u,w) unless edge?(u,w)} end end; self end 
 (Object) strong_components
strong_components computes the strongly connected components of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan Depth_First_Search_and_Linear_Graph_Algorithms. SIAM Journal on Computing, 1(2):146160, 1972
The output of the algorithm is an array of components where is component is an array of vertices
A strongly connected component of a directed graph G=(V,E) is a maximal set of vertices U which is in V such that for every pair of vertices u and v in U, we have both a path from u to v and path from v to u. That is to say that u and v are reachable from each other.
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
# File 'lib/plexus/strong_components.rb', line 17 def strong_components dfs_num = 0 stack = []; result = []; root = {}; comp = {}; number = {} # Enter vertex callback enter = Proc.new do v root[v] = v comp[v] = :new number[v] = (dfs_num += 1) stack.push(v) end # Exit vertex callback exit = Proc.new do v adjacent(v).each do w if comp[w] == :new root[v] = (number[root[v]] < number[root[w]] ? root[v] : root[w]) end end if root[v] == v component = [] begin w = stack.pop comp[w] = :assigned component << w end until w == v result << component end end # Execute depth first search dfs({:enter_vertex => enter, :exit_vertex => exit}); result end 
 (Object) transitive_closure
This returns the transitive closure of a graph. The original graph is not changed.
83 
# File 'lib/plexus/strong_components.rb', line 83 def transitive_closure() self.class.new(self).transitive_closure!; end 
 (Object) transitive_closure!
Compute transitive closure of a graph. That is any node that is reachable along a path is added as a directed edge.
70 71 72 73 74 75 76 77 78 79 
# File 'lib/plexus/strong_components.rb', line 70 def transitive_closure! cgtc = condensation.plexus_inner_transitive_closure! cgtc.each do cgv cgtc.adjacent(cgv).each do adj cgv.each do u adj.each {v add_edge!(u,v)} end end end; self end 