Class: ArchUnit::Common::Projection::Cycles::JohnsonCycles

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

Overview

Enumerates every elementary directed cycle once using Johnson's algorithm.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(adjacency) ⇒ JohnsonCycles

Returns a new instance of JohnsonCycles.



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

def initialize(adjacency)
  @vertices = (adjacency.keys + adjacency.values.flatten).uniq.sort
  @adjacency = @vertices.to_h do |vertex|
    neighbours = adjacency.fetch(vertex, []).reject { |item| item == vertex }.uniq.sort
    [vertex, neighbours]
  end
  @cycles = []
end

Class Method Details

.call(adjacency) ⇒ Object 



11
12
13
 
# File 'lib/archunit/common/projection/cycles/johnson_cycles.rb', line 11

def self.call(adjacency)
  new(adjacency).call
end

Instance Method Details

#call ⇒ Object 



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/archunit/common/projection/cycles/johnson_cycles.rb', line 24

def call
  lower_bound = @vertices.first

  while lower_bound
    component = next_component(lower_bound)
    break unless component

    start = component.min
    prepare_search(component, start)
    circuit(start)
    lower_bound = @vertices.find { |vertex| vertex > start }
  end

  @cycles.map(&:freeze).freeze
end