Module: GRATR::Graph::StrongComponents

Included in:
Digraph
Defined in:
lib/gratr/strong_components.rb

Instance Method Summary collapse

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



86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/gratr/strong_components.rb', line 86

def condensation
  sc  = strong_components
  cg  = self.class.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 {|v| cg.add_edge!(c, map[v]) unless c == map[v]}
    end
  end; cg
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.



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/gratr/strong_components.rb', line 48

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.



114
 
# File 'lib/gratr/strong_components.rb', line 114

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.



101
102
103
104
105
106
107
108
109
110
 
# File 'lib/gratr/strong_components.rb', line 101

def transitive_closure!
  cgtc = condensation.gratr_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