# Module: Plexus::StrongComponents

Included in:
DirectedGraphBuilder::Algorithms
Defined in:
lib/plexus/strong_components.rb

## Instance Method Summary collapse

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

• :nodoc:.

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

• This returns the transitive closure of a graph.

• Compute transitive closure of a graph.

## Instance Method Details

### #condensation ⇒ Object

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```

### #plexus_inner_transitive_closure! ⇒ Object

: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```

### #strong_components ⇒ Object

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):146-160, 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```

### #transitive_closure ⇒ Object

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```

### #transitive_closure! ⇒ Object

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```