diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 55b39fadf..6d153b46d 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -1,448 +1,449 @@
 #  Created by Luke A. Kanies on 2007-11-07.
 #  Copyright (c) 2007. All rights reserved.
 
 require 'puppet/external/dot'
 require 'puppet/relationship'
 require 'set'
 
 # 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 send(direction.to_s + "_edges") if options[:type] == :edges
-
-      @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_edges + out_edges
-    end
-
-    # Test whether we share an edge with a given vertex.
-    def has_edge?(direction, vertex)
-      return(vertex_adjacencies(direction, vertex).length > 0 ? true : 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("#{direction}_edges") do
-        @adjacencies[direction].values.inject([]) { |total, adjacent| total += adjacent.to_a; total }
-      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] ||= Set.new
-      @adjacencies[direction][vertex]
-    end
-  end
-
+  #
+  # All public methods of this class must maintain (assume ^ ensure) the following invariants, where "=~=" means
+  # equiv. up to order:
+  #
+  #   @in_to.keys =~= @out_to.keys =~= all vertices
+  #   @in_to.values.collect { |x| x.values }.flatten =~= @out_from.values.collect { |x| x.values }.flatten =~= all edges
+  #   @in_to[v1][v2] =~= @out_from[v2][v1] =~= all edges from v1 to v2
+  #   @in_to   [v].keys =~= vertices with edges leading to   v
+  #   @out_from[v].keys =~= vertices with edges leading from v
+  #   no operation may shed reference loops (for gc)
+  #   recursive operation must scale with the depth of the spanning trees, or better (e.g. no recursion over the set
+  #       of all vertices, etc.)
+  #
+  # This class is intended to be used with DAGs.  However, if the
+  # graph has a cycle, it will not cause non-termination of any of the
+  # algorithms.  The topsort method detects and reports cycles.
+  #
   def initialize
-    @vertices = {}
-    @edges = []
+    @in_to = {}
+    @out_from = {}
+    @upstream_from = {}
+    @downstream_from = {}
   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
+    @in_to.clear
+    @out_from.clear
+    @upstream_from.clear
+    @downstream_from.clear
   end
 
   # Which resources depend upon the given resource.
   def dependencies(resource)
-    # Cache the reversal graph, because it's somewhat expensive
-    # to create.
-    @reversal ||= reversal
-    # 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
+    vertex?(resource) ? upstream_from_vertex(resource).keys : []
+  end
+
+  def dependents(resource)
+    vertex?(resource) ? downstream_from_vertex(resource).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? }
+    tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? }
   end
 
   # Collect all of the edges that the passed events match.  Returns
   # an array of edges.
   def matching_edges(event, base = nil)
     source = base || event.resource
 
     unless vertex?(source)
       Puppet.warning "Got an event from invalid vertex #{source.ref}"
       return []
     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
+    @out_from[source].values.flatten.find_all { |edge| edge.match?(event.name) }
   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)
+      result.add_edge edge.class.new(edge.target, edge.source, edge.label)
     end
     result
   end
 
   # Return the size of the graph.
   def size
-    @vertices.length
+    vertices.size
   end
 
-  # Return the graph as an array.
   def to_a
-    @vertices.keys
+    vertices
+  end
+
+  # Provide a topological sort with cycle reporting
+  def topsort_with_cycles
+    degree = {}
+    zeros = []
+    result = []
+
+    # Collect each of our vertices, with the number of in-edges each has.
+    vertices.each do |v|
+      edges = @in_to[v].dup
+      zeros << v if edges.empty?
+      degree[v] = edges
+    end
+
+    # Iterate over each 0-degree vertex, decrementing the degree of
+    # each of its out-edges.
+    while v = zeros.pop
+      result << v
+      @out_from[v].each { |v2,es| 
+        degree[v2].delete(v)
+        zeros << v2 if degree[v2].empty?
+      }
+    end
+
+    # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
+    if cycles = degree.values.reject { |ns| ns.empty? } and cycles.length > 0
+      message = cycles.collect { |edges| '('+edges.collect { |e| e.to_s }.join(", ")+')' }.join(", ")
+      raise Puppet::Error, "Found dependency cycles in the following relationships: #{message}; try using the '--graph' option and open the '.dot' files in OmniGraffle or GraphViz"
+    end
+
+    result
   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
+    vertices.each do |v|
+      edges = @in_to[v]
+      zeros << v if edges.empty?
+      degree[v] = edges.length
     end
 
     # Iterate over each 0-degree vertex, decrementing the degree of
     # each of its out-edges.
-    while wrapper = zeros.pop
-      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
+    while v = zeros.pop
+      result << v
+      @out_from[v].each { |v2,es| 
+        zeros << v2 if (degree[v2] -= 1) == 0
+      }
     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: #{message}; try using the '--graph' option and open the '.dot' files in OmniGraffle or GraphViz"
+    if cycles = degree.values.reject { |ns| ns == 0  } and cycles.length > 0
+      topsort_with_cycles
     end
 
     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.
+    @in_to[vertex]    ||= {}
+    @out_from[vertex] ||= {}
   end
 
   # Remove a vertex from the graph.
-  def remove_vertex!(vertex)
-    return nil unless vertex?(vertex)
-    @vertices[vertex].edges.each { |edge| remove_edge!(edge) }
-    @edges -= @vertices[vertex].edges
-    @vertices[vertex].clear
-    @vertices.delete(vertex)
+  def remove_vertex!(v)
+    return unless vertex?(v)
+    @upstream_from.clear
+    @downstream_from.clear
+    (@in_to[v].values+@out_from[v].values).flatten.each { |e| remove_edge!(e) }
+    @in_to.delete(v)
+    @out_from.delete(v)
   end
 
   # Test whether a given vertex is in the graph.
-  def vertex?(vertex)
-    @vertices.include?(vertex)
+  def vertex?(v)
+    @in_to.include?(v)
   end
 
   # Return a list of all vertices.
   def vertices
-    @vertices.keys
+    @in_to.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
+  def add_edge(e,*a)
+    return add_relationship(e,*a) unless a.empty?
+    @upstream_from.clear
+    @downstream_from.clear
+    add_vertex(e.source)
+    add_vertex(e.target)
+    @in_to[   e.target][e.source] ||= []; @in_to[   e.target][e.source] |= [e]
+    @out_from[e.source][e.target] ||= []; @out_from[e.source][e.target] |= [e]
   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 }
+  def add_relationship(source, target, label = nil)
+    add_edge Puppet::Relationship.new(source, target, label)
   end
 
-  def edge_label(source, target)
-    return nil unless edge = edge(source, target)
-    edge.label
+  # Find all matching edges.
+  def edges_between(source, target)
+    (@out_from[source] || {})[target] || []
   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)
+    vertex?(source) and vertex?(target) and @out_from[source][target]
   end
 
   def edges
-    @edges.dup
+    @in_to.values.collect { |x| x.values }.flatten
   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)
-
-    @edges.delete(edge)
-    nil
+  def each_edge
+    @in_to.each { |t,ns| ns.each { |s,es| es.each { |e| yield e }}}
   end
 
-  # Find adjacent edges.
-  def adjacent(vertex, options = {})
-    return [] unless wrapper = @vertices[vertex]
-    wrapper.adjacent(options)
+  # Remove an edge from our graph.
+  def remove_edge!(e)
+    if edge?(e.source,e.target)
+      @upstream_from.clear
+      @downstream_from.clear
+      @in_to   [e.target].delete e.source if (@in_to   [e.target][e.source] -= [e]).empty?
+      @out_from[e.source].delete e.target if (@out_from[e.source][e.target] -= [e]).empty?
+    end
   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)
+  # Find adjacent edges.
+  def adjacent(v, options = {})
+    return [] unless ns = (options[:direction] == :in) ? @in_to[v] : @out_from[v]
+    (options[:type] == :edges) ? ns.values.flatten : ns.keys
   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.
     stage_class = Puppet::Type.type(:stage)
     whit_class  = Puppet::Type.type(:whit)
     containers = other.topsort.find_all { |v| (v.is_a?(type) or v.is_a?(stage_class)) and vertex?(v) }
     containers.each do |container|
       # Get the list of children from the other graph.
       children = other.adjacent(container, :direction => :out)
 
       # MQR TODO: Luke suggests that it should be possible to refactor the system so that
       #           container nodes are retained, thus obviating the need for the whit. 
       children = [whit_class.new(:name => container.name, :catalog => other)] if children.empty?
 
       # 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
 
   # Just walk the tree and pass each edge.
   def walk(source, direction)
     # Use an iterative, breadth-first traversal of the graph. One could do
     # this recursively, but Ruby's slow function calls and even slower
     # recursion make the shorter, recursive algorithm cost-prohibitive.
     stack = [source]
     seen = Set.new
     until stack.empty?
       node = stack.shift
       next if seen.member? node
       connected = adjacent(node, :direction => direction)
       connected.each do |target|
         yield node, target
       end
       stack.concat(connected)
       seen << node
     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
 
