Merge branch 'rest'

13 files changed, 575 insertions, 144 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 83b6710e2..5a7103403 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,3 +1,8 @@
+    Replaced GRATR::Digraph with Puppet::SimpleGraph as
+    the base class for Puppet's graphing.  Functionality
+    should be equivalent but with dramatically better
+    performance.
+
     The --use-nodes and --no-nodes options are now obsolete.
     Puppet automatically detects when nodes are defined, and if
     they are defined it will require that a node be found,
diff --git a/lib/puppet/network/xmlrpc/client.rb b/lib/puppet/network/xmlrpc/client.rb
index c652dbf8d..ab4117b0e 100644
--- a/lib/puppet/network/xmlrpc/client.rb
+++ b/lib/puppet/network/xmlrpc/client.rb
@@ -128,12 +128,12 @@ module Puppet::Network
                 120 # a two minute timeout, instead of 30 seconds
             )
 
-	    # We overwrite the uninitialized @http here with a cached one.
+            # We overwrite the uninitialized @http here with a cached one.
             key = "%s%s" % [hash[:Server], hash[:Port]]
             if @@http_cache[key]
-                    @http = @@http_cache[key]
+                @http = @@http_cache[key]
             else
-                    @@http_cache[key] = @http
+                @@http_cache[key] = @http
             end
         end
 
@@ -150,4 +150,3 @@ module Puppet::Network
         end
     end
 end
-
diff --git a/lib/puppet/node/configuration.rb b/lib/puppet/node/configuration.rb
index f2bbfca00..e49090d70 100644
--- a/lib/puppet/node/configuration.rb
+++ b/lib/puppet/node/configuration.rb
@@ -33,6 +33,11 @@ class Puppet::Node::Configuration < Puppet::PGraph
     # that the host configuration needs.
     attr_accessor :host_config
 
+    # Whether this graph is another configuration's relationship graph.
+    # We don't want to accidentally create a relationship graph for another
+    # relationship graph.
+    attr_accessor :is_relationship_graph
+
     # Add classes to our class list.
     def add_class(*classes)
         classes.each do |klass|
@@ -56,7 +61,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
             else
                 @resource_table[ref] = resource
             end
-            resource.configuration = self
+            resource.configuration = self unless is_relationship_graph
             add_vertex!(resource)
         end
     end
@@ -78,6 +83,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
 
         transaction.addtimes :config_retrieval => @retrieval_duration
 
+
         begin
             transaction.evaluate
         rescue Puppet::Error => detail
@@ -167,6 +173,9 @@ class Puppet::Node::Configuration < Puppet::PGraph
 
         @transient_resources << resource if applying?
         add_resource(resource)
+        if @relationship_graph
+            @relationship_graph.add_resource(resource) unless @relationship_graph.resource(resource.ref)
+        end
         resource
     end
 
@@ -273,6 +282,8 @@ class Puppet::Node::Configuration < Puppet::PGraph
     
     # Create a graph of all of the relationships in our configuration.
     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
@@ -281,6 +292,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
             # then we get into an infinite loop.
             @relationship_graph = Puppet::Node::Configuration.new
             @relationship_graph.host_config = host_config?
+            @relationship_graph.is_relationship_graph = true
             
             # First create the dependency graph
             self.vertices.each do |vertex|
@@ -293,7 +305,7 @@ class Puppet::Node::Configuration < Puppet::PGraph
             # Lastly, add in any autorequires
             @relationship_graph.vertices.each do |vertex|
                 vertex.autorequire.each do |edge|
-                    unless @relationship_graph.edge?(edge)
+                    unless @relationship_graph.edge?(edge.source, edge.target) # don't let automatic relationships conflict with manual ones.
                         unless @relationship_graph.edge?(edge.target, edge.source)
                             vertex.debug "Autorequiring %s" % [edge.source]
                             @relationship_graph.add_edge!(edge)
diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
index ca45aa2b3..49fd21401 100644
--- a/lib/puppet/pgraph.rb
+++ b/lib/puppet/pgraph.rb
@@ -4,11 +4,13 @@
 require 'puppet/external/gratr/digraph'
 require 'puppet/external/gratr/import'
 require 'puppet/external/gratr/dot'
+
 require 'puppet/relationship'
+require 'puppet/simple_graph'
 
 # This class subclasses a graph class in order to handle relationships
 # among resources.
-class Puppet::PGraph < GRATR::Digraph
+class Puppet::PGraph < Puppet::SimpleGraph
     # This is the type used for splicing.
     attr_accessor :container_type
 
@@ -23,13 +25,6 @@ class Puppet::PGraph < GRATR::Digraph
         @reversal = nil
         super
     end
-    
-    def clear
-        @vertex_dict.clear
-        if defined? @edge_number
-            @edge_number.clear
-        end
-    end
 
     # Make sure whichever edge has a label keeps the label
     def copy_label(source, target, label)
@@ -149,7 +144,7 @@ class Puppet::PGraph < GRATR::Digraph
                     # Now get rid of the edge, so remove_vertex! works correctly.
                     remove_edge!(edge)
                     Puppet.debug "%s: %s => %s: %s" % [container,
-                        edge.source, edge.target, edge?(edge)]
+                        edge.source, edge.target, edge?(edge.source, edge.target)]
                 end
             end
             remove_vertex!(container)
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
new file mode 100644
index 000000000..48bf4991e
--- /dev/null
+++ b/lib/puppet/simple_graph.rb
@@ -0,0 +1,251 @@
+#  Created by Luke A. Kanies on 2007-11-07.
+#  Copyright (c) 2007. All rights reserved.
+
+require 'puppet/external/gratr/dot'
+require 'puppet/relationship'
+require 'puppet/external/gratr/search'
+
+# A hopefully-faster graph class to replace the use of GRATR.
+class Puppet::SimpleGraph
+    include GRATR::Graph::Search
+
+    # 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 => Hash.new { |h,k| h[k] = [] }, :out => Hash.new { |h,k| h[k] = [] }}
+            #@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
+        end
+
+        # Add an edge to our list.
+        def add_edge(direction, edge)
+            @adjacencies[direction][other_vertex(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 @adjacencies[direction][vertex].length > 0
+            return false
+        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)
+            @adjacencies[direction][other_vertex(direction, edge)].delete(edge)
+        end
+    end
+
+    def initialize
+        @vertices = {}
+        @edges = []
+    end
+
+    # Clear our graph.
+    def clear
+        @vertices.each { |vertex, wrapper| wrapper.clear }
+        @vertices.clear
+        @edges.clear
+    end
+
+    # Whether our graph is directed.  Always true.  (Used by the GRATR search lib.)
+    def directed?
+        true
+    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. Used by GRATR.
+    def size
+        @vertices.length
+    end
+
+    # Return the graph as an array.  Again, used by GRATR.
+    def to_a
+        @vertices.keys
+    end
+
+    # Add a new vertex to the graph.
+    def add_vertex!(vertex)
+        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)
+        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
+
+    # 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 = vertex_label(v)
+        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 = edge_label(e)
+        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
+end
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index 3c72f6e97..c8fc2f199 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -202,12 +202,7 @@ class Transaction
             end
             
             if children
-                children.each do |child|
-                    child.finish
-                    # Make sure that the vertex is in the relationship graph.
-                    relationship_graph.add_resource(child) unless relationship_graph.resource(child.ref)
-                    child.configuration = relationship_graph
-                end
+                children.each { |child| child.finish }
                 @generated += children
                 return children
             end
@@ -299,7 +294,7 @@ class Transaction
     # necessary events.
     def evaluate
         @count = 0
-        
+
         # Start logging.
         Puppet::Util::Log.newdestination(@report)
         
