From 828b1ea605786183c69a8be3bca2272b50761790 Mon Sep 17 00:00:00 2001 From: Luke Kanies Date: Tue, 21 Apr 2009 17:49:05 -0500 Subject: Fixing #2182 - SimpleGraph#walk is now iterative It was previously recursive, and was causing significant performance problems for large, wide graphs. Signed-off-by: Luke Kanies --- lib/puppet/simple_graph.rb | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index b1aaf6363..05420eab9 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 -- cgit