+  def downstream_from_vertex(v)
+    return @downstream_from[v] if @downstream_from[v]
+    result = @downstream_from[v] = {}
+    @out_from[v].keys.each do |node|
+      result[node] = 1
+      result.update(downstream_from_vertex(node))
+    end
+    result
+  end
+
+  def upstream_from_vertex(v)
+    return @upstream_from[v] if @upstream_from[v]
+    result = @upstream_from[v] = {}
+    @in_to[v].keys.each do |node|
+      result[node] = 1
+      result.update(upstream_from_vertex(node))
+    end
+    result
+  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], "#{name}.dot")
     File.open(file, "w") { |f|
       f.puts to_dot("name" => name.to_s.capitalize)
     }
   end
+
+  # This flag may be set to true to use the new YAML serialzation
+  # format (where @vertices is a simple list of vertices rather than a
+  # list of VertexWrapper objects).  Deserialization supports both
+  # formats regardless of the setting of this flag.
+  class << self
+    attr_accessor :use_new_yaml_format
+  end
+  self.use_new_yaml_format = false
+
+  # Stub class to allow graphs to be represented in YAML using the old
+  # (version 2.6) format.
+  class VertexWrapper
+    attr_reader :vertex, :adjacencies
+    def initialize(vertex, adjacencies)
+      @vertex = vertex
+      @adjacencies = adjacencies
+    end
+  end
+
+  # instance_variable_get is used by Object.to_zaml to get instance
+  # variables.  Override it so that we can simulate the presence of
+  # instance variables @edges and @vertices for serialization.
+  def instance_variable_get(v)
+    case v.to_s
+    when '@edges' then
+      edges
+    when '@vertices' then
+      if self.class.use_new_yaml_format
+        vertices
+      else
+        result = {}
+        vertices.each do |vertex|
+          adjacencies = {}
+          [:in, :out].each do |direction|
+            adjacencies[direction] = {}
+            adjacent(vertex, :direction => direction, :type => :edges).each do |edge|
+              other_vertex = direction == :in ? edge.source : edge.target
+              (adjacencies[direction][other_vertex] ||= Set.new).add(edge)
+            end
+          end
+          result[vertex] = Puppet::SimpleGraph::VertexWrapper.new(vertex, adjacencies)
+        end
+        result
+      end
+    else
+      super(v)
+    end
+  end
+
+  def to_yaml_properties
+    other_vars = instance_variables.reject { |v| %w{@in_to @out_from @upstream_from @downstream_from}.include?(v) }
+    (other_vars + %w{@vertices @edges}).sort.uniq
+  end
+
+  def yaml_initialize(tag, var)
+    initialize()
+    vertices = var.delete('vertices')
+    edges = var.delete('edges')
+    if vertices.is_a?(Hash)
+      # Support old (2.6) format
+      vertices = vertices.keys
+    end
+    vertices.each { |v| add_vertex(v) }
+    edges.each { |e| add_edge(e) }
+    var.each do |varname, value|
+      instance_variable_set("@#{varname}", value)
+    end
+  end
 end
diff --git a/lib/puppet/util/monkey_patches.rb b/lib/puppet/util/monkey_patches.rb
index bdce5ec1d..1c35ae523 100644
--- a/lib/puppet/util/monkey_patches.rb
+++ b/lib/puppet/util/monkey_patches.rb
@@ -1,58 +1,73 @@
 
 unless defined? JRUBY_VERSION
   Process.maxgroups = 1024
 end
 
 module RDoc
   def self.caller(skip=nil)
     in_gem_wrapper = false
     Kernel.caller.reject { |call|
       in_gem_wrapper ||= call =~ /#{Regexp.escape $0}:\d+:in `load'/
     }
   end
 end
 
 
 require "yaml"
 require "puppet/util/zaml.rb"
 
 class Symbol
   def to_zaml(z)
     z.emit("!ruby/sym ")
     to_s.to_zaml(z)
   end
 end
 
 [Object, Exception, Integer, Struct, Date, Time, Range, Regexp, Hash, Array, Float, String, FalseClass, TrueClass, Symbol, NilClass, Class].each { |cls|
   cls.class_eval do
     def to_yaml(ignored=nil)
       ZAML.dump(self)
     end
   end
 }
 
 def YAML.dump(*args)
   ZAML.dump(*args)
 end
 
 #
 # Workaround for bug in MRI 1.8.7, see
 #     http://redmine.ruby-lang.org/issues/show/2708
 # for details
 #
 if RUBY_VERSION == '1.8.7'
   class NilClass
     def closed?
       true
     end
   end
 end
 
+
 class Object
   # ActiveSupport 2.3.x mixes in a dangerous method
   # that can cause rspec to fork bomb
   # and other strange things like that.
   def daemonize
     raise NotImplementedError, "Kernel.daemonize is too dangerous, please don't try to use it."
   end
 end
