It was previously recursive, and was causing significant performance problems for large, wide graphs.
Signed-off-by: Luke Kanies <[email protected]> --- lib/puppet/simple_graph.rb | 19 +++++++++++++++---- 1 files changed, 15 insertions(+), 4 deletions(-) diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index bc81a6a..7daa6b6 100644 --- a/lib/puppet/simple_graph.rb +++ b/lib/puppet/simple_graph.rb @@ -364,10 +364,21 @@ class Puppet::SimpleGraph end # Just walk the tree and pass each edge. - def walk(source, direction, &block) - adjacent(source, :direction => direction).each do |target| - yield source, target - walk(target, direction, &block) + def walk(source, direction) + # Use an iterative, breadth-first traversal of the graph. One could do + # this recursively, but Ruby's slow function calls and even slower + # recursion make the shorter, recursive algorithm cost-prohibitive. + stack = [source] + seen = Set.new + until stack.empty? + node = stack.shift + next if seen.member? node + connected = adjacent(node, :direction => direction) + connected.each do |target| + yield node, target + end + stack.concat(connected) + seen << node end end -- 1.6.1 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Puppet Developers" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/puppet-dev?hl=en -~----------~----~----~----~------~----~------~--~---
