diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index d6418e04f..bc81a6a65 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -1,448 +1,448 @@
 #  Created by Luke A. Kanies on 2007-11-07.
 #  Copyright (c) 2007. All rights reserved.
 
 require 'puppet/external/dot'
 require 'puppet/relationship'
 
 # A hopefully-faster graph class to replace the use of GRATR.
 class Puppet::SimpleGraph
     # An internal class for handling a vertex's edges.
     class VertexWrapper
         attr_accessor :in, :out, :vertex
 
         # Remove all references to everything.
         def clear
             @adjacencies[:in].clear
             @adjacencies[:out].clear
             @vertex = nil
         end
 
         def initialize(vertex)
             @vertex = vertex
             @adjacencies = {:in => {}, :out => {}}
         end
 
         # Find adjacent vertices or edges.
         def adjacent(options)
             direction = options[:direction] || :out
             options[:type] ||= :vertices
 
             return @adjacencies[direction].values.flatten if options[:type] == :edges
 
-            return @adjacencies[direction].keys
+            return @adjacencies[direction].keys.reject { |vertex| @adjacencies[direction][vertex].empty? }
         end
 
         # Add an edge to our list.
         def add_edge(direction, edge)
             opposite_adjacencies(direction, edge) << edge
         end
 
         # Return all known edges.
         def edges
             [:in, :out].collect { |dir| @adjacencies[dir].values }.flatten
         end
 
         # Test whether we share an edge with a given vertex.
         def has_edge?(direction, vertex)
             return true if vertex_adjacencies(direction, vertex).length > 0
             return false
         end
 
         # Create methods for returning the degree and edges.
         [:in, :out].each do |direction|
             # LAK:NOTE If you decide to create methods for directly
             # testing the degree, you'll have to get the values and flatten
             # the results -- you might have duplicate edges, which can give
             # a false impression of what the degree is.  That's just
             # as expensive as just getting the edge list, so I've decided
             # to only add this method.
             define_method("%s_edges" % direction) do
                 @adjacencies[direction].values.flatten
             end
         end
 
         # The other vertex in the edge.
         def other_vertex(direction, edge)
             case direction
             when :in; edge.source
             else
                 edge.target
             end
         end
 
         # Remove an edge from our list.  Assumes that we've already checked
         # that the edge is valid.
         def remove_edge(direction, edge)
             opposite_adjacencies(direction, edge).delete(edge)
         end
 
         def to_s
             vertex.to_s
         end
 
         private
 
         # These methods exist so we don't need a Hash with a default proc.
 
         # Look up the adjacencies for a vertex at the other end of an
         # edge.
         def opposite_adjacencies(direction, edge)
             opposite_vertex = other_vertex(direction, edge)
             vertex_adjacencies(direction, opposite_vertex)
         end
 
         # Look up the adjacencies for a given vertex.
         def vertex_adjacencies(direction, vertex)
             @adjacencies[direction][vertex] ||= []
             @adjacencies[direction][vertex]
         end
     end
 
     def initialize
         @vertices = {}
         @edges = []
     end
 
     # Clear our graph.
     def clear
         @vertices.each { |vertex, wrapper| wrapper.clear }
         @vertices.clear
         @edges.clear
     end
 
     # Which resources a given resource depends upon.
     def dependents(resource)
         tree_from_vertex(resource).keys
     end
     
     # Which resources depend upon the given resource.
     def dependencies(resource)
         # Cache the reversal graph, because it's somewhat expensive
         # to create.
         unless defined? @reversal and @reversal
             @reversal = reversal
         end
         # Strangely, it's significantly faster to search a reversed
         # tree in the :out direction than to search a normal tree
         # in the :in direction.
         @reversal.tree_from_vertex(resource, :out).keys
     end
 
     # Whether our graph is directed.  Always true.  Used to produce dot files.
     def directed?
         true
     end
 
     # Determine all of the leaf nodes below a given vertex.
     def leaves(vertex, direction = :out)
         tree = tree_from_vertex(vertex, direction)
         l = tree.keys.find_all { |c| adjacent(c, :direction => direction).empty? }
         return l
     end
     
     # Collect all of the edges that the passed events match.  Returns
     # an array of edges.
     def matching_edges(events, base = nil)
         events.collect do |event|
             source = base || event.source
 
             unless vertex?(source)
                 Puppet.warning "Got an event from invalid vertex %s" % source.ref
                 next
             end
             # Get all of the edges that this vertex should forward events
             # to, which is the same thing as saying all edges directly below
             # This vertex in the graph.
             adjacent(source, :direction => :out, :type => :edges).find_all do |edge|
                 edge.match?(event.name)
             end
         end.compact.flatten
     end
 
     # Return a reversed version of this graph.
     def reversal
         result = self.class.new
         vertices.each { |vertex| result.add_vertex(vertex) }
         edges.each do |edge|
             newedge = edge.class.new(edge.target, edge.source, edge.label)
             result.add_edge(newedge)
         end
         result
     end
 
     # Return the size of the graph.
     def size
         @vertices.length
     end
 
     # Return the graph as an array.
     def to_a
         @vertices.keys
     end
 
     # Provide a topological sort.
     def topsort
         degree = {}
         zeros = []
         result = []
 
         # Collect each of our vertices, with the number of in-edges each has.
         @vertices.each do |name, wrapper|
             edges = wrapper.in_edges
             zeros << wrapper if edges.length == 0
             degree[wrapper.vertex] = edges
         end
 
         # Iterate over each 0-degree vertex, decrementing the degree of
         # each of its out-edges.
         while wrapper = zeros.pop do
             result << wrapper.vertex
             wrapper.out_edges.each do |edge|
                 degree[edge.target].delete(edge)
                 zeros << @vertices[edge.target] if degree[edge.target].length == 0
             end
         end
 
         # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
         if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
             message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
             raise Puppet::Error, "Found dependency cycles in the following relationships: %s" % message
         end
 
         return result
     end
 
     # Add a new vertex to the graph.
     def add_vertex(vertex)
         @reversal = nil
         return false if vertex?(vertex)
         setup_vertex(vertex)
         true # don't return the VertexWrapper instance.
     end
 
     # Remove a vertex from the graph.
     def remove_vertex!(vertex)
         return nil unless vertex?(vertex)
         @vertices[vertex].edges.each { |edge| remove_edge!(edge) }
         @vertices[vertex].clear
         @vertices.delete(vertex)
     end
 
     # Test whether a given vertex is in the graph.
     def vertex?(vertex)
         @vertices.include?(vertex)
     end
 
     # Return a list of all vertices.
     def vertices
         @vertices.keys
     end
 
     # Add a new edge.  The graph user has to create the edge instance,
     # since they have to specify what kind of edge it is.
     def add_edge(source, target = nil, label = nil)
         @reversal = nil
         if target
             edge = Puppet::Relationship.new(source, target, label)
         else
             edge = source
         end
         [edge.source, edge.target].each { |vertex| setup_vertex(vertex) unless vertex?(vertex) }
         @vertices[edge.source].add_edge :out, edge
         @vertices[edge.target].add_edge :in, edge
         @edges << edge
         true
     end
 
     # Find a matching edge.  Note that this only finds the first edge,
     # not all of them or whatever.
     def edge(source, target)
         @edges.each_with_index { |test_edge, index| return test_edge if test_edge.source == source and test_edge.target == target }
     end
 
     def edge_label(source, target)
         return nil unless edge = edge(source, target)
         edge.label
     end
 
     # Is there an edge between the two vertices?
     def edge?(source, target)
         return false unless vertex?(source) and vertex?(target)
 
         @vertices[source].has_edge?(:out, target)
     end
 
     def edges
         @edges.dup
     end
 
     # Remove an edge from our graph.
     def remove_edge!(edge)
         @vertices[edge.source].remove_edge(:out, edge)
         @vertices[edge.target].remove_edge(:in, edge)
         
         # Here we are looking for an exact edge, so we don't want to use ==, because
         # it's too darn expensive (in testing, deleting 3000 edges went from 6 seconds to
         # 0.05 seconds with this change).
         @edges.each_with_index { |test_edge, index| @edges.delete_at(index) and break if edge.equal?(test_edge) }
         nil
     end
 
     # Find adjacent edges.
     def adjacent(vertex, options = {})
         return [] unless wrapper = @vertices[vertex]
         return wrapper.adjacent(options)
     end
 
     private
 
     # An internal method that skips the validation, so we don't have
     # duplicate validation calls.
     def setup_vertex(vertex)
         @vertices[vertex] = VertexWrapper.new(vertex)
     end
  
     public
     
 #    # For some reason, unconnected vertices do not show up in
 #    # this graph.
 #    def to_jpg(path, name)
 #        gv = vertices()
 #        Dir.chdir(path) do
 #            induced_subgraph(gv).write_to_graphic_file('jpg', name)
 #        end
 #    end
     
     # Take container information from another graph and use it
     # to replace any container vertices with their respective leaves.
     # This creates direct relationships where there were previously
     # indirect relationships through the containers. 
     def splice!(other, type)
         # We have to get the container list via a topological sort on the
         # configuration graph, because otherwise containers that contain
         # other containers will add those containers back into the
         # graph.  We could get a similar affect by only setting relationships
         # to container leaves, but that would result in many more
         # relationships.
         containers = other.topsort.find_all { |v| v.is_a?(type) and vertex?(v) }
         containers.each do |container|
             # Get the list of children from the other graph.
             children = other.adjacent(container, :direction => :out)
 
             # Just remove the container if it's empty.
             if children.empty?
                 remove_vertex!(container)
                 next
             end
             
             # First create new edges for each of the :in edges
             [:in, :out].each do |dir|
                 edges = adjacent(container, :direction => dir, :type => :edges)
                 edges.each do |edge|
                     children.each do |child|
                         if dir == :in
                             s = edge.source
                             t = child
                         else
                             s = child
                             t = edge.target
                         end
 
                         add_edge(s, t, edge.label)
                     end
 
                     # Now get rid of the edge, so remove_vertex! works correctly.
                     remove_edge!(edge)
                 end
             end
             remove_vertex!(container)
         end
     end
 
     def to_yaml_properties
         instance_variables
     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)
         end
     end
 
     # A different way of walking a tree, and a much faster way than the
     # one that comes with GRATR.
     def tree_from_vertex(start, direction = :out)
         predecessor={}
         walk(start, direction) do |parent, child|
             predecessor[child] = parent
         end
         predecessor       
     end
 
     # LAK:FIXME This is just a paste of the GRATR code with slight modifications.
 
     # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an
     # undirected Graph.  _params_ can contain any graph property specified in
     # rdot.rb. If an edge or vertex label is a kind of Hash then the keys
     # which match +dot+ properties will be used as well.
     def to_dot_graph (params = {})
       params['name'] ||= self.class.name.gsub(/:/,'_')
       fontsize   = params['fontsize'] ? params['fontsize'] : '8'
       graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
       edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge
       vertices.each do |v|
         name = v.to_s
         params = {'name'     => '"'+name+'"',
                   'fontsize' => fontsize,
                   'label'    => name}
         v_label = v.to_s
         params.merge!(v_label) if v_label and v_label.kind_of? Hash
         graph << DOT::DOTNode.new(params)
       end
       edges.each do |e|
         params = {'from'     => '"'+ e.source.to_s + '"',
                   'to'       => '"'+ e.target.to_s + '"',
                   'fontsize' => fontsize }
         e_label = e.to_s
         params.merge!(e_label) if e_label and e_label.kind_of? Hash
         graph << edge_klass.new(params)
       end
       graph
     end
     
     # Output the dot format as a string
     def to_dot (params={}) to_dot_graph(params).to_s; end
 
     # Call +dotty+ for the graph which is written to the file 'graph.dot'
     # in the # current directory.
     def dotty (params = {}, dotfile = 'graph.dot')
       File.open(dotfile, 'w') {|f| f << to_dot(params) }
       system('dotty', dotfile)
     end
 
     # Use +dot+ to create a graphical representation of the graph.  Returns the
     # filename of the graphics file.
     def write_to_graphic_file (fmt='png', dotfile='graph')
       src = dotfile + '.dot'
       dot = dotfile + '.' + fmt
       
       File.open(src, 'w') {|f| f << self.to_dot << "\n"}
       
       system( "dot -T#{fmt} #{src} -o #{dot}" )
       dot
     end
 
     # Produce the graph files if requested.
     def write_graph(name)
         return unless Puppet[:graph]
 
         Puppet.settings.use(:graphing)
 
         file = File.join(Puppet[:graphdir], "%s.dot" % name.to_s)
         File.open(file, "w") { |f|
             f.puts to_dot("name" => name.to_s.capitalize)
         }
     end
 end
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index 2c061ae1a..a5984c989 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -1,520 +1,529 @@
 #!/usr/bin/env ruby
 #
 #  Created by Luke Kanies on 2007-11-1.
 #  Copyright (c) 2006. All rights reserved.
 
 require File.dirname(__FILE__) + '/../spec_helper'
 require 'puppet/simple_graph'
 
 describe Puppet::SimpleGraph do
     it "should return the number of its vertices as its length" do
         @graph = Puppet::SimpleGraph.new
         @graph.add_vertex("one")
         @graph.add_vertex("two")
         @graph.size.should == 2
     end
 
     it "should consider itself a directed graph" do
         Puppet::SimpleGraph.new.directed?.should be_true
     end
 
     it "should provide a method for reversing the graph" do
         @graph = Puppet::SimpleGraph.new
         @graph.add_edge(:one, :two)
         @graph.reversal.edge?(:two, :one).should be_true
     end
 
     it "should be able to produce a dot graph" do
         @graph = Puppet::SimpleGraph.new
         @graph.add_edge(:one, :two)
 
         proc { @graph.to_dot_graph }.should_not raise_error
     end
 
     describe "when managing vertices" do
         before do
             @graph = Puppet::SimpleGraph.new
         end
 
         it "should provide a method to add a vertex" do
             @graph.add_vertex(:test)
             @graph.vertex?(:test).should be_true
         end
 
         it "should reset its reversed graph when vertices are added" do
             rev = @graph.reversal
             @graph.add_vertex(:test)
             @graph.reversal.should_not equal(rev)
         end
 
         it "should ignore already-present vertices when asked to add a vertex" do
             @graph.add_vertex(:test)
             proc { @graph.add_vertex(:test) }.should_not raise_error
         end
 
         it "should return true when asked if a vertex is present" do
             @graph.add_vertex(:test)
             @graph.vertex?(:test).should be_true
         end
 
         it "should return false when asked if a non-vertex is present" do
             @graph.vertex?(:test).should be_false
         end
 
         it "should return all set vertices when asked" do
             @graph.add_vertex(:one)
             @graph.add_vertex(:two)
             @graph.vertices.length.should == 2
             @graph.vertices.should include(:one)
             @graph.vertices.should include(:two)
         end
 
         it "should remove a given vertex when asked" do
             @graph.add_vertex(:one)
             @graph.remove_vertex!(:one)
             @graph.vertex?(:one).should be_false
         end
 
         it "should do nothing when a non-vertex is asked to be removed" do
             proc { @graph.remove_vertex!(:one) }.should_not raise_error
         end
     end
 
     describe "when managing edges" do
         before do
             @graph = Puppet::SimpleGraph.new
         end
 
         it "should provide a method to test whether a given vertex pair is an edge" do
             @graph.should respond_to(:edge?)
         end
 
         it "should reset its reversed graph when edges are added" do
             rev = @graph.reversal
             @graph.add_edge(:one, :two)
             @graph.reversal.should_not equal(rev)
         end
 
         it "should provide a method to add an edge as an instance of the edge class" do
             edge = Puppet::Relationship.new(:one, :two)
             @graph.add_edge(edge)
             @graph.edge?(:one, :two).should be_true
         end
 
         it "should provide a method to add an edge by specifying the two vertices" do
             @graph.add_edge(:one, :two)
             @graph.edge?(:one, :two).should be_true
         end
 
         it "should provide a method to add an edge by specifying the two vertices and a label" do
             @graph.add_edge(:one, :two, :callback => :awesome)
             @graph.edge?(:one, :two).should be_true
         end
 
         it "should provide a method for retrieving an edge label" do
             edge = Puppet::Relationship.new(:one, :two, :callback => :awesome)
             @graph.add_edge(edge)
             @graph.edge_label(:one, :two).should == {:callback => :awesome}
         end
 
         it "should provide a method for retrieving an edge" do
             edge = Puppet::Relationship.new(:one, :two)
             @graph.add_edge(edge)
             @graph.edge(:one, :two).should equal(edge)
         end
 
         it "should add the edge source as a vertex if it is not already" do
             edge = Puppet::Relationship.new(:one, :two)
             @graph.add_edge(edge)
             @graph.vertex?(:one).should be_true
         end
 
         it "should add the edge target as a vertex if it is not already" do
             edge = Puppet::Relationship.new(:one, :two)
             @graph.add_edge(edge)
             @graph.vertex?(:two).should be_true
         end
 
         it "should return all edges as edge instances when asked" do
             one = Puppet::Relationship.new(:one, :two)
             two = Puppet::Relationship.new(:two, :three)
             @graph.add_edge(one)
             @graph.add_edge(two)
             edges = @graph.edges
             edges.length.should == 2
             edges.should include(one)
             edges.should include(two)
         end
 
         it "should remove an edge when asked" do
             edge = Puppet::Relationship.new(:one, :two)
             @graph.add_edge(edge)
             @graph.remove_edge!(edge)
             @graph.edge?(edge.source, edge.target).should be_false
         end
 
         it "should remove all related edges when a vertex is removed" do
             one = Puppet::Relationship.new(:one, :two)
             two = Puppet::Relationship.new(:two, :three)
             @graph.add_edge(one)
             @graph.add_edge(two)
             @graph.remove_vertex!(:two)
             @graph.edge?(:one, :two).should be_false
             @graph.edge?(:two, :three).should be_false
             @graph.edges.length.should == 0
         end
     end
 
     describe "when finding adjacent vertices" do
         before do
             @graph = Puppet::SimpleGraph.new
             @one_two = Puppet::Relationship.new(:one, :two)
             @two_three = Puppet::Relationship.new(:two, :three)
             @one_three = Puppet::Relationship.new(:one, :three)
             @graph.add_edge(@one_two)
             @graph.add_edge(@one_three)
             @graph.add_edge(@two_three)
         end
 
         it "should return adjacent vertices" do
             adj = @graph.adjacent(:one)
             adj.should be_include(:three)
             adj.should be_include(:two)
         end
 
         it "should default to finding :out vertices" do
             @graph.adjacent(:two).should == [:three]
         end
 
         it "should support selecting :in vertices" do
             @graph.adjacent(:two, :direction => :in).should == [:one]
         end
 
         it "should default to returning the matching vertices as an array of vertices" do
             @graph.adjacent(:two).should == [:three]
         end
 
         it "should support returning an array of matching edges" do
             @graph.adjacent(:two, :type => :edges).should == [@two_three]
         end