+
+# Workaround for yaml_initialize, which isn't supported before Ruby
+# 1.8.3.
+if RUBY_VERSION == '1.8.1' || RUBY_VERSION == '1.8.2'
+  YAML.add_ruby_type( /^object/ ) { |tag, val|
+    type, obj_class = YAML.read_type_class( tag, Object )
+    r = YAML.object_maker( obj_class, val )
+    if r.respond_to? :yaml_initialize
+      r.instance_eval { instance_variables.each { |name| remove_instance_variable name } }
+      r.yaml_initialize(tag, val)
+    end
+    r
+  }
+end
diff --git a/spec/unit/resource/catalog_spec.rb b/spec/unit/resource/catalog_spec.rb
index 2b6beb5e9..fbfe29ff3 100755
--- a/spec/unit/resource/catalog_spec.rb
+++ b/spec/unit/resource/catalog_spec.rb
@@ -1,1078 +1,1078 @@
 #!/usr/bin/env ruby
 
 require File.dirname(__FILE__) + '/../../spec_helper'
 
 describe Puppet::Resource::Catalog, "when compiling" do
 
   before do
     @basepath = Puppet.features.posix? ? "/somepath" : "C:/somepath"
     # stub this to not try to create state.yaml
     Puppet::Util::Storage.stubs(:store)
   end
 
   it "should be an Expirer" do
     Puppet::Resource::Catalog.ancestors.should be_include(Puppet::Util::Cacher::Expirer)
   end
 
   it "should always be expired if it's not applying" do
     @catalog = Puppet::Resource::Catalog.new("host")
     @catalog.expects(:applying?).returns false
     @catalog.should be_dependent_data_expired(Time.now)
   end
 
   it "should not be expired if it's applying and the timestamp is late enough" do
     @catalog = Puppet::Resource::Catalog.new("host")
     @catalog.expire
     @catalog.expects(:applying?).returns true
     @catalog.should_not be_dependent_data_expired(Time.now)
   end
 
   it "should be able to write its list of classes to the class file" do
     @catalog = Puppet::Resource::Catalog.new("host")
 
     @catalog.add_class "foo", "bar"
 
     Puppet.settings.expects(:value).with(:classfile).returns "/class/file"
 
     fh = mock 'filehandle'
     File.expects(:open).with("/class/file", "w").yields fh
 
     fh.expects(:puts).with "foo\nbar"
 
     @catalog.write_class_file
   end
 
   it "should have a client_version attribute" do
     @catalog = Puppet::Resource::Catalog.new("host")
     @catalog.client_version = 5
     @catalog.client_version.should == 5
   end
 
   it "should have a server_version attribute" do
     @catalog = Puppet::Resource::Catalog.new("host")
     @catalog.server_version = 5
     @catalog.server_version.should == 5
   end
 
   describe "when compiling" do
     it "should accept tags" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.tag("one")
       config.tags.should == %w{one}
     end
 
     it "should accept multiple tags at once" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.tag("one", "two")
       config.tags.should == %w{one two}
     end
 
     it "should convert all tags to strings" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.tag("one", :two)
       config.tags.should == %w{one two}
     end
 
     it "should tag with both the qualified name and the split name" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.tag("one::two")
       config.tags.include?("one").should be_true
       config.tags.include?("one::two").should be_true
     end
 
     it "should accept classes" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.add_class("one")
       config.classes.should == %w{one}
       config.add_class("two", "three")
       config.classes.should == %w{one two three}
     end
 
     it "should tag itself with passed class names" do
       config = Puppet::Resource::Catalog.new("mynode")
       config.add_class("one")
       config.tags.should == %w{one}
     end
   end
 
   describe "when extracting transobjects" do
 
     def mkscope
       @node = Puppet::Node.new("mynode")
       @compiler = Puppet::Parser::Compiler.new(@node)
 
       # XXX This is ridiculous.
       @compiler.send(:evaluate_main)
       @scope = @compiler.topscope
     end
 
     def mkresource(type, name)
       Puppet::Parser::Resource.new(type, name, :source => @source, :scope => @scope)
     end
 
     it "should fail if no 'main' stage can be found" do
       lambda { Puppet::Resource::Catalog.new("mynode").extract }.should raise_error(Puppet::DevError)
     end
 
     it "should warn if any non-main stages are present" do
       config = Puppet::Resource::Catalog.new("mynode")
 
       @scope = mkscope
       @source = mock 'source'
 
       main = mkresource("stage", "main")
       config.add_resource(main)
 
       other = mkresource("stage", "other")
       config.add_resource(other)
 
       Puppet.expects(:warning)
 
       config.extract
     end
 
     it "should always create a TransBucket for the 'main' stage" do
       config = Puppet::Resource::Catalog.new("mynode")
 
       @scope = mkscope
       @source = mock 'source'
 
       main = mkresource("stage", "main")
       config.add_resource(main)
 
       result = config.extract
       result.type.should == "Stage"
       result.name.should == "main"
     end
 
     # Now try it with a more complicated graph -- a three tier graph, each tier
     it "should transform arbitrarily deep graphs into isomorphic trees" do
       config = Puppet::Resource::Catalog.new("mynode")
 
       @scope = mkscope
       @scope.stubs(:tags).returns([])
       @source = mock 'source'
 
       # Create our scopes.
       top = mkresource "stage", "main"
 
       config.add_resource top
       topbucket = []
       topbucket.expects(:classes=).with([])
       top.expects(:to_trans).returns(topbucket)
       topres = mkresource "file", "/top"
       topres.expects(:to_trans).returns(:topres)
       config.add_edge top, topres
 
       middle = mkresource "class", "middle"
       middle.expects(:to_trans).returns([])
       config.add_edge top, middle
       midres = mkresource "file", "/mid"
       midres.expects(:to_trans).returns(:midres)
       config.add_edge middle, midres
 
       bottom = mkresource "class", "bottom"
       bottom.expects(:to_trans).returns([])
       config.add_edge middle, bottom
       botres = mkresource "file", "/bot"
       botres.expects(:to_trans).returns(:botres)
       config.add_edge bottom, botres
 
       toparray = config.extract
 
       # This is annoying; it should look like:
       #   [[[:botres], :midres], :topres]
       # but we can't guarantee sort order.
       toparray.include?(:topres).should be_true
 
       midarray = toparray.find { |t| t.is_a?(Array) }
       midarray.include?(:midres).should be_true
       botarray = midarray.find { |t| t.is_a?(Array) }
       botarray.include?(:botres).should be_true
     end
   end
 
   describe " when converting to a Puppet::Resource catalog" do
     before do
       @original = Puppet::Resource::Catalog.new("mynode")
       @original.tag(*%w{one two three})
       @original.add_class *%w{four five six}
 
       @top            = Puppet::TransObject.new 'top', "class"
       @topobject      = Puppet::TransObject.new '/topobject', "file"
       @middle         = Puppet::TransObject.new 'middle', "class"
       @middleobject   = Puppet::TransObject.new '/middleobject', "file"
       @bottom         = Puppet::TransObject.new 'bottom', "class"
       @bottomobject   = Puppet::TransObject.new '/bottomobject', "file"
 
       @resources = [@top, @topobject, @middle, @middleobject, @bottom, @bottomobject]
 
       @original.add_resource(*@resources)
 
       @original.add_edge(@top, @topobject)
       @original.add_edge(@top, @middle)
       @original.add_edge(@middle, @middleobject)
       @original.add_edge(@middle, @bottom)
       @original.add_edge(@bottom, @bottomobject)
 
       @catalog = @original.to_resource
     end
 
     it "should copy over the version" do
       @original.version = "foo"
       @original.to_resource.version.should == "foo"
     end
 
     it "should convert parser resources to plain resources" do
       resource = Puppet::Parser::Resource.new(:file, "foo", :scope => stub("scope", :environment => nil, :namespaces => nil), :source => stub("source"))
       catalog = Puppet::Resource::Catalog.new("whev")
       catalog.add_resource(resource)
       new = catalog.to_resource
       new.resource(:file, "foo").class.should == Puppet::Resource
     end
 
     it "should add all resources as Puppet::Resource instances" do
       @resources.each { |resource| @catalog.resource(resource.ref).should be_instance_of(Puppet::Resource) }
     end
 
     it "should copy the tag list to the new catalog" do
       @catalog.tags.sort.should == @original.tags.sort
     end
 
     it "should copy the class list to the new catalog" do
       @catalog.classes.should == @original.classes
     end
 
     it "should duplicate the original edges" do
       @original.edges.each do |edge|
         @catalog.edge?(@catalog.resource(edge.source.ref), @catalog.resource(edge.target.ref)).should be_true
       end
     end
 
     it "should set itself as the catalog for each converted resource" do
       @catalog.vertices.each { |v| v.catalog.object_id.should equal(@catalog.object_id) }
     end
   end
 
   describe "when converting to a RAL catalog" do
     before do
       @original = Puppet::Resource::Catalog.new("mynode")
       @original.tag(*%w{one two three})
       @original.add_class *%w{four five six}
 
       @top            = Puppet::Resource.new :class, 'top'
       @topobject      = Puppet::Resource.new :file, @basepath+'/topobject'
       @middle         = Puppet::Resource.new :class, 'middle'
       @middleobject   = Puppet::Resource.new :file, @basepath+'/middleobject'
       @bottom         = Puppet::Resource.new :class, 'bottom'
       @bottomobject   = Puppet::Resource.new :file, @basepath+'/bottomobject'
 
       @resources = [@top, @topobject, @middle, @middleobject, @bottom, @bottomobject]
 
       @original.add_resource(*@resources)
 
       @original.add_edge(@top, @topobject)
       @original.add_edge(@top, @middle)
       @original.add_edge(@middle, @middleobject)
       @original.add_edge(@middle, @bottom)
       @original.add_edge(@bottom, @bottomobject)
 
       @catalog = @original.to_ral
     end
 
     it "should add all resources as RAL instances" do
       @resources.each { |resource| @catalog.resource(resource.ref).should be_instance_of(Puppet::Type) }
     end
 
     it "should copy the tag list to the new catalog" do
       @catalog.tags.sort.should == @original.tags.sort
     end
 
     it "should copy the class list to the new catalog" do
       @catalog.classes.should == @original.classes
     end
 
     it "should duplicate the original edges" do
       @original.edges.each do |edge|
         @catalog.edge?(@catalog.resource(edge.source.ref), @catalog.resource(edge.target.ref)).should be_true
       end
     end
 
     it "should set itself as the catalog for each converted resource" do
       @catalog.vertices.each { |v| v.catalog.object_id.should equal(@catalog.object_id) }
     end
 
     # This tests #931.
     it "should not lose track of resources whose names vary" do
       changer = Puppet::TransObject.new 'changer', 'test'
 
       config = Puppet::Resource::Catalog.new('test')
       config.add_resource(changer)
       config.add_resource(@top)
 
       config.add_edge(@top, changer)
 
       resource = stub 'resource', :name => "changer2", :title => "changer2", :ref => "Test[changer2]", :catalog= => nil, :remove => nil
 
       #changer is going to get duplicated as part of a fix for aliases 1094
       changer.expects(:dup).returns(changer)
       changer.expects(:to_ral).returns(resource)
 
       newconfig = nil
 
       proc { @catalog = config.to_ral }.should_not raise_error
       @catalog.resource("Test[changer2]").should equal(resource)
     end
 
     after do
       # Remove all resource instances.
       @catalog.clear(true)
     end
   end
 
   describe "when filtering" do
     before :each do
       @original = Puppet::Resource::Catalog.new("mynode")
       @original.tag(*%w{one two three})
       @original.add_class *%w{four five six}
 
       @r1 = stub_everything 'r1', :ref => "File[/a]"
       @r1.stubs(:respond_to?).with(:ref).returns(true)
       @r1.stubs(:dup).returns(@r1)
       @r1.stubs(:is_a?).returns(Puppet::Resource).returns(true)
 
       @r2 = stub_everything 'r2', :ref => "File[/b]"
       @r2.stubs(:respond_to?).with(:ref).returns(true)
       @r2.stubs(:dup).returns(@r2)
       @r2.stubs(:is_a?).returns(Puppet::Resource).returns(true)
 
       @resources = [@r1,@r2]
 
       @original.add_resource(@r1,@r2)
     end
 
     it "should transform the catalog to a resource catalog" do
       @original.expects(:to_catalog).with { |h,b| h == :to_resource }
 
       @original.filter
     end
 
     it "should scan each catalog resource in turn and apply filtering block" do
       @resources.each { |r| r.expects(:test?) }
       @original.filter do |r|
         r.test?
       end
     end
 
     it "should filter out resources which produce true when the filter block is evaluated" do
       @original.filter do |r|
         r == @r1
       end.resource("File[/a]").should be_nil
     end
 
     it "should not consider edges against resources that were filtered out" do
       @original.add_edge(@r1,@r2)
       @original.filter do |r|
         r == @r1
