Class: CycleFinder

Inherits:
Object
  • Object
show all
Defined in:
backend/app/lib/cycle_finder.rb

Defined Under Namespace

Classes: Path

Instance Method Summary collapse

Constructor Details

#initialize(graph, ticker) ⇒ CycleFinder

Expects an instance of a DependencySet representing a dependency graph like:

{ ‘/uri/1’ => [‘/uri/2’, ‘/uri/3’], ‘/uri/2’ => [‘/uri/1’, ‘/uri/4’] }



9
10
11
12
13
14
15
 
# File 'backend/app/lib/cycle_finder.rb', line 9

def initialize(graph, ticker)
  @graph = graph
  @ticker = ticker
  @whitelisted_nodes = {}

  @ticker.tick_estimate = @graph.keys.length
end

Instance Method Details

#each ⇒ Object

Yields each URI involved in a cycle as we find them



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'backend/app/lib/cycle_finder.rb', line 18

def each
  cycles_found = []

  @graph.keys.each do |start_node|
    @ticker.tick
    next if cycles_found.include?(start_node)

    find_cycles(start_node).each do |cycle|
      unless cycles_found.include?(cycle.node)
        cycles_found << cycle.node
        yield cycle.node
      end
    end
  end
end