+
+        # Bug #2111
+        it "should not consider a vertex adjacent just because it was asked about previously" do
+            @graph = Puppet::SimpleGraph.new
+            @graph.add_vertex("a")
+            @graph.add_vertex("b")
+            @graph.edge?("a", "b")
+            @graph.adjacent("a").should == []
+        end
     end
 
     describe "when clearing" do
         before do
             @graph = Puppet::SimpleGraph.new
             one = Puppet::Relationship.new(:one, :two)
             two = Puppet::Relationship.new(:two, :three)
             @graph.add_edge(one)
             @graph.add_edge(two)
 
             @graph.clear
         end
 
         it "should remove all vertices" do
             @graph.vertices.should be_empty
         end
 
         it "should remove all edges" do
             @graph.edges.should be_empty
         end
     end
 
     describe "when reversing graphs" do
         before do
             @graph = Puppet::SimpleGraph.new
         end
 
         it "should provide a method for reversing the graph" do
             @graph.add_edge(:one, :two)
             @graph.reversal.edge?(:two, :one).should be_true
         end
 
         it "should add all vertices to the reversed graph" do
             @graph.add_edge(:one, :two)
             @graph.vertex?(:one).should be_true
             @graph.vertex?(:two).should be_true
         end
         
         it "should retain labels on edges" do
             @graph.add_edge(:one, :two, :callback => :awesome)
             edge = @graph.reversal.edge(:two, :one)
             edge.label.should == {:callback => :awesome}
         end
     end
 
     describe "when sorting the graph" do
         before do
             @graph = Puppet::SimpleGraph.new
         end
 
         def add_edges(hash)
             hash.each do |a,b|
                 @graph.add_edge(a, b)
             end
         end
 
         it "should sort the graph topologically" do
             add_edges :a => :b, :b => :c
             @graph.topsort.should == [:a, :b, :c]
         end
 
         it "should fail on two-vertex loops" do
             add_edges :a => :b, :b => :a
             proc { @graph.topsort }.should raise_error(Puppet::Error)
         end
 
         it "should fail on multi-vertex loops" do
             add_edges :a => :b, :b => :c, :c => :a
             proc { @graph.topsort }.should raise_error(Puppet::Error)
         end
 
         it "should fail when a larger tree contains a small cycle" do
             add_edges :a => :b, :b => :a, :c => :a, :d => :c
             proc { @graph.topsort }.should raise_error(Puppet::Error)
         end
 
         it "should succeed on trees with no cycles" do
             add_edges :a => :b, :b => :e, :c => :a, :d => :c
             proc { @graph.topsort }.should_not raise_error
         end
 
         # Our graph's add_edge method is smart enough not to add
         # duplicate edges, so we use the objects, which it doesn't
         # check.
         it "should be able to sort graphs with duplicate edges" do
             one = Puppet::Relationship.new(:a, :b)
             @graph.add_edge(one)
             two = Puppet::Relationship.new(:a, :b)
             @graph.add_edge(two)
             proc { @graph.topsort }.should_not raise_error
         end
     end
 
     describe "when writing dot files" do
         before do
             @graph = Puppet::SimpleGraph.new
             @name = :test
             @file = File.join(Puppet[:graphdir], @name.to_s + ".dot")
         end
 
         it "should only write when graphing is enabled" do
             File.expects(:open).with(@file).never
             Puppet[:graph] = false
             @graph.write_graph(@name)
         end
 
         it "should write a dot file based on the passed name" do
             File.expects(:open).with(@file, "w").yields(stub("file", :puts => nil))
             @graph.expects(:to_dot).with("name" => @name.to_s.capitalize)
             Puppet[:graph] = true
             @graph.write_graph(@name)
         end
 
         after do
             Puppet.settings.clear
         end
     end
 
     describe Puppet::SimpleGraph do
         before do
             @graph = Puppet::SimpleGraph.new
         end
 
         it "should correctly clear vertices and edges when asked" do
             @graph.add_edge("a", "b")
             @graph.add_vertex "c"
             @graph.clear
             @graph.vertices.should be_empty
             @graph.edges.should be_empty
         end
     end
 
     describe "when matching edges" do
         before do
             @graph = Puppet::SimpleGraph.new
             @event = Puppet::Transaction::Event.new(:yay, "a")
             @none = Puppet::Transaction::Event.new(:NONE, "a")
 
             @edges = {}
             @edges["a/b"] = Puppet::Relationship.new("a", "b", {:event => :yay, :callback => :refresh})
             @edges["a/c"] = Puppet::Relationship.new("a", "c", {:event => :yay, :callback => :refresh})
             @graph.add_edge(@edges["a/b"])
         end
 
         it "should match edges whose source matches the source of the event" do
             @graph.matching_edges([@event]).should == [@edges["a/b"]]
         end
 
         it "should match always match nothing when the event is :NONE" do
             @graph.matching_edges([@none]).should be_empty
         end
 
         it "should match multiple edges" do
             @graph.add_edge(@edges["a/c"])
             edges = @graph.matching_edges([@event])
             edges.should be_include(@edges["a/b"])
             edges.should be_include(@edges["a/c"])
         end
     end
 
     describe "when determining dependencies" do
         before do
             @graph = Puppet::SimpleGraph.new
             
             @graph.add_edge("a", "b")
             @graph.add_edge("a", "c")
             @graph.add_edge("b", "d")
         end
 
         it "should find all dependents when they are on multiple levels" do
             @graph.dependents("a").sort.should == %w{b c d}.sort
         end
 
         it "should find single dependents" do
             @graph.dependents("b").sort.should == %w{d}.sort
         end
 
         it "should return an empty array when there are no dependents" do
             @graph.dependents("c").sort.should == [].sort
         end
 
         it "should find all dependencies when they are on multiple levels" do
             @graph.dependencies("d").sort.should == %w{a b}
         end
 
         it "should find single dependencies" do
             @graph.dependencies("c").sort.should == %w{a}
         end
         
         it "should return an empty array when there are no dependencies" do
             @graph.dependencies("a").sort.should == []
         end
     end
 
     require 'puppet/util/graph'
 
     class Container
         include Puppet::Util::Graph
         include Enumerable
         attr_accessor :name
         def each
             @children.each do |c| yield c end
         end
         
         def initialize(name, ary)
             @name = name
             @children = ary
         end
         
         def push(*ary)
             ary.each { |c| @children.push(c)}
         end
         
         def to_s
             @name
         end
     end
 
     describe "when splicing the graph" do
         def container_graph
             @one = Container.new("one", %w{a b})
             @two = Container.new("two", ["c", "d"])
             @three = Container.new("three", ["i", "j"])
             @middle = Container.new("middle", ["e", "f", @two])
             @top = Container.new("top", ["g", "h", @middle, @one, @three])
             @empty = Container.new("empty", [])
 
             @contgraph = @top.to_graph
 
             # We have to add the container to the main graph, else it won't
             # be spliced in the dependency graph.
             @contgraph.add_vertex(@empty)
         end
 
         def dependency_graph
             @depgraph = Puppet::SimpleGraph.new
             @contgraph.vertices.each do |v|
                 @depgraph.add_vertex(v)
             end
 
             # We have to specify a relationship to our empty container, else it
             # never makes it into the dep graph in the first place.
             {@one => @two, "f" => "c", "h" => @middle, "c" => @empty}.each do |source, target|
                 @depgraph.add_edge(source, target, :callback => :refresh)
             end
         end
 
         def splice
             @depgraph.splice!(@contgraph, Container)
         end
 
         before do
             container_graph
             dependency_graph
             splice
         end
 
         # This is the real heart of splicing -- replacing all containers in
         # our relationship and exploding their relationships so that each
         # relationship to a container gets copied to all of its children.
         it "should remove all Container objects from the dependency graph" do
             @depgraph.vertices.find_all { |v| v.is_a?(Container) }.should be_empty
         end
 
         it "should add container relationships to contained objects" do
             @contgraph.leaves(@middle).each do |leaf|
                 @depgraph.should be_edge("h", leaf)
             end
         end
 
         it "should explode container-to-container relationships, making edges between all respective contained objects" do
             @one.each do |oobj|
                 @two.each do |tobj|
                     @depgraph.should be_edge(oobj, tobj)
                 end
             end
         end
 
         it "should no longer contain anything but the non-container objects" do
             @depgraph.vertices.find_all { |v| ! v.is_a?(String) }.should be_empty
         end
 
         it "should copy labels" do
             @depgraph.edges.each do |edge|
                 edge.label.should == {:callback => :refresh}
             end
         end
 
         it "should not add labels to edges that have none" do
             @depgraph.add_edge(@two, @three)
             splice
             @depgraph.edge_label("c", "i").should == {}
         end
 
         it "should copy labels over edges that have none" do
             @depgraph.add_edge("c", @three, {:callback => :refresh})
             splice
             # And make sure the label got copied.
             @depgraph.edge_label("c", "i").should == {:callback => :refresh}
         end
 
         it "should not replace a label with a nil label" do
             # Lastly, add some new label-less edges and make sure the label stays.
             @depgraph.add_edge(@middle, @three)
             @depgraph.add_edge("c", @three, {:callback => :refresh})
             splice
             @depgraph.edge_label("c", "i").should == {:callback => :refresh}
         end
 
         it "should copy labels to all created edges" do
             @depgraph.add_edge(@middle, @three)
             @depgraph.add_edge("c", @three, {:callback => :refresh})
             splice
             @three.each do |child|
                 edge = Puppet::Relationship.new("c", child)
                 @depgraph.should be_edge(edge.source, edge.target)
                 @depgraph.edge_label(edge.source, edge.target).should == {:callback => :refresh}
             end
         end
     end
 end