-      end.edge(@r1,@r2).should be_empty
+      end.edge?(@r1,@r2).should_not be
     end
   end
 
   describe "when functioning as a resource container" do
     before do
       @catalog = Puppet::Resource::Catalog.new("host")
       @one = Puppet::Type.type(:notify).new :name => "one"
       @two = Puppet::Type.type(:notify).new :name => "two"
       @dupe = Puppet::Type.type(:notify).new :name => "one"
     end
 
     it "should provide a method to add one or more resources" do
       @catalog.add_resource @one, @two
       @catalog.resource(@one.ref).should equal(@one)
       @catalog.resource(@two.ref).should equal(@two)
     end
 
     it "should add resources to the relationship graph if it exists" do
       relgraph = @catalog.relationship_graph
       @catalog.add_resource @one
       relgraph.should be_vertex(@one)
     end
 
     it "should yield added resources if a block is provided" do
       yielded = []
       @catalog.add_resource(@one, @two) { |r| yielded << r }
       yielded.length.should == 2
     end
 
     it "should set itself as the resource's catalog if it is not a relationship graph" do
       @one.expects(:catalog=).with(@catalog)
       @catalog.add_resource @one
     end
 
     it "should make all vertices available by resource reference" do
       @catalog.add_resource(@one)
       @catalog.resource(@one.ref).should equal(@one)
       @catalog.vertices.find { |r| r.ref == @one.ref }.should equal(@one)
     end
 
     it "should canonize how resources are referred to during retrieval when both type and title are provided" do
       @catalog.add_resource(@one)
 
       @catalog.resource("notify", "one").should equal(@one)
     end
 
     it "should canonize how resources are referred to during retrieval when just the title is provided" do
       @catalog.add_resource(@one)
 
       @catalog.resource("notify[one]", nil).should equal(@one)
     end
 
     it "should not allow two resources with the same resource reference" do
       @catalog.add_resource(@one)
 
       proc { @catalog.add_resource(@dupe) }.should raise_error(Puppet::Resource::Catalog::DuplicateResourceError)
     end
 
     it "should not store objects that do not respond to :ref" do
       proc { @catalog.add_resource("thing") }.should raise_error(ArgumentError)
     end
 
     it "should remove all resources when asked" do
       @catalog.add_resource @one
       @catalog.add_resource @two
       @one.expects :remove
       @two.expects :remove
       @catalog.clear(true)
     end
 
     it "should support a mechanism for finishing resources" do
       @one.expects :finish
       @two.expects :finish
       @catalog.add_resource @one
       @catalog.add_resource @two
 
       @catalog.finalize
     end
 
     it "should make default resources when finalizing" do
       @catalog.expects(:make_default_resources)
       @catalog.finalize
     end
 
     it "should add default resources to the catalog upon creation" do
       @catalog.make_default_resources
       @catalog.resource(:schedule, "daily").should_not be_nil
     end
 
     it "should optionally support an initialization block and should finalize after such blocks" do
       @one.expects :finish
       @two.expects :finish
       config = Puppet::Resource::Catalog.new("host") do |conf|
         conf.add_resource @one
         conf.add_resource @two
       end
     end
 
     it "should inform the resource that it is the resource's catalog" do
       @one.expects(:catalog=).with(@catalog)
       @catalog.add_resource @one
     end
 
     it "should be able to find resources by reference" do
       @catalog.add_resource @one
       @catalog.resource(@one.ref).should equal(@one)
     end
 
     it "should be able to find resources by reference or by type/title tuple" do
       @catalog.add_resource @one
       @catalog.resource("notify", "one").should equal(@one)
     end
 
     it "should have a mechanism for removing resources" do
       @catalog.add_resource @one
       @one.expects :remove
       @catalog.remove_resource(@one)
       @catalog.resource(@one.ref).should be_nil
       @catalog.vertex?(@one).should be_false
     end
 
     it "should have a method for creating aliases for resources" do
       @catalog.add_resource @one
       @catalog.alias(@one, "other")
       @catalog.resource("notify", "other").should equal(@one)
     end
 
     it "should ignore conflicting aliases that point to the aliased resource" do
       @catalog.alias(@one, "other")
       lambda { @catalog.alias(@one, "other") }.should_not raise_error
     end
 
     it "should create aliases for resources isomorphic resources whose names do not match their titles" do
       resource = Puppet::Type::File.new(:title => "testing", :path => @basepath+"/something")
 
       @catalog.add_resource(resource)
 
       @catalog.resource(:file, @basepath+"/something").should equal(resource)
     end
 
     it "should not create aliases for resources non-isomorphic resources whose names do not match their titles" do
       resource = Puppet::Type.type(:exec).new(:title => "testing", :command => "echo", :path => %w{/bin /usr/bin /usr/local/bin})
 
       @catalog.add_resource(resource)
 
       # Yay, I've already got a 'should' method
       @catalog.resource(:exec, "echo").object_id.should == nil.object_id
     end
 
     # This test is the same as the previous, but the behaviour should be explicit.
     it "should alias using the class name from the resource reference, not the resource class name" do
       @catalog.add_resource @one
       @catalog.alias(@one, "other")
       @catalog.resource("notify", "other").should equal(@one)
     end
 
     it "should ignore conflicting aliases that point to the aliased resource" do
       @catalog.alias(@one, "other")
       lambda { @catalog.alias(@one, "other") }.should_not raise_error
     end
 
     it "should fail to add an alias if the aliased name already exists" do
       @catalog.add_resource @one
       proc { @catalog.alias @two, "one" }.should raise_error(ArgumentError)
     end
 
     it "should not fail when a resource has duplicate aliases created" do
       @catalog.add_resource @one
       proc { @catalog.alias @one, "one" }.should_not raise_error
     end
 
     it "should not create aliases that point back to the resource" do
       @catalog.alias(@one, "one")
       @catalog.resource(:notify, "one").should be_nil
     end
 
     it "should be able to look resources up by their aliases" do
       @catalog.add_resource @one
       @catalog.alias @one, "two"
       @catalog.resource(:notify, "two").should equal(@one)
     end
 
     it "should remove resource aliases when the target resource is removed" do
       @catalog.add_resource @one
       @catalog.alias(@one, "other")
       @one.expects :remove
       @catalog.remove_resource(@one)
       @catalog.resource("notify", "other").should be_nil
     end
 
     it "should add an alias for the namevar when the title and name differ on isomorphic resource types" do
       resource = Puppet::Type.type(:file).new :path => @basepath+"/something", :title => "other", :content => "blah"
       resource.expects(:isomorphic?).returns(true)
       @catalog.add_resource(resource)
       @catalog.resource(:file, "other").should equal(resource)
       @catalog.resource(:file, @basepath+"/something").ref.should == resource.ref
     end
 
     it "should not add an alias for the namevar when the title and name differ on non-isomorphic resource types" do
       resource = Puppet::Type.type(:file).new :path => @basepath+"/something", :title => "other", :content => "blah"
       resource.expects(:isomorphic?).returns(false)
       @catalog.add_resource(resource)
       @catalog.resource(:file, resource.title).should equal(resource)
       # We can't use .should here, because the resources respond to that method.
       raise "Aliased non-isomorphic resource" if @catalog.resource(:file, resource.name)
     end
 
     it "should provide a method to create additional resources that also registers the resource" do
       args = {:name => "/yay", :ensure => :file}
       resource = stub 'file', :ref => "File[/yay]", :catalog= => @catalog, :title => "/yay", :[] => "/yay"
       Puppet::Type.type(:file).expects(:new).with(args).returns(resource)
       @catalog.create_resource :file, args
       @catalog.resource("File[/yay]").should equal(resource)
     end
   end
 
   describe "when applying" do
     before :each do
       @catalog = Puppet::Resource::Catalog.new("host")
 
       @transaction = mock 'transaction'
       Puppet::Transaction.stubs(:new).returns(@transaction)
       @transaction.stubs(:evaluate)
       @transaction.stubs(:add_times)
 
       Puppet.settings.stubs(:use)
     end
 
     it "should create and evaluate a transaction" do
       @transaction.expects(:evaluate)
       @catalog.apply
     end
 
     it "should provide the catalog retrieval time to the transaction" do
       @catalog.retrieval_duration = 5
       @transaction.expects(:add_times).with(:config_retrieval => 5)
       @catalog.apply
     end
 
     it "should use a retrieval time of 0 if none is set in the catalog" do
       @catalog.retrieval_duration = nil
       @transaction.expects(:add_times).with(:config_retrieval => 0)
       @catalog.apply
     end
 
     it "should return the transaction" do
       @catalog.apply.should equal(@transaction)
     end
 
     it "should yield the transaction if a block is provided" do
       @catalog.apply do |trans|
         trans.should equal(@transaction)
       end
     end
 
     it "should default to being a host catalog" do
       @catalog.host_config.should be_true
     end
 
     it "should be able to be set to a non-host_config" do
       @catalog.host_config = false
       @catalog.host_config.should be_false
     end
 
     it "should pass supplied tags on to the transaction" do
       @transaction.expects(:tags=).with(%w{one two})
       @catalog.apply(:tags => %w{one two})
     end
 
     it "should set ignoreschedules on the transaction if specified in apply()" do
       @transaction.expects(:ignoreschedules=).with(true)
       @catalog.apply(:ignoreschedules => true)
     end
 
     it "should expire cached data in the resources both before and after the transaction" do
       @catalog.expects(:expire).times(2)
       @catalog.apply
     end
 
     describe "host catalogs" do
 
       # super() doesn't work in the setup method for some reason
       before do
         @catalog.host_config = true
         Puppet::Util::Storage.stubs(:store)
       end
 
       it "should initialize the state database before applying a catalog" do
         Puppet::Util::Storage.expects(:load)
 
         # Short-circuit the apply, so we know we're loading before the transaction
         Puppet::Transaction.expects(:new).raises ArgumentError
         proc { @catalog.apply }.should raise_error(ArgumentError)
       end
 
       it "should sync the state database after applying" do
         Puppet::Util::Storage.expects(:store)
         @transaction.stubs :any_failed? => false
         @catalog.apply
       end
 
       after { Puppet.settings.clear }
     end
 
     describe "non-host catalogs" do
 
       before do
         @catalog.host_config = false
       end
 
       it "should never send reports" do
         Puppet[:report] = true
         Puppet[:summarize] = true
         @catalog.apply
       end
 
       it "should never modify the state database" do
         Puppet::Util::Storage.expects(:load).never
         Puppet::Util::Storage.expects(:store).never
         @catalog.apply
       end
 
       after { Puppet.settings.clear }
     end
   end
 
   describe "when creating a relationship graph" do
     before do
       Puppet::Type.type(:component)
       @catalog = Puppet::Resource::Catalog.new("host")
       @compone = Puppet::Type::Component.new :name => "one"
       @comptwo = Puppet::Type::Component.new :name => "two", :require => "Class[one]"
       @file = Puppet::Type.type(:file)
       @one = @file.new :path => @basepath+"/one"
       @two = @file.new :path => @basepath+"/two"
       @sub = @file.new :path => @basepath+"/two/subdir"
       @catalog.add_edge @compone, @one
       @catalog.add_edge @comptwo, @two
 
       @three = @file.new :path => @basepath+"/three"
       @four = @file.new :path => @basepath+"/four", :require => "File[#{@basepath}/three]"
       @five = @file.new :path => @basepath+"/five"
       @catalog.add_resource @compone, @comptwo, @one, @two, @three, @four, @five, @sub
 
       @relationships = @catalog.relationship_graph
     end
 
     it "should be able to create a relationship graph" do
       @relationships.should be_instance_of(Puppet::SimpleGraph)
     end
 
     it "should not have any components" do
       @relationships.vertices.find { |r| r.instance_of?(Puppet::Type::Component) }.should be_nil
     end
 
     it "should have all non-component resources from the catalog" do
       # The failures print out too much info, so i just do a class comparison
       @relationships.vertex?(@five).should be_true
     end
 
     it "should have all resource relationships set as edges" do
       @relationships.edge?(@three, @four).should be_true
     end
 
     it "should copy component relationships to all contained resources" do
       @relationships.edge?(@one, @two).should be_true
     end
 
     it "should add automatic relationships to the relationship graph" do
       @relationships.edge?(@two, @sub).should be_true
     end
 
     it "should get removed when the catalog is cleaned up" do
       @relationships.expects(:clear)
       @catalog.clear
       @catalog.instance_variable_get("@relationship_graph").should be_nil
     end
 
     it "should write :relationships and :expanded_relationships graph files if the catalog is a host catalog" do
       @catalog.clear
       graph = Puppet::SimpleGraph.new
       Puppet::SimpleGraph.expects(:new).returns graph
 
       graph.expects(:write_graph).with(:relationships)
       graph.expects(:write_graph).with(:expanded_relationships)
 
       @catalog.host_config = true
 
       @catalog.relationship_graph
     end
 
     it "should not write graph files if the catalog is not a host catalog" do
       @catalog.clear
       graph = Puppet::SimpleGraph.new
       Puppet::SimpleGraph.expects(:new).returns graph
 
       graph.expects(:write_graph).never
 
       @catalog.host_config = false
 
       @catalog.relationship_graph
     end
 
     it "should create a new relationship graph after clearing the old one" do
       @relationships.expects(:clear)
       @catalog.clear
       @catalog.relationship_graph.should be_instance_of(Puppet::SimpleGraph)
     end
 
     it "should remove removed resources from the relationship graph if it exists" do
       @catalog.remove_resource(@one)
       @catalog.relationship_graph.vertex?(@one).should be_false
     end
   end
 
   describe "when writing dot files" do
     before do
       @catalog = Puppet::Resource::Catalog.new("host")
       @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
       Puppet[:graph] = true
       @catalog.write_graph(@name)
     end
 
     after do
       Puppet.settings.clear
     end
   end
 
   describe "when indirecting" do
     before do
       @real_indirection = Puppet::Resource::Catalog.indirection
 
       @indirection = stub 'indirection', :name => :catalog
 
       Puppet::Util::Cacher.expire
     end
 
     it "should redirect to the indirection for retrieval" do
       Puppet::Resource::Catalog.stubs(:indirection).returns(@indirection)
       @indirection.expects(:find)
       Puppet::Resource::Catalog.find(:myconfig)
     end
 
     it "should use the value of the 'catalog_terminus' setting to determine its terminus class" do
       # Puppet only checks the terminus setting the first time you ask
       # so this returns the object to the clean state
       # at the expense of making this test less pure
       Puppet::Resource::Catalog.indirection.reset_terminus_class
 
       Puppet.settings[:catalog_terminus] = "rest"
       Puppet::Resource::Catalog.indirection.terminus_class.should == :rest
     end
 
     it "should allow the terminus class to be set manually" do
       Puppet::Resource::Catalog.indirection.terminus_class = :rest
       Puppet::Resource::Catalog.indirection.terminus_class.should == :rest
     end
 
     after do
       Puppet::Util::Cacher.expire
       @real_indirection.reset_terminus_class
     end
   end
 
   describe "when converting to yaml" do
     before do
       @catalog = Puppet::Resource::Catalog.new("me")
       @catalog.add_edge("one", "two")
     end
 
     it "should be able to be dumped to yaml" do
       YAML.dump(@catalog).should be_instance_of(String)
     end
   end
 
   describe "when converting from yaml" do
     before do
       @catalog = Puppet::Resource::Catalog.new("me")
       @catalog.add_edge("one", "two")
 
       text = YAML.dump(@catalog)
       @newcatalog = YAML.load(text)
     end
 
     it "should get converted back to a catalog" do
       @newcatalog.should be_instance_of(Puppet::Resource::Catalog)
     end
 
     it "should have all vertices" do
       @newcatalog.vertex?("one").should be_true
       @newcatalog.vertex?("two").should be_true
     end
 
     it "should have all edges" do
       @newcatalog.edge?("one", "two").should be_true
     end
   end
 end
 
 describe Puppet::Resource::Catalog, "when converting to pson" do
   confine "Missing 'pson' library" => Puppet.features.pson?
 
   before do
     @catalog = Puppet::Resource::Catalog.new("myhost")
   end
 
   def pson_output_should
     @catalog.class.expects(:pson_create).with { |hash| yield hash }.returns(:something)
   end
 
   # LAK:NOTE For all of these tests, we convert back to the resource so we can
   # trap the actual data structure then.
   it "should set its document_type to 'Catalog'" do
     pson_output_should { |hash| hash['document_type'] == "Catalog" }
 
     PSON.parse @catalog.to_pson
   end
 
   it "should set its data as a hash" do
     pson_output_should { |hash| hash['data'].is_a?(Hash) }
     PSON.parse @catalog.to_pson
   end
 
   [:name, :version, :tags, :classes].each do |param|
     it "should set its #{param} to the #{param} of the resource" do
       @catalog.send(param.to_s + "=", "testing") unless @catalog.send(param)
 
       pson_output_should { |hash| hash['data'][param.to_s] == @catalog.send(param) }
       PSON.parse @catalog.to_pson
     end
   end
 
   it "should convert its resources to a PSON-encoded array and store it as the 'resources' data" do
     one = stub 'one', :to_pson_data_hash => "one_resource", :ref => "Foo[one]"
     two = stub 'two', :to_pson_data_hash => "two_resource", :ref => "Foo[two]"
 
     @catalog.add_resource(one)
     @catalog.add_resource(two)
 
     # TODO this should really guarantee sort order
     PSON.parse(@catalog.to_pson,:create_additions => false)['data']['resources'].sort.should == ["one_resource", "two_resource"].sort
 
   end
 
   it "should convert its edges to a PSON-encoded array and store it as the 'edges' data" do
     one   = stub 'one',   :to_pson_data_hash => "one_resource",   :ref => 'Foo[one]'
     two   = stub 'two',   :to_pson_data_hash => "two_resource",   :ref => 'Foo[two]'
     three = stub 'three', :to_pson_data_hash => "three_resource", :ref => 'Foo[three]'
 
     @catalog.add_edge(one, two)
     @catalog.add_edge(two, three)
 
