Method: Puppet::Graph::SimpleGraph#paths_in_cycle

Defined in:

lib/puppet/graph/simple_graph.rb

#paths_in_cycle(cycle, max_paths = 1) ⇒ Object

Perform a BFS on the sub graph representing the cycle, with a view to generating a sufficient set of paths to report the cycle meaningfully, and ideally usefully, for the end user.

BFS is preferred because it will generally report the shortest paths through the graph first, which are more likely to be interesting to the user. I think; it would be interesting to verify that. –daniel 2011-01-23

Raises:

• (ArgumentError)

# File 'lib/puppet/graph/simple_graph.rb', line 199

def paths_in_cycle(cycle, max_paths = 1)
  # TRANSLATORS "negative or zero" refers to the count of paths
  raise ArgumentError, _("negative or zero max_paths") if max_paths < 1

  # Calculate our filtered outbound vertex lists...
  adj = {}
  cycle.each do |vertex|
    adj[vertex] = adjacent(vertex).select { |s| cycle.member? s }
  end

  found = []

  # frame struct is vertex, [path]
  stack = [[cycle.first, []]]
  while frame = stack.shift # rubocop:disable Lint/AssignmentInCondition
    if frame[1].member?(frame[0]) then
      found << frame[1] + [frame[0]]
      break if found.length >= max_paths
    else
      adj[frame[0]].each do |to|
        stack.push [to, frame[1] + [frame[0]]]
      end
    end
  end

  found.sort
end