Removing the PGraph class and subsuming it into SimpleGraph.

This class is a holdover from when I was using GRATR, and it's
obsolete now.

Signed-off-by: Luke Kanies <luke@madstop.com>

8 files changed, 545 insertions, 591 deletions

diff --git a/lib/puppet/node/catalog.rb b/lib/puppet/node/catalog.rb
index 39b3fdfdc..0138fd8cb 100644
--- a/lib/puppet/node/catalog.rb
+++ b/lib/puppet/node/catalog.rb
@@ -1,5 +1,5 @@
 require 'puppet/indirector'
-require 'puppet/pgraph'
+require 'puppet/simple_graph'
 require 'puppet/transaction'
 
 require 'puppet/util/tagging'
@@ -8,7 +8,7 @@ require 'puppet/util/tagging'
 # meant to be passed from server to client, and it contains all
 # of the information in the catalog, including the resources
 # and the relationships between them.
-class Puppet::Node::Catalog < Puppet::PGraph
+class Puppet::Node::Catalog < Puppet::SimpleGraph
     extend Puppet::Indirector
     indirects :catalog, :terminus_class => :compiler
 
@@ -321,17 +321,13 @@ class Puppet::Node::Catalog < Puppet::PGraph
     
     # Create a graph of all of the relationships in our catalog.
     def relationship_graph
-        raise(Puppet::DevError, "Tried get a relationship graph for a relationship graph") if self.is_relationship_graph
-
         unless defined? @relationship_graph and @relationship_graph
             # It's important that we assign the graph immediately, because
             # the debug messages below use the relationships in the
             # relationship graph to determine the path to the resources
             # spitting out the messages.  If this is not set,
             # then we get into an infinite loop.
-            @relationship_graph = Puppet::Node::Catalog.new
-            @relationship_graph.host_config = host_config?
-            @relationship_graph.is_relationship_graph = true
+            @relationship_graph = Puppet::SimpleGraph.new
             
             # First create the dependency graph
             self.vertices.each do |vertex|
@@ -355,12 +351,12 @@ class Puppet::Node::Catalog < Puppet::PGraph
                 end
             end
             
-            @relationship_graph.write_graph(:relationships)
+            @relationship_graph.write_graph(:relationships) if host_config?
             
             # Then splice in the container information
             @relationship_graph.splice!(self, Puppet::Type::Component)
 
-            @relationship_graph.write_graph(:expanded_relationships)
+            @relationship_graph.write_graph(:expanded_relationships) if host_config?
         end
         @relationship_graph
     end
@@ -391,11 +387,7 @@ class Puppet::Node::Catalog < Puppet::PGraph
             # Reference class canonizes for us.
             ref = Puppet::ResourceReference.new(nil, type).to_s
         end
-        if resource = @resource_table[ref]
-            return resource
-        elsif defined?(@relationship_graph) and @relationship_graph
-            @relationship_graph.resource(ref)
-        end
+        @resource_table[ref]
     end
 
     # Return an array of all resources.
@@ -417,15 +409,8 @@ class Puppet::Node::Catalog < Puppet::PGraph
     def write_graph(name)
         # We only want to graph the main host catalog.
         return unless host_config?
-        
-        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)
-        }
+        super
     end
 
     # LAK:NOTE We cannot yaml-dump the class in the edgelist_class, because classes cannot be
diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
deleted file mode 100644
index 55ad7d2c1..000000000
--- a/lib/puppet/pgraph.rb
+++ /dev/null
@@ -1,121 +0,0 @@
-#  Created by Luke A. Kanies on 2006-11-24.
-#  Copyright (c) 2006. All rights reserved.
-
-require 'puppet/relationship'
-require 'puppet/simple_graph'
-
-# This class subclasses a graph class in order to handle relationships
-# among resources.
-class Puppet::PGraph < Puppet::SimpleGraph
-    include Puppet::Util
-
-    def add_edge(*args)
-        @reversal = nil
-        super
-    end
-
-    def add_vertex(*args)
-        @reversal = nil
-        super
-    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
-    
-    # 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
-    
-    # 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
-
-    # 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
-end
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index c926258ca..73a6bdfed 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -94,10 +94,47 @@ class Puppet::SimpleGraph
         @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
+    
+    # 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
@@ -154,6 +191,7 @@ class Puppet::SimpleGraph
 
     # 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.
@@ -180,6 +218,7 @@ class Puppet::SimpleGraph
     # 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
@@ -250,6 +289,52 @@ class Puppet::SimpleGraph
 #            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
@@ -263,6 +348,16 @@ class Puppet::SimpleGraph
         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
@@ -304,6 +399,14 @@ class Puppet::SimpleGraph
       system('dotty', dotfile)
     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
+
     # 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')
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index e6dc60681..86467a5b4 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -431,8 +431,8 @@ class Transaction
     def initialize(resources)
         if resources.is_a?(Puppet::Node::Catalog)
             @catalog = resources