-    @catalog.edge(one, two  ).expects(:to_pson_data_hash).returns "one_two_pson"
-    @catalog.edge(two, three).expects(:to_pson_data_hash).returns "two_three_pson"
+    @catalog.edges_between(one, two  )[0].expects(:to_pson_data_hash).returns "one_two_pson"
+    @catalog.edges_between(two, three)[0].expects(:to_pson_data_hash).returns "two_three_pson"
 
     PSON.parse(@catalog.to_pson,:create_additions => false)['data']['edges'].sort.should == %w{one_two_pson two_three_pson}.sort
   end
 end
 
 describe Puppet::Resource::Catalog, "when converting from pson" do
   confine "Missing 'pson' library" => Puppet.features.pson?
 
   def pson_result_should
     Puppet::Resource::Catalog.expects(:new).with { |hash| yield hash }
   end
 
   before do
     @data = {
       'name' => "myhost"
     }
     @pson = {
       'document_type' => 'Puppet::Resource::Catalog',
       'data' => @data,
       'metadata' => {}
     }
 
     @catalog = Puppet::Resource::Catalog.new("myhost")
     Puppet::Resource::Catalog.stubs(:new).returns @catalog
   end
 
   it "should be extended with the PSON utility module" do
     Puppet::Resource::Catalog.singleton_class.ancestors.should be_include(Puppet::Util::Pson)
   end
 
   it "should create it with the provided name" do
     Puppet::Resource::Catalog.expects(:new).with('myhost').returns @catalog
     PSON.parse @pson.to_pson
   end
 
   it "should set the provided version on the catalog if one is set" do
     @data['version'] = 50
     PSON.parse @pson.to_pson
     @catalog.version.should == @data['version']
   end
 
   it "should set any provided tags on the catalog" do
     @data['tags'] = %w{one two}
     PSON.parse @pson.to_pson
     @catalog.tags.should == @data['tags']
   end
 
   it "should set any provided classes on the catalog" do
     @data['classes'] = %w{one two}
     PSON.parse @pson.to_pson
     @catalog.classes.should == @data['classes']
   end
 
   it 'should convert the resources list into resources and add each of them' do
     @data['resources'] = [Puppet::Resource.new(:file, "/foo"), Puppet::Resource.new(:file, "/bar")]
 
     @catalog.expects(:add_resource).times(2).with { |res| res.type == "File" }
     PSON.parse @pson.to_pson
   end
 
   it 'should convert resources even if they do not include "type" information' do
     @data['resources'] = [Puppet::Resource.new(:file, "/foo")]
 
     @data['resources'][0].expects(:to_pson).returns '{"title":"/foo","tags":["file"],"type":"File"}'
 
     @catalog.expects(:add_resource).with { |res| res.type == "File" }
 
     PSON.parse @pson.to_pson
   end
 
   it 'should convert the edges list into edges and add each of them' do
     one = Puppet::Relationship.new("osource", "otarget", :event => "one", :callback => "refresh")
     two = Puppet::Relationship.new("tsource", "ttarget", :event => "two", :callback => "refresh")
 
     @data['edges'] = [one, two]
 
     @catalog.stubs(:resource).returns("eh")
 
     @catalog.expects(:add_edge).with { |edge| edge.event == "one" }
     @catalog.expects(:add_edge).with { |edge| edge.event == "two" }
 
     PSON.parse @pson.to_pson
   end
 
   it "should be able to convert relationships that do not include 'type' information" do
     one = Puppet::Relationship.new("osource", "otarget", :event => "one", :callback => "refresh")
     one.expects(:to_pson).returns "{\"event\":\"one\",\"callback\":\"refresh\",\"source\":\"osource\",\"target\":\"otarget\"}"
 
     @data['edges'] = [one]
 
     @catalog.stubs(:resource).returns("eh")
 
     @catalog.expects(:add_edge).with { |edge| edge.event == "one" }
 
     PSON.parse @pson.to_pson
   end
 
   it "should set the source and target for each edge to the actual resource" do
     edge = Puppet::Relationship.new("source", "target")
 
     @data['edges'] = [edge]
 
     @catalog.expects(:resource).with("source").returns("source_resource")
     @catalog.expects(:resource).with("target").returns("target_resource")
 
     @catalog.expects(:add_edge).with { |edge| edge.source == "source_resource" and edge.target == "target_resource" }
 
     PSON.parse @pson.to_pson
   end
 
   it "should fail if the source resource cannot be found" do
     edge = Puppet::Relationship.new("source", "target")
 
     @data['edges'] = [edge]
 
     @catalog.expects(:resource).with("source").returns(nil)
     @catalog.stubs(:resource).with("target").returns("target_resource")
 
     lambda { PSON.parse @pson.to_pson }.should raise_error(ArgumentError)
   end
 
   it "should fail if the target resource cannot be found" do
     edge = Puppet::Relationship.new("source", "target")
 
     @data['edges'] = [edge]
 
     @catalog.stubs(:resource).with("source").returns("source_resource")
     @catalog.expects(:resource).with("target").returns(nil)
 
     lambda { PSON.parse @pson.to_pson }.should raise_error(ArgumentError)
   end
 
   describe "#title_key_for_ref" do
     it "should parse a resource ref string into a pair" do
       @catalog.title_key_for_ref("Title[name]").should == ["Title", "name"]
     end
     it "should parse a resource ref string into a pair, even if there's a newline inside the name" do
       @catalog.title_key_for_ref("Title[na\nme]").should == ["Title", "na\nme"]
     end
   end
 end
