## mark a section (Learn more)

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index dacea1a..c064a1d 100644 --- a/lib/puppet/simple_graph.rb +++ b/lib/puppet/simple_graph.rb @@ -95,7 +95,7 @@ class Puppet::SimpleGraph # Look up the adjacencies for a given vertex. def vertex_adjacencies(direction, vertex) - @adjacencies[direction][vertex] ||= Set.new + @adjacencies[direction][vertex] ||= [] @adjacencies[direction][vertex] end end @@ -374,23 +374,12 @@ class Puppet::SimpleGraph end # Just walk the tree and pass each edge. - 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 + def walk(source, direction, &block) + adjacent(source, :direction => direction).each do |target| + yield source, target + walk(target, direction, &block) end - end + end # A different way of walking a tree, and a much faster way than the # one that comes with GRATR.

This paste will be private.