-        elsif resources.is_a?(Puppet::PGraph)
-            raise "Transactions should get catalogs now, not PGraph"
+        elsif resources.is_a?(Puppet::SimpleGraph)
+            raise "Transactions should get catalogs now, not SimpleGraph"
         else
             raise "Transactions require catalogs"
         end
diff --git a/lib/puppet/util/graph.rb b/lib/puppet/util/graph.rb
index d1ef36f8e..fc05cafd9 100644
--- a/lib/puppet/util/graph.rb
+++ b/lib/puppet/util/graph.rb
@@ -2,7 +2,7 @@
 #  Copyright (c) 2006. All rights reserved.
 
 require 'puppet'
-require 'puppet/pgraph'
+require 'puppet/simple_graph'
 
 # A module that handles the small amount of graph stuff in Puppet.
 module Puppet::Util::Graph
@@ -12,7 +12,7 @@ module Puppet::Util::Graph
     def to_graph(graph = nil, &block)
         # Allow our calling function to send in a graph, so that we
         # can call this recursively with one graph.
-        graph ||= Puppet::PGraph.new
+        graph ||= Puppet::SimpleGraph.new
         
         self.each do |child|
             unless block_given? and ! yield(child)
diff --git a/spec/unit/node/catalog.rb b/spec/unit/node/catalog.rb
index 68b8af347..6451632d5 100755
--- a/spec/unit/node/catalog.rb
+++ b/spec/unit/node/catalog.rb
@@ -685,12 +685,8 @@ describe Puppet::Node::Catalog, " when creating a relationship graph" do
         @relationships = @catalog.relationship_graph
     end
 
-    it "should fail when trying to create a relationship graph for a relationship graph" do
-        proc { @relationships.relationship_graph }.should raise_error(Puppet::DevError)
-    end
-
     it "should be able to create a relationship graph" do
-        @relationships.should be_instance_of(Puppet::Node::Catalog)
+        @relationships.should be_instance_of(Puppet::SimpleGraph)
     end
 
     it "should copy its host_config setting to the relationship graph" do
@@ -810,6 +806,7 @@ describe Puppet::Node::Catalog, " when writing dot files" do
         @name = :test
         @file = File.join(Puppet[:graphdir], @name.to_s + ".dot")
     end
+
     it "should only write when it is a host catalog" do
         File.expects(:open).with(@file).never
         @catalog.host_config = false
@@ -817,21 +814,6 @@ describe Puppet::Node::Catalog, " when writing dot files" do
         @catalog.write_graph(@name)
     end
 
-    it "should only write when graphing is enabled" do
-        File.expects(:open).with(@file).never
-        @catalog.host_config = true
-        Puppet[:graph] = false
-        @catalog.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))
-        @catalog.expects(:to_dot).with("name" => @name.to_s.capitalize)
-        @catalog.host_config = true
-        Puppet[:graph] = true
-        @catalog.write_graph(@name)
-    end
-
     after do
         Puppet.settings.clear
     end
diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb
deleted file mode 100755
index cad0832a5..000000000
--- a/spec/unit/other/pgraph.rb
+++ /dev/null
@@ -1,210 +0,0 @@
-#!/usr/bin/env ruby
-#
-#  Created by Luke Kanies on 2007-9-12.
-#  Copyright (c) 2006. All rights reserved.
-
-require File.dirname(__FILE__) + '/../../spec_helper'
-
-require 'puppet/pgraph'
-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 Puppet::PGraph do
-    before do
-        @graph = Puppet::PGraph.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 Puppet::PGraph, " when matching edges" do
-    before do
-        @graph = Puppet::PGraph.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 Puppet::PGraph, " when determining dependencies" do
-    before do
-        @graph = Puppet::PGraph.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
-
-describe Puppet::PGraph, " when splicing the relationship 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::PGraph.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
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index 322a527f1..a73e75a42 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -30,276 +30,491 @@ describe Puppet::SimpleGraph do
 
         proc { @graph.to_dot_graph }.should_not raise_error
     end
-end
 
-describe Puppet::SimpleGraph, " when managing vertices" do
-    before do
-        @graph = Puppet::SimpleGraph.new
-    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 provide a method to add a vertex" do
+            @graph.add_vertex(:test)
+            @graph.vertex?(:test).should be_true
+        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 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 return true when asked if a vertex is present" do
-        @graph.add_vertex(:test)
-        @graph.vertex?(:test).should be_true
-    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 false when asked if a non-vertex is present" do
-        @graph.vertex?(:test).should be_false
-    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 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 return false when asked if a non-vertex is present" do
+            @graph.vertex?(:test).should be_false
+        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 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 do nothing when a non-vertex is asked to be removed" do
-        proc { @graph.remove_vertex!(:one) }.should_not raise_error
-    end
-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
 