diff --git a/spec/unit/simple_graph_spec.rb b/spec/unit/simple_graph_spec.rb
index 2ca8888c5..fa0bcb06a 100755
--- a/spec/unit/simple_graph_spec.rb
+++ b/spec/unit/simple_graph_spec.rb
@@ -1,554 +1,762 @@
 #!/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
 
-  it "should always put its edges first when printing yaml" do
-    @graph = Puppet::SimpleGraph.new
-    @graph.add_edge(:one, :two)
-    @graph.to_yaml_properties[0].should == "@edges"
-  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
+    describe "when retrieving edges between two nodes" do
+      it "should handle the case of nodes not in the graph" do
+        @graph.edges_between(:one, :two).should == []
+      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)
+      it "should handle the case of nodes with no edges between them" do
+        @graph.add_vertex(:one)
+        @graph.add_vertex(:two)
+        @graph.edges_between(:one, :two).should == []
+      end
+
+      it "should handle the case of nodes connected by a single edge" do
+        edge = Puppet::Relationship.new(:one, :two)
+        @graph.add_edge(edge)
+        @graph.edges_between(:one, :two).length.should == 1
+        @graph.edges_between(:one, :two)[0].should equal(edge)
+      end
+
+      it "should handle the case of nodes connected by multiple edges" do
+        edge1 = Puppet::Relationship.new(:one, :two, :callback => :foo)
+        edge2 = Puppet::Relationship.new(:one, :two, :callback => :bar)
+        @graph.add_edge(edge1)
+        @graph.add_edge(edge2)
+        Set.new(@graph.edges_between(:one, :two)).should == Set.new([edge1, edge2])
+      end
     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.should be_instance_of(Array)
       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 = @graph.reversal.edges_between(:two, :one)[0]
       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(:name => :yay, :resource => "a")
       @none = Puppet::Transaction::Event.new(:name => :NONE, :resource => "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", [])
       
       @whit  = Puppet::Type.type(:whit)
       @stage = Puppet::Type.type(:stage).new(:name => "foo")
 
       @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
 
     # This is a bit hideous, but required to make stages work with relationships - they're
     # the top of the graph.
     it "should remove all Stage resources from the dependency graph" do
       @depgraph.vertices.find_all { |v| v.is_a?(Puppet::Type.type(:stage)) }.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 contain a whit-resource to mark the place held by the empty container" do
       @depgraph.vertices.find_all { |v| v.is_a?(@whit) }.length.should == 1
     end
 
     it "should replace edges to empty containers with edges to their residual whit" do
       emptys_whit = @depgraph.vertices.find_all { |v| v.is_a?(@whit) }.first
       @depgraph.should be_edge("c", emptys_whit)
     end
 
     it "should no longer contain anything but the non-container objects" do
       @depgraph.vertices.find_all { |v| ! v.is_a?(String) and ! v.is_a?(@whit)}.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 == {}
