Merge branch '0.24.x'

68 files changed, 2052 insertions, 2692 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 346577be8..0908aeaa5 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,3 +1,9 @@
+    Fixed #971 -- classes can once again be included multiple
+    times.
+
+    Added builtin support for Nagios types using
+    Naginator to parse and generate the files.
+
 0.24.1
     Updated vim filetype detection. (#900 and #963)
 
diff --git a/bin/puppetrun b/bin/puppetrun
index cc78f81a8..5f99d6325 100755
--- a/bin/puppetrun
+++ b/bin/puppetrun
@@ -40,7 +40,7 @@
 # you want any Puppet daemon to allow -- it is currently global to all Puppet
 # daemons.
 #
-# An example file looks like this:
+# An example file looks like this::
 #
 #     [fileserver]
 #         allow *.madstop.com
diff --git a/bin/ralsh b/bin/ralsh
index e43177d35..fdf64916f 100755
--- a/bin/ralsh
+++ b/bin/ralsh
@@ -63,17 +63,18 @@
 #
 # = Example
 #
-#   $ ralsh user luke
-#   user { 'luke':
-#       home => '/home/luke',
-#       uid => '100',
-#       ensure => 'present',
-#       comment => 'Luke Kanies,,,',
-#       gid => '1000',
-#       shell => '/bin/bash',
-#       groups => ['sysadmin','audio','video','puppet']
-#   }
-#   $
+# This example uses ``ralsh`` to return Puppet configuration for the user ``luke``::
+#   
+# $ ralsh user luke
+#    user { 'luke':
+#      home => '/home/luke',
+#      uid => '100',
+#      ensure => 'present',
+#      comment => 'Luke Kanies,,,',
+#      gid => '1000',
+#      shell => '/bin/bash',
+#      groups => ['sysadmin','audio','video','puppet']
+#    }
 #
 # = Author
 #
diff --git a/ext/logcheck/puppet b/ext/logcheck/puppet
index ab617e754..8b854dc48 100644
--- a/ext/logcheck/puppet
+++ b/ext/logcheck/puppet
@@ -13,3 +13,5 @@
 ^\w{3} [ :0-9]{11} [._[:alnum:]-]+ puppetd\[[0-9]+\]: Caught (TERM|INT); shutting down$
 ^\w{3} [ :0-9]{11} [._[:alnum:]-]+ puppetd\[[0-9]+\]: Shutting down$
 ^\w{3} [ :0-9]{11} [._[:alnum:]-]+ puppetd\[[0-9]+\]: Restarting with .*$
+^\w{3} [ :0-9]{11} [._[:alnum:]-]+ puppetd\[[0-9]+\]: Starting catalog run$
+^\w{3} [ :0-9]{11} [._[:alnum:]-]+ puppetd\[[0-9]+\]: Finished catalog run in [.0-9]+ seconds$
diff --git a/ext/puppet-test b/ext/puppet-test
index 362a43996..0f33e0cbb 100755
--- a/ext/puppet-test
+++ b/ext/puppet-test
@@ -53,6 +53,9 @@
 # list::
 #   List all available tests.
 #
+# pause::
+#  Pause before starting test (useful for testing with dtrace).
+#
 # repeat::
 #  How many times to perform the test.
 #
@@ -88,7 +91,7 @@
 # Do an initial trap, so that cancels don't get a stack trace.
 trap(:INT) do
     $stderr.puts "Cancelling startup"
-    exit(0)
+    exit(1)
 end
 
 require 'puppet'
@@ -165,6 +168,12 @@ class Suite
         puts "Running %s %s test" % [@name, test]
         prepare()
 
+        if $options[:pause]
+            puts "Hit any key to continue"
+            $stdin.readline
+            puts "Continuing with test"
+        end
+
         if $options[:fork] > 0
             @forking = true
             $options[:fork].times {
@@ -200,6 +209,17 @@ class Suite
     end
 end
 
+Suite.new :parser, "Manifest parsing" do
+    def prepare
+        @parser = Puppet::Parser::Parser.new(:environment => Puppet[:environment])
+        @parser.file = Puppet[:manifest]
+    end
+
+    newtest :parse, "Parsed files" do
+        @parser.parse
+    end
+end
+
 Suite.new :catalog, "Catalog handling" do
     def prepare
         $args[:cache] = false
@@ -325,12 +345,13 @@ end
 
 $cmdargs = [
 	[ "--compile",    "-c",			GetoptLong::NO_ARGUMENT ],
-	[ "--describe",  "-D",			GetoptLong::REQUIRED_ARGUMENT ],
+	[ "--describe",     			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--retrieve",  "-R",			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--fork",          			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--fqdn",      "-F",			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--suite",     "-s",			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--test",      "-t",			GetoptLong::REQUIRED_ARGUMENT ],
+	[ "--pause",	 "-p",			GetoptLong::NO_ARGUMENT ],
 	[ "--repeat",    "-r",			GetoptLong::REQUIRED_ARGUMENT ],
 	[ "--debug",	 "-d",			GetoptLong::NO_ARGUMENT ],
 	[ "--help",		 "-h",			GetoptLong::NO_ARGUMENT ],
@@ -340,14 +361,14 @@ $cmdargs = [
 ]
 
 # Add all of the config parameters as valid $options.
-Puppet.config.addargs($cmdargs)
+Puppet.settings.addargs($cmdargs)
 Puppet::Util::Log.newdestination(:console)
 
 result = GetoptLong.new(*$cmdargs)
 
 $args = {}
 
-$options = {:repeat => 1, :fork => 0}
+$options = {:repeat => 1, :fork => 0, :pause => false}
 
 begin
     explicit_waitforcert = false
@@ -399,6 +420,8 @@ begin
                 $options[:test] = arg.intern
             when "--file"
                 $options[:file] = arg
+            when "--pause"
+                $options[:pause] = true
             when "--list"
                 Suite.suites.sort { |a,b| a.to_s <=> b.to_s }.each do |suite_name|
                     suite = Suite[suite_name]
@@ -407,7 +430,7 @@ begin
                 end
                 exit(0)
             else
-                Puppet.config.handlearg(opt, arg)
+                Puppet.settings.handlearg(opt, arg)
         end
     }
 rescue GetoptLong::InvalidOption => detail
diff --git a/lib/puppet/external/gratr/rdot.rb b/lib/puppet/external/dot.rb
index b94568c12..b94568c12 100644
--- a/lib/puppet/external/gratr/rdot.rb
+++ b/lib/puppet/external/dot.rb
diff --git a/lib/puppet/external/gratr.rb b/lib/puppet/external/gratr.rb
deleted file mode 100644
index b830caeb4..000000000
--- a/lib/puppet/external/gratr.rb
+++ /dev/null
@@ -1,33 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/base'
-require 'puppet/external/gratr/digraph'
-require 'puppet/external/gratr/undirected_graph'
-require 'puppet/external/gratr/common'
diff --git a/lib/puppet/external/gratr/adjacency_graph.rb b/lib/puppet/external/gratr/adjacency_graph.rb
deleted file mode 100644
index b740c4722..000000000
--- a/lib/puppet/external/gratr/adjacency_graph.rb
+++ /dev/null
@@ -1,257 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/edge'
-require 'puppet/external/gratr/graph'
-require 'set'
-
-module GRATR
-
-  # This provides the basic routines needed to implement the Digraph, UndirectedGraph,
-  # PseudoGraph, DirectedPseudoGraph, MultiGraph and DirectedPseudoGraph class.
-  module AdjacencyGraph
-    
-    include Graph
-
-    class ArrayWithAdd < Array # :nodoc:
-      alias add push
-    end
-
-    # Initialization parameters can include an Array of edges to add, Graphs to
-    # copy (will merge if multiple)
-    # :parallel_edges denotes that duplicate edges are allowed
-    # :loops denotes that loops are allowed
-    def initialize(*params)
-      @vertex_dict     = Hash.new    
-      raise ArgumentError if params.any? do |p| 
-        !(p.kind_of? GRATR::Graph or 
-          p.kind_of? Array or 
-          p == :parallel_edges or
-          p == :loops)
-      end
-      clear_all_labels
-
-      # Basic configuration of adjacency
-      @allow_loops    = params.any? {|p| p == :loops}
-      @parallel_edges = params.any? {|p| p == :parallel_edges}
-      @edgelist_class = @parallel_edges ? ArrayWithAdd : Set
-      if @parallel_edges
-        @edge_number      = Hash.new
-        @next_edge_number = 0 
-      end
-
-      # Copy any given graph into this graph
-      params.select {|p| p.kind_of? GRATR::Graph}.each do |g|
-        g.edges.each do |e| 
-          add_edge!(e)
-          edge_label_set(e, edge_label(e)) if edge_label(e)
-        end
-        g.vertices.each do |v|
-          vertex_label_set(v, vertex_label(v)) if vertex_label(v)
-        end  
-      end
-
-      # Add all array edges specified
-      params.select {|p| p.kind_of? Array}.each do |a|
-        0.step(a.size-1, 2) {|i| add_edge!(a[i], a[i+1])}
-      end
-
-    end
-
-    # Returns true if v is a vertex of this Graph
-    # An O(1) implementation of vertex?
-    def vertex?(v) @vertex_dict.has_key?(v); end
-
-    # Returns true if [u,v] or u is an Edge
-    # An O(1) implementation 
-    def edge?(u, v=nil)
-      u, v = u.source, u.target if u.kind_of? GRATR::Edge
-      vertex?(u) and @vertex_dict[u].include?(v)
-    end
-
-    # Adds a vertex to the graph with an optional label
-    def add_vertex!(vertex, label=nil)
-      @vertex_dict[vertex] ||= @edgelist_class.new
-      self[vertex] = label if label
-      self
-    end
-
-    # Adds an edge to the graph
-    # Can be called in two basic ways, label is optional
-    #   * add_edge!(Edge[source,target], "Label")
-    #   * add_edge!(source,target, "Label")
-    def add_edge!(u, v=nil, l=nil, n=nil)
-      if u.class.include? EdgeNumber and n.nil?
-          n = u.number
-      end
-      if u.kind_of? GRATR::Edge
-          edge = u
-          u, v, l = u.source, u.target, u.label
-      end
-      if not @allow_loops and u == v
-          return self
-      end
-      if @parallel_edges and ! n
-          n = (@next_edge_number+=1)
-      end
-      add_vertex!(u);
-      add_vertex!(v)        
-      @vertex_dict[u].add(v)
-
-      if @parallel_edges
-          (@edge_number[u] ||= @edgelist_class.new).add(n)
-      end
-      unless directed?
-        @vertex_dict[v].add(u)
-        if @parallel_edges
-            (@edge_number[v] ||= @edgelist_class.new).add(n)
-        end
-      end        
-
-      if l
-          unless edge
-              if n
-                  edge = edge_class[u,v,n]
-              else
-                  edge = edge_class[u,v]
-              end
-          end
-          self[edge] = l
-      end
-      self
-    end
-
-    # Removes a given vertex from the graph
-    def remove_vertex!(v)
-# FIXME This is broken for multi graphs 
-      @vertex_dict.delete(v)
-      @vertex_dict.each_value { |adjList| adjList.delete(v) }
-      @vertex_dict.keys.each  do |u| 
-        delete_label(edge_class[u,v]) 
-        delete_label(edge_class[v,u])
-      end
-      delete_label(v) 
-      self
-    end
-
-    # Removes an edge from the graph, can be called with source and target or with
-    # and object of GRATR::Edge derivation
-    def remove_edge!(u, v=nil)
-      unless u.kind_of? GRATR::Edge
-        raise ArgumentError if @parallel_edges
-        u = edge_class[u,v]
-      end
-      raise ArgumentError if @parallel_edges and (u.number || 0) == 0
-      return self unless @vertex_dict[u.source] # It doesn't exist
-      delete_label(u) # Get rid of label
-      if @parallel_edges
-        index = @edge_number[u.source].index(u.number)
-        raise NoEdgeError unless index
-        @vertex_dict[u.source].delete_at(index)
-        @edge_number[u.source].delete_at(index) 
-      else
-        @vertex_dict[u.source].delete(u.target) 
-      end
-      self
-    end
-
-    # Returns an array of vertices that the graph has
-    def vertices() @vertex_dict.keys; end
-
-    # Returns an array of edges, most likely of class Edge or UndirectedEdge depending 
-    # upon the type of graph
-    def edges
-      @vertex_dict.keys.inject(Set.new) do |a,v|
-        if @parallel_edges and @edge_number[v]
-          @vertex_dict[v].zip(@edge_number[v]).each do |w|
-            s,t,n = v,w[0],w[1]
-            a.add( edge_class[ s,t,n, edge_label(s,t,n) ] )
-          end
-        else
-          @vertex_dict[v].each do |w|
-            a.add(edge_class[v,w,edge_label(v,w)])
-          end
-        end; a
-      end.to_a
-    end
- 
-    alias graph_adjacent adjacent
-    def adjacent(x, options={})
-        unless @vertex_dict.has_key?(x)
-            raise ArgumentError, "%s is not a vertex" % x
-        end
-      options[:direction] ||= :out
-      if !x.kind_of?(GRATR::Edge) and (options[:direction] == :out || !directed?)
-        if options[:type] == :edges
-          @parallel_edges ?
-            @vertex_dict[x].map {|v| e=edge_class[x,v,@edge_number[x][v]]; e.label = self[e]; e} :
-            @vertex_dict[x].map {|v| e=edge_class[x,v];  e.label = self[e]; e}
-        else
-          @vertex_dict[x].to_a
-        end
-      else
-        graph_adjacent(x,options)
-      end
-    end
-    
- 
-  public
-
-    def self.included(cl)
-      # Shortcut for creating a Graph
-      #
-      #  Example: GRATR::Digraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s =>
-      #    "(1-2)(2-3)(2-4)(4-5)"
-      # 
-      # Or as a Hash for specifying lables
-      # GRATR::Digraph[ [:a,:b] => 3, [:b,:c] => 4 ]  (Note: Do not use for Multi or Pseudo graphs)
-      def cl.[] (*a)
-        result = new
-        if a.size == 1 and a[0].kind_of? Hash
-          # Convert to edge class
-          a[0].each do |k,v|
-            if result.edge_class.include? GRATR::EdgeNumber
-              result.add_edge!(result.edge_class[k[0],k[1],nil,v])
-            else
-             result.add_edge!(result.edge_class[k[0],k[1],v])
-            end 
-          end
-        elsif a[0].kind_of? GRATR::Edge
-          a.each{|e| result.add_edge!(e); result[e] = e.label}
-        elsif a.size % 2 == 0    
-          0.step(a.size-1, 2) {|i| result.add_edge!(a[i], a[i+1])}
-        else
-          raise ArgumentError
-        end
-        result
-      end
-    end
-          
-  end # Adjacency Graph
-end # GRATR
diff --git a/lib/puppet/external/gratr/base.rb b/lib/puppet/external/gratr/base.rb
deleted file mode 100644
index 72dded73f..000000000
--- a/lib/puppet/external/gratr/base.rb
+++ /dev/null
@@ -1,34 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-GRATR_VERSION = "0.4.1"
-
-module GRATR
-  class NoVertexError      < IndexError;   end
-  class NoEdgeError        < IndexError;   end
-end
diff --git a/lib/puppet/external/gratr/biconnected.rb b/lib/puppet/external/gratr/biconnected.rb
deleted file mode 100644
index c976b2c04..000000000
--- a/lib/puppet/external/gratr/biconnected.rb
+++ /dev/null
@@ -1,116 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'set'
-
-module GRATR
-  module Graph    
-    # Biconnected is a module for adding the biconnected algorithm to 
-    # UndirectedGraphs
-    module Biconnected
-
-      # biconnected computes the biconnected subgraphs
-      # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan
-      # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on 
-      # Computing, 1(2):146-160, 1972
-      #
-      # The output of the algorithm is a pair, the first value is an 
-      # array of biconnected subgraphs. The second is the set of
-      # articulation vertices.
-      #
-      # A connected graph is biconnected if the removal of any single vertex 
-      # (and all edges incident on that vertex) cannot disconnect the graph.
-      # More generally, the biconnected components of a graph are the maximal
-      # subsets of vertices such that the removal of a vertex from a particular
-      # component will not disconnect the component. Unlike connected components,
-      # vertices may belong to multiple biconnected components: those vertices
-      # that belong to more than one biconnected component are called articulation
-      # points or, equivalently, cut vertices. Articulation points are vertices
-      # whose removal would increase the number of connected components in the graph.
-      # Thus, a graph without articulation points is biconnected.
-      def biconnected
-        dfs_num     = 0
-        number      = {}; predecessor = {}; low_point   = {}
-        stack       = []; result      = []; articulation= []
-
-        root_vertex  = Proc.new {|v| predecessor[v]=v }
-        enter_vertex = Proc.new {|u| number[u]=low_point[u]=(dfs_num+=1) }
-        tree_edge  = Proc.new do |e|
-          stack.push(e)
-          predecessor[e.target] = e.source
-        end
-        back_edge  = Proc.new do |e|
-          if e.target != predecessor[e.source]
-            stack.push(e)
-            low_point[e.source] = [low_point[e.source], number[e.target]].min
-          end
-        end
-        exit_vertex = Proc.new do |u|
-          parent = predecessor[u]
-          is_articulation_point = false
-          if number[parent] > number[u]
-            parent = predecessor[parent]
-            is_articulation_point = true
-          end
-          if parent == u
-            is_articulation_point = false if (number[u] + 1) == number[predecessor[u]]
-          else
-            low_point[parent] = [low_point[parent], low_point[u]].min
-            if low_point[u] >= number[parent]
-              if number[parent] > number[predecessor[parent]]
-                predecessor[u] = predecessor[parent]
-                predecessor[parent] = u
-              end
-              result << (component = self.class.new)
-              while number[stack[-1].source] >= number[u]
-                component.add_edge!(stack.pop)
-              end
-              component.add_edge!(stack.pop)
-              if stack.empty?
-                predecessor[u] = parent
-                predecessor[parent] = u
-              end
-            end
-          end
-          articulation << u if is_articulation_point
-        end
-
-        # Execute depth first search
-        dfs({:root_vertex  => root_vertex,
-             :enter_vertex => enter_vertex, 
-             :tree_edge    => tree_edge,
-             :back_edge    => back_edge,
-             :exit_vertex  => exit_vertex})
-           
-        [result, articulation]
-      end # biconnected
-
-    end # Biconnected
-
-  end # Graph
-end # GRATR
diff --git a/lib/puppet/external/gratr/chinese_postman.rb b/lib/puppet/external/gratr/chinese_postman.rb
deleted file mode 100644
index 338a88bed..000000000
--- a/lib/puppet/external/gratr/chinese_postman.rb
+++ /dev/null
@@ -1,123 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/digraph_distance'
-
-module GRATR
-  module Graph
-    module ChinesePostman    
-  
-      # Returns the shortest walk that traverses all arcs at least
-      # once, returning to the specified start node.
-      def closed_chinese_postman_tour(start, weight=nil, zero=0)
-        cost, path, delta = floyd_warshall(weight, zero)
-        return nil unless cp_valid_least_cost? cost, zero
-        positive, negative = cp_unbalanced(delta)
-        f = cp_find_feasible(delta, positive, negative, zero)
-        while cp_improve(f, positive, negative, cost, zero); end
-        cp_euler_circuit(start, f, path)
-      end
-
-    private
-   
-      def cp_euler_circuit(start, f, path) # :nodoc:
-        circuit = [u=v=start]
-        bridge_taken = Hash.new {|h,k| h[k] = Hash.new}
-        until v.nil?
-          if v=f[u].keys.detect {|k| f[u][k] > 0}
-            f[u][v] -= 1
-            circuit << (u = path[u][v]) while u != v 
-          else
-            unless bridge_taken[u][bridge = path[u][start]]
-              v = vertices.detect {|v1| v1 != bridge && edge?(u,v1) && !bridge_taken[u][v1]} || bridge
-              bridge_taken[u][v] = true
-              circuit << v            
-            end
-          end  
-          u=v
-        end; circuit
-      end
-   
-      def cp_cancel_cycle(cost, path, f, start, zero) # :nodoc:
-        u = start; k = nil
-        begin
-          v = path[u][start]
-          k = f[v][u] if cost[u][v] < zero and (k.nil? || k > f[v][u])
-        end until (u=v) != start
-        u = start
-        begin
-          v = path[u][start]
-          cost[u][v] < zero ? f[v][u] -= k : f[u][v] += k
-        end until (u=v) != start
-        true # This routine always returns true to make cp_improve easier
-      end
-    
-      def cp_improve(f, positive, negative, cost, zero) # :nodoc:
-        residual = self.class.new
-        negative.each do |u|
-          positive.each do |v|
-            residual.add_edge!(u,v,cost[u][v])
-            residual.add_edge!(v,u,-cost[u][v]) if f[u][v] != 0
-          end
-        end
-        r_cost, r_path, r_delta = residual.floyd_warshall(nil, zero)
-        i = residual.vertices.detect {|v| r_cost[v][v] and r_cost[v][v] < zero}
-        i ? cp_cancel_cycle(r_cost, r_path, f, i) : false
-      end
-    
-      def cp_find_feasible(delta, positive, negative, zero) # :nodoc:
-        f = Hash.new {|h,k| h[k] = Hash.new}
-        negative.each do |i|
-          positive.each do |j|
-            f[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j]
-            delta[i] += f[i][j]
-            delta[j] -= f[i][j]
-          end
-        end; f
-      end
-   
-      def cp_valid_least_cost?(c, zero) # :nodoc:
-        vertices.each do |i|
-          vertices.each do |j|
-            return false unless c[i][j] and c[i][j] >= zero
-          end
-        end; true
-      end
-    
-      def cp_unbalanced(delta) # :nodoc:
-        negative = []; positive = []
-        vertices.each do |v|
-          negative << v if delta[v] < 0
-          positive << v if delta[v] > 0
-        end; [positive, negative]  
-      end
-
-    end # Chinese Postman
-  end # Graph
-end # GRATR
-  
diff --git a/lib/puppet/external/gratr/common.rb b/lib/puppet/external/gratr/common.rb
deleted file mode 100644
index 347250edc..000000000
--- a/lib/puppet/external/gratr/common.rb
+++ /dev/null
@@ -1,73 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/edge'
-require 'puppet/external/gratr/graph'
-
-module GRATR
-  # This class defines a cycle graph of size n
-  # This is easily done by using the base Graph
-  # class and implemeting the minimum methods needed to
-  # make it work. This is a good example to look
-  # at for making one's own graph classes
-  class Cycle
-    
-    def initialize(n) @size = n;       end
-    def directed?()     false;           end
-    def vertices()    (1..@size).to_a; end
-    def vertex?(v)    v > 0 and v <= @size; end
-    def edge?(u,v=nil)
-      u, v = [u.source, v.target] if u.kind_of? GRATR::Edge
-      vertex?(u) && vertex?(v) && ((v-u == 1) or (u==@size && v=1))
-    end
-    def edges() Array.new(@size) {|i| GRATR::UndirectedEdge[i+1, (i+1)==@size ? 1 : i+2]}; end
-  end
-  
-  # This class defines a complete graph of size n
-  # This is easily done by using the base Graph
-  # class and implemeting the minimum methods needed to
-  # make it work. This is a good example to look
-  # at for making one's own graph classes
-  class Complete < Cycle
-    def initialize(n) @size = n; @edges = nil; end
-    def edges
-      return @edges if @edges      # Cache edges
-      @edges = []
-      @size.times do |u|
-        @size.times {|v| @edges << GRATR::UndirectedEdge[u+1, v+1]}
-      end; @edges
-    end
-    def edge?(u,v=nil)
-      u, v = [u.source, v.target] if u.kind_of? GRATR::Edge
-      vertex?(u) && vertex?(v)
-    end
-  end              # Complete
-  
-  
-  
-end                # GRATR
diff --git a/lib/puppet/external/gratr/comparability.rb b/lib/puppet/external/gratr/comparability.rb
deleted file mode 100644
index 1546fbefe..000000000
--- a/lib/puppet/external/gratr/comparability.rb
+++ /dev/null
@@ -1,92 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-module GRATR
-  module Graph
-    module Comparability
-      
-      # A comparability graph is an UndirectedGraph that has a transitive
-      # orientation. This returns a boolean that says if this graph
-      # is a comparability graph.
-      def comparability?() gamma_decomposition[1]; end
-      
-      # Returns an array with two values, the first being a hash of edges 
-      # with a number containing their class assignment, the second valud
-      # is a boolean which states whether or not the graph is a 
-      # comparability graph
-      #
-      # Complexity in time O(d*|E|) where d is the maximum degree of a vertex
-      # Complexity in space O(|V|+|E|)
-      def gamma_decomposition
-        k = 0; comparability=true; classification={}
-        edges.map {|edge| [edge.source,edge.target]}.each do |e|
-          if classification[e].nil?
-            k += 1
-            classification[e] = k; classification[e.reverse] = -k
-            comparability &&= gratr_comparability_explore(e, k, classification)
-          end
-        end; [classification, comparability]
-      end
-      
-      # Returns one of the possible transitive orientations of 
-      # the UndirectedGraph as a Digraph
-      def transitive_orientation(digraph_class=Digraph)
-        raise NotImplementError
-      end
-      
-     private
-     
-      # Taken from Figure 5.10, on pg. 130 of Martin Golumbic's, _Algorithmic_Graph_
-      # _Theory_and_Perfect_Graphs.
-      def gratr_comparability_explore(edge, k, classification, space='')
-        ret = gratr_comparability_explore_inner(edge, k, classification, :forward, space)
-        gratr_comparability_explore_inner(edge.reverse, k, classification, :backward, space) && ret
-      end
-      
-      def gratr_comparability_explore_inner(edge, k, classification, direction,space)
-        comparability = true  
-        adj_target = adjacent(edge[1])
-        adjacent(edge[0]).select do |mt|
-          (classification[[edge[1],mt]] || k).abs < k or
-          not adj_target.any? {|adj_t| adj_t == mt} 
-        end.each do |m|
-          e = (direction == :forward) ? [edge[0], m] : [m,edge[0]]
-          if classification[e].nil?
-            classification[e] = k
-            classification[e.reverse] = -k
-            comparability = gratr_comparability_explore(e, k, classification, '  '+space) && comparability
-          elsif classification[e] == -k
-            classification[e] = k
-            gratr_comparability_explore(e, k, classification, '  '+space)
-            comparability = false
-          end
-        end; comparability
-      end # gratr_comparability_explore_inner
-      
-    end # Comparability
-  end # Graph
-end # GRATR
\ No newline at end of file
diff --git a/lib/puppet/external/gratr/digraph.rb b/lib/puppet/external/gratr/digraph.rb
deleted file mode 100644
index 1223a65a1..000000000
--- a/lib/puppet/external/gratr/digraph.rb
+++ /dev/null
@@ -1,116 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-require 'puppet/external/gratr/edge'
-require 'puppet/external/gratr/graph'
-require 'puppet/external/gratr/search'
-require 'puppet/external/gratr/adjacency_graph'
-require 'puppet/external/gratr/strong_components'
-require 'puppet/external/gratr/digraph_distance'
-require 'puppet/external/gratr/chinese_postman'
-
-module GRATR
-  #
-  # Digraph is a directed graph which is a finite set of vertices
-  # and a finite set of edges connecting vertices. It cannot contain parallel
-  # edges going from the same source vertex to the same target. It also
-  # cannot contain loops, i.e. edges that go have the same vertex for source 
-  # and target.
-  #
-  # DirectedPseudoGraph is a class that allows for parallel edges, and a
-  # DirectedMultiGraph is a class that allows for parallel edges and loops
-  # as well.
-  class Digraph
-    include AdjacencyGraph
-    include Graph::Search
-    include Graph::StrongComponents
-    include Graph::Distance
-    include Graph::ChinesePostman
-  
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? GRATR::Graph or p.kind_of? Array)
-      end if self.class == GRATR::Digraph
-      super(*params)
-    end 
-
-    # A directed graph is directed by definition
-    def directed?() true; end
-
-    # A digraph uses the Edge class for edges
-    def edge_class() @parallel_edges ? GRATR::MultiEdge : GRATR::Edge; end
-
-    # Reverse all edges in a graph
-    def reversal
-      return new(self) unless directed?
-      result = self.class.new
-      edges.inject(result) {|a,e| a << e.reverse}
-      vertices.each { |v| result.add_vertex!(v) unless result.vertex?(v) }
-      result
-    end
-
-    # Return true if the Graph is oriented.
-    def oriented?
-      e = edges
-      re = e.map {|x| x.reverse}
-      not e.any? {|x| re.include?(x)}
-    end
-    
-    # Balanced is when the out edge count is equal to the in edge count
-    def balanced?(v) out_degree(v) == in_degree(v); end
-    
-    # Returns out_degree(v) - in_degree(v)
-    def delta(v) out_degree(v) - in_degree(v); end
-          
-  end
-
-  # DirectedGraph is just an alias for Digraph should one desire
-  DirectedGraph = Digraph
-
-  # This is a Digraph that allows for parallel edges, but does not
-  # allow loops
-  class DirectedPseudoGraph < Digraph
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? GRATR::Graph or p.kind_of? Array)
-      end
-      super(:parallel_edges, *params)
-    end 
-  end
-
-  # This is a Digraph that allows for parallel edges and loops
-  class DirectedMultiGraph < Digraph
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? GRATR::Graph or p.kind_of? Array)
-      end
-      super(:parallel_edges, :loops, *params)
-    end 
-  end
-
-end
diff --git a/lib/puppet/external/gratr/digraph_distance.rb b/lib/puppet/external/gratr/digraph_distance.rb
deleted file mode 100644
index 6f90384e7..000000000
--- a/lib/puppet/external/gratr/digraph_distance.rb
+++ /dev/null
@@ -1,185 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-module GRATR
-  module Graph
-    module Distance
-              
-      # Shortest path from Jorgen Band-Jensen and Gregory Gutin,
-      # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54
-      #
-      # Requires that the graph be acyclic. If the graph is not
-      # acyclic, then see dijkstras_algorithm or bellman_ford_moore
-      # for possible solutions.
-      #
-      # start is the starting vertex 
-      # weight can be a Proc, or anything else is accessed using the [] for the
-      #     the label or it defaults to using
-      #     the value stored in the label for the Edge. If it is a Proc it will 
-      #     pass the edge to the proc and use the resulting value.
-      # zero is used for math system with a different definition of zero
-      #
-      # Returns a hash with the key being a vertex and the value being the
-      # distance. A missing vertex from the hash is an infinite distance
-      #
-      # Complexity O(n+m)
-      def shortest_path(start, weight=nil, zero=0)
-        dist = {start => zero}; path = {}
-        topsort(start) do |vi|
-          next if vi == start
-          dist[vi],path[vi] = adjacent(vi, :direction => :in).map do |vj|
-            [dist[vj] + cost(vj,vi,weight), vj] 
-          end.min {|a,b| a[0] <=> b[0]}
-        end; 
-        dist.keys.size == vertices.size ? [dist,path] : nil
-      end # shortest_path    
-    
-      # Algorithm from Jorgen Band-Jensen and Gregory Gutin,
-      # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54
-      #  
-      # Finds the distances from a given vertex s in a weighted digraph
-      # to the rest of the vertices, provided all the weights of arcs
-      # are non-negative. If negative arcs exist in the graph, two 
-      # basic options exist, 1) modify all weights to be positive by
-      # using an offset, or 2) use the bellman_ford_moore algorithm.
-      # Also if the graph is acyclic, use the shortest_path algorithm.
-      #
-      # weight can be a Proc, or anything else is accessed using the [] for the
-      #     the label or it defaults to using
-      #     the value stored in the label for the Edge. If it is a Proc it will 
-      #     pass the edge to the proc and use the resulting value.
-      #  
-      # zero is used for math system with a different definition of zero
-      #
-      # Returns a hash with the key being a vertex and the value being the
-      # distance. A missing vertex from the hash is an infinite distance
-      #
-      # O(n*log(n) + m) complexity
-      def dijkstras_algorithm(s, weight = nil, zero = 0)
-        q = vertices; distance = { s => zero }; path = {}
-        while not q.empty?
-          v = (q & distance.keys).inject(nil) {|a,k| (!a.nil?) && (distance[a] < distance[k]) ? a : k} 
-          q.delete(v)
-          (q & adjacent(v)).each do |u|
-            c = cost(v,u,weight)
-            if distance[u].nil? or distance[u] > (c+distance[v])
-              distance[u] = c + distance[v]
-              path[u] = v
-            end
-          end
-        end; [distance, path]
-      end # dijkstras_algorithm
-
-      # Algorithm from Jorgen Band-Jensen and Gregory Gutin,
-      # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58
-      #  
-      # Finds the distances from a given vertex s in a weighted digraph
-      # to the rest of the vertices, provided the graph has no negative cycle.
-      # If no negative weights exist, then dijkstras_algorithm is more
-      # efficient in time and space. Also if the graph is acyclic, use the
-      # shortest_path algorithm.
-      #
-      # weight can be a Proc, or anything else is accessed using the [] for the
-      #     the label or it defaults to using
-      #     the value stored in the label for the Edge. If it is a Proc it will 
-      #     pass the edge to the proc and use the resulting value.
-      #  
-      # zero is used for math system with a different definition of zero
-      #
-      # Returns a hash with the key being a vertex and the value being the
-      # distance. A missing vertex from the hash is an infinite distance
-      #
-      # O(nm) complexity   
-      def bellman_ford_moore(start, weight = nil, zero = 0)
-        distance = { start => zero }; path = {}
-        2.upto(vertices.size) do
-          edges.each do |e|
-            u,v = e[0],e[1]
-            unless distance[u].nil?
-              c = cost(u, v, weight)+distance[u]
-              if distance[v].nil? or c < distance[v]
-                distance[v] = c
-                path[v] = u
-              end 
-            end        
-          end
-        end; [distance, path]
-      end # bellman_ford_moore
-    
-      # This uses the Floyd-Warshall algorithm to efficiently find
-      # and record shortest paths at the same time as establishing
-      # the costs for all vertices in a graph.
-      # See, S.Skiena, "The Algorithm Design Manual", 
-      # Springer Verlag, 1998 for more details.
-      #  
-      # Returns a pair of matrices and a hash of delta values. 
-      # The matrices will be indexed by two vertices and are
-      # implemented as a Hash of Hashes. The first matrix is the cost, the second
-      # matrix is the shortest path spanning tree. The delta (difference of number
-      # of in edges and out edges) is indexed by vertex.
-      #
-      # weight specifies how an edge weight is determined, if it's a
-      # Proc the Edge is passed to it, if it's nil it will just use
-      # the value in the label for the Edge, otherwise the weight is
-      # determined by applying the [] operator to the value in the 
-      # label for the Edge
-      #
-      # zero defines the zero value in the math system used. Defaults
-      # of course, to 0. This allows for no assumptions to be made
-      # about the math system and fully functional duck typing.
-      #
-      # O(n^3) complexity in time.
-      def floyd_warshall(weight=nil, zero=0)
-        c     = Hash.new {|h,k| h[k] = Hash.new}
-        path  = Hash.new {|h,k| h[k] = Hash.new}
-        delta = Hash.new {|h,k| h[k] = 0}
-        edges.each do |e| 
-          delta[e.source] += 1
-          delta[e.target] -= 1
-          path[e.source][e.target] = e.target      
-          c[e.source][e.target] = cost(e, weight)
-        end
-        vertices.each do |k|
-          vertices.each do |i|
-            if c[i][k]
-              vertices.each do |j|
-                if c[k][j] && 
-                  (c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j]))
-                  path[i][j] = path[i][k]
-                  c[i][j] = c[i][k] + c[k][j]
-                  return nil if i == j and c[i][j] < zero
-                end
-              end
-            end  
-          end
-        end
-        [c, path, delta]
-      end # floyd_warshall
-           
-    end # Distance
-  end # Graph
-end # GRATR
\ No newline at end of file
diff --git a/lib/puppet/external/gratr/dot.rb b/lib/puppet/external/gratr/dot.rb
deleted file mode 100644
index 5b74776aa..000000000
--- a/lib/puppet/external/gratr/dot.rb
+++ /dev/null
@@ -1,90 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-#
-# Minimal Dot support, based on Dave Thomas's dot module (included in rdoc).
-# rdot.rb is a modified version which also contains support for undirected
-# graphs.
-
-require 'puppet/external/gratr/rdot'
-
-module GRATR
-  module Graph
- 
-    # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an
-    # undirected Graph.  _params_ can contain any graph property specified in
-    # rdot.rb. If an edge or vertex label is a kind of Hash then the keys
-    # which match +dot+ properties will be used as well.
-    def to_dot_graph (params = {})
-      params['name'] ||= self.class.name.gsub(/:/,'_')
-      fontsize   = params['fontsize'] ? params['fontsize'] : '8'
-      graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
-      edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge
-      vertices.each do |v|
-        name = v.to_s
-        params = {'name'     => '"'+name+'"',
-                  'fontsize' => fontsize,
-                  'label'    => name}
-        v_label = vertex_label(v)
-        params.merge!(v_label) if v_label and v_label.kind_of? Hash
-        graph << DOT::DOTNode.new(params)
-      end
-      edges.each do |e|
-        params = {'from'     => '"'+ e.source.to_s + '"',
-                  'to'       => '"'+ e.target.to_s + '"',
-                  'fontsize' => fontsize }
-        e_label = edge_label(e)
-        params.merge!(e_label) if e_label and e_label.kind_of? Hash
-        graph << edge_klass.new(params)
-      end
-      graph
-    end
-    
-    # Output the dot format as a string
-    def to_dot (params={}) to_dot_graph(params).to_s; end
-
-    # Call +dotty+ for the graph which is written to the file 'graph.dot'
-    # in the # current directory.
-    def dotty (params = {}, dotfile = 'graph.dot')
-      File.open(dotfile, 'w') {|f| f << to_dot(params) }
-      system('dotty', dotfile)
-    end
-
-    # Use +dot+ to create a graphical representation of the graph.  Returns the
-    # filename of the graphics file.
-    def write_to_graphic_file (fmt='png', dotfile='graph')
-      src = dotfile + '.dot'
-      dot = dotfile + '.' + fmt
-      
-      File.open(src, 'w') {|f| f << self.to_dot << "\n"}
-      
-      system( "dot -T#{fmt} #{src} -o #{dot}" )
-      dot
-    end
-
-  end                           # module Graph
-end                             # module GRATR
diff --git a/lib/puppet/external/gratr/edge.rb b/lib/puppet/external/gratr/edge.rb
deleted file mode 100644
index 8470e5458..000000000
--- a/lib/puppet/external/gratr/edge.rb
+++ /dev/null
@@ -1,145 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-module GRATR
-
-  # Edge includes classes for representing egdes of directed and
-  # undirected graphs. There is no need for a Vertex class, because any ruby
-  # object can be a vertex of a graph.
-  #
-  # Edge's base is a Struct with a :source, a :target and a :label
-  Struct.new("EdgeBase",:source, :target, :label)
-
-  class Edge < Struct::EdgeBase
-
-    def initialize(p_source,p_target,p_label=nil)
-      super(p_source, p_target, p_label)
-    end
-
-    # Ignore labels for equality
-    def eql?(other) self.class == other.class and target==other.target and source==other.source; end
-
-    # Alias for eql?
-    alias == eql?
-
-    # Returns (v,u) if self == (u,v).
-    def reverse() self.class.new(target, source, label); end
-
-    # Sort support
-    def <=>(rhs) [source,target] <=> [rhs.source,rhs.target]; end
-
-    # Edge.new[1,2].to_s => "(1-2 'label')"
-    def to_s
-      l = label ? " '#{label.to_s}'" : ''
-      "(#{source}-#{target}#{l})"
-    end
-    
-    # Hash is defined in such a way that label is not
-    # part of the hash value
-    def hash() source.hash ^ (target.hash+1); end
-
-    # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2]
-    def self.[](p_source, p_target, p_label=nil)
-      new(p_source, p_target, p_label)
-    end
-    
-    def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{label.inspect}]"; end
-    
-  end
-    
-  # An undirected edge is simply an undirected pair (source, target) used in
-  # undirected graphs. UndirectedEdge[u,v] == UndirectedEdge[v,u]
-  class UndirectedEdge < Edge
-
-    # Equality allows for the swapping of source and target
-    def eql?(other) super or (self.class == other.class and target==other.source and source==other.target); end
-      
-    # Alias for eql?
-    alias == eql?
-
-    # Hash is defined such that source and target can be reversed and the
-    # hash value will be the same
-    #
-    # This will cause problems with self loops
-    def hash() source.hash ^ target.hash; end
-
-    # Sort support
-    def <=>(rhs)
-      [[source,target].max,[source,target].min] <=> 
-      [[rhs.source,rhs.target].max,[rhs.source,rhs.target].min]
-    end
-    
-    # UndirectedEdge[1,2].to_s == "(1=2 'label)"
-    def to_s
-      l = label ? " '#{label.to_s}'" : ''
-      s = source.to_s
-      t = target.to_s
-      "(#{[s,t].min}=#{[s,t].max}#{l})"
-    end
-    
-  end
-  
-  # This module provides for internal numbering of edges for differentiating between mutliple edges
-  module EdgeNumber
-    
-    attr_accessor :number # Used to differentiate between mutli-edges
-    
-    def initialize(p_source,p_target,p_number,p_label=nil)
-      self.number = p_number 
-      super(p_source, p_target, p_label)
-    end
-
-    # Returns (v,u) if self == (u,v).
-    def reverse() self.class.new(target, source, number, label); end
-    def hash() super ^ number.hash; end    
-    def to_s() super + "[#{number}]"; end
-    def <=>(rhs) (result = super(rhs)) == 0 ? number <=> rhs.number : result; end 
-    def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{number.inspect},#{label.inspect}]"; end
-    def eql?(rhs) super(rhs) and (rhs.number.nil? or number.nil? or number == rhs.number); end 
-    def ==(rhs) eql?(rhs); end
-
-    # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2]
-    def self.included(cl)
-      
-      def cl.[](p_source, p_target, p_number=nil, p_label=nil)
-        new(p_source, p_target, p_number, p_label)
-      end
-    end
-
-  end
-  
-  class MultiEdge < Edge
-    include EdgeNumber
-  end
-  
-  class MultiUndirectedEdge < UndirectedEdge
-    include EdgeNumber
-  end
-  
-end
diff --git a/lib/puppet/external/gratr/graph.rb b/lib/puppet/external/gratr/graph.rb
deleted file mode 100644
index 7b73afccc..000000000
--- a/lib/puppet/external/gratr/graph.rb
+++ /dev/null
@@ -1,303 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/edge'
-require 'puppet/external/gratr/labels'
-require 'puppet/external/gratr/graph_api'
-
-module GRATR
-  
-  # Using the functions required by the GraphAPI, it implements all the
-  # basic functions of a Graph class by using only functions in GraphAPI.
-  # An actual implementation still needs to be done, as in Digraph or
-  # UndirectedGraph.
-  module Graph
-    include Enumerable
-    include Labels
-    include GraphAPI
-      
-    # Non destructive version of add_vertex!, returns modified copy of Graph
-    def add_vertex(v, l=nil) x=self.class.new(self); x.add_vertex!(v,l); end
-      
-    # Non destructive version add_edge!, returns modified copy of Graph  
-    def add_edge(u, v=nil, l=nil) x=self.class.new(self); x.add_edge!(u,v,l); end
-      
-    # Non destructive version of remove_vertex!, returns modified copy of Graph
-    def remove_vertex(v) x=self.class.new(self); x.remove_vertex!(v); end  
-
-    # Non destructive version of remove_edge!, returns modified copy of Graph
-    def remove_edge(u,v=nil) x=self.class.new(self); x.remove_edge!(u,v); end
-      
-    # Return Array of adjacent portions of the Graph
-    #  x can either be a vertex an edge.
-    #  options specifies parameters about the adjacency search
-    #   :type can be either :edges or :vertices (default).
-    #   :direction can be :in, :out(default) or :all.
-    #
-    # Note: It is probably more efficently done in implementation.
-    def adjacent(x, options={})
-      d = directed? ? (options[:direction] || :out) : :all
-
-      # Discharge the easy ones first
-      return [x.source] if x.kind_of? Edge and options[:type] == :vertices and d == :in
-      return [x.target] if x.kind_of? Edge and options[:type] == :vertices and d == :out
-      return [x.source, x.target] if x.kind_of? Edge and options[:type] != :edges and d == :all
-
-      (options[:type] == :edges ? edges : to_a).select {|u| adjacent?(x,u,d)}
-    end
-
-    # Add all objects in _a_ to the vertex set.
-    def add_vertices!(*a) a.each {|v| add_vertex! v}; self; end
-      
-    # See add_vertices!
-
-    def add_vertices(*a) x=self.class.new(self); x.add_vertices(*a); self; end
-
-    # Add all edges in the _edges_ Enumerable to the edge set.  Elements of the
-    # Enumerable can be both two-element arrays or instances of DirectedEdge or
-    # UnDirectedEdge. 
-    def add_edges!(*args) args.each { |edge| add_edge!(edge) }; self; end
-      
-    # See add_edge!
-    def add_edges(*a) x=self.class.new(self); x.add_edges!(*a); self; end
-
-    # Remove all vertices specified by the Enumerable a from the graph by
-    # calling remove_vertex!.
-    def remove_vertices!(*a) a.each { |v| remove_vertex! v }; end
-      
-    # See remove_vertices!
-    def remove_vertices(*a) x=self.class.new(self); x.remove_vertices(*a); end
-
-    # Remove all vertices edges by the Enumerable a from the graph by
-    # calling remove_edge!
-    def remove_edges!(*a) a.each { |e| remove_edges! e }; end
-
-    # See remove_edges
-    def remove_edges(*a) x=self.class.new(self); x.remove_edges(*a); end
-
-    # Execute given block for each vertex, provides for methods in Enumerable
-    def each(&block) vertices.each(&block); end
-
-    # Returns true if _v_ is a vertex of the graph.
-    # This is a default implementation that is of O(n) average complexity.
-    # If a subclass uses a hash to store vertices, then this can be
-    # made into an O(1) average complexity operation.
-    def vertex?(v) vertices.include?(v); end  
-    
-    # Returns true if u or (u,v) is an Edge of the graph.
-    def edge?(*arg) edges.include?(edge_convert(*args)); end  
-
-    # Tests two objects to see if they are adjacent.
-    # direction parameter specifies direction of adjacency, :in, :out, or :all(default)
-    # All denotes that if there is any adjacency, then it will return true.
-    # Note that the default is different than adjacent where one is primarily concerned with finding
-    # all adjacent objects in a graph to a given object. Here the concern is primarily on seeing
-    # if two objects touch. For vertexes, any edge between the two will usually do, but the direction
-    # can be specified if need be.
-    def adjacent?(source, target, direction=:all)
-      if source.kind_of? GRATR::Edge
-        raise NoEdgeError unless edge? source
-        if target.kind_of? GRATR::Edge
-          raise NoEdgeError unless edge? target
-          (direction != :out and source.source == target.target) or (direction != :in and source.target == target.source)
-        else
-          raise NoVertexError unless vertex? target
-          (direction != :out and source.source == target)  or (direction != :in and source.target == target)
-        end
-      else
-        raise NoVertexError unless vertex? source
-        if target.kind_of? GRATR::Edge
-          raise NoEdgeError unless edge? target
-          (direction != :out and source == target.target) or (direction != :in and source == target.source)
-        else
-          raise NoVertexError unless vertex? target
-          (direction != :out and edge?(target,source)) or (direction != :in and edge?(source,target))
-        end
-      end
-    end
-
-    # Returns true if the graph has no vertex, i.e. num_vertices == 0.
-    def empty?() vertices.size.zero?; end
-
-    # Returns true if the given object is a vertex or Edge in the Graph.
-    # 
-    def include?(x) x.kind_of?(GRATR::Edge) ? edge?(x) : vertex?(x); end
-
-    # Returns the neighboorhood of the given vertex (or Edge)
-    # This is equivalent to adjacent, but bases type on the type of object.
-    # direction can be :all, :in, or :out 
-    def neighborhood(x, direction = :all)
-      adjacent(x, :direction => direction, :type => ((x.kind_of? GRATR::Edge) ? :edges : :vertices )) 
-    end
-    
-    # Union of all neighborhoods of vertices (or edges) in the Enumerable x minus the contents of x
-    # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 4
-    def set_neighborhood(x, direction = :all)
-      x.inject(Set.new) {|a,v| a.merge(neighborhood(v,direction))}.reject {|v2| x.include?(v2)}
-    end  
-    
-    # Union of all set_neighborhoods reachable in p edges
-    # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46
-    def closed_pth_neighborhood(w,p,direction=:all)
-      if p <= 0
-        w 
-      elsif p == 1
-        (w + set_neighborhood(w,direction)).uniq
-      else
-        n = set_neighborhood(w, direction)
-        (w + n + closed_pth_neighborhood(n,p-1,direction)).uniq
-      end
-    end
-    
-    # Returns the neighboorhoods reachable in p steps from every vertex (or edge)
-    # in the Enumerable x        
-    # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46
-    def open_pth_neighborhood(x, p, direction=:all)
-      if    p <= 0
-        x
-      elsif p == 1
-        set_neighborhood(x,direction)
-      else  
-        set_neighborhood(open_pth_neighborhood(x, p-1, direction),direction) - closed_pth_neighborhood(x,p-1,direction)
-      end    
-    end
-    
-    # Returns the number of out-edges (for directed graphs) or the number of
-    # incident edges (for undirected graphs) of vertex _v_.
-    def out_degree(v) adjacent(v, :direction => :out).size; end
-
-    # Returns the number of in-edges (for directed graphs) or the number of
-    # incident edges (for undirected graphs) of vertex _v_.
-    def in_degree(v)  adjacent(v, :direction => :in ).size; end
-
-    # Returns the sum of the number in and out edges for a vertex
-    def degree(v) in_degree(v) + out_degree(v); end
-
-    # Minimum in-degree 
-    def min_in_degree() to_a.map {|v| in_degree(v)}.min; end
-
-    # Minimum out-degree
-    def min_out_degree() to_a.map {|v| out_degree(v)}.min; end
-
-    # Minimum degree of all vertexes
-    def min_degree() [min_in_degree, min_out_degree].min; end
-
-    # Maximum in-degree 
-    def max_in_degree() vertices.map {|v| in_degree(v)}.max; end
-
-    # Maximum out-degree
-    def max_out_degree() vertices.map {|v| out_degree(v)}.max; end
-
-    # Minimum degree of all vertexes
-    def max_degree() [max_in_degree, max_out_degree].max; end
-
-    # Regular
-    def regular?() min_degree == max_degree; end
-
-    # Returns the number of vertices.
-    def size()         vertices.size; end
-
-    # Synonym for size.
-    def num_vertices() vertices.size; end
-
-    # Returns the number of edges.
-    def num_edges()    edges.size; end
-
-    # Utility method to show a string representation of the edges of the graph.
-    def to_s() edges.to_s; end
-
-    # Equality is defined to be same set of edges and directed?
-    def eql?(g) 
-      return false unless g.kind_of? GRATR::Graph
-
-      (g.directed?   == self.directed?)  and 
-      (vertices.sort == g.vertices.sort) and
-      (g.edges.sort  == edges.sort)
-    end
-
-    # Synonym for eql?
-    def ==(rhs) eql?(rhs); end
-
-    # Merge another graph into this one
-    def merge(other)
-      other.vertices.each {|v| add_vertex!(v)      }
-      other.edges.each    {|e| add_edge!(e)         }
-      other.edges.each    {|e| add_edge!(e.reverse) } if directed? and !other.directed? 
-      self 
-    end
-
-    # A synonym for merge, that doesn't modify the current graph
-    def +(other)
-      result = self.class.new(self)
-      case other
-        when GRATR::Graph : result.merge(other)
-        when GRATR::Edge  : result.add_edge!(other)
-        else              result.add_vertex!(other)
-      end
-    end
-
-    # Remove all vertices in the specified right hand side graph
-    def -(other)
-      case  other
-        when GRATR::Graph : induced_subgraph(vertices - other.vertices)
-        when GRATR::Edge  : self.class.new(self).remove_edge!(other)
-        else              self.class.new(self).remove_vertex!(other)
-      end
-    end
-
-    # A synonym for add_edge!
-    def <<(edge) add_edge!(edge); end
-
-    # Return the complement of the current graph
-    def complement
-      vertices.inject(self.class.new) do |a,v|
-        a.add_vertex!(v)
-        vertices.each {|v2| a.add_edge!(v,v2) unless edge?(v,v2) }; a
-      end
-    end
-
-    # Given an array of vertices return the induced subgraph
-    def induced_subgraph(v)
-      edges.inject(self.class.new) do |a,e| 
-        ( v.include?(e.source) and v.include?(e.target) ) ?  (a << e) : a
-      end;
-    end
-    
-    def inspect
-      l = vertices.select {|v| self[v]}.map {|u| "vertex_label_set(#{u.inspect},#{self[u].inspect})"}.join('.')
-      self.class.to_s + '[' + edges.map {|e| e.inspect}.join(', ') + ']' + (l ? '.'+l : '')
-    end
-    
-   private
-    def edge_convert(*args) args[0].kind_of?(GRATR::Edge) ? args[0] : edge_class[*args]; end
-    
-
-  end # Graph
-
-end # GRATR
diff --git a/lib/puppet/external/gratr/graph_api.rb b/lib/puppet/external/gratr/graph_api.rb
deleted file mode 100644
index 26d18958a..000000000
--- a/lib/puppet/external/gratr/graph_api.rb
+++ /dev/null
@@ -1,83 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-module GRATR
-  
-  # This defines the minimum set of functions required to make a graph class that can
-  # use the algorithms defined by this library
-  module GraphAPI
-    
-    # Is the graph directed?
-    # 
-    # This method must be implemented by the specific graph class
-    def directed?()             raise NotImplementedError; end
-
-    # Add a vertex to the Graph and return the Graph
-    # An additional label l can be specified as well
-    # 
-    # This method must be implemented by the specific graph class    
-    def add_vertex!(v,l=nil)     raise NotImplementedError; end
-      
-    # Add an edge to the Graph and return the Graph
-    # u can be an object of type GRATR::Edge or u,v specifies
-    # a source, target pair. The last parameter is an optional label
-    # 
-    # This method must be implemented by the specific graph class
-    def add_edge!(u,v=nil,l=nil) raise NotImplementedError; end
-      
-    # Remove a vertex to the Graph and return the Graph
-    # 
-    # This method must be implemented by the specific graph class
-    def remove_vertex!(v)        raise NotImplementedError; end
-      
-    # Remove an edge from the Graph and return the Graph
-    # 
-    # Can be a type of GRATR::Edge or a source and target
-    # This method must be implemented by the specific graph class
-    def remove_edge!(u,v=nil)    raise NotImplementedError; end
-            
-    # Return the array of vertices.
-    # 
-    # This method must be implemented by the specific graph class
-    def vertices()              raise NotImplementedError; end
-
-    # Return the array of edges.
-    # 
-    # This method must be implemented by the specific graph class
-    def edges()                 raise NotImplementedError; end
-      
-    # Returns the edge class
-    def edge_class()            raise NotImplementedError; end
-    
-    # Return the chromatic number for this graph
-    # This is currently incomplete and in some cases will be NP-complete
-    # FIXME: Should this even be here? My gut feeling is no...
-    def chromatic_number()      raise NotImplementedError; end
-  end
-end
\ No newline at end of file
diff --git a/lib/puppet/external/gratr/import.rb b/lib/puppet/external/gratr/import.rb
deleted file mode 100644
index d3678d8b6..000000000
--- a/lib/puppet/external/gratr/import.rb
+++ /dev/null
@@ -1,44 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr'
-
-# Pull all GRATR classes up into the current namespace
-Edge                  = GRATR::Edge
-UndirectedEdge        = GRATR::UndirectedEdge
-MultiEdge             = GRATR::MultiEdge
-MultiUndirectedEdge   = GRATR::MultiUndirectedEdge
-Graph                 = GRATR::Graph
-Digraph               = GRATR::Digraph
-DirectedGraph         = GRATR::DirectedGraph
-DirectedPseudoGraph   = GRATR::DirectedPseudoGraph
-DirectedMultiGraph    = GRATR::DirectedMultiGraph
-UndirectedGraph       = GRATR::UndirectedGraph
-UndirectedPseudoGraph = GRATR::UndirectedPseudoGraph
-UndirectedMultiGraph  = GRATR::UndirectedMultiGraph
-Complete              = GRATR::Complete
diff --git a/lib/puppet/external/gratr/labels.rb b/lib/puppet/external/gratr/labels.rb
deleted file mode 100644
index 7e53df404..000000000
--- a/lib/puppet/external/gratr/labels.rb
+++ /dev/null
@@ -1,90 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-module GRATR
-  module Labels
-    # Return a label for an edge or vertex
-    def [](u) (u.kind_of? GRATR::Edge) ? edge_label(u) : vertex_label(u); end
-
-    # Set a label for an edge or vertex
-    def []= (u, value) (u.kind_of? GRATR::Edge) ? edge_label_set(u,value) : vertex_label_set(u, value); end
-
-    # Delete a label entirely
-    def delete_label(u) (u.kind_of? GRATR::Edge) ? edge_label_delete(u) : vertex_label_delete(u); end
-
-    # Get the label for an edge
-    def vertex_label(v)        vertex_label_dict[v]; end
-
-    # Set the label for an edge
-    def vertex_label_set(v, l) vertex_label_dict[v] = l; self; end
-
-    # Get the label for an edge
-    def edge_label(u,v=nil,n=nil)
-      u = edge_convert(u,v,n)
-      edge_label_dict[u]
-    end
-
-    # Set the label for an edge
-    def edge_label_set(u, v=nil, l=nil, n=nil) 
-      u.kind_of?(GRATR::Edge) ? l = v : u = edge_convert(u,v,n)
-      edge_label_dict[u] = l; self
-    end
-
-    # Delete all graph labels
-    def clear_all_labels()  @vertex_labels = {}; @edge_labels = {}; end
-
-    # Delete an edge label
-    def edge_label_delete(u, v=nil, n=nil)
-      u = edge_convert(u,v,n)
-      edge_label_dict.delete(u)
-    end
-
-    # Delete a vertex label
-    def vertex_label_delete(v) vertex_label_dict.delete(v); end
-
-   protected
-
-    def vertex_label_dict() @vertex_labels ||= {}; end
-    def edge_label_dict()   @edge_labels   ||= {}; end
-
-    # A generic cost function. It either calls the weight function with and edge
-    # constructed from the two nodes, or calls the [] operator of the label
-    # when given a value. If no weight value is specified, the label itself is
-    # treated as the cost value.
-    #
-    # Note: This function will not work for Pseudo or Multi graphs at present. 
-    def cost(u,v=nil,weight=nil)
-      u.kind_of?(Edge) ? weight = v : u = edge_class[u,v] 
-      case weight
-        when Proc : weight.call(u)
-        when nil  : self[u]
-        else        self[u][weight]
-      end
-    end
-
-  end
-end
diff --git a/lib/puppet/external/gratr/maximum_flow.rb b/lib/puppet/external/gratr/maximum_flow.rb
deleted file mode 100644
index 7b3ef9b2f..000000000
--- a/lib/puppet/external/gratr/maximum_flow.rb
+++ /dev/null
@@ -1,64 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-module GRATR
-
-  module Graph
-
-    module MaximumFlow
-
-      # Maximum flow, it returns an array with the maximum flow and a hash of flow per edge
-      # Currently a highly inefficient implementation, FIXME, This should use Goldberg and Tarjan's method.
-      def maximum_flow(s, t, capacity = nil, zero = 0)
-        flow       = Hash.new(zero)
-        available  = Hash.new(zero)
-        total      = zero
-        edges.each {|e| available[e] = cost(e,capacity)} 
-        adj_positive = Proc.new do |u|
-          adjacent(u).select {|r| available[edge_class[u,r]] > zero}
-        end
-        while (tree = bfs_tree_from_vertex(start))[t]
-          route = [t]
-          while route[-1] != s
-            route << tree[route[route[-1]]]
-            raise ArgumentError, "No route from #{s} to #{t} possible"
-          end; route.reverse
-          amt   = route.map {|e| available[e]}.min
-          route.each do |e|
-            flow[e]      += amt
-            available[e] -= amt
-          end
-          total += amt
-        end
-        
-        [total, flow]
-      end
-
-    end # MaximumFlow
-  end # Graph
-end # GRATR
\ No newline at end of file
diff --git a/lib/puppet/external/gratr/search.rb b/lib/puppet/external/gratr/search.rb
deleted file mode 100644
index 3206ec5d9..000000000
--- a/lib/puppet/external/gratr/search.rb
+++ /dev/null
@@ -1,409 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-module GRATR
-  module Graph
-    module Search
-
-      # Options are mostly callbacks passed in as a hash. 
-      # The following are valid, anything else is ignored
-      # :enter_vertex  => Proc  Called upon entry of a vertex
-      # :exit_vertex   => Proc  Called upon exit of a vertex
-      # :root_vertex   => Proc  Called when a vertex the a root of a tree
-      # :start_vertex  => Proc  Called for the first vertex of the search
-      # :examine_edge  => Proc  Called when an edge is examined
-      # :tree_edge     => Proc  Called when the edge is a member of the tree
-      # :back_edge     => Proc  Called when the edge is a back edge
-      # :forward_edge  => Proc  Called when the edge is a forward edge
-      # :adjacent      => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms
-      #
-      # :start         => Vertex  Specifies the vertex to start search from
-      #
-      # If a &block is specified it defaults to :enter_vertex
-      #
-      # Returns the list of vertexes as reached by enter_vertex
-      # This allows for calls like, g.bfs.each {|v| ...}
-      #
-      # Can also be called like bfs_examine_edge {|e| ... } or
-      # dfs_back_edge {|e| ... } for any of the callbacks
-      #
-      # A full example usage is as follows:
-      #
-      #  ev = Proc.new {|x| puts "Enter Vertex #{x}"}
-      #  xv = Proc.new {|x| puts "Exit Vertex #{x}"}
-      #  sv = Proc.new {|x| puts "Start Vertex #{x}"}
-      #  ee = Proc.new {|x| puts "Examine Edge #{x}"}
-      #  te = Proc.new {|x| puts "Tree Edge #{x}"}
-      #  be = Proc.new {|x| puts "Back Edge #{x}"}
-      #  fe = Proc.new {|x| puts "Forward Edge #{x}"}
-      #  Digraph[1,2,2,3,3,4].dfs({ 
-      #        :enter_vertex => ev, 
-      #        :exit_vertex  => xv,
-      #        :start_vertex => sv,
-      #        :examine_edge => ee,
-      #        :tree_edge    => te,
-      #        :back_edge    => be,
-      #        :forward_edge => fe })
-      # 
-      # Which outputs:
-      #
-      # Start Vertex 1
-      # Enter Vertex 1
-      # Examine Edge (1=2)
-      # Tree Edge (1=2)
-      # Enter Vertex 2
-      # Examine Edge (2=3)
-      # Tree Edge (2=3)
-      # Enter Vertex 3
-      # Examine Edge (3=4)
-      # Tree Edge (3=4)
-      # Enter Vertex 4
-      # Examine Edge (1=4)
-      # Back Edge (1=4)
-      # Exit Vertex 4
-      # Exit Vertex 3
-      # Exit Vertex 2
-      # Exit Vertex 1
-      def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end
-
-      # See options for bfs method
-      def dfs(options={}, &block) gratr_search_helper(:pop,   options, &block); end
-      
-      # Routine to compute a spanning forest for the given search method
-      # Returns two values, first is a hash of predecessors and second an array of root nodes
-      def spanning_forest(start, routine)
-        predecessor = {}
-        roots       = []
-        te = Proc.new {|e| predecessor[e.target] = e.source}
-        rv = Proc.new {|v| roots << v}
-        method(routine).call :start => start, :tree_edge => te, :root_vertex => rv
-        [predecessor, roots]
-      end
-      
-      # Return the dfs spanning forest for the given start node, see spanning_forest
-      def dfs_spanning_forest(start) spanning_forest(start, :dfs); end
-      
-      # Return the bfs spanning forest for the given start node, see spanning_forest
-      def bfs_spanning_forest(start) spanning_forest(start, :bfs); end
-      
-      # Returns a hash of predecessors in a tree rooted at the start node. If this is a connected graph
-      # then it will be a spanning tree and contain all vertices. An easier way to tell if it's a spanning tree is to
-      # use a spanning_forest call and check if there is a single root node.
-      def tree_from_vertex(start, routine)
-        predecessor={}
-        correct_tree = false
-        te = Proc.new {|e| predecessor[e.target] = e.source if correct_tree}
-        rv = Proc.new {|v| correct_tree = (v == start)}
-        method(routine).call :start => start, :tree_edge => te, :root_vertex => rv
-        predecessor       
-      end
-      
-      # Returns a hash of predecessors for the depth first search tree rooted at the given node
-      def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end
-      
-      # Returns a hash of predecessors for the depth first search tree rooted at the given node
-      def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end
-       
-      # An inner class used for greater efficiency in lexicograph_bfs
-      #
-      # Original desgn taken from Golumbic's, "Algorithmic Graph Theory and
-      # Perfect Graphs" pg, 87-89
-      class LexicographicQueue
-      
-        # Called with the initial values (array)
-        def initialize(values)
-          @node = Struct.new(:back, :forward, :data)
-          @node.class_eval { def hash() @hash; end; @@cnt=0 }
-          @set  = {}
-          @tail = @node.new(nil, nil, Array.new(values))
-          @tail.instance_eval { @hash = (@@cnt+=1) }
-          values.each {|a| @set[a] = @tail}        
-        end
-     
-        # Pop an entry with maximum lexical value from queue 
-        def pop()
-          return nil unless @tail
-          value = @tail[:data].pop
-          @tail = @tail[:forward] while @tail and @tail[:data].size == 0
-          @set.delete(value); value
-        end
-      
-        # Increase lexical value of given values (array)
-        def add_lexeme(values)
-          fix = {}
-          values.select {|v| @set[v]}.each do |w|
-            sw = @set[w]
-            if fix[sw]
-              s_prime        = sw[:back]
-            else 
-              s_prime             = @node.new(sw[:back], sw, [])
-              s_prime.instance_eval { @hash = (@@cnt+=1) }
-              @tail = s_prime if @tail == sw
-              sw[:back][:forward] = s_prime if sw[:back]
-              sw[:back]           = s_prime
-              fix[sw]             = true
-            end
-            s_prime[:data] << w
-            sw[:data].delete(w)
-            @set[w] = s_prime
-          end
-          fix.keys.select {|n| n[:data].size == 0}.each do |e|
-            e[:forward][:back] = e[:back] if e[:forward]
-            e[:back][:forward] = e[:forward] if e[:back]
-          end
-        end 
-      
-      end
-    
-      # Lexicographic breadth-first search, the usual queue of vertices
-      # is replaced by a queue of unordered subsets of the vertices,
-      # which is sometimes refined but never reordered.
-      # 
-      # Originally developed by Rose, Tarjan, and Leuker, "Algorithmic
-      # aspects of vertex elimination on graphs", SIAM J. Comput. 5, 266-283
-      # MR53 #12077
-      #
-      # Implementation taken from Golumbic's, "Algorithmic Graph Theory and
-      # Perfect Graphs" pg, 84-90
-      def lexicograph_bfs(&block)
-        lex_q = GRATR::Graph::Search::LexicographicQueue.new(vertices)
-        result = []
-        num_vertices.times do               
-          v = lex_q.pop
-          result.unshift(v)
-          lex_q.add_lexeme(adjacent(v))            
-        end
-        result.each {|r| block.call(r)} if block
-        result
-      end
-
-
-      # A* Heuristic best first search
-      # 
-      # start is the starting vertex for the search
-      #
-      # func is a Proc that when passed a vertex returns the heuristic 
-      #   weight of sending the path through that node. It must always
-      #   be equal to or less than the true cost
-      # 
-      # options are mostly callbacks passed in as a hash, the default block is 
-      # :discover_vertex and weight is assumed to be the label for the Edge.
-      # The following options are valid, anything else is ignored.
-      #
-      # * :weight => can be a Proc, or anything else is accessed using the [] for the
-      #     the label or it defaults to using
-      #     the value stored in the label for the Edge. If it is a Proc it will 
-      #     pass the edge to the proc and use the resulting value.
-      # * :discover_vertex => Proc invoked when a vertex is first discovered
-      #   and is added to the open list.
-      # * :examine_vertex  => Proc invoked when a vertex is popped from the
-      #   queue (i.e., it has the lowest cost on the open list).
-      # * :examine_edge    => Proc invoked on each out-edge of a vertex
-      #   immediately after it is examined.
-      # * :edge_relaxed    => Proc invoked on edge (u,v) if d[u] + w(u,v) < d[v].
-      # * :edge_not_relaxed=> Proc invoked if the edge is not relaxed (see above).
-      # * :black_target    => Proc invoked when a vertex that is on the closed 
-      #     list is "rediscovered" via a more efficient path, and is re-added
-      #     to the OPEN list.
-      # * :finish_vertex    => Proc invoked on a vertex when it is added to the 
-      #     closed list, which happens after all of its out edges have been
-      #     examined. 
-      #
-      # Returns array of nodes in path, or calls block on all nodes, 
-      # upon failure returns nil
-      #
-      # Can also be called like astar_examine_edge {|e| ... } or
-      # astar_edge_relaxed {|e| ... } for any of the callbacks
-      #
-      # The criteria for expanding a vertex on the open list is that it has the
-      # lowest f(v) = g(v) + h(v) value of all vertices on open.
-      #
-      # The time complexity of A* depends on the heuristic. It is exponential 
-      # in the worst case, but is polynomial when the heuristic function h
-      # meets the following condition: |h(x) - h*(x)| < O(log h*(x)) where h*  
-      # is the optimal heuristic, i.e. the exact cost to get from x to the goal.
-      #
-      # Also see: http://en.wikipedia.org/wiki/A-star_search_algorithm
-      #
-      def astar(start, goal, func, options, &block)
-        options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end"
-        options.instance_eval "def handle_edge(sym,u,v) self[sym].call(#{edge_class}[u,v]) if self[sym]; end"
-
-        d = { start => 0 }
-        f = { start => func.call(start) }
-        color = {start => :gray}
-        p = Hash.new {|k| p[k] = k}
-        queue = [start]
-        block.call(start) if block
-        until queue.empty?
-          u = queue.pop
-          options.handle_vertex(:examine_vertex, u)
-          adjacent(u).each do |v|
-            e = edge_class[u,v]
-            options.handle_edge(:examine_edge, u, v)
-            w = cost(e, options[:weight])
-            raise ArgumentError unless w
-            if d[v].nil? or (w + d[u]) < d[v] 
-              options.handle_edge(:edge_relaxed, u, v)
-              d[v] = w + d[u]
-              f[v] = d[v] + func.call(u)
-              p[v] = u
-              unless color[v] == :gray
-                options.handle_vertex(:black_target, v) if color[v] == :black
-                color[v] = :gray 
-                options.handle_vertex(:discover_vertex, v)
-                queue << v 
-                block.call(v) if block
-                return [start]+queue if v == goal
-              end
-            else
-              options.handle_edge(:edge_not_relaxed, u, v)
-            end
-          end # adjacent(u)
-          color[u] = :black
-          options.handle_vertex(:finish_vertex,u)
-        end # queue.empty?
-        nil # failure, on fall through
-      end # astar
-    
-      # Best first has all the same options as astar with func set to h(v) = 0.
-      # There is an additional option zero which should be defined to zero
-      # for the operation '+' on the objects used in the computation of cost.
-      # The parameter zero defaults to 0.
-      def best_first(start, goal, options, zero=0, &block)
-        func = Proc.new {|v| zero}   
-        astar(start, goal, func, options, &block)
-      end
-
-      alias_method :pre_search_method_missing, :method_missing # :nodoc: 
-      def method_missing(sym,*args, &block) # :nodoc:
-        m1=/^dfs_(\w+)$/.match(sym.to_s)
-        dfs((args[0] || {}).merge({m1.captures[0].to_sym => block})) if m1
-        m2=/^bfs_(\w+)$/.match(sym.to_s)
-        bfs((args[0] || {}).merge({m2.captures[0].to_sym => block})) if m2
-        pre_search_method_missing(sym, *args, &block) unless m1 or m2
-      end
-
-     private
-
-      def gratr_search_helper(op, options={}, &block) # :nodoc: 
-        return nil if size == 0
-        result = []
-        # Create options hash that handles callbacks
-        options = {:enter_vertex => block, :start => to_a[0]}.merge(options)
-        options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end"
-        options.instance_eval "def handle_edge(sym,e) self[sym].call(e) if self[sym]; end"
-        # Create waiting list that is a queue or stack depending on op specified.
-        # First entry is the start vertex.
-        waiting = [options[:start]]
-        waiting.instance_eval "def next() #{op.to_s}; end" 
-        # Create color map with all set to unvisited except for start vertex
-        # will be set to waiting
-        color_map = vertices.inject({}) {|a,v| a[v] = :unvisited; a}
-        color_map.merge!(waiting[0] => :waiting)
-        options.handle_vertex(:start_vertex, waiting[0])
-        options.handle_vertex(:root_vertex,  waiting[0])
-        # Perform the actual search until nothing is waiting
-        until waiting.empty?
-          # Loop till the search iterator exhausts the waiting list
-          visited_edges={} # This prevents retraversing edges in undirected graphs
-          until waiting.empty?
-            gratr_search_iteration(options, waiting, color_map, visited_edges, result, op == :pop) 
-          end
-          # Waiting list is exhausted, see if a new root vertex is available
-          u=color_map.detect {|key,value| value == :unvisited}
-          waiting.push(u[0]) if u
-          options.handle_vertex(:root_vertex, u[0]) if u
-        end; result
-      end
-
-      def gratr_search_iteration(options, waiting, color_map, visited_edges, result, recursive=false) # :nodoc:
-        # Get the next waiting vertex in the list
-        u = waiting.next  
-        options.handle_vertex(:enter_vertex,u)
-        result << u
-        # Examine all adjacent outgoing edges, not previously traversed
-        adj_proc = options[:adjacent] || self.method(:adjacent).to_proc
-        adj_proc.call(u,:type => :edges, :direction => :out).reject {|w| visited_edges[w]}.each do |e|
-          e = e.reverse unless directed? or e.source == u # Preserves directionality where required 
-          v = e.target
-          options.handle_edge(:examine_edge, e)
-          visited_edges[e]=true
-          case color_map[v]
-            # If it's unvisited it goes into the waiting list
-            when :unvisited 
-              options.handle_edge(:tree_edge, e)
-              color_map[v] = :waiting
-              waiting.push(v) 
-              # If it's recursive (i.e. dfs) then call self
-              gratr_search_iteration(options, waiting, color_map, visited_edges, result, true) if recursive
-            when :waiting 
-              options.handle_edge(:back_edge, e)
-            else 
-              options.handle_edge(:forward_edge, e)
-          end
-        end
-        # Finished with this vertex
-        options.handle_vertex(:exit_vertex, u)
-        color_map[u] = :visited
-      end
-      
-     public
-      # Topological Sort Iterator
-      #
-      # The topological sort algorithm creates a linear ordering of the vertices
-      # such that if edge (u,v) appears in the graph, then u comes before v in
-      # the ordering. The graph must be a directed acyclic graph (DAG).
-      #
-      # The iterator can also be applied to undirected graph or to a DG graph
-      # which contains a cycle.  In this case, the Iterator does not reach all
-      # vertices.  The implementation of acyclic? and cyclic? uses this fact.
-      #
-      # Can be called with a block as a standard Ruby iterator, or it can
-      # be used directly as it will return the result as an Array
-      def topsort(start = nil, &block)
-        result  = []
-        go      = true 
-        back    = Proc.new {|e| go = false } 
-        push    = Proc.new {|v| result.unshift(v) if go}
-        start   ||= vertices[0]
-        dfs({:exit_vertex => push, :back_edge => back, :start => start})
-        result.each {|v| block.call(v)} if block; result
-      end
-
-      # Returns true if a graph contains no cycles, false otherwise
-      def acyclic?() topsort.size == size; end
-
-      # Returns false if a graph contains no cycles, true otherwise
-      def cyclic?()  not acyclic?; end
-
-      
-    end # Search 
-  end # Graph
-end # GRATR
diff --git a/lib/puppet/external/gratr/strong_components.rb b/lib/puppet/external/gratr/strong_components.rb
deleted file mode 100644
index 796ae16bb..000000000
--- a/lib/puppet/external/gratr/strong_components.rb
+++ /dev/null
@@ -1,127 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'set'
-
-module GRATR
-  module Graph
-    module StrongComponents
-      # strong_components computes the strongly connected components
-      # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan
-      # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on 
-      # Computing, 1(2):146-160, 1972
-      #
-      # The output of the algorithm is an array of components where is 
-      # component is an array of vertices
-      #
-      # A strongly connected component of a directed graph G=(V,E) is a maximal
-      # set of vertices U which is in V such that for every pair of 
-      # vertices u and v in U, we have both a path from u to v 
-      # and path from v to u. That is to say that u and v are reachable 
-      # from each other.
-      #
-      def strong_components
-
-        dfs_num    = 0
-        stack = []; result = []; root = {}; comp = {}; number = {}
-
-        # Enter vertex callback
-        enter = Proc.new do |v| 
-          root[v] = v
-          comp[v] = :new
-          number[v] = (dfs_num += 1)
-          stack.push(v)
-        end
-
-        # Exit vertex callback
-        exit  = Proc.new do |v|
-          adjacent(v).each do |w|
-            if comp[w] == :new
-              root[v] = (number[root[v]] < number[root[w]] ? root[v] : root[w])
-            end
-          end
-          if root[v] == v
-            component = []
-            begin
-              w = stack.pop
-              comp[w] = :assigned
-              component << w
-            end until w == v
-            result << component
-          end
-        end
-
-        # Execute depth first search
-        dfs({:enter_vertex => enter, :exit_vertex => exit}); result
-
-      end # strong_components
-      
-      # Returns a condensation graph of the strongly connected components
-      # Each node is an array of nodes from the original graph
-      def condensation
-        sc  = strong_components
-        cg  = self.class.new
-        map = sc.inject({}) do |a,c| 
-          c.each {|v| a[v] = c }; a
-        end
-        sc.each do |c|
-          c.each do |v|
-            adjacent(v).each {|v| cg.add_edge!(c, map[v]) unless c == map[v]}
-          end
-        end; cg
-      end
-
-      # Compute transitive closure of a graph. That is any node that is reachable
-      # along a path is added as a directed edge.
-      def transitive_closure!
-        cgtc = condensation.gratr_inner_transitive_closure!
-        cgtc.each do |cgv|
-          cgtc.adjacent(cgv).each do |adj|
-            cgv.each do |u| 
-              adj.each {|v| add_edge!(u,v)}  
-            end
-          end
-        end; self
-      end
-
-      # This returns the transitive closure of a graph. The original graph
-      # is not changed.
-      def transitive_closure() self.class.new(self).transitive_closure!; end
-
-     private
-      def gratr_inner_transitive_closure!  # :nodoc:
-        topsort.reverse.each do |u| 
-          adjacent(u).each do |v|
-            adjacent(v).each {|w| add_edge!(u,w) unless edge?(u,w)}
-          end
-        end; self
-      end
-    end # StrongComponens
-    
-  end # Graph
-end # GRATR
diff --git a/lib/puppet/external/gratr/undirected_graph.rb b/lib/puppet/external/gratr/undirected_graph.rb
deleted file mode 100644
index 86963d27c..000000000
--- a/lib/puppet/external/gratr/undirected_graph.rb
+++ /dev/null
@@ -1,153 +0,0 @@
-#--
-# Copyright (c) 2006 Shawn Patrick Garbett
-# Copyright (c) 2002,2004,2005 by Horst Duchene
-# 
-# Redistribution and use in source and binary forms, with or without modification,
-# are permitted provided that the following conditions are met:
-# 
-#     * Redistributions of source code must retain the above copyright notice(s),
-#       this list of conditions and the following disclaimer.
-#     * Redistributions in binary form must reproduce the above copyright notice,
-#       this list of conditions and the following disclaimer in the documentation
-#       and/or other materials provided with the distribution.
-#     * Neither the name of the Shawn Garbett nor the names of its contributors
-#       may be used to endorse or promote products derived from this software
-#       without specific prior written permission.
-# 
-# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
-# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#++
-
-
-require 'puppet/external/gratr/adjacency_graph'
-require 'puppet/external/gratr/search'
-require 'puppet/external/gratr/biconnected'
-require 'puppet/external/gratr/comparability'
-require 'set'
-
-module GRATR
-  class UndirectedGraph
-    include AdjacencyGraph
-    include Graph::Search
-    include Graph::Biconnected
-    include Graph::Comparability
-    
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? GRATR::Graph or p.kind_of? Array)
-      end if self.class == GRATR::UndirectedGraph
-      super(*params)
-    end 
-
-    # UndirectedGraph is by definition undirected, always returns false
-    def directed?()  false; end
-      
-    # Redefine degree (default was sum)
-    def degree(v)    in_degree(v); end
-      
-    # A vertex of an undirected graph is balanced by definition
-    def balanced?(v)  true;  end
-
-    # UndirectedGraph uses UndirectedEdge for the edge class.
-    def edge_class() @parallel_edges ? GRATR::MultiUndirectedEdge : GRATR::UndirectedEdge; end
-
-    def remove_edge!(u, v=nil)
-      unless u.kind_of? GRATR::Edge
-        raise ArgumentError if @parallel_edges 
-        u = edge_class[u,v]
-      end
-      super(u.reverse) unless u.source == u.target
-      super(u)
-    end
-    
-    # A triangulated graph is an undirected perfect graph that every cycle of length greater than
-    # three possesses a chord. They have also been called chordal, rigid circuit, monotone transitive,
-    # and perfect elimination graphs.
-    #
-    # Implementation taken from Golumbic's, "Algorithmic Graph Theory and
-    # Perfect Graphs" pg. 90
-    def triangulated?
-      a = Hash.new {|h,k| h[k]=Set.new}; sigma=lexicograph_bfs
-      inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc}
-      sigma[0..-2].each do |v|
-        x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] }
-        unless x.empty?
-           u = sigma[x.map {|y| inv_sigma[y]}.min]
-           a[u].merge(x - [u])
-        end
-        return false unless a[v].all? {|z| adjacent?(v,z)}
-      end
-      true
-    end
-    
-    def chromatic_number
-      return triangulated_chromatic_number if triangulated?
-      raise NotImplementedError    
-    end
-    
-    # An interval graph can have its vertices into one-to-one
-    # correspondence with a set of intervals F of a linearly ordered
-    # set (like the real line) such that two vertices are connected
-    # by an edge of G if and only if their corresponding intervals
-    # have nonempty intersection.
-    def interval?() triangulated? and complement.comparability?; end
-    
-    # A permutation diagram consists of n points on each of two parallel
-    # lines and n straight line segments matchin the points. The intersection
-    # graph of the line segments is called a permutation graph.
-    def permutation?() comparability? and complement.comparability?; end
-    
-    # An undirected graph is defined to be split if there is a partition
-    # V = S + K of its vertex set into a stable set S and a complete set K.    
-    def split?() triangulated? and complement.triangulated?; end
-    
-   private
-   # Implementation taken from Golumbic's, "Algorithmic Graph Theory and
-   # Perfect Graphs" pg. 99
-    def triangulated_chromatic_number
-      chi = 1; s= Hash.new {|h,k| h[k]=0}
-      sigma=lexicograph_bfs
-      inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc}
-      sigma.each do |v|
-        x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] }
-        unless x.empty?
-          u = sigma[x.map {|y| inv_sigma[y]}.min]
-          s[u] = [s[u], x.size-1].max
-          chi = [chi, x.size+1].max if s[v] < x.size
-        end
-      end; chi
-    end
-   
-  end # UndirectedGraph
-
-  # This is a UndirectedGraph that allows for parallel edges, but does not
-  # allow loops
-  class UndirectedPseudoGraph < UndirectedGraph
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? Graph or p.kind_of? Array)
-      end
-      super(:parallel_edges, *params)
-    end 
-  end
-
-  # This is a UndirectedGraph that allows for parallel edges and loops
-  class UndirectedMultiGraph < UndirectedGraph
-    def initialize(*params)
-      raise ArgumentError if params.any? do |p| 
-       !(p.kind_of? Graph or p.kind_of? Array)
-      end
-      super(:parallel_edges, :loops, *params)
-    end 
-  end
-
-
-end # GRATR
diff --git a/lib/puppet/external/nagios.rb b/lib/puppet/external/nagios.rb
new file mode 100755
index 000000000..78459fcb6
--- /dev/null
+++ b/lib/puppet/external/nagios.rb
@@ -0,0 +1,50 @@
+#!/usr/local/bin/ruby -w
+
+#--------------------
+# A script to retrieve hosts from ldap and create an importable
+# cfservd file from them
+#
+# $Id: nagios.rb,v 1.3 2004/06/09 20:32:46 luke Exp $
+
+require 'digest/md5'
+#require 'ldap'
+require 'puppet/external/nagios/parser.rb'
+require 'puppet/external/nagios/base.rb'
+
+module Nagios
+    NAGIOSVERSION = '1.1'
+    # yay colors
+    PINK = ""
+    GREEN = ""
+    YELLOW = ""
+    SLATE = ""
+    ORANGE = ""
+    BLUE = ""
+    NOCOLOR = ""
+    RESET = ""
+
+    def self.version
+        NAGIOSVERSION
+    end
+
+	class Config
+		def Config.import(config)
+
+			text = String.new
+
+			File.open(config) { |file|
+				file.each { |line|
+					text += line
+				}
+			}
+			parser = Nagios::Parser.new
+			return parser.parse(text)
+		end
+		
+		def Config.each
+			Nagios::Object.objects.each { |object|
+				yield object
+			}
+		end
+	end
+end
diff --git a/lib/puppet/external/nagios/base.rb b/lib/puppet/external/nagios/base.rb
new file mode 100755
index 000000000..efc3982b4
--- /dev/null
+++ b/lib/puppet/external/nagios/base.rb
@@ -0,0 +1,421 @@
+# The base class for all of our Nagios object types.  Everything else
+# is mostly just data.
+class Nagios::Base
+
+    class UnknownNagiosType < RuntimeError # When an unknown type is asked for by name.
+    end
+
+    include Enumerable
+
+    class << self
+        attr_accessor :parameters, :derivatives, :ocs, :name, :att
+        attr_accessor :ldapbase
+
+        attr_writer :namevar
+
+        attr_reader :superior
+    end
+
+    # Attach one class to another.
+    def self.attach(hash)
+        @attach ||= {}
+        hash.each do |n, v| @attach[n] = v end
+    end
+
+    # Convert a parameter to camelcase
+    def self.camelcase(param)
+        param.gsub(/_./) do |match|
+            match.sub(/_/,'').capitalize
+        end
+    end
+
+    # Uncamelcase a parameter.
+    def self.decamelcase(param)
+        param.gsub(/[A-Z]/) do |match|
+            "_" + match.downcase
+        end
+    end
+
+    # Create a new instance of a given class.
+    def self.create(name, args = {})
+        name = name.intern if name.is_a? String
+
+        if @types.include?(name)
+            @types[name].new(args)
+        else
+            raise UnknownNagiosType, "Unknown type %s" % name
+        end
+    end
+
+    # Yield each type in turn.
+    def self.eachtype
+        @types.each do |name, type|
+            yield [name, type]
+        end
+    end
+
+    # Create a mapping.
+    def self.map(hash)
+        @map ||= {}
+        hash.each do |n, v| @map[n] = v end
+    end
+
+    # Return a mapping (or nil) for a param
+    def self.mapping(name)
+        name = name.intern if name.is_a? String
+        if defined? @map
+            @map[name]
+        else
+            nil
+        end
+    end
+
+    # Return the namevar for the canonical name.
+    def self.namevar
+        if defined? @namevar
+            return @namevar
+        else
+            if parameter?(:name)
+                return :name
+            elsif tmp = (self.name.to_s + "_name").intern and parameter?(tmp)
+                @namevar = tmp
+                return @namevar
+            else
+                raise "Type %s has no name var" % self.name
+            end
+        end
+    end
+
+    # Create a new type.
+    def self.newtype(name, &block)
+        name = name.intern if name.is_a? String
+
+        @types ||= {}
+
+        # Create the class, with the correct name.
+        t = Class.new(self)
+        t.name = name
+
+        # Everyone gets this.  There should probably be a better way, and I
+        # should probably hack the attribute system to look things up based on
+        # this "use" setting, but, eh.
+        t.parameters = [:use]
+
+        const_set(name.to_s.capitalize,t)
+
+        # Evaluate the passed block.  This should usually define all of the work.
+        t.class_eval(&block)
+
+        @types[name] = t
+    end
+
+    # Define both the normal case and camelcase method for a parameter
+    def self.paramattr(name)
+        camel = camelcase(name)
+        param = name
+
+        [name, camel].each do |method|
+            define_method(method) do
+                @parameters[param]
+            end
+
+            define_method(method.to_s + "=") do |value|
+                @parameters[param] = value
+            end
+        end
+
+    end
+
+    # Is the specified name a valid parameter?
+    def self.parameter?(name)
+        name = name.intern if name.is_a? String
+        return @parameters.include?(name)
+    end
+
+    # Manually set the namevar
+    def self.setnamevar(name)
+        name = name.intern if name.is_a? String
+        @namevar = name
+    end
+
+    # Set the valid parameters for this class
+    def self.setparameters(*array)
+        @parameters += array
+    end
+
+    # Set the superior ldap object class.  Seems silly to include this
+    # in this class, but, eh.
+    def self.setsuperior(name)
+        @superior = name
+    end
+
+    # Parameters to suppress in output.
+    def self.suppress(name)
+        @suppress ||= []
+        @suppress << name
+    end
+
+    # Whether a given parameter is suppressed.
+    def self.suppress?(name)
+        defined? @suppress and @suppress.include?(name)
+    end
+
+    # Return our name as the string.
+    def self.to_s
+        self.name.to_s
+    end
+
+    # Return a type by name.
+    def self.type(name)
+        name = name.intern if name.is_a? String
+
+        @types[name]
+    end
+
+    # Convenience methods.
+    def [](param)
+        send(param)
+    end
+
+    # Convenience methods.
+    def []=(param,value)
+        send(param.to_s + "=", value)
+    end
+
+    # Iterate across all ofour set parameters.
+    def each
+        @parameters.each { |param,value|
+            yield(param,value)
+        }
+    end
+
+    # Initialize our object, optionally with a list of parameters.
+    def initialize(args = {})
+        @parameters = {}
+
+        args.each { |param,value|
+            self[param] = value
+        }
+    end
+
+    # Handle parameters like attributes.
+    def method_missing(mname, *args)
+        pname = mname.to_s
+        pname.sub!(/=/, '')
+
+        if self.class.parameter?(pname)
+            if pname =~ /A-Z/
+                pname = self.class.decamelcase(pname)
+            end
+            self.class.paramattr(pname)
+
+            # Now access the parameters directly, to make it at least less
+            # likely we'll end up in an infinite recursion.
+            if mname.to_s =~ /=$/
+                @parameters[pname] = *args
+            else
+                return @parameters[mname]
+            end
+        else
+            super
+        end
+    end
+
+    # Retrieve our name, through a bit of redirection.
+    def name
+        send(self.class.namevar)
+    end
+
+    # This is probably a bad idea.
+    def name=(value)
+        send(self.class.namevar.to_s + "=", value)
+    end
+
+    def namevar
+        return (self.type + "_name").intern
+    end
+
+    def parammap(param)
+        unless defined? @map
+            map = {
+                self.namevar => "cn"
+            }
+            if self.class.map
+                map.update(self.class.map)
+            end
+        end
+        if map.include?(param)
+            return map[param]
+        else
+            return "nagios-" + param.id2name.gsub(/_/,'-')
+        end
+    end
+
+    def parent
+        unless defined? self.class.attached
+            puts "Duh, you called parent on an unattached class"
+            return
+        end
+
+        klass,param = self.class.attached
+        unless @parameters.include?(param)
+            puts "Huh, no attachment param"
+            return
+        end
+        klass[@parameters[param]]
+    end
+
+    # okay, this sucks
+    # how do i get my list of ocs?
+    def to_ldif
+        base = self.class.ldapbase
+        str = self.dn + "\n"
+        ocs = Array.new
+        if self.class.ocs
+            # i'm storing an array, so i have to flatten it and stuff
+            kocs = self.class.ocs
+            ocs.push(*kocs)
+        end
+        ocs.push "top"
+        oc = self.class.to_s
+        oc.sub!(/Nagios/,'nagios')
+        oc.sub!(/::/,'')
+        ocs.push oc
+        ocs.each { |oc|
+            str += "objectclass: " + oc + "\n"
+        }
+        @parameters.each { |name,value|
+            if self.class.suppress.include?(name)
+                next
+            end
+            ldapname = self.parammap(name)
+            str += ldapname + ": " + value + "\n"
+        }
+        str += "\n"
+        str
+    end
+
+    def to_s
+        str = "define #{self.type} {\n"
+
+        self.each { |param,value|
+            str += %{\t%-30s %s\n} % [ param,
+                if value.is_a? Array
+                    value.join(",")
+                else
+                    value
+                end
+                ]
+        }
+
+        str += "}\n"
+
+        str
+    end
+
+    # The type of object we are.
+    def type
+        self.class.name
+    end
+
+	# object types
+	newtype :command do
+		setparameters :command_name, :command_line
+	end
+
+	newtype :contact do
+        setparameters :contact_name, :alias, :host_notification_period,
+			:host_notification_commands, :service_notification_period,
+			:service_notification_commands,
+			:email, :pager, :service_notification_options, :host_notification_options
+
+        setsuperior "person"
+	end
+
+	newtype :contactgroup do
+		setparameters :contactgroup_name, :alias, :members
+	end
+
+	newtype :host do
+        setparameters :host_name, :notifications_enabled, :event_handler_enabled,
+			:flap_detection_enabled, :process_perf_data, :retain_status_information,
+			:retain_nonstatus_information, :register, :use, :alias,
+			:address, :check_command, :max_check_attempts, :notification_interval,
+			:notification_period, :notification_options, :checks_enabled,
+            :failure_prediction_enabled, :parents
+
+        setsuperior "person"
+
+        map :address => "ipHostNumber"
+	end
+
+	newtype :hostextinfo do
+		auxiliary = true
+
+        setparameters :host_name, :notes_url, :icon_image, :icon_image_alt, :vrml_image,
+			"2d_coords".intern, "3d_coords".intern
+
+        setnamevar :host_name
+	end
+
+	newtype :hostgroup do
+        setparameters :hostgroup_name, :alias, :contact_groups, :members
+	end
+
+	newtype :hostgroupescalation do
+		auxiliary = true
+        setparameters :hostgroup_name, :first_notification, :last_notification,
+			:contact_groups, :notification_interval
+
+        setnamevar :hostgroup_name
+	end
+
+	newtype :service do
+        attach :host => :host_name
+        setparameters :name, :active_checks_enabled, :passive_checks_enabled,
+            :parallelize_check, :obsess_over_service, :check_freshness,
+            :notifications_enabled, :event_handler_enabled,
+            :flap_detection_enabled, :process_perf_data,
+            :retain_status_information, :retain_nonstatus_information, :register,
+            :is_volatile, :check_period, :max_check_attempts,
+            :normal_check_interval, :retry_check_interval, :contact_groups,
+            :notification_interval, :notification_period, :notification_options,
+            :service_description, :host_name, :freshness_threshold,
+            :check_command
+
+        suppress :host_name
+
+        setnamevar :service_description
+	end
+
+	newtype :servicedependency do
+        auxiliary = true
+        setparameters :host_name, :service_description, :dependent_host_name,
+			:dependent_service_description, :execution_failure_criteria,
+			:notification_failure_criteria
+
+        setnamevar :host_name
+	end
+
+    newtype :serviceescalation do
+        setparameters :host_name, :service_description, :first_notification,
+            :last_notification, :contact_groups, :notification_interval
+
+        setnamevar :host_name
+    end
+
+	newtype :serviceextinfo do
+        auxiliary = true
+
+        setparameters :host_name, :service_description, :icon_image, :icon_image_alt
+
+        setnamevar :host_name
+	end
+
+	newtype :timeperiod do
+        setparameters :timeperiod_name, :alias, :sunday, :monday, :tuesday, :wednesday,
+			:thursday, :friday, :saturday
+	end
+end
+
+# $Id$
diff --git a/lib/puppet/external/nagios/grammar.ry b/lib/puppet/external/nagios/grammar.ry
new file mode 100644
index 000000000..f50818f1a
--- /dev/null
+++ b/lib/puppet/external/nagios/grammar.ry
@@ -0,0 +1,188 @@
+# vim: syntax=ruby
+class Nagios::Parser
+
+token DEFINE NAME STRING PARAM LCURLY RCURLY VALUE RETURN COMMENT INLINECOMMENT
+
+rule
+decls: decl { return val[0] if val[0] }
+	| decls decl {
+		if val[1].nil?
+			result = val[0]
+		else
+			if val[0].nil?
+				result = val[1]
+			else
+				result = [ val[0], val[1] ].flatten
+			end
+		end
+	}
+	;
+
+decl: object { result = [val[0]] }
+	| RETURN { result = nil }
+	| comment
+	;
+	
+comment: COMMENT RETURN { result = nil }
+	;
+
+object: DEFINE NAME LCURLY RETURN vars RCURLY {
+		result = Nagios::Base.create(val[1],val[4])
+	}
+	;
+
+vars: var
+	| vars var {
+		val[1].each {|p,v|
+			val[0][p] = v
+		}
+		result = val[0]
+	}
+	;
+
+var: PARAM VALUE icomment returns { result = {val[0],val[1]} }
+	;
+
+returns:      RETURN
+            | returns RETURN
+            ;
+
+icomment: # nothing
+	| INLINECOMMENT
+	;
+
+end
+
+----inner
+
+def parse(src)
+	@src = src
+
+	# state variables
+	@invar = false
+	@inobject = false
+	@done = false
+
+	@line = 0
+	@yydebug = true
+
+    begin
+        do_parse
+    rescue SyntaxError
+        $stderr.print "#{$!}\n"
+        exit
+    end
+end
+
+# The lexer.  Very simple.
+def token
+	@src.sub!(/\A\n/,'')
+	if $&
+		@line += 1
+		return [ :RETURN, "\n" ]
+	end
+
+	if @done
+		return nil
+	end
+	yytext = String.new
+
+
+	# remove comments from this line
+	@src.sub!(/\A[ \t]*;.*\n/,"\n")
+	if $&
+		return [:INLINECOMMENT, ""]
+	end
+
+	@src.sub!(/\A#.*\n/,"\n")
+	if $&
+		return [:COMMENT, ""]
+	end
+
+	@src.sub!(/#.*/,'')
+
+	if @src.length == 0
+		@done = true
+		return [false, '$']
+	end
+
+	if @invar
+		@src.sub!(/\A[ \t]+/,'')
+		@src.sub!(/\A([^;\n]+)(\n|;)/,'\2')
+		if $1
+			yytext += $1
+		end
+		@invar = false
+		return [:VALUE, yytext]
+	else
+		@src.sub!(/\A[\t ]*(\S+)([\t ]*|$)/,'')
+        if $1
+            yytext = $1
+            case yytext
+            when 'define'
+                #puts "got define"
+                return [:DEFINE, yytext]
+            when '{'
+                #puts "got {"
+                @inobject = true
+                return [:LCURLY, yytext]
+            else
+                unless @inobject
+                    #puts "got type: #{yytext}"
+                    if yytext =~ /\W/
+                        giveback = yytext.dup
+                        giveback.sub!(/^\w+/,'')
+                        #puts "giveback " + giveback
+                        #puts "yytext " + yytext
+                        yytext.sub!(/\W.*$/,'')
+                        #puts "yytext " + yytext
+                        #puts "all [#{giveback} #{yytext} #{orig}]"
+                        @src = giveback + @src
+                    end
+                    return [:NAME, yytext]
+                else
+                    if yytext == '}'
+                        #puts "got closure: #{yytext}"
+                        @inobject = false
+                        return [:RCURLY, '}']
+                    end
+
+                    unless @invar
+                        @invar = true
+                        return [:PARAM, $1]
+                    else
+                    end
+                end
+            end
+        end
+	end
+end
+
+def next_token
+	token
+end
+
+def yydebug
+    1
+end
+
+def yywrap
+    0
+end
+
+def on_error(token, value, vstack )
+	msg = ""
+	unless value.nil?
+		msg = "line #{@line}: syntax error at '#{value}'"
+	else
+		msg = "line #{@line}: syntax error at '#{token}'"
+	end
+	unless @src.size > 0
+		msg = "line #{@line}: Unexpected end of file"
+	end
+	if token == '$end'.intern
+		puts "okay, this is silly"
+	else
+		raise SyntaxError, msg
+	end
+end
diff --git a/lib/puppet/external/nagios/makefile b/lib/puppet/external/nagios/makefile
new file mode 100644
index 000000000..fc14564b7
--- /dev/null
+++ b/lib/puppet/external/nagios/makefile
@@ -0,0 +1,9 @@
+all: parser.rb
+
+debug: parser.rb setdebug
+
+parser.rb: grammar.ry
+	racc -E -oparser.rb grammar.ry
+
+setdebug:
+	perl -pi -e 's{\@yydebug =.*$$}{\@yydebug = true}' parser.rb
diff --git a/lib/puppet/external/nagios/parser.rb b/lib/puppet/external/nagios/parser.rb
new file mode 100644
index 000000000..b7e2c21d8
--- /dev/null
+++ b/lib/puppet/external/nagios/parser.rb
@@ -0,0 +1,816 @@
+#
+# DO NOT MODIFY!!!!
+# This file is automatically generated by racc 1.4.4
+# from racc grammer file "grammar.ry".
+#
+#
+# parser.rb: generated by racc (runtime embedded)
+#
+
+###### racc/parser.rb
+
+unless $".index 'racc/parser.rb'
+$".push 'racc/parser.rb'
+
+self.class.module_eval <<'..end /usr/lib/ruby/1.8/racc/parser.rb modeval..id1306b79176', '/usr/lib/ruby/1.8/racc/parser.rb', 1
+#
+# parser.rb
+#
+# Copyright (c) 1999-2003 Minero Aoki <aamine@loveruby.net>
+#
+# This program is free software.
+# You can distribute/modify this program under the same terms of ruby.
+#
+# As a special exception, when this code is copied by Racc
+# into a Racc output file, you may use that output file
+# without restriction.
+#
+# $raccId: parser.rb,v 1.4 2003/11/03 13:41:47 aamine Exp $
+#
+
+unless defined?(NotImplementedError)
+  NotImplementedError = NotImplementError
+end
+
+module Racc
+  class ParseError < StandardError; end
+end
+unless defined?(::ParseError)
+  ParseError = Racc::ParseError
+end
+
+
+module Racc
+
+  unless defined?(Racc_No_Extentions)
+    Racc_No_Extentions = false
+  end
+
+  class Parser
+
+    Racc_Runtime_Version = '1.4.4'
+    Racc_Runtime_Revision = '$raccRevision: 1.4 $'.split[1]
+
+    Racc_Runtime_Core_Version_R = '1.4.4'
+    Racc_Runtime_Core_Revision_R = '$raccRevision: 1.4 $'.split[1]
+    begin
+      require 'racc/cparse'
+    # Racc_Runtime_Core_Version_C  = (defined in extension)
+      Racc_Runtime_Core_Revision_C = Racc_Runtime_Core_Id_C.split[2]
+      unless new.respond_to?(:_racc_do_parse_c, true)
+        raise LoadError, 'old cparse.so'
+      end
+      if Racc_No_Extentions
+        raise LoadError, 'selecting ruby version of racc runtime core'
+      end
+
+      Racc_Main_Parsing_Routine    = :_racc_do_parse_c
+      Racc_YY_Parse_Method         = :_racc_yyparse_c
+      Racc_Runtime_Core_Version    = Racc_Runtime_Core_Version_C
+      Racc_Runtime_Core_Revision   = Racc_Runtime_Core_Revision_C
+      Racc_Runtime_Type            = 'c'
+    rescue LoadError
+      Racc_Main_Parsing_Routine    = :_racc_do_parse_rb
+      Racc_YY_Parse_Method         = :_racc_yyparse_rb
+      Racc_Runtime_Core_Version    = Racc_Runtime_Core_Version_R
+      Racc_Runtime_Core_Revision   = Racc_Runtime_Core_Revision_R
+      Racc_Runtime_Type            = 'ruby'
+    end
+
+    def Parser.racc_runtime_type
+      Racc_Runtime_Type
+    end
+
+    private
+
+    def _racc_setup
+      @yydebug = false unless self.class::Racc_debug_parser
+      @yydebug = false unless defined?(@yydebug)
+      if @yydebug
+        @racc_debug_out = $stderr unless defined?(@racc_debug_out)
+        @racc_debug_out ||= $stderr
+      end
+      arg = self.class::Racc_arg
+      arg[13] = true if arg.size < 14
+      arg
+    end
+
+    def _racc_init_sysvars
+      @racc_state  = [0]
+      @racc_tstack = []
+      @racc_vstack = []
+
+      @racc_t = nil
+      @racc_val = nil
+
+      @racc_read_next = true
+
+      @racc_user_yyerror = false
+      @racc_error_status = 0
+    end
+
+    ###
+    ### do_parse
+    ###
+
+    def do_parse
+      __send__(Racc_Main_Parsing_Routine, _racc_setup(), false)
+    end
+
+    def next_token
+      raise NotImplementedError, "#{self.class}\#next_token is not defined"
+    end
+
+    def _racc_do_parse_rb( arg, in_debug )
+      action_table, action_check, action_default, action_pointer,
+      goto_table,   goto_check,   goto_default,   goto_pointer,
+      nt_base,      reduce_table, token_table,    shift_n,
+      reduce_n,     use_result,   * = arg
+
+      _racc_init_sysvars
+      tok = act = i = nil
+      nerr = 0
+
+      catch(:racc_end_parse) {
+        while true
+          if i = action_pointer[@racc_state[-1]]
+            if @racc_read_next
+              if @racc_t != 0   # not EOF
+                tok, @racc_val = next_token()
+                unless tok      # EOF
+                  @racc_t = 0
+                else
+                  @racc_t = (token_table[tok] or 1)   # error token
+                end
+                racc_read_token(@racc_t, tok, @racc_val) if @yydebug
+                @racc_read_next = false
+              end
+            end
+            i += @racc_t
+            unless i >= 0 and
+                   act = action_table[i] and
+                   action_check[i] == @racc_state[-1]
+              act = action_default[@racc_state[-1]]
+            end
+          else
+            act = action_default[@racc_state[-1]]
+          end
+          while act = _racc_evalact(act, arg)
+            ;
+          end
+        end
+      }
+    end
+
+    ###
+    ### yyparse
+    ###
+
+    def yyparse( recv, mid )
+      __send__(Racc_YY_Parse_Method, recv, mid, _racc_setup(), true)
+    end
+
+    def _racc_yyparse_rb( recv, mid, arg, c_debug )
+      action_table, action_check, action_default, action_pointer,
+      goto_table,   goto_check,   goto_default,   goto_pointer,
+      nt_base,      reduce_table, token_table,    shift_n,
+      reduce_n,     use_result,   * = arg
+
+      _racc_init_sysvars
+      tok = nil
+      act = nil
+      i = nil
+      nerr = 0
+
+      catch(:racc_end_parse) {
+        until i = action_pointer[@racc_state[-1]]
+          while act = _racc_evalact(action_default[@racc_state[-1]], arg)
+            ;
+          end
+        end
+        recv.__send__(mid) do |tok, val|
+# $stderr.puts "rd: tok=#{tok}, val=#{val}"
+          unless tok
+            @racc_t = 0
+          else
+            @racc_t = (token_table[tok] or 1)   # error token
+          end
+          @racc_val = val
+          @racc_read_next = false
+
+          i += @racc_t
+          unless i >= 0 and
+                 act = action_table[i] and
+                 action_check[i] == @racc_state[-1]
+            act = action_default[@racc_state[-1]]
+# $stderr.puts "02: act=#{act}"
+# $stderr.puts "curstate=#{@racc_state[-1]}"
+          else
+# $stderr.puts "01: act=#{act}"
+          end
+
+          while act = _racc_evalact(act, arg)
+            ;
+          end
+
+          while not (i = action_pointer[@racc_state[-1]]) or
+                not @racc_read_next or
+                @racc_t == 0   # $
+            unless i and i += @racc_t and
+                   i >= 0 and
+                   act = action_table[i] and
+                   action_check[i] == @racc_state[-1]
+              act = action_default[@racc_state[-1]]
+# $stderr.puts "04: act=#{act}"
+            else
+# $stderr.puts "03: act=#{act}"
+            end
+            while act = _racc_evalact(act, arg)
+              ;
+            end
+          end
+        end
+      }
+    end
+
+    ###
+    ### common
+    ###
+
+    def _racc_evalact( act, arg )
+# $stderr.puts "ea: act=#{act}"
+      action_table, action_check, action_default, action_pointer,
+      goto_table,   goto_check,   goto_default,   goto_pointer,
+      nt_base,      reduce_table, token_table,    shift_n,
+      reduce_n,     use_result,   * = arg
+nerr = 0   # tmp
+
+      if act > 0 and act < shift_n
+        #
+        # shift
+        #
+        if @racc_error_status > 0
+          @racc_error_status -= 1 unless @racc_t == 1   # error token
+        end
+        @racc_vstack.push @racc_val
+        @racc_state.push act
+        @racc_read_next = true
+        if @yydebug
+          @racc_tstack.push @racc_t
+          racc_shift @racc_t, @racc_tstack, @racc_vstack
+        end
+
+      elsif act < 0 and act > -reduce_n
+        #
+        # reduce
+        #
+        code = catch(:racc_jump) {
+          @racc_state.push _racc_do_reduce(arg, act)
+          false
+        }
+        if code
+          case code
+          when 1 # yyerror
+            @racc_user_yyerror = true   # user_yyerror
+            return -reduce_n
+          when 2 # yyaccept
+            return shift_n
+          else
+            raise RuntimeError, '[Racc Bug] unknown jump code'
+          end
+        end
+
+      elsif act == shift_n
+        #
+        # accept
+        #
+        racc_accept if @yydebug
+        throw :racc_end_parse, @racc_vstack[0]
+
+      elsif act == -reduce_n
+        #
+        # error
+        #
+        case @racc_error_status
+        when 0
+          unless arg[21]    # user_yyerror
+            nerr += 1
+            on_error @racc_t, @racc_val, @racc_vstack
+          end
+        when 3
+          if @racc_t == 0   # is $
+            throw :racc_end_parse, nil
+          end
+          @racc_read_next = true
+        end
+        @racc_user_yyerror = false
+        @racc_error_status = 3
+        while true
+          if i = action_pointer[@racc_state[-1]]
+            i += 1   # error token
+            if  i >= 0 and
+                (act = action_table[i]) and
+                action_check[i] == @racc_state[-1]
+              break
+            end
+          end
+
+          throw :racc_end_parse, nil if @racc_state.size <= 1
+          @racc_state.pop
+          @racc_vstack.pop
+          if @yydebug
+            @racc_tstack.pop
+            racc_e_pop @racc_state, @racc_tstack, @racc_vstack
+          end
+        end
+        return act
+
+      else
+        raise RuntimeError, "[Racc Bug] unknown action #{act.inspect}"
+      end
+
+      racc_next_state(@racc_state[-1], @racc_state) if @yydebug
+
+      nil
+    end
+
+    def _racc_do_reduce( arg, act )
+      action_table, action_check, action_default, action_pointer,
+      goto_table,   goto_check,   goto_default,   goto_pointer,
+      nt_base,      reduce_table, token_table,    shift_n,
+      reduce_n,     use_result,   * = arg
+      state = @racc_state
+      vstack = @racc_vstack
+      tstack = @racc_tstack
+
+      i = act * -3
+      len       = reduce_table[i]
+      reduce_to = reduce_table[i+1]
+      method_id = reduce_table[i+2]
+      void_array = []
+
+      tmp_t = tstack[-len, len] if @yydebug
+      tmp_v = vstack[-len, len]
+      tstack[-len, len] = void_array if @yydebug
+      vstack[-len, len] = void_array
+      state[-len, len]  = void_array
+
+      # tstack must be updated AFTER method call
+      if use_result
+        vstack.push __send__(method_id, tmp_v, vstack, tmp_v[0])
+      else
+        vstack.push __send__(method_id, tmp_v, vstack)
+      end
+      tstack.push reduce_to
+
+      racc_reduce(tmp_t, reduce_to, tstack, vstack) if @yydebug
+
+      k1 = reduce_to - nt_base
+      if i = goto_pointer[k1]
+        i += state[-1]
+        if i >= 0 and (curstate = goto_table[i]) and goto_check[i] == k1
+          return curstate
+        end
+      end
+      goto_default[k1]
+    end
+
+    def on_error( t, val, vstack )
+      raise ParseError, sprintf("\nparse error on value %s (%s)",
+                                val.inspect, token_to_str(t) || '?')
+    end
+
+    def yyerror
+      throw :racc_jump, 1
+    end
+
+    def yyaccept
+      throw :racc_jump, 2
+    end
+
+    def yyerrok
+      @racc_error_status = 0
+    end
+
+    #
+    # for debugging output
+    #
+
+    def racc_read_token( t, tok, val )
+      @racc_debug_out.print 'read    '
+      @racc_debug_out.print tok.inspect, '(', racc_token2str(t), ') '
+      @racc_debug_out.puts val.inspect
+      @racc_debug_out.puts
+    end
+
+    def racc_shift( tok, tstack, vstack )
+      @racc_debug_out.puts "shift   #{racc_token2str tok}"
+      racc_print_stacks tstack, vstack
+      @racc_debug_out.puts
+    end
+
+    def racc_reduce( toks, sim, tstack, vstack )
+      out = @racc_debug_out
+      out.print 'reduce '
+      if toks.empty?
+        out.print ' <none>'
+      else
+        toks.each {|t| out.print ' ', racc_token2str(t) }
+      end
+      out.puts " --> #{racc_token2str(sim)}"
+          
+      racc_print_stacks tstack, vstack
+      @racc_debug_out.puts
+    end
+
+    def racc_accept
+      @racc_debug_out.puts 'accept'
+      @racc_debug_out.puts
+    end
+
+    def racc_e_pop( state, tstack, vstack )
+      @racc_debug_out.puts 'error recovering mode: pop token'
+      racc_print_states state
+      racc_print_stacks tstack, vstack
+      @racc_debug_out.puts
+    end
+
+    def racc_next_state( curstate, state )
+      @racc_debug_out.puts  "goto    #{curstate}"
+      racc_print_states state
+      @racc_debug_out.puts
+    end
+
+    def racc_print_stacks( t, v )
+      out = @racc_debug_out
+      out.print '        ['
+      t.each_index do |i|
+        out.print ' (', racc_token2str(t[i]), ' ', v[i].inspect, ')'
+      end
+      out.puts ' ]'
+    end
+
+    def racc_print_states( s )
+      out = @racc_debug_out
+      out.print '        ['
+      s.each {|st| out.print ' ', st }
+      out.puts ' ]'
+    end
+
+    def racc_token2str( tok )
+      self.class::Racc_token_to_s_table[tok] or
+          raise RuntimeError, "[Racc Bug] can't convert token #{tok} to string"
+    end
+
+    def token_to_str( t )
+      self.class::Racc_token_to_s_table[t]
+    end
+
+  end
+
+end
+..end /usr/lib/ruby/1.8/racc/parser.rb modeval..id1306b79176
+end   # end of racc/parser.rb
+
+
+module Nagios
+
+  class Parser < Racc::Parser
+
+module_eval <<'..end grammar.ry modeval..id458299781d', 'grammar.ry', 57
+
+def parse(src)
+	@src = src
+
+	# state variables
+	@invar = false
+	@inobject = false
+	@done = false
+
+	@line = 0
+	@yydebug = true
+
+    begin
+        do_parse
+    rescue SyntaxError
+        $stderr.print "#{$!}\n"
+        exit
+    end
+end
+
+# The lexer.  Very simple.
+def token
+	@src.sub!(/\A\n/,'')
+	if $&
+		@line += 1
+		return [ :RETURN, "\n" ]
+	end
+
+	if @done
+		return nil
+	end
+	yytext = String.new
+
+
+	# remove comments from this line
+	@src.sub!(/\A[ \t]*;.*\n/,"\n")
+	if $&
+		return [:INLINECOMMENT, ""]
+	end
+
+	@src.sub!(/\A#.*\n/,"\n")
+	if $&
+		return [:COMMENT, ""]
+	end
+
+	@src.sub!(/#.*/,'')
+
+	if @src.length == 0
+		@done = true
+		return [false, '$']
+	end
+
+	if @invar
+		@src.sub!(/\A[ \t]+/,'')
+		@src.sub!(/\A([^;\n]+)(\n|;)/,'\2')
+		if $1
+			yytext += $1
+		end
+		@invar = false
+		return [:VALUE, yytext]
+	else
+		@src.sub!(/\A[\t ]*(\S+)([\t ]*|$)/,'')
+        if $1
+            yytext = $1
+            case yytext
+            when 'define'
+                #puts "got define"
+                return [:DEFINE, yytext]
+            when '{'
+                #puts "got {"
+                @inobject = true
+                return [:LCURLY, yytext]
+            else
+                unless @inobject
+                    #puts "got type: #{yytext}"
+                    if yytext =~ /\W/
+                        giveback = yytext.dup
+                        giveback.sub!(/^\w+/,'')
+                        #puts "giveback " + giveback
+                        #puts "yytext " + yytext
+                        yytext.sub!(/\W.*$/,'')
+                        #puts "yytext " + yytext
+                        #puts "all [#{giveback} #{yytext} #{orig}]"
+                        @src = giveback + @src
+                    end
+                    return [:NAME, yytext]
+                else
+                    if yytext == '}'
+                        #puts "got closure: #{yytext}"
+                        @inobject = false
+                        return [:RCURLY, '}']
+                    end
+
+                    unless @invar
+                        @invar = true
+                        return [:PARAM, $1]
+                    else
+                    end
+                end
+            end
+        end
+	end
+end
+
+def next_token
+	token
+end
+
+def yydebug
+    1
+end
+
+def yywrap
+    0
+end
+
+def on_error(token, value, vstack )
+	msg = ""
+	unless value.nil?
+		msg = "line #{@line}: syntax error at '#{value}'"
+	else
+		msg = "line #{@line}: syntax error at '#{token}'"
+	end
+	unless @src.size > 0
+		msg = "line #{@line}: Unexpected end of file"
+	end
+	if token == '$end'.intern
+		puts "okay, this is silly"
+	else
+		raise SyntaxError, msg
+	end
+end
+..end grammar.ry modeval..id458299781d
+
+##### racc 1.4.4 generates ###
+
+racc_reduce_table = [
+ 0, 0, :racc_error,
+ 1, 13, :_reduce_1,
+ 2, 13, :_reduce_2,
+ 1, 14, :_reduce_3,
+ 1, 14, :_reduce_4,
+ 1, 14, :_reduce_none,
+ 2, 16, :_reduce_6,
+ 6, 15, :_reduce_7,
+ 1, 17, :_reduce_none,
+ 2, 17, :_reduce_9,
+ 4, 18, :_reduce_10,
+ 1, 20, :_reduce_none,
+ 2, 20, :_reduce_none,
+ 0, 19, :_reduce_none,
+ 1, 19, :_reduce_none ]
+
+racc_reduce_n = 15
+
+racc_shift_n = 26
+
+racc_action_table = [
+     9,    15,     1,    20,     1,    14,    12,    13,    11,     6,
+     7,     6,     7,    15,    18,     8,    21,    23,    25 ]
+
+racc_action_check = [
+     2,    16,     2,    16,     0,    12,     8,     9,     7,     2,
+     2,     0,     0,    14,    15,     1,    18,    22,    24 ]
+
+racc_action_pointer = [
+     2,    12,     0,   nil,   nil,   nil,   nil,    -1,     0,     7,
+   nil,   nil,    -4,   nil,     8,     6,    -4,   nil,     5,   nil,
+   nil,   nil,     8,   nil,     9,   nil ]
+
+racc_action_default = [
+   -15,   -15,   -15,    -1,    -3,    -5,    -4,   -15,   -15,   -15,
+    -2,    -6,   -15,    26,   -15,   -15,   -15,    -8,   -13,    -9,
+    -7,   -14,   -15,   -11,   -10,   -12 ]
+
+racc_goto_table = [
+    17,     3,    19,    10,     2,    16,    22,    24 ]
+
+racc_goto_check = [
+     6,     2,     6,     2,     1,     5,     7,     8 ]
+
+racc_goto_pointer = [
+   nil,     4,     1,   nil,   nil,    -9,   -14,   -12,   -15 ]
+
+racc_goto_default = [
+   nil,   nil,   nil,     4,     5,   nil,   nil,   nil,   nil ]
+
+racc_token_table = {
+ false => 0,
+ Object.new => 1,
+ :DEFINE => 2,
+ :NAME => 3,
+ :STRING => 4,
+ :PARAM => 5,
+ :LCURLY => 6,
+ :RCURLY => 7,
+ :VALUE => 8,
+ :RETURN => 9,
+ :COMMENT => 10,
+ :INLINECOMMENT => 11 }
+
+racc_use_result_var = true
+
+racc_nt_base = 12
+
+Racc_arg = [
+ racc_action_table,
+ racc_action_check,
+ racc_action_default,
+ racc_action_pointer,
+ racc_goto_table,
+ racc_goto_check,
+ racc_goto_default,
+ racc_goto_pointer,
+ racc_nt_base,
+ racc_reduce_table,
+ racc_token_table,
+ racc_shift_n,
+ racc_reduce_n,
+ racc_use_result_var ]
+
+Racc_token_to_s_table = [
+'$end',
+'error',
+'DEFINE',
+'NAME',
+'STRING',
+'PARAM',
+'LCURLY',
+'RCURLY',
+'VALUE',
+'RETURN',
+'COMMENT',
+'INLINECOMMENT',
+'$start',
+'decls',
+'decl',
+'object',
+'comment',
+'vars',
+'var',
+'icomment',
+'returns']
+
+Racc_debug_parser = false
+
+##### racc system variables end #####
+
+ # reduce 0 omitted
+
+module_eval <<'.,.,', 'grammar.ry', 6
+  def _reduce_1( val, _values, result )
+ return val[0] if val[0]
+   result
+  end
+.,.,
+
+module_eval <<'.,.,', 'grammar.ry', 18
+  def _reduce_2( val, _values, result )
+		if val[1].nil?
+			result = val[0]
+		else
+			if val[0].nil?
+				result = val[1]
+			else
+				result = [ val[0], val[1] ].flatten
+			end
+		end
+   result
+  end
+.,.,
+
+module_eval <<'.,.,', 'grammar.ry', 20
+  def _reduce_3( val, _values, result )
+ result = [val[0]]
+   result
+  end
+.,.,
+
+module_eval <<'.,.,', 'grammar.ry', 21
+  def _reduce_4( val, _values, result )
+ result = nil
+   result
+  end
+.,.,
+
+ # reduce 5 omitted
+
+module_eval <<'.,.,', 'grammar.ry', 25
+  def _reduce_6( val, _values, result )
+ result = nil
+   result
+  end
+.,.,
+
+module_eval <<'.,.,', 'grammar.ry', 31
+  def _reduce_7( val, _values, result )
+		result = Nagios::Base.create(val[1],val[4])
+   result
+  end
+.,.,
+
+ # reduce 8 omitted
+
+module_eval <<'.,.,', 'grammar.ry', 40
+  def _reduce_9( val, _values, result )
+		val[1].each {|p,v|
+			val[0][p] = v
+		}
+		result = val[0]
+   result
+  end
+.,.,
+
+module_eval <<'.,.,', 'grammar.ry', 42
+  def _reduce_10( val, _values, result )
+ result = {val[0],val[1]}
+   result
+  end
+.,.,
+
+ # reduce 11 omitted
+
+ # reduce 12 omitted
+
+ # reduce 13 omitted
+
+ # reduce 14 omitted
+
+ def _reduce_none( val, _values, result )
+  result
+ end
+
+  end   # class Parser
+
+end   # module Nagios
diff --git a/lib/puppet/node/catalog.rb b/lib/puppet/node/catalog.rb
index c9de2019d..9601309d8 100644
--- a/lib/puppet/node/catalog.rb
+++ b/lib/puppet/node/catalog.rb
@@ -1,5 +1,4 @@
 require 'puppet/indirector'
-require 'puppet/external/gratr/digraph'
 
 # This class models a node catalog.  It is the thing
 # meant to be passed from server to client, and it contains all
@@ -212,9 +211,8 @@ class Puppet::Node::Catalog < Puppet::PGraph
         # Create a proc for examining edges, which we'll use to build our tree
         # of TransBuckets and TransObjects.
         bucket = nil
-        edges = proc do |edge|
+        walk(main, :out) do |source, target|
             # The sources are always non-builtins.
-            source, target = edge.source, edge.target
             unless tmp = buckets[source.to_s]
                 if tmp = buckets[source.to_s] = source.to_trans
                     bucket = tmp
@@ -239,11 +237,6 @@ class Puppet::Node::Catalog < Puppet::PGraph
                 end
             end
         end
-        dfs(:start => main, :examine_edge => edges)
-
-        unless main
-            raise Puppet::DevError, "Could not find 'main' class; cannot generate catalog"
-        end
 
         # Retrieve the bucket for the top-level scope and set the appropriate metadata.
         unless result = buckets[main.to_s]
diff --git a/lib/puppet/parser/compile.rb b/lib/puppet/parser/compile.rb
index fdd0cbcf2..f76103a28 100644
--- a/lib/puppet/parser/compile.rb
+++ b/lib/puppet/parser/compile.rb
@@ -1,10 +1,6 @@
 #  Created by Luke A. Kanies on 2007-08-13.
 #  Copyright (c) 2007. All rights reserved.
 
-require 'puppet/external/gratr/digraph'
-require 'puppet/external/gratr/import'
-require 'puppet/external/gratr/dot'
-
 require 'puppet/node'
 require 'puppet/node/catalog'
 require 'puppet/util/errors'
@@ -122,9 +118,12 @@ class Puppet::Parser::Compile
         classes.each do |name|
             # If we can find the class, then make a resource that will evaluate it.
             if klass = scope.findclass(name)
+                found << name and next if class_scope(klass)
+
                 # Create a resource to model this class, and then add it to the list
                 # of resources.
                 resource = Puppet::Parser::Resource.new(:type => "class", :title => klass.classname, :scope => scope, :source => scope.source)
+
                 store_resource(scope, resource)
 
                 # If they've disabled lazy evaluation (which the :include function does),
@@ -417,7 +416,7 @@ class Puppet::Parser::Compile
         @tags = []
 
         # A graph for maintaining scope relationships.
-        @scope_graph = GRATR::Digraph.new
+        @scope_graph = Puppet::SimpleGraph.new
 
         # For maintaining the relationship between scopes and their resources.
         @catalog = Puppet::Node::Catalog.new(@node.name)
diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb
index 49fd21401..54b815b45 100644
--- a/lib/puppet/pgraph.rb
+++ b/lib/puppet/pgraph.rb
@@ -1,10 +1,6 @@
 #  Created by Luke A. Kanies on 2006-11-24.
 #  Copyright (c) 2006. All rights reserved.
 
-require 'puppet/external/gratr/digraph'
-require 'puppet/external/gratr/import'
-require 'puppet/external/gratr/dot'
-
 require 'puppet/relationship'
 require 'puppet/simple_graph'
 
@@ -45,7 +41,7 @@ class Puppet::PGraph < Puppet::SimpleGraph
 
     # Which resources a given resource depends upon.
     def dependents(resource)
-        tree_from_vertex2(resource).keys
+        tree_from_vertex(resource).keys
     end
     
     # Which resources depend upon the given resource.
@@ -58,8 +54,7 @@ class Puppet::PGraph < Puppet::SimpleGraph
         # 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_vertex2(resource, :out).keys
-        #tree_from_vertex2(resource, :in).keys
+        @reversal.tree_from_vertex(resource, :out).keys
     end
     
     # Override this method to use our class instead.
@@ -68,9 +63,9 @@ class Puppet::PGraph < Puppet::SimpleGraph
     end
     
     # Determine all of the leaf nodes below a given vertex.
-    def leaves(vertex, type = :dfs)
-        tree = tree_from_vertex(vertex, type)
-        l = tree.keys.find_all { |c| adjacent(c, :direction => :out).empty? }
+    def leaves(vertex, direction = :out)
+        tree = tree_from_vertex(vertex, direction)
+        l = tree.keys.find_all { |c| adjacent(c, :direction => direction).empty? }
         return l
     end
     
@@ -150,61 +145,14 @@ class Puppet::PGraph < Puppet::SimpleGraph
             remove_vertex!(container)
         end
     end
-    
-    # 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
-
-    # Replace the default method, because we want to throw errors on back edges,
-    # not just skip them.
-    def topsort(start = nil, &block)
-        result  = []
-        go      = true 
-        cycles = []
-        back    = Proc.new { |e|
-            cycles << e
-            go = false
-        }
-        push    = Proc.new { |v| result.unshift(v) if go}
-        start   ||= vertices[0]
-        dfs({:exit_vertex => push, :back_edge => back, :start => start})
-        if block_given?
-            result.each {|v| yield(v) }
-        end
-
-        if cycles.length > 0
-            msg = "Found cycles in the following relationships:"
-            cycles.each { |edge| msg += " %s => %s" % [edge.source, edge.target] }
-            raise Puppet::Error, msg
-        end
-        return result
-    end
-
-    def to_yaml_properties
-        instance_variables
-    end
 
     # A different way of walking a tree, and a much faster way than the
     # one that comes with GRATR.
-    def tree_from_vertex2(start, direction = :out)
+    def tree_from_vertex(start, direction = :out)
         predecessor={}
         walk(start, direction) do |parent, child|
             predecessor[child] = parent
         end
         predecessor       
     end
-
-    # A support method for tree_from_vertex2.  Just walk the tree and pass
-    # the parents and children.
-    def walk(source, direction, &block)
-        adjacent(source, :direction => direction).each do |target|
-            yield source, target
-            walk(target, direction, &block)
-        end
-    end
 end
diff --git a/lib/puppet/provider/mount/parsed.rb b/lib/puppet/provider/mount/parsed.rb
index 20908333d..9bc1cf5a5 100755
--- a/lib/puppet/provider/mount/parsed.rb
+++ b/lib/puppet/provider/mount/parsed.rb
@@ -14,7 +14,7 @@ Puppet::Type.type(:mount).provide(:parsed,
     :filetype => :flat
 ) do
     include Puppet::Provider::Mount
-    confine :exists => fstab
+    #confine :exists => fstab
 
     commands :mountcmd => "mount", :umount => "umount"
 
diff --git a/lib/puppet/provider/naginator.rb b/lib/puppet/provider/naginator.rb
new file mode 100644
index 000000000..8e8a3d65e
--- /dev/null
+++ b/lib/puppet/provider/naginator.rb
@@ -0,0 +1,55 @@
+#  Created by Luke Kanies on 2007-11-27.
+#  Copyright (c) 2007. All rights reserved.
+
+require 'puppet'
+require 'puppet/provider/parsedfile'
+require 'puppet/external/nagios'
+
+# The base class for all Naginator providers.
+class Puppet::Provider::Naginator < Puppet::Provider::ParsedFile
+    # Retrieve the associated class from Nagios::Base.
+    def self.nagios_type
+        unless defined?(@nagios_type) and @nagios_type
+            name = resource_type.name.to_s.sub(/^nagios_/, '')
+            unless @nagios_type = Nagios::Base.type(name.to_sym)
+                raise Puppet::DevError, "Could not find nagios type '%s'" % name
+            end
+
+            # And add our 'ensure' settings, since they aren't a part of
+            # Naginator by default
+            @nagios_type.send(:attr_accessor, :ensure, :target, :on_disk)
+        end
+        @nagios_type
+    end
+
+    def self.parse(text)
+        Nagios::Parser.new.parse(text)
+    end
+
+    def self.to_file(records)
+        header + records.collect { |record| record.to_s }.join("\n")
+    end
+
+    def self.skip_record?(record)
+        false
+    end
+
+    def self.valid_attr?(klass, attr_name)
+        nagios_type.parameters.include?(attr_name)
+    end
+
+    def initialize(resource = nil)
+        if resource.is_a?(Nagios::Base)
+            # We don't use a duplicate here, because some providers (ParsedFile, at least)
+            # use the hash here for later events.
+            @property_hash = resource
+        elsif resource
+            @resource = resource if resource
+            # LAK 2007-05-09: Keep the model stuff around for backward compatibility
+            @model = resource
+            @property_hash = self.class.nagios_type.new
+        else
+            @property_hash = self.class.nagios_type.new
+        end
+    end
+end
diff --git a/lib/puppet/provider/package/pkgdmg.rb b/lib/puppet/provider/package/pkgdmg.rb
index b7601cde9..2020b6b56 100644
--- a/lib/puppet/provider/package/pkgdmg.rb
+++ b/lib/puppet/provider/package/pkgdmg.rb
@@ -87,10 +87,8 @@ Example usage::
 
 **WARNING**: Because I assume files will be downloaded to /tmp, the current
 implementation attempts to delete DMG files if you install directly from the
-file system and not via a URL method.
-"
+file system and not via a URL method."
   
-
     confine :exists => "/Library/Receipts"
     commands :installer => "/usr/sbin/installer"
     commands :hdiutil => "/usr/bin/hdiutil"
diff --git a/lib/puppet/provider/parsedfile.rb b/lib/puppet/provider/parsedfile.rb
index 76654c4f4..b4a4a3b91 100755
--- a/lib/puppet/provider/parsedfile.rb
+++ b/lib/puppet/provider/parsedfile.rb
@@ -180,7 +180,7 @@ class Puppet::Provider::ParsedFile < Puppet::Provider
             matchers = resources.dup
             @records.each do |record|
                 # Skip things like comments and blank lines
-                next if record_type(record[:record_type]).text?
+                next if skip_record?(record)
 
                 if name = record[:name] and resource = resources[name]
                     resource.provider = new(record)
@@ -243,6 +243,12 @@ class Puppet::Provider::ParsedFile < Puppet::Provider
         end
     end
 
+    # Should we skip the record?  Basically, we skip text records.
+    # This is only here so subclasses can override it.
+    def self.skip_record?(record)
+        record_type(record[:record_type]).text?
+    end
+
     # Initialize the object if necessary.
     def self.target_object(target)
         @target_objects[target] ||= filetype.new(target)
diff --git a/lib/puppet/provider/sshkey/parsed.rb b/lib/puppet/provider/sshkey/parsed.rb
index cb1010c5b..6f7d98f56 100755
--- a/lib/puppet/provider/sshkey/parsed.rb
+++ b/lib/puppet/provider/sshkey/parsed.rb
@@ -12,6 +12,8 @@ Puppet::Type.type(:sshkey).provide(:parsed,
     :default_target => known,
     :filetype => :flat
 ) do
+    desc "Parse and generate host-wide known hosts files for SSH."
+
     text_line :comment, :match => /^#/
     text_line :blank, :match => /^\s+/
 
diff --git a/lib/puppet/relationship.rb b/lib/puppet/relationship.rb
index c611928f2..05b7dc39e 100644
--- a/lib/puppet/relationship.rb
+++ b/lib/puppet/relationship.rb
@@ -59,7 +59,11 @@ class Puppet::Relationship
     end
     
     def ref
-        "%s => %s" % [source.ref, target.ref]
+        "%s => %s" % [source, target]
+    end
+
+    def to_s
+        ref
     end
 end
 
diff --git a/lib/puppet/reports/tagmail.rb b/lib/puppet/reports/tagmail.rb
index a2c973f8f..9b3711148 100644
--- a/lib/puppet/reports/tagmail.rb
+++ b/lib/puppet/reports/tagmail.rb
@@ -28,6 +28,10 @@ Puppet::Reports.register_report(:tagmail) do
 
         This will send all messages to ``me@domain.com``, and all messages from
         webservers that are not also from mailservers to ``httpadmins@domain.com``.
+
+        If you are using anti-spam controls, such as grey-listing, on your mail 
+        server you should whitelist the sending email (controlled by ``reportform`` 
+        configuration option) to ensure your email is not discarded as spam.  
         "
 
 
@@ -127,7 +131,14 @@ Puppet::Reports.register_report(:tagmail) do
                     Net::SMTP.start(Puppet[:smtpserver]) do |smtp|
                         reports.each do |emails, messages|
                             Puppet.info "Sending report to %s" % emails.join(", ")
-                            smtp.send_message(messages, Puppet[:reportfrom], *emails)
+                            smtp.open_message_stream(Puppet[:reportfrom], *emails) do |p|
+                              p.puts "From: #{Puppet[:reportfrom]}"
+                              p.puts "Subject: Puppet Report for %s" % self.host
+                              p.puts "To: " + emails.join(", ")
+                              p.puts "Date: " + Time.now.rfc2822
+                              p.puts
+                              p.puts messages
+                            end 
                         end
                     end
                 rescue => detail
diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index c9920e60a..11542ad53 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -1,14 +1,11 @@
 #  Created by Luke A. Kanies on 2007-11-07.
 #  Copyright (c) 2007. All rights reserved.
 
-require 'puppet/external/gratr/dot'
+require 'puppet/external/dot'
 require 'puppet/relationship'
-require 'puppet/external/gratr/search'
 
 # A hopefully-faster graph class to replace the use of GRATR.
 class Puppet::SimpleGraph
-    include GRATR::Graph::Search
-
     # An internal class for handling a vertex's edges.
     class VertexWrapper
         attr_accessor :in, :out, :vertex
@@ -52,6 +49,17 @@ class Puppet::SimpleGraph
             return false
         end
 
+        # Create methods for returning the degree and edges.
+        [:in, :out].each do |direction|
+            define_method("%s_degree" % direction) do
+                @adjacencies[direction].length
+            end
+
+            define_method("%s_edges" % direction) do
+                @adjacencies[direction].values.flatten
+            end
+        end
+
         # The other vertex in the edge.
         def other_vertex(direction, edge)
             case direction
@@ -66,6 +74,10 @@ class Puppet::SimpleGraph
         def remove_edge(direction, edge)
             @adjacencies[direction][other_vertex(direction, edge)].delete(edge)
         end
+
+        def to_s
+            vertex.to_s
+        end
     end
 
     def initialize
@@ -80,7 +92,7 @@ class Puppet::SimpleGraph
         @edges.clear
     end
 
-    # Whether our graph is directed.  Always true.  (Used by the GRATR search lib.)
+    # Whether our graph is directed.  Always true.  Used to produce dot files.
     def directed?
         true
     end
@@ -96,16 +108,47 @@ class Puppet::SimpleGraph
         result
     end
 
-    # Return the size of the graph. Used by GRATR.
+    # Return the size of the graph.
     def size
         @vertices.length
     end
 
-    # Return the graph as an array.  Again, used by GRATR.
+    # Return the graph as an array.
     def to_a
         @vertices.keys
     end
 
+    # Provide a topological sort.
+    def topsort
+        degree = {}
+        zeros = []
+        result = []
+
+        # Collect each of our vertices, with the number of in-edges each has.
+        @vertices.each do |name, wrapper|
+            zeros << wrapper if wrapper.in_degree == 0
+            degree[wrapper.vertex] = wrapper.in_edges
+        end
+
+        # Iterate over each 0-degree vertex, decrementing the degree of
+        # each of its out-edges.
+        while wrapper = zeros.pop do
+            result << wrapper.vertex
+            wrapper.out_edges.each do |edge|
+                degree[edge.target].delete(edge)
+                zeros << @vertices[edge.target] if degree[edge.target].length == 0
+            end
+        end
+
+        # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
+        if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
+            message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
+            raise Puppet::Error, "Found dependency cycles in the following relationships: %s" % message
+        end
+
+        return result
+    end
+
     # Add a new vertex to the graph.
     def add_vertex!(vertex)
         return false if vertex?(vertex)
@@ -195,6 +238,27 @@ class Puppet::SimpleGraph
     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
+
+    def to_yaml_properties
+        instance_variables
+    end
+
+    # Just walk the tree and pass each edge.
+    def walk(source, direction, &block)
+        adjacent(source, :direction => direction).each do |target|
+            yield source, target
+            walk(target, direction, &block)
+        end
+    end
 
     # LAK:FIXME This is just a paste of the GRATR code with slight modifications.
 
diff --git a/lib/puppet/type/cron.rb b/lib/puppet/type/cron.rb
index 17cb1667f..7882745dc 100755
--- a/lib/puppet/type/cron.rb
+++ b/lib/puppet/type/cron.rb
@@ -8,6 +8,13 @@ Puppet::Type.newtype(:cron) do
         fields would result in the command being executed every
         minute.  While the name of the cron job is not part of the actual
         job, it is used by Puppet to store and retrieve it.
+
+        You may specify periodic fields as integers, using the standard cron
+        range syntax (two numbers separated by a hyphen to indicate a range
+        of values), or using the cron step syntax (for example, '*/2' to
+        indicate command execution every other time unit). This type does
+        not yet support the combiantion of these two syntaxes, or lists of
+        ranges.
         
         If you specify a cron job that matches an existing job in every way
         except name, then the jobs will be considered equivalent and the
diff --git a/lib/puppet/type/nagios_command.rb b/lib/puppet/type/nagios_command.rb
new file mode 100644
index 000000000..0d0e11b17
--- /dev/null
+++ b/lib/puppet/type/nagios_command.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :command
diff --git a/lib/puppet/type/nagios_contact.rb b/lib/puppet/type/nagios_contact.rb
new file mode 100644
index 000000000..d5a1f3cba
--- /dev/null
+++ b/lib/puppet/type/nagios_contact.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :contact
diff --git a/lib/puppet/type/nagios_contactgroup.rb b/lib/puppet/type/nagios_contactgroup.rb
new file mode 100644
index 000000000..b8f14c07b
--- /dev/null
+++ b/lib/puppet/type/nagios_contactgroup.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :contactgroup
diff --git a/lib/puppet/type/nagios_host.rb b/lib/puppet/type/nagios_host.rb
new file mode 100644
index 000000000..f2e03f6fb
--- /dev/null
+++ b/lib/puppet/type/nagios_host.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :host
diff --git a/lib/puppet/type/nagios_hostextinfo.rb b/lib/puppet/type/nagios_hostextinfo.rb
new file mode 100644
index 000000000..da8e08dd8
--- /dev/null
+++ b/lib/puppet/type/nagios_hostextinfo.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :hostextinfo
diff --git a/lib/puppet/type/nagios_hostgroup.rb b/lib/puppet/type/nagios_hostgroup.rb
new file mode 100644
index 000000000..e1943beec
--- /dev/null
+++ b/lib/puppet/type/nagios_hostgroup.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :hostgroup
diff --git a/lib/puppet/type/nagios_hostgroupescalation.rb b/lib/puppet/type/nagios_hostgroupescalation.rb
new file mode 100644
index 000000000..21b39f681
--- /dev/null
+++ b/lib/puppet/type/nagios_hostgroupescalation.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :hostgroupescalation
diff --git a/lib/puppet/type/nagios_service.rb b/lib/puppet/type/nagios_service.rb
new file mode 100644
index 000000000..22b987f56
--- /dev/null
+++ b/lib/puppet/type/nagios_service.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :service
diff --git a/lib/puppet/type/nagios_servicedependency.rb b/lib/puppet/type/nagios_servicedependency.rb
new file mode 100644
index 000000000..0e3340c6e
--- /dev/null
+++ b/lib/puppet/type/nagios_servicedependency.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :servicedependency
diff --git a/lib/puppet/type/nagios_serviceescalation.rb b/lib/puppet/type/nagios_serviceescalation.rb
new file mode 100644
index 000000000..cb2af1545
--- /dev/null
+++ b/lib/puppet/type/nagios_serviceescalation.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :serviceescalation
diff --git a/lib/puppet/type/nagios_serviceextinfo.rb b/lib/puppet/type/nagios_serviceextinfo.rb
new file mode 100644
index 000000000..6bdc70900
--- /dev/null
+++ b/lib/puppet/type/nagios_serviceextinfo.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :serviceextinfo
diff --git a/lib/puppet/type/nagios_timeperiod.rb b/lib/puppet/type/nagios_timeperiod.rb
new file mode 100644
index 000000000..25a06d3ed
--- /dev/null
+++ b/lib/puppet/type/nagios_timeperiod.rb
@@ -0,0 +1,3 @@
+require 'puppet/util/nagios_maker'
+
+Puppet::Util::NagiosMaker.create_nagios_type :timeperiod
diff --git a/lib/puppet/type/package.rb b/lib/puppet/type/package.rb
index 616362206..9173eaa1c 100644
--- a/lib/puppet/type/package.rb
+++ b/lib/puppet/type/package.rb
@@ -248,7 +248,7 @@ module Puppet
 
         newparam(:responsefile) do
             desc "A file containing any necessary answers to questions asked by
-                the package.  This is currently only used on Solaris.  The
+                the package.  This is currently used on Solaris and Debian.  The
                 value will be validated according to system rules, but it should
                 generally be a fully qualified path."
         end
diff --git a/lib/puppet/type/pfile.rb b/lib/puppet/type/pfile.rb
index f86e1e273..7d928d959 100644
--- a/lib/puppet/type/pfile.rb
+++ b/lib/puppet/type/pfile.rb
@@ -460,7 +460,9 @@ module Puppet
             super
 
             # Get rid of any duplicate slashes, and remove any trailing slashes.
-            @title = @title.gsub(/\/+/, "/").sub(/\/$/, "")
+            @title = @title.gsub(/\/+/, "/")
+            
+            @title.sub!(/\/$/, "") unless @title == "/"
 
             # Clean out as many references to any file paths as possible.
             # This was the source of many, many bugs.
diff --git a/lib/puppet/type/sshkey.rb b/lib/puppet/type/sshkey.rb
index bf4b0aac8..c2bdd39e3 100755
--- a/lib/puppet/type/sshkey.rb
+++ b/lib/puppet/type/sshkey.rb
@@ -53,14 +53,14 @@ module Puppet
         end
 
         newparam(:name) do
-            desc "The host name."
+            desc "The host name that the key is associated with."
 
             isnamevar
         end
 
         newproperty(:target) do
-            desc "The file in which to store the mount table.  Only used by
-                those providers that write to disk (i.e., not NetInfo)."
+            desc "The file in which to store the ssh key.  Only used by
+                the ``parsed`` provider."
 
             defaultto { if @resource.class.defaultprovider.ancestors.include?(Puppet::Provider::ParsedFile)
                     @resource.class.defaultprovider.default_target
diff --git a/lib/puppet/util/graph.rb b/lib/puppet/util/graph.rb
index 028df5539..a9744578b 100644
--- a/lib/puppet/util/graph.rb
+++ b/lib/puppet/util/graph.rb
@@ -17,20 +17,14 @@ module Puppet::Util::Graph
         self.each do |child|
             unless block_given? and ! yield(child)
                 graph.add_edge!(self, child)
-
-                if graph.cyclic?
-                    raise Puppet::Error, "%s created a cyclic graph" % self
-                end
                 
                 if child.respond_to?(:to_graph)
                     child.to_graph(graph, &block)
                 end
             end
         end
-        
-        if graph.cyclic?
-            raise Puppet::Error, "%s created a cyclic graph" % self
-        end
+
+        # Do a topsort, which will throw an exception if the graph is cyclic.
         
         graph
     end
diff --git a/lib/puppet/util/nagios_maker.rb b/lib/puppet/util/nagios_maker.rb
new file mode 100644
index 000000000..a7aae4e70
--- /dev/null
+++ b/lib/puppet/util/nagios_maker.rb
@@ -0,0 +1,57 @@
+require 'puppet/external/nagios'
+require 'puppet/external/nagios/base'
+require 'puppet/provider/naginator'
+
+module Puppet::Util::NagiosMaker
+    # Create a new nagios type, using all of the parameters
+    # from the parser.
+    def self.create_nagios_type(name)
+        name = name.to_sym
+        full_name = ("nagios_" + name.to_s).to_sym
+
+        raise(Puppet::DevError, "No nagios type for %s" % name) unless nagtype = Nagios::Base.type(name)
+
+        type = Puppet::Type.newtype(full_name) {}
+
+        type.ensurable
+
+        type.newparam(nagtype.namevar, :namevar => true) do
+            desc "The name parameter for Nagios type %s" % nagtype.name
+        end
+
+        # We deduplicate the parameters because it makes sense to allow Naginator to have dupes.
+        nagtype.parameters.uniq.each do |param|
+            next if param == nagtype.namevar
+
+            # We can't turn these parameter names into constants, so at least for now they aren't
+            # supported.
+            next if param.to_s =~ /^[0-9]/
+
+            type.newproperty(param) do
+                desc "Nagios configuration file parameter."
+            end
+        end
+
+        type.newproperty(:target) do
+            desc 'target'
+
+            defaultto do
+                resource.class.defaultprovider.default_target
+            end
+        end
+
+        target = "/etc/nagios/#{full_name.to_s}.cfg"
+        provider = type.provide(:naginator, :parent => Puppet::Provider::Naginator, :default_target => target) {}
+
+        type.desc "The Nagios type #{name.to_s}.  This resource type is autogenerated using the
+            model developed in Naginator_, and all of the Nagios types are generated using the
+            same code and the same library.
+
+            This type generates Nagios configuration statements in Nagios-parseable configuration
+            files.  By default, the statements will be added to ``#{target}``, but
+            you can send them to a different file by setting their ``target`` attribute.
+
+            .. _naginator: http://reductivelabs.com/trac/naginator
+        "
+    end
+end
diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb
index 41835ebc7..252a807ec 100755
--- a/spec/unit/other/pgraph.rb
+++ b/spec/unit/other/pgraph.rb
@@ -144,10 +144,6 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
         splice
     end
 
-    it "should not create a cyclic graph" do
-        @depgraph.should_not be_cyclic
-    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.
@@ -211,35 +207,3 @@ describe Puppet::PGraph, " when splicing the relationship graph" do
         end
     end
 end
-
-describe Puppet::PGraph, " when sorting the graph" do
-    before do
-        @graph = Puppet::PGraph.new
-    end
-
-    def add_edges(hash)
-        hash.each do |a,b|
-            @graph.add_edge!(a, b)
-        end
-    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
-end
diff --git a/spec/unit/parser/compile.rb b/spec/unit/parser/compile.rb
index 2ae99b5fd..092bece0c 100755
--- a/spec/unit/parser/compile.rb
+++ b/spec/unit/parser/compile.rb
@@ -106,7 +106,7 @@ describe Puppet::Parser::Compile, " when evaluating found classes" do
         @class = stub 'class', :classname => "my::class"
         @scope.stubs(:findclass).with("myclass").returns(@class)
 
-        @resource = mock 'resource'
+        @resource = stub 'resource', :ref => 'Class[myclass]'
     end
 
     it "should create a resource for each found class" do
@@ -156,6 +156,19 @@ describe Puppet::Parser::Compile, " when evaluating found classes" do
         @compile.evaluate_classes(%w{myclass}, @scope, false)
     end
 
+    it "should skip classes that have already been evaluated" do
+        @compile.catalog.stubs(:tag)
+
+        @compile.expects(:class_scope).with(@class).returns("something")
+
+        @compile.expects(:store_resource).never
+
+        @resource.expects(:evaluate).never
+
+        Puppet::Parser::Resource.expects(:new).never
+        @compile.evaluate_classes(%w{myclass}, @scope, false)
+    end
+
     it "should return the list of found classes" do
         @compile.catalog.stubs(:tag)
 
diff --git a/spec/unit/ral/types/mount.rb b/spec/unit/ral/types/mount.rb
index 0c4b94177..7d01022b5 100755
--- a/spec/unit/ral/types/mount.rb
+++ b/spec/unit/ral/types/mount.rb
@@ -9,7 +9,7 @@ describe Puppet::Type::Mount do
         Puppet::Type::Mount.provider_feature(:refreshable).methods.should == [:remount]
     end
 
-    it "should have no default value" do
+    it "should have no default value for :ensure" do
         mount = Puppet::Type::Mount.create(:name => "yay")
         mount.should(:ensure).should be_nil
     end
diff --git a/spec/unit/ral/types/nagios.rb b/spec/unit/ral/types/nagios.rb
new file mode 100755
index 000000000..8aca7d401
--- /dev/null
+++ b/spec/unit/ral/types/nagios.rb
@@ -0,0 +1,55 @@
+#!/usr/bin/env ruby
+
+require File.dirname(__FILE__) + '/../../../spec_helper'
+
+require 'puppet/external/nagios'
+
+Nagios::Base.eachtype do |name, nagios_type|
+    puppet_type = Puppet::Type.type("nagios_" + name.to_s)
+
+    describe puppet_type do
+        it "should be defined as a Puppet resource type" do
+            puppet_type.should_not be_nil
+        end
+
+        it "should have documentation" do
+            puppet_type.instance_variable_get("@doc").should_not == ""
+        end
+
+        it "should have %s as its namevar" % nagios_type.namevar do
+            puppet_type.namevar.should == nagios_type.namevar
+        end
+
+        it "should have documentation for its %s parameter" % nagios_type.namevar do
+            puppet_type.attrclass(nagios_type.namevar).instance_variable_get("@doc").should_not be_nil
+        end
+
+        it "should have an ensure property" do
+            puppet_type.should be_validproperty(:ensure)
+        end
+
+        it "should have a target property" do
+            puppet_type.should be_validproperty(:target)
+        end
+
+        it "should have documentation for its target property" do
+            puppet_type.attrclass(:target).instance_variable_get("@doc").should_not be_nil
+        end
+
+        nagios_type.parameters.reject { |param| param == nagios_type.namevar or param.to_s =~ /^[0-9]/ }.each do |param|
+            it "should have a %s property" % param do
+                puppet_type.should be_validproperty(param)
+            end
+
+            it "should have documentation for its %s property" % param do
+                puppet_type.attrclass(param).instance_variable_get("@doc").should_not be_nil
+            end
+        end
+
+        nagios_type.parameters.find_all { |param| param.to_s =~ /^[0-9]/ }.each do |param|
+            it "should have not have a %s property" % param do
+                puppet_type.should_not be_validproperty(:param)
+            end
+        end
+    end
+end
diff --git a/spec/unit/relationship.rb b/spec/unit/relationship.rb
index 5d90a9349..5f96cdf8c 100755
--- a/spec/unit/relationship.rb
+++ b/spec/unit/relationship.rb
@@ -24,7 +24,7 @@ describe Puppet::Relationship do
     end
 
     it "should provide a :ref method that describes the edge" do
-        @edge = Puppet::Relationship.new(stub("a", :ref => "a"), stub("b", :ref => "b"))
+        @edge = Puppet::Relationship.new("a", "b")
         @edge.ref.should == "a => b"
     end
 end
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index 88873663c..061a07458 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -219,6 +219,9 @@ describe Puppet::SimpleGraph, " when reversing graphs" do
     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
@@ -227,3 +230,40 @@ describe Puppet::SimpleGraph, " when reversing graphs" do
         edge.label.should == {:stuff => :awesome}
     end
 end
+
+describe Puppet::SimpleGraph, " 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
+end
diff --git a/spec/unit/util/nagios_maker.rb b/spec/unit/util/nagios_maker.rb
new file mode 100755
index 000000000..b75439400
--- /dev/null
+++ b/spec/unit/util/nagios_maker.rb
@@ -0,0 +1,128 @@
+#!/usr/bin/env ruby
+#
+#  Created by Luke Kanies on 2007-11-18.
+#  Copyright (c) 2007. All rights reserved.
+
+require File.dirname(__FILE__) + '/../../spec_helper'
+
+require 'puppet/util/nagios_maker'
+
+describe Puppet::Util::NagiosMaker do
+    before do
+        @module = Puppet::Util::NagiosMaker
+
+        @nagtype = stub 'nagios type', :parameters => [], :namevar => :name
+        Nagios::Base.stubs(:type).with(:test).returns(@nagtype)
+    end
+
+    it "should be able to create a new nagios type" do
+        @module.should respond_to(:create_nagios_type)
+    end
+
+    it "should fail if it cannot find the named Naginator type" do
+        Nagios::Base.stubs(:type).returns(nil)
+
+        lambda { @module.create_nagios_type(:no_such_type) }.should raise_error(Puppet::DevError)
+    end
+
+    it "should create a new RAL type with the provided name prefixed with 'nagios_'" do
+        type = stub 'type', :newparam => nil, :newproperty => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should mark the created type as ensurable" do
+        type = stub 'type', :newparam => nil, :newproperty => nil, :provide => nil, :desc => nil
+
+        type.expects(:ensurable)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should create a namevar parameter for the nagios type's name parameter" do
+        type = stub 'type', :newproperty => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        type.expects(:newparam).with(:name, :namevar => true)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should create a property for all non-namevar parameters" do
+        type = stub 'type', :newparam => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        @nagtype.stubs(:parameters).returns([:one, :two])
+
+        type.expects(:newproperty).with(:one)
+        type.expects(:newproperty).with(:two)
+        type.expects(:newproperty).with(:target)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should skip parameters that start with integers" do
+        type = stub 'type', :newparam => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        @nagtype.stubs(:parameters).returns(["2dcoords".to_sym, :other])
+
+        type.expects(:newproperty).with(:other)
+        type.expects(:newproperty).with(:target)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should deduplicate the parameter list" do
+        type = stub 'type', :newparam => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        @nagtype.stubs(:parameters).returns([:one, :one])
+
+        type.expects(:newproperty).with(:one)
+        type.expects(:newproperty).with(:target)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+
+    it "should create a target property" do
+        type = stub 'type', :newparam => nil, :ensurable => nil, :provide => nil, :desc => nil
+
+        type.expects(:newproperty).with(:target)
+
+        Puppet::Type.expects(:newtype).with(:nagios_test).returns(type)
+        @module.create_nagios_type(:test)
+    end
+end
+
+describe Puppet::Util::NagiosMaker, " when creating the naginator provider" do
+    before do
+        @module = Puppet::Util::NagiosMaker
+
+        @nagtype = stub 'nagios type', :parameters => [], :namevar => :name
+        Nagios::Base.stubs(:type).with(:test).returns(@nagtype)
+
+        @type = stub 'type', :newparam => nil, :ensurable => nil, :newproperty => nil, :desc => nil
+        Puppet::Type.stubs(:newtype).with(:nagios_test).returns(@type)
+    end
+
+    it "should add a naginator provider" do
+        @type.expects(:provide).with { |name, options| name == :naginator }
+
+        @module.create_nagios_type(:test)
+    end
+
+    it "should set Puppet::Provider::Naginator as the parent class of the provider" do
+        @type.expects(:provide).with { |name, options| options[:parent] == Puppet::Provider::Naginator }
+
+        @module.create_nagios_type(:test)
+    end
+
+    it "should use /etc/nagios/$name.cfg as the default target" do
+        @type.expects(:provide).with { |name, options| options[:default_target] == "/etc/nagios/nagios_test.cfg" }
+
+        @module.create_nagios_type(:test)
+    end
+end
diff --git a/test/ral/providers/package.rb b/test/ral/providers/package.rb
index 90c862178..f2d28d0f0 100755
--- a/test/ral/providers/package.rb
+++ b/test/ral/providers/package.rb
@@ -46,7 +46,7 @@ class TestPackageProvider < Test::Unit::TestCase
         end
         facts = {}
         Facter.to_hash.each do |fact, value|
-            facts[fact.downcase.intern] = value.downcase.intern
+            facts[fact.to_s.downcase.intern] = value.to_s.downcase.intern
         end
         list.find_all { |hash| # First find the matching providers
             hash.include?(:provider) and providers.include?(hash[:provider])
diff --git a/test/ral/types/file.rb b/test/ral/types/file.rb
index a3a0c579a..aa2e63a89 100755
--- a/test/ral/types/file.rb
+++ b/test/ral/types/file.rb
@@ -1817,5 +1817,10 @@ class TestFile < Test::Unit::TestCase
         changes = obj.evaluate
         assert(changes.empty?, "Missing file with no ensure resulted in changes")
     end
+
+    def test_root_dir_is_named_correctly
+        obj = Puppet::Type.newfile(:path => '/', :mode => 0755)
+        assert_equal("/", obj.title, "/ directory was changed to empty string")
+    end
 end