Class: ArchUnit::Common::Projection::Cycles::TarjanScc

Inherits:
Object
  • Object
show all
Defined in:
lib/archunit/common/projection/cycles/tarjan_scc.rb

Overview

Finds strongly connected components in a directed adjacency map.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(adjacency, vertices) ⇒ TarjanScc

Returns a new instance of TarjanScc.



13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/archunit/common/projection/cycles/tarjan_scc.rb', line 13

def initialize(adjacency, vertices)
  @adjacency = adjacency
  @vertices = vertices.to_a
  @allowed = @vertices.to_set
  @next_index = 0
  @indices = {}
  @lowlinks = {}
  @stack = []
  @on_stack = Set.new
  @components = []
end

Class Method Details

.call(adjacency, vertices: adjacency.keys) ⇒ Object 



9
10
11
 
# File 'lib/archunit/common/projection/cycles/tarjan_scc.rb', line 9

def self.call(adjacency, vertices: adjacency.keys)
  new(adjacency, vertices).call
end

Instance Method Details

#call ⇒ Object 



25
26
27
28
 
# File 'lib/archunit/common/projection/cycles/tarjan_scc.rb', line 25

def call
  @vertices.each { |vertex| visit(vertex) unless @indices.key?(vertex) }
  @components.map(&:freeze).freeze
end