+      @depgraph.edges_between("c", "i")[0].label.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}
+      @depgraph.edges_between("c", "i")[0].label.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}
+      @depgraph.edges_between("c", "i")[0].label.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}
+        @depgraph.edges_between(edge.source, edge.target)[0].label.should == {:callback => :refresh}
+      end
+    end
+  end
+
+  it "should serialize to YAML using the old format by default" do
+    Puppet::SimpleGraph.use_new_yaml_format.should == false
+  end
+
+  describe "(yaml tests)" do
+    def empty_graph(graph)
+    end
+
+    def one_vertex_graph(graph)
+      graph.add_vertex(:a)
+    end
+
+    def graph_without_edges(graph)
+      [:a, :b, :c].each { |x| graph.add_vertex(x) }
+    end
+
+    def one_edge_graph(graph)
+      graph.add_edge(:a, :b)
+    end
+
+    def many_edge_graph(graph)
+      graph.add_edge(:a, :b)
+      graph.add_edge(:a, :c)
+      graph.add_edge(:b, :d)
+      graph.add_edge(:c, :d)
+    end
+
+    def labeled_edge_graph(graph)
+      graph.add_edge(:a, :b, :callback => :foo, :event => :bar)
+    end
+
+    def overlapping_edge_graph(graph)
+      graph.add_edge(:a, :b, :callback => :foo, :event => :bar)
+      graph.add_edge(:a, :b, :callback => :biz, :event => :baz)
+    end
+
+    def self.all_test_graphs
+      [:empty_graph, :one_vertex_graph, :graph_without_edges, :one_edge_graph, :many_edge_graph, :labeled_edge_graph,
+       :overlapping_edge_graph]
+    end
+
+    def object_ids(enumerable)
+      # Return a sorted list of the object id's of the elements of an
+      # enumerable.
+      enumerable.collect { |x| x.object_id }.sort
+    end
+
+    def graph_to_yaml(graph, which_format)
+      previous_use_new_yaml_format = Puppet::SimpleGraph.use_new_yaml_format
+      Puppet::SimpleGraph.use_new_yaml_format = (which_format == :new)
+      ZAML.dump(graph)
+    ensure
+      Puppet::SimpleGraph.use_new_yaml_format = previous_use_new_yaml_format
+    end
+
+    # Test serialization of graph to YAML.
+    [:old, :new].each do |which_format|
+      all_test_graphs.each do |graph_to_test|
+        it "should be able to serialize #{graph_to_test} to YAML (#{which_format} format)" do
+          graph = Puppet::SimpleGraph.new
+          send(graph_to_test, graph)
+          yaml_form = graph_to_yaml(graph, which_format)
+
+          # Hack the YAML so that objects in the Puppet namespace get
+          # changed to YAML::DomainType objects.  This lets us inspect
+          # the serialized objects easily without invoking any
+          # yaml_initialize hooks.
+          yaml_form.gsub!('!ruby/object:Puppet::', '!hack/object:Puppet::')
+          serialized_object = YAML.load(yaml_form)
+
+          # Check that the object contains instance variables @edges and
+          # @vertices only.  @reversal is also permitted, but we don't
+          # check it, because it is going to be phased out.
+          serialized_object.type_id.should == 'object:Puppet::SimpleGraph'
+          serialized_object.value.keys.reject { |x| x == 'reversal' }.sort.should == ['edges', 'vertices']
+
+          # Check edges by forming a set of tuples (source, target,
+          # callback, event) based on the graph and the YAML and make sure
+          # they match.
+          edges = serialized_object.value['edges']
+          edges.should be_a(Array)
+          expected_edge_tuples = graph.edges.collect { |edge| [edge.source, edge.target, edge.callback, edge.event] }
+          actual_edge_tuples = edges.collect do |edge|
+            edge.type_id.should == 'object:Puppet::Relationship'
+            %w{source target}.each { |x| edge.value.keys.should include(x) }
+            edge.value.keys.each { |x| ['source', 'target', 'callback', 'event'].should include(x) }
+            %w{source target callback event}.collect { |x| edge.value[x] }
+          end
+          Set.new(actual_edge_tuples).should == Set.new(expected_edge_tuples)
+          actual_edge_tuples.length.should == expected_edge_tuples.length
+
+          # Check vertices one by one.
+          vertices = serialized_object.value['vertices']
+          if which_format == :old
+            vertices.should be_a(Hash)
+            Set.new(vertices.keys).should == Set.new(graph.vertices)
+            vertices.each do |key, value|
+              value.type_id.should == 'object:Puppet::SimpleGraph::VertexWrapper'
+              value.value.keys.sort.should == %w{adjacencies vertex}
+              value.value['vertex'].should equal(key)
+              adjacencies = value.value['adjacencies']
+              adjacencies.should be_a(Hash)
+              Set.new(adjacencies.keys).should == Set.new([:in, :out])
+              [:in, :out].each do |direction|
+                adjacencies[direction].should be_a(Hash)
+                expected_adjacent_vertices = Set.new(graph.adjacent(key, :direction => direction, :type => :vertices))
+                Set.new(adjacencies[direction].keys).should == expected_adjacent_vertices
+                adjacencies[direction].each do |adj_key, adj_value|
+                  # Since we already checked edges, just check consistency
+                  # with edges.
+                  desired_source = direction == :in ? adj_key : key
+                  desired_target = direction == :in ? key : adj_key
+                  expected_edges = edges.select do |edge|
+                    edge.value['source'] == desired_source && edge.value['target'] == desired_target
+                  end
+                  adj_value.should be_a(Set)
+                  if object_ids(adj_value) != object_ids(expected_edges)
+                    raise "For vertex #{key.inspect}, direction #{direction.inspect}: expected adjacencies #{expected_edges.inspect} but got #{adj_value.inspect}"
+                  end
+                end
+              end
+            end
+          else
+            vertices.should be_a(Array)
+            Set.new(vertices).should == Set.new(graph.vertices)
+            vertices.length.should == graph.vertices.length
+          end
+        end
+      end
+
+      # Test deserialization of graph from YAML.  This presumes the
+      # correctness of serialization to YAML, which has already been
+      # tested.
+      all_test_graphs.each do |graph_to_test|
+        it "should be able to deserialize #{graph_to_test} from YAML (#{which_format} format)" do
+          reference_graph = Puppet::SimpleGraph.new
+          send(graph_to_test, reference_graph)
+          yaml_form = graph_to_yaml(reference_graph, which_format)
+          recovered_graph = YAML.load(yaml_form)
+
+          # Test that the recovered vertices match the vertices in the
+          # reference graph.
+          expected_vertices = reference_graph.vertices.to_a
+          recovered_vertices = recovered_graph.vertices.to_a
+          Set.new(recovered_vertices).should == Set.new(expected_vertices)
+          recovered_vertices.length.should == expected_vertices.length
+
+          # Test that the recovered edges match the edges in the
+          # reference graph.
+          expected_edge_tuples = reference_graph.edges.collect do |edge|
+            [edge.source, edge.target, edge.callback, edge.event]
+          end
+          recovered_edge_tuples = recovered_graph.edges.collect do |edge|
+            [edge.source, edge.target, edge.callback, edge.event]
+          end
+          Set.new(recovered_edge_tuples).should == Set.new(expected_edge_tuples)
+          recovered_edge_tuples.length.should == expected_edge_tuples.length
+
+          # We ought to test that the recovered graph is self-consistent
+          # too.  But we're not going to bother with that yet because
+          # the internal representation of the graph is about to change.
+        end
+      end
+
+      it "should be able to serialize a graph where the vertices contain backreferences to the graph (#{which_format} format)" do
+        reference_graph = Puppet::SimpleGraph.new
+        vertex = Object.new
+        vertex.instance_eval { @graph = reference_graph }
+        reference_graph.add_edge(vertex, :other_vertex)
+        yaml_form = graph_to_yaml(reference_graph, which_format)
+        recovered_graph = YAML.load(yaml_form)
+
+        recovered_graph.vertices.length.should == 2
+        recovered_vertex = recovered_graph.vertices.reject { |x| x.is_a?(Symbol) }[0]
+        recovered_vertex.instance_eval { @graph }.should equal(recovered_graph)
+        recovered_graph.edges.length.should == 1
+        recovered_edge = recovered_graph.edges[0]
+        recovered_edge.source.should equal(recovered_vertex)
+        recovered_edge.target.should == :other_vertex
+      end
+    end
+
+    it "should serialize properly when used as a base class" do
+      class Puppet::TestDerivedClass < Puppet::SimpleGraph
+        attr_accessor :foo
       end
