Class: ArchSpec::Rules::StronglyConnectedComponents

Inherits:
Object
  • Object
show all
Defined in:
lib/archspec/rules/cycle_rule.rb

Overview

Tarjan's algorithm: the components that mutually reach each other, in one pass over the graph.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(adjacency) ⇒ StronglyConnectedComponents

Returns a new instance of StronglyConnectedComponents.



129
130
131
132
133
134
135
136
137
 
# File 'lib/archspec/rules/cycle_rule.rb', line 129

def initialize(adjacency)
  @adjacency = adjacency
  @index = 0
  @indexes = {}
  @lowlinks = {}
  @stack = []
  @on_stack = Set.new
  @found = []
end

Class Method Details

.of(adjacency) ⇒ Object 



125
126
127
 
# File 'lib/archspec/rules/cycle_rule.rb', line 125

def self.of(adjacency)
  new(adjacency).components
end

Instance Method Details

#components ⇒ Object 



139
140
141
142
 
# File 'lib/archspec/rules/cycle_rule.rb', line 139

def components
  @adjacency.each_key { |node| visit(node) unless @indexes.key?(node) }
  @found
end