-describe Puppet::SimpleGraph, " when managing edges" do
-    before do
-        @graph = Puppet::SimpleGraph.new
+        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
 
-    it "should provide a method to test whether a given vertex pair is an edge" do
-        @graph.should respond_to(:edge?)
-    end
+    describe "when managing edges" do
+        before do
+            @graph = Puppet::SimpleGraph.new
+        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 test whether a given vertex pair is an edge" do
+            @graph.should respond_to(:edge?)
+        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 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 by specifying the two vertices and a label" do
-        @graph.add_edge(:one, :two, :stuff => :awesome)
-        @graph.edge?(:one, :two).should be_true
-    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 for retrieving an edge label" do
-        edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome)
-        @graph.add_edge(edge)
-        @graph.edge_label(:one, :two).should == {:stuff => :awesome}
-    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 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 provide a method to add an edge by specifying the two vertices and a label" do
+            @graph.add_edge(:one, :two, :stuff => :awesome)
+            @graph.edge?(:one, :two).should be_true
+        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 provide a method for retrieving an edge label" do
+            edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome)
+            @graph.add_edge(edge)
+            @graph.edge_label(:one, :two).should == {:stuff => :awesome}
+        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 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 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 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 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 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 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
+        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
 
-describe Puppet::SimpleGraph, " 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 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 return adjacent vertices" do
-        adj = @graph.adjacent(:one)
-        adj.should be_include(:three)
-        adj.should be_include(:two)
+        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
 
-    it "should default to finding :out vertices" do
-        @graph.adjacent(:two).should == [:three]
-    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 support selecting :in vertices" do
-        @graph.adjacent(:two, :direction => :in).should == [:one]
-    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 returning the matching vertices as an array of vertices" do
-        @graph.adjacent(:two).should == [:three]
-    end
+        it "should default to finding :out 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
-end
+        it "should support selecting :in vertices" do
+            @graph.adjacent(:two, :direction => :in).should == [:one]
+        end
 
-describe Puppet::SimpleGraph, " 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)
+        it "should default to returning the matching vertices as an array of vertices" do
+            @graph.adjacent(:two).should == [:three]
+        end
 
-        @graph.clear
+        it "should support returning an array of matching edges" do
+            @graph.adjacent(:two, :type => :edges).should == [@two_three]
+        end
     end
 
-    it "should remove all vertices" do
-        @graph.vertices.should be_empty
-    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)
 
-    it "should remove all edges" do
-        @graph.edges.should be_empty
-    end
-end
+            @graph.clear
+        end
 
-describe Puppet::SimpleGraph, " when reversing graphs" do
-    before do
-        @graph = Puppet::SimpleGraph.new
-    end
+        it "should remove all vertices" do
+            @graph.vertices.should be_empty
+        end
 
-    it "should provide a method for reversing the graph" do
-        @graph.add_edge(:one, :two)
-        @graph.reversal.edge?(:two, :one).should be_true
+        it "should remove all edges" do
+            @graph.edges.should be_empty
+        end
     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, :stuff => :awesome)
-        edge = @graph.reversal.edge(:two, :one)
-        edge.label.should == {:stuff => :awesome}
-    end
-end
+    describe "when reversing graphs" do
+        before do
+            @graph = Puppet::SimpleGraph.new
+        end
 
-describe Puppet::SimpleGraph, " when sorting the graph" 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
 
-    def add_edges(hash)
-        hash.each do |a,b|
-            @graph.add_edge(a, b)
+        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, :stuff => :awesome)
+            edge = @graph.reversal.edge(:two, :one)
+            edge.label.should == {:stuff => :awesome}
         end
     end
 
-    it "should sort the graph topologically" do
-        add_edges :a => :b, :b => :c
-        @graph.topsort.should == [:a, :b, :c]
-    end
+    describe "when sorting the graph" do
+        before do
+            @graph = Puppet::SimpleGraph.new
+        end
 
-    it "should fail on two-vertex loops" do
-        add_edges :a => :b, :b => :a
-        proc { @graph.topsort }.should raise_error(Puppet::Error)
-    end
+        def add_edges(hash)
+            hash.each do |a,b|
+                @graph.add_edge(a, b)
+            end
+        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 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
 
-    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)
+        # 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
 
-    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
+    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
 
-    # 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
+    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
-end
 
-describe Puppet::SimpleGraph, " when writing dot files" do
-    before do
-        @graph = Puppet::SimpleGraph.new
-        @name = :test
-        @file = File.join(Puppet[:graphdir], @name.to_s + ".dot")
+    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
 
-    it "should only write when graphing is enabled" do
-        File.expects(:open).with(@file).never
-        Puppet[:graph] = false
-        @graph.write_graph(@name)
+    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
 
-    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)
+    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
 
-    after do
-        Puppet.settings.clear
+    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