+      derived = Puppet::TestDerivedClass.new
+      derived.add_edge(:a, :b)
+      derived.foo = 1234
+      recovered_derived = YAML.load(YAML.dump(derived))
+      recovered_derived.class.should equal(Puppet::TestDerivedClass)
+      recovered_derived.edges.length.should == 1
+      recovered_derived.edges[0].source.should == :a
+      recovered_derived.edges[0].target.should == :b
+      recovered_derived.vertices.length.should == 2
+      recovered_derived.foo.should == 1234
     end
   end
 end
diff --git a/spec/unit/util/monkey_patches_spec.rb b/spec/unit/util/monkey_patches_spec.rb
index b0f61c808..049ed1044 100644
--- a/spec/unit/util/monkey_patches_spec.rb
+++ b/spec/unit/util/monkey_patches_spec.rb
@@ -1,7 +1,33 @@
 #!/usr/bin/env ruby
 
 Dir.chdir(File.dirname(__FILE__)) { (s = lambda { |f| File.exist?(f) ? require(f) : Dir.chdir("..") { s.call(f) } }).call("spec/spec_helper.rb") }
 
 require 'puppet/util/monkey_patches'
 
 
+
+describe "yaml deserialization" do
+  it "should call yaml_initialize when deserializing objects that have that method defined" do
+    class Puppet::TestYamlInitializeClass
+      attr_reader :foo
+
+      def yaml_initialize(tag, var)
+        var.should == {'foo' => 100}
+        instance_variables.should == []
+        @foo = 200
+      end
+    end
+
+    obj = YAML.load("--- !ruby/object:Puppet::TestYamlInitializeClass\n  foo: 100")
+    obj.foo.should == 200
+  end
+
+  it "should not call yaml_initialize if not defined" do
+    class Puppet::TestYamlNonInitializeClass
+      attr_reader :foo
+    end
+
+    obj = YAML.load("--- !ruby/object:Puppet::TestYamlNonInitializeClass\n  foo: 100")
+    obj.foo.should == 100
+  end
+end
diff --git a/spec/unit/util/zaml_spec.rb b/spec/unit/util/zaml_spec.rb
index b223f89d4..358c6aa11 100755
--- a/spec/unit/util/zaml_spec.rb
+++ b/spec/unit/util/zaml_spec.rb
@@ -1,64 +1,63 @@
 #!/usr/bin/env ruby
 
 Dir.chdir(File.dirname(__FILE__)) { (s = lambda { |f| File.exist?(f) ? require(f) : Dir.chdir("..") { s.call(f) } }).call("spec/spec_helper.rb") }
 
 require 'puppet/util/monkey_patches'
 
 describe "Pure ruby yaml implementation" do
   {
   7            => "--- 7",
   3.14159      => "--- 3.14159",
   'test'       => "--- test",
   []           => "--- []",
   :symbol      => "--- !ruby/sym symbol",
   {:a => "A"}  => "--- \n  !ruby/sym a: A",
   {:a => "x\ny"} => "--- \n  !ruby/sym a: |-\n    x\n    y" 
   }.each { |o,y|
     it "should convert the #{o.class} #{o.inspect} to yaml" do
       o.to_yaml.should == y
     end
     it "should produce yaml for the #{o.class} #{o.inspect} that can be reconstituted" do
       YAML.load(o.to_yaml).should == o
     end
   }
   #
   # Can't test for equality on raw objects
   {
   Object.new                   => "--- !ruby/object {}",
   [Object.new]                 => "--- \n  - !ruby/object {}",
   {Object.new => Object.new}   => "--- \n  ? !ruby/object {}\n  : !ruby/object {}"
   }.each { |o,y|
     it "should convert the #{o.class} #{o.inspect} to yaml" do
       o.to_yaml.should == y
     end
     it "should produce yaml for the #{o.class} #{o.inspect} that can be reconstituted" do
       lambda { YAML.load(o.to_yaml) }.should_not raise_error
     end
   }
 
   it "should emit proper labels and backreferences for common objects" do
     # Note: this test makes assumptions about the names ZAML chooses
     # for labels.
     x = [1, 2]
     y = [3, 4]
     z = [x, y, x, y]
     z.to_yaml.should == "--- \n  - &id001\n    - 1\n    - 2\n  - &id002\n    - 3\n    - 4\n  - *id001\n  - *id002"
     z2 = YAML.load(z.to_yaml)
     z2.should == z
     z2[0].should equal(z2[2])
     z2[1].should equal(z2[3])
   end
 
   it "should emit proper labels and backreferences for recursive objects" do
     x = [1, 2]
     x << x
     x.to_yaml.should == "--- &id001\n  \n  - 1\n  - 2\n  - *id001"
     x2 = YAML.load(x.to_yaml)
     x2.should be_a(Array)
     x2.length.should == 3
     x2[0].should == 1
     x2[1].should == 2
     x2[2].should equal(x2)
   end
 end
-