@@ -483,7 +478,7 @@ class Transaction
     # types, just providers.
     def prefetch
         prefetchers = {}
-        @configuration.each do |resource|
+        @configuration.vertices.each do |resource|
             if provider = resource.provider and provider.class.respond_to?(:prefetch)
                 prefetchers[provider.class] ||= {}
                 prefetchers[provider.class][resource.title] = resource
diff --git a/lib/puppet/type.rb b/lib/puppet/type.rb
index 0a6ccdaa4..b7ff1f664 100644
--- a/lib/puppet/type.rb
+++ b/lib/puppet/type.rb
@@ -316,19 +316,22 @@ class Type
     def parent
         return nil unless configuration
 
-        # This is kinda weird.
-        if implicit?
-            parents = configuration.relationship_graph.adjacent(self, :direction => :in)
-        else
-            parents = configuration.adjacent(self, :direction => :in)
-        end
-        if parents
-            # We should never have more than one parent, so let's just ignore
-            # it if we happen to.
-            return parents.shift
-        else
-            return nil
+        unless defined?(@parent)
+            # This is kinda weird.
+            if implicit?
+                parents = configuration.relationship_graph.adjacent(self, :direction => :in)
+            else
+                parents = configuration.adjacent(self, :direction => :in)
+            end
+            if parents
+                # We should never have more than one parent, so let's just ignore
+                # it if we happen to.
+                @parent = parents.shift
+            else
+                @parent = nil
+            end
         end
+        @parent
     end
 
     # Return the "type[name]" style reference.
diff --git a/lib/puppet/type/pfile.rb b/lib/puppet/type/pfile.rb
index f0a805525..73c60bd14 100644
--- a/lib/puppet/type/pfile.rb
+++ b/lib/puppet/type/pfile.rb
@@ -574,9 +574,8 @@ module Puppet
         # Create a new file or directory object as a child to the current
         # object.
         def newchild(path, local, hash = {})
-            unless configuration
-                raise Puppet::DevError, "File recursion cannot happen without a configuration"
-            end
+            raise(Puppet::DevError, "File recursion cannot happen without a configuration") unless configuration
+
             # make local copy of arguments
             args = symbolize_options(@arghash)
 
@@ -655,9 +654,7 @@ module Puppet
             # LAK:FIXME This shouldn't be necessary, but as long as we're
             # modeling the relationship graph specifically, it is.
             configuration.relationship_graph.add_edge! self, child
-            unless child.parent
-                raise "Did not set parent of %s" % child.ref
-            end
+
             return child
         end
 
diff --git a/spec/unit/node/configuration.rb b/spec/unit/node/configuration.rb
index 5f807b9b6..e9dc6b85d 100755
--- a/spec/unit/node/configuration.rb
+++ b/spec/unit/node/configuration.rb
@@ -312,6 +312,17 @@ describe Puppet::Node::Configuration, " when functioning as a resource container
         @config.resource(@two.ref).should equal(@two)
     end
 
+    it "should set itself as the resource's configuration if it is not a relationship graph" do
+        @one.expects(:configuration=).with(@config)
+        @config.add_resource @one
+    end
+
+    it "should not set itself as the resource's configuration if it is a relationship graph" do
+        @one.expects(:configuration=).never
+        @config.is_relationship_graph = true
+        @config.add_resource @one
+    end
+
     it "should make all vertices available by resource reference" do
         @config.add_resource(@one)
         @config.resource(@one.ref).should equal(@one)
@@ -516,6 +527,10 @@ describe Puppet::Node::Configuration, " when creating a relationship graph" do
         @relationships = @config.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::Configuration)
     end
@@ -578,6 +593,18 @@ describe Puppet::Node::Configuration, " when creating a relationship graph" do
         @config.resource("File[/yay]").should equal(resource)
     end
 
