Method: Puppet::Graph::SimpleGraph#find_cycles_in_graph

Defined in:
lib/puppet/graph/simple_graph.rb

#find_cycles_in_graph ⇒ Object

Find all cycles in the graph by detecting all the strongly connected components, then eliminating everything with a size of one as uninteresting - which it is, because it can’t be a cycle. :)

This has an unhealthy relationship with the ‘tarjan’ method above, which it uses to implement the detection of strongly connected components.



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/puppet/graph/simple_graph.rb', line 166

def find_cycles_in_graph
  state = {
    :number => 0, :index => {}, :lowlink => {}, :scc => [],
    :stack => [], :seen => {}
  }

  # we usually have a disconnected graph, must walk all possible roots
  vertices.each do |vertex|
    unless state[:index][vertex] then
      tarjan vertex, state
    end
  end

  # To provide consistent results to the user, given that a hash is never
  # assured to return the same order, and given our graph processing is
  # based on hash tables, we need to sort the cycles internally, as well as
  # the set of cycles.
  #
  # Given we are in a failure state here, any extra cost is more or less
  # irrelevant compared to the cost of a fix - which is on a human
  # time-scale.
  state[:scc].select do |component|
    multi_vertex_component?(component) || single_vertex_referring_to_self?(component)
  end.map(&:sort).sort
end