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 195

def paths_in_cycle(cycle, max_paths = 1)
  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 do
    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

  return found.sort
end