+    it "should add implicit resources to the relationship graph if there is one" do
+        args = {:name => "/yay", :ensure => :file}
+        resource = stub 'file', :ref => "File[/yay]", :configuration= => @config
+        resource.expects(:implicit=).with(true)
+        Puppet::Type.type(:file).expects(:create).with(args).returns(resource)
+        # build the graph
+        relgraph = @config.relationship_graph
+
+        @config.create_implicit_resource :file, args
+        relgraph.resource("File[/yay]").should equal(resource)
+    end
+
     it "should remove resources created mid-transaction" do
         args = {:name => "/yay", :ensure => :file}
         resource = stub 'file', :ref => "File[/yay]", :configuration= => @config
diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb
index 19809ac1e..9446a8371 100755
--- a/spec/unit/other/pgraph.rb
+++ b/spec/unit/other/pgraph.rb
@@ -122,7 +122,7 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
     def dependency_graph
         @depgraph = Puppet::PGraph.new
         @contgraph.vertices.each do |v|
-            @depgraph.add_vertex(v)
+            @depgraph.add_vertex!(v)
         end
 
         # We have to specify a relationship to our empty container, else it
@@ -204,54 +204,12 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
         splice
         @three.each do |child|
             edge = @depgraph.edge_class.new("c", child)
-            @depgraph.should be_edge(edge)
-            @depgraph[edge].should == {:callback => :refresh}
+            @depgraph.should be_edge(edge.source, edge.target)
+            @depgraph.edge_label(edge.source, edge.target).should == {:callback => :refresh}
         end
     end
 end
 
-# Labels in this graph are used for managing relationships,
-# including callbacks, so they're quite important.
-describe Puppet::PGraph, " when managing labels" do
-    before do
-        @graph = Puppet::PGraph.new
-        @label = {:callback => :yay}
-    end
-
-    it "should return nil for edges with no label" do
-        @graph.add_edge!(:a, :b)
-        @graph.edge_label(:a, :b).should be_nil
-    end
-
-    it "should just return empty label hashes" do
-        @graph.add_edge!(:a, :b, {})
-        @graph.edge_label(:a, :b).should == {}
-    end
-
-    it "should consider empty label hashes to be nil when copying" do
-        @graph.add_edge!(:a, :b)
-        @graph.copy_label(:a, :b, {})
-        @graph.edge_label(:a, :b).should be_nil
-    end
-
-    it "should return label hashes" do
-        @graph.add_edge!(:a, :b, @label)
-        @graph.edge_label(:a, :b).should == @label
-    end
-
-    it "should replace nil labels with real labels" do
-        @graph.add_edge!(:a, :b)
-        @graph.copy_label(:a, :b, @label)
-        @graph.edge_label(:a, :b).should == @label
-    end
-
-    it "should not replace labels with nil labels" do
-        @graph.add_edge!(:a, :b, @label)
-        @graph.copy_label(:a, :b, {})
-        @graph.edge_label(:a, :b).should == @label
-    end
-end
-
 describe Puppet::PGraph, " when sorting the graph" do
     before do
         @graph = Puppet::PGraph.new
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
new file mode 100755
index 000000000..1be29c0dc
--- /dev/null
+++ b/spec/unit/simple_graph.rb
@@ -0,0 +1,225 @@
+#!/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
+end
+
+describe Puppet::SimpleGraph, " 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 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.should == [:one, :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 Puppet::SimpleGraph, " 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 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, :stuff => :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, :stuff => :awesome)
+        @graph.add_edge!(edge)
+        @graph.edge_label(:one, :two).should == {:stuff => :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 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 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
+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)
+
+        @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 Puppet::SimpleGraph, " 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
+    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 Puppet::SimpleGraph, " when making DOT files" do
+    # LAK:FIXME yay
+    it "should have tests"
+end
diff --git a/test/executables/puppetd.rb b/test/executables/puppetd.rb
index a482e4b34..3dd3856fd 100755
--- a/test/executables/puppetd.rb
+++ b/test/executables/puppetd.rb
@@ -10,49 +10,44 @@ require 'facter'
 
 class TestPuppetDExe < Test::Unit::TestCase
     include PuppetTest::ExeTest
-    def test_normalstart
+    def setup
+        super
         # start the master
-        file = startmasterd
-
-        # create the client
-        client = Puppet::Network::Client.master.new(:Server => "localhost", :Port => @@port)
-
-        # make a new fqdn
-        fqdn = Puppet[:certname].sub(/^\w+\./, "testing.")
-
-        cmd = "puppetd"
-        cmd += " --verbose"
-        cmd += " --onetime"
-        cmd += " --masterport %s" % @@port
-        cmd += " --confdir %s" % Puppet[:confdir]
-        cmd += " --rundir %s" % File.join(Puppet[:vardir], "run")
-        cmd += " --vardir %s" % Puppet[:vardir]
-        cmd += " --server localhost"
+        @manifest = startmasterd
+
+        @cmd = "puppetd"
+        @cmd += " --verbose"
+        @cmd += " --test"
+        @cmd += " --masterport %s" % @@port
+        @cmd += " --confdir %s" % Puppet[:confdir]
+        @cmd += " --rundir %s" % File.join(Puppet[:vardir], "run")
+        @cmd += " --vardir %s" % Puppet[:vardir]
+        @cmd += " --server localhost"
+    end
 
+    def test_normalstart
         # and verify our daemon runs
+        output = nil
         assert_nothing_raised {
-            %x{#{cmd} 2>&1}
+            output = %x{#{@cmd} 2>&1}
         }
         sleep 1
         assert($? == 0, "Puppetd exited with code %s" % $?)
 
-        assert(FileTest.exists?(@createdfile),
-            "Failed to create config'ed file")
-
-        # now verify that --noop works
-        File.unlink(@createdfile)
+        assert(FileTest.exists?(@createdfile), "Failed to create file %s" % @createdfile)
+    end
 
-        cmd += " --noop"
+    # now verify that --noop works
+    def test_noop_start
+        @cmd += " --noop"
         assert_nothing_raised {
-            output = %x{#{cmd}}.chomp
+            output = %x{#{@cmd}}.chomp
         }
         sleep 1
         assert($? == 0, "Puppetd exited with code %s" % $?)
 
         assert(! FileTest.exists?(@createdfile),
             "Noop created config'ed file")
-
-        stopmasterd
     end
 end
 
diff --git a/test/other/transactions.rb b/test/other/transactions.rb
index fb5cf4018..8156ba478 100755
--- a/test/other/transactions.rb
+++ b/test/other/transactions.rb
@@ -1006,37 +1006,6 @@ class TestTransactions < Test::Unit::TestCase
         end
     end
 
-    def test_labeled_deps_beat_unlabeled
-        one = Puppet::Type.type(:exec).create :command => "/bin/echo one"
-        two = Puppet::Type.type(:exec).create :command => "/bin/echo two"
-
-        one[:require] = two
-        one[:subscribe] = two
-
-        comp = mk_configuration(one, two)
-        trans = Puppet::Transaction.new(comp)
-        graph = trans.relationship_graph
-
-        label = graph.edge_label(two, one)
-        assert(label, "require beat subscribe")
-        assert_equal(:refresh, label[:callback],
-            "did not get correct callback from subscribe")
-
-        one.delete(:require)
-        one.delete(:subscribe)
-
-        two[:before] = one
-        two[:notify] = one
-
-        trans = Puppet::Transaction.new(comp)
-        graph = trans.relationship_graph
-
-        label = graph.edge_label(two, one)
-        assert(label, "before beat notify")
-        assert_equal(:refresh, label[:callback],
-            "did not get correct callback from notify")
-    end
-
     # #542 - make sure resources in noop mode still notify their resources,
     # so that users know if a service will get restarted.
     def test_noop_with_notify