Moving code from external sources into an external/ directory

git-svn-id: https://reductivelabs.com/svn/puppet/trunk@2119 980ebf18-57e1-0310-9a29-db15c13687c0

26 files changed, 3890 insertions, 0 deletions

diff --git a/lib/puppet/external/base64.rb b/lib/puppet/external/base64.rb
new file mode 100755
index 000000000..4030ad358
--- /dev/null
+++ b/lib/puppet/external/base64.rb
@@ -0,0 +1,19 @@
+# a stupid hack class to get rid of all of the warnings but
+# still make the encode/decode methods available
+
+# 1.8.2 has a Base64 class, but 1.8.1 just imports the methods directly
+# into Object
+
+require 'base64'
+
+unless defined? Base64
+    class Base64
+        def Base64.encode64(*args)
+            Object.method(:encode64).call(*args)
+        end
+
+        def Base64.decode64(*args)
+            Object.method(:decode64).call(*args)
+        end
+    end
+end
diff --git a/lib/puppet/external/event-loop.rb b/lib/puppet/external/event-loop.rb
new file mode 100644
index 000000000..476fb0ba3
--- /dev/null
+++ b/lib/puppet/external/event-loop.rb
@@ -0,0 +1 @@
+require "puppet/external/event-loop/event-loop"
diff --git a/lib/puppet/external/event-loop/better-definers.rb b/lib/puppet/external/event-loop/better-definers.rb
new file mode 100644
index 000000000..0af37da62
--- /dev/null
+++ b/lib/puppet/external/event-loop/better-definers.rb
@@ -0,0 +1,367 @@
+## better-definers.rb --- better attribute and method definers
+# Copyright (C) 2005  Daniel Brockman
+
+# This program is free software; you can redistribute it
+# and/or modify it under the terms of the GNU General Public
+# License as published by the Free Software Foundation;
+# either version 2 of the License, or (at your option) any
+# later version.
+
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty
+# of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+# See the GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public
+# License along with this program; if not, write to the Free
+# Software Foundation, 51 Franklin Street, Fifth Floor,
+# Boston, MA 02110-1301, USA.
+
+class Symbol
+  def predicate?
+    to_s.include? "?" end
+  def imperative?
+    to_s.include? "!" end
+  def writer?
+    to_s.include? "=" end
+
+  def punctuated?
+    predicate? or imperative? or writer? end
+  def without_punctuation
+    to_s.delete("?!=").to_sym end
+
+  def predicate
+    without_punctuation.to_s + "?" end
+  def imperative
+    without_punctuation.to_s + "!" end
+  def writer
+    without_punctuation.to_s + "=" end
+end
+
+class Hash
+  def collect! (&block)
+    replace Hash[*collect(&block).flatten]
+  end
+
+  def flatten
+    to_a.flatten
+  end
+end
+
+module Kernel
+  def returning (value)
+    yield value ; value
+  end
+end
+
+class Module
+  def define_hard_aliases (name_pairs)
+    for new_aliases, existing_name in name_pairs do
+      new_aliases.kind_of? Array or new_aliases = [new_aliases]
+      for new_alias in new_aliases do
+        alias_method(new_alias, existing_name)
+      end
+    end
+  end
+
+  def define_soft_aliases (name_pairs)
+    for new_aliases, existing_name in name_pairs do
+      new_aliases.kind_of? Array or new_aliases = [new_aliases]
+      for new_alias in new_aliases do
+        class_eval %{def #{new_alias}(*args, &block)
+                       #{existing_name}(*args, &block) end}
+      end
+    end
+  end
+
+  define_soft_aliases \
+    :define_hard_alias => :define_hard_aliases,
+    :define_soft_alias => :define_soft_aliases
+
+  # This method lets you define predicates like :foo?,
+  # which will be defined to return the value of @foo.
+  def define_readers (*names)
+    for name in names.map { |x| x.to_sym } do
+      if name.punctuated?
+        # There's no way to define an efficient reader whose
+        # name is different from the instance variable.
+        class_eval %{def #{name} ; @#{name.without_punctuation} end}
+      else
+        # Use `attr_reader' to define an efficient method.
+        attr_reader(name)
+      end
+    end
+  end
+
+  def writer_defined? (name)
+    method_defined? name.to_sym.writer
+  end
+
+  # If you pass a predicate symbol :foo? to this method, it'll first
+  # define a regular writer method :foo, without a question mark.
+  # Then it'll define an imperative writer method :foo! as a shorthand
+  # for setting the property to true.
+  def define_writers (*names, &body)
+    for name in names.map { |x| x.to_sym } do
+      if block_given?
+        define_method(name.writer, &body)
+      else
+        attr_writer(name.without_punctuation)
+      end
+      if name.predicate?
+        class_eval %{def #{name.imperative}
+                       self.#{name.writer} true end}
+      end
+    end
+  end
+
+  define_soft_aliases \
+    :define_reader => :define_readers,
+    :define_writer => :define_writers
+
+  # We don't need a singular alias for `define_accessors',
+  # because it always defines at least two methods.
+
+  def define_accessors (*names)
+    define_readers(*names)
+    define_writers(*names)
+  end
+
+  def define_opposite_readers (name_pairs)
+    name_pairs.collect! { |k, v| [k.to_sym, v.to_sym] }
+    for opposite_name, name in name_pairs do
+      define_reader(name) unless method_defined? name
+      class_eval %{def #{opposite_name} ; not #{name} end}
+    end
+  end
+
+  def define_opposite_writers (name_pairs)
+    name_pairs.collect! { |k, v| [k.to_sym, v.to_sym] }
+    for opposite_name, name in name_pairs do
+      define_writer(name) unless writer_defined? name
+      class_eval %{def #{opposite_name.writer} x
+                     self.#{name.writer} !x end} 
+      class_eval %{def #{opposite_name.imperative}
+                     self.#{name.writer} false end}
+    end
+  end
+
+  define_soft_aliases \
+    :define_opposite_reader => :define_opposite_readers,
+    :define_opposite_writer => :define_opposite_writers
+
+  def define_opposite_accessors (name_pairs)
+    define_opposite_readers name_pairs
+    define_opposite_writers name_pairs
+  end
+
+  def define_reader_with_opposite (name_pair, &body)
+    name, opposite_name = name_pair.flatten.collect { |x| x.to_sym }
+    define_method(name, &body)
+    define_opposite_reader(opposite_name => name)
+  end
+
+  def define_writer_with_opposite (name_pair, &body)
+    name, opposite_name = name_pair.flatten.collect { |x| x.to_sym }
+    define_writer(name, &body)
+    define_opposite_writer(opposite_name => name)
+  end
+
+  public :define_method
+
+  def define_methods (*names, &body)
+    names.each { |name| define_method(name, &body) }
+  end
+  
+  def define_private_methods (*names, &body)
+    define_methods(*names, &body)
+    names.each { |name| private name }
+  end
+
+  def define_protected_methods (*names, &body)
+    define_methods(*names, &body)
+    names.each { |name| protected name }
+  end
+
+  def define_private_method (name, &body)
+    define_method(name, &body)
+    private name
+  end
+
+  def define_protected_method (name, &body)
+    define_method(name, &body)
+    protected name
+  end
+end
+
+class ImmutableAttributeError < StandardError
+  def initialize (attribute=nil, message=nil)
+    super message
+    @attribute = attribute
+  end
+
+  define_accessors :attribute
+
+  def to_s
+    if @attribute and @message
+      "cannot change the value of `#@attribute': #@message"
+    elsif @attribute
+      "cannot change the value of `#@attribute'"
+    elsif @message
+      "cannot change the value of attribute: #@message"
+    else
+      "cannot change the value of attribute"
+    end
+  end
+end
+
+class Module
+  # Guard each of the specified attributes by replacing the writer
+  # method with a proxy that asks the supplied block before proceeding
+  # with the change.
+  #
+  # If it's okay to change the attribute, the block should return
+  # either nil or the symbol :mutable.  If it isn't okay, the block
+  # should return a string saying why the attribute can't be changed.
+  # If you don't want to provide a reason, you can have the block
+  # return just the symbol :immutable.
+  def guard_writers(*names, &predicate)
+    for name in names.map { |x| x.to_sym } do
+      define_hard_alias("__unguarded_#{name.writer}" => name.writer)
+      define_method(name.writer) do |new_value|
+        case result = predicate.call
+        when :mutable, nil
+          __send__("__unguarded_#{name.writer}", new_value)
+        when :immutable
+          raise ImmutableAttributeError.new(name)
+        else
+          raise ImmutableAttributeError.new(name, result)
+        end
+      end
+    end
+  end
+
+  def define_guarded_writers (*names, &block)
+    define_writers(*names)
+    guard_writers(*names, &block)
+  end
+
+  define_soft_alias :guard_writer => :guard_writers
+  define_soft_alias :define_guarded_writer => :define_guarded_writers
+end
+
+if __FILE__ == $0
+  require "test/unit"
+
+  class DefineAccessorsTest < Test::Unit::TestCase
+    def setup
+      @X = Class.new
+      @Y = Class.new @X
+      @x = @X.new
+      @y = @Y.new
+    end
+
+    def test_define_hard_aliases
+      @X.define_method(:foo) { 123 }
+      @X.define_method(:baz) { 321 }
+      @X.define_hard_aliases :bar => :foo, :quux => :baz
+      assert_equal @x.foo, 123
+      assert_equal @x.bar, 123
+      assert_equal @y.foo, 123
+      assert_equal @y.bar, 123
+      assert_equal @x.baz, 321
+      assert_equal @x.quux, 321
+      assert_equal @y.baz, 321
+      assert_equal @y.quux, 321
+      @Y.define_method(:foo) { 456 }
+      assert_equal @y.foo, 456
+      assert_equal @y.bar, 123
+      @Y.define_method(:quux) { 654 }
+      assert_equal @y.baz, 321
+      assert_equal @y.quux, 654
+    end
+    
+    def test_define_soft_aliases
+      @X.define_method(:foo) { 123 }
+      @X.define_method(:baz) { 321 }
+      @X.define_soft_aliases :bar => :foo, :quux => :baz
+      assert_equal @x.foo, 123
+      assert_equal @x.bar, 123
+      assert_equal @y.foo, 123
+      assert_equal @y.bar, 123
+      assert_equal @x.baz, 321
+      assert_equal @x.quux, 321
+      assert_equal @y.baz, 321
+      assert_equal @y.quux, 321
+      @Y.define_method(:foo) { 456 }
+      assert_equal @y.foo, @y.bar, 456
+      @Y.define_method(:quux) { 654 }
+      assert_equal @y.baz, 321
+      assert_equal @y.quux, 654
+    end
+
+    def test_define_readers
+      @X.define_readers :foo, :bar
+      assert !@x.respond_to?(:foo=)
+      assert !@x.respond_to?(:bar=)
+      @x.instance_eval { @foo = 123 ; @bar = 456 }
+      assert_equal @x.foo, 123
+      assert_equal @x.bar, 456
+      @X.define_readers :baz?, :quux?
+      assert !@x.respond_to?(:baz=)
+      assert !@x.respond_to?(:quux=)
+      @x.instance_eval { @baz = false ; @quux = true }
+      assert !@x.baz?
+      assert @x.quux?
+    end
+
+    def test_define_writers
+      assert !@X.writer_defined?(:foo)
+      assert !@X.writer_defined?(:bar)
+      @X.define_writers :foo, :bar
+      assert @X.writer_defined?(:foo)
+      assert @X.writer_defined?(:bar)
+      assert @X.writer_defined?(:foo=)
+      assert @X.writer_defined?(:bar=)
+      assert @X.writer_defined?(:foo?)
+      assert @X.writer_defined?(:bar?)
+      assert !@x.respond_to?(:foo)
+      assert !@x.respond_to?(:bar)
+      @x.foo = 123
+      @x.bar = 456
+      assert_equal @x.instance_eval { @foo }, 123
+      assert_equal @x.instance_eval { @bar }, 456
+      @X.define_writers :baz?, :quux?
+      assert !@x.respond_to?(:baz?)
+      assert !@x.respond_to?(:quux?)
+      @x.baz = true
+      @x.quux = false
+      assert_equal @x.instance_eval { @baz }, true
+      assert_equal @x.instance_eval { @quux }, false
+    end
+
+    def test_define_accessors
+      @X.define_accessors :foo, :bar
+      @x.foo = 123 ; @x.bar = 456
+      assert_equal @x.foo, 123
+      assert_equal @x.bar, 456
+    end
+
+    def test_define_opposite_readers
+      @X.define_opposite_readers :foo? => :bar?, :baz? => :quux?
+      assert !@x.respond_to?(:foo=)
+      assert !@x.respond_to?(:bar=)
+      assert !@x.respond_to?(:baz=)
+      assert !@x.respond_to?(:quux=)
+      @x.instance_eval { @bar = true ; @quux = false }
+      assert !@x.foo?
+      assert @x.bar?
+      assert @x.baz?
+      assert !@x.quux?
+    end
+
+    def test_define_opposite_writers
+      @X.define_opposite_writers :foo? => :bar?, :baz => :quux
+    end
+  end
+end
diff --git a/lib/puppet/external/event-loop/event-loop.rb b/lib/puppet/external/event-loop/event-loop.rb
new file mode 100644
index 000000000..6e40d275c
--- /dev/null
+++ b/lib/puppet/external/event-loop/event-loop.rb
@@ -0,0 +1,355 @@
+## event-loop.rb --- high-level IO multiplexer
+# Copyright (C) 2005  Daniel Brockman
+
+# This program is free software; you can redistribute it
+# and/or modify it under the terms of the GNU General Public
+# License as published by the Free Software Foundation;
+# either version 2 of the License, or (at your option) any
+# later version.
+
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty
+# of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+# See the GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public
+# License along with this program; if not, write to the Free
+# Software Foundation, 51 Franklin Street, Fifth Floor,
+# Boston, MA 02110-1301, USA.
+
+require "puppet/external/event-loop/better-definers"
+require "puppet/external/event-loop/signal-system"
+
+require "fcntl"
+
+class EventLoop
+  include SignalEmitter
+
+  IO_STATES = [:readable, :writable, :exceptional]
+
+  class << self
+    def default ; @default ||= new end
+    def default= x ; @default = x end
+
+    def current
+      Thread.current["event-loop::current"] || default end
+    def current= x
+      Thread.current["event-loop::current"] = x end
+
+    def with_current (new)
+      if current == new
+        yield
+      else
+        begin
+          old = self.current
+          self.current = new
+          yield
+        ensure
+          self.current = old
+        end
+      end
+    end
+
+    def method_missing (name, *args, &block)
+      if current.respond_to? name
+        current.__send__(name, *args, &block)
+      else
+        super
+      end
+    end
+  end
+
+  define_signals :before_sleep, :after_sleep
+
+  def initialize
+    @running = false
+    @awake = false
+    @wakeup_time = nil
+    @timers = []
+
+    @io_arrays = [[], [], []]
+    @ios = Hash.new do |h, k| raise ArgumentError,
+      "invalid IO event: #{k}", caller(2) end
+    IO_STATES.each_with_index { |x, i| @ios[x] = @io_arrays[i] }
+
+    @notify_src, @notify_snk = IO.pipe
+
+    @notify_src.will_block = false
+    @notify_snk.will_block = false
+
+    # Each time a byte is sent through the notification pipe
+    # we need to read it, or IO.select will keep returning.
+    monitor_io(@notify_src, :readable)
+    @notify_src.extend(Watchable)
+    @notify_src.on_readable do
+      begin
+        @notify_src.sysread(256)
+      rescue Errno::EAGAIN
+        # The pipe wasn't readable after all.
+      end
+    end
+  end
+
+  define_opposite_accessors \
+    :stopped?  => :running?,
+    :sleeping? => :awake?
+
+  def run
+    if block_given?
+      thread = Thread.new { run }
+      yield ; quit ; thread.join
+    else
+      running!
+      iterate while running?
+    end
+  ensure
+    quit
+  end
+
+  def iterate (user_timeout=nil)
+    t1, t2 = user_timeout, max_timeout
+    timeout = t1 && t2 ? [t1, t2].min : t1 || t2
+    select(timeout).zip(IO_STATES) do |ios, state|
+      ios.each { |x| x.signal(state) } if ios
+    end
+  end
+
+ private
+
+  def select (timeout)
+    @wakeup_time = timeout ? Time.now + timeout : nil
+    # puts "waiting: #{timeout} seconds"
+    signal :before_sleep ; sleeping!
+    IO.select(*@io_arrays + [timeout]) || []
+  ensure
+    awake! ; signal :after_sleep
+    @timers.each { |x| x.sound_alarm if x.ready? }
+  end
+
+ public
+
+  def quit ; stopped! ; wake_up ; self end
+
+  def monitoring_io? (io, event)
+    @ios[event].include? io end
+  def monitoring_timer? (timer)
+    @timers.include? timer end
+
+  def monitor_io (io, *events)
+    for event in events do
+      unless monitoring_io?(io, event)
+        @ios[event] << io ; wake_up
+      end
+    end
+  end
+
+  def monitor_timer (timer)
+    unless monitoring_timer? timer
+      @timers << timer
+    end
+  end
+
+  def check_timer (timer)
+    wake_up if timer.end_time < @wakeup_time
+  end
+
+  def ignore_io (io, *events)
+    events = IO_STATES if events.empty?
+    for event in events do
+      wake_up if @ios[event].delete(io)
+    end
+  end
+
+  def ignore_timer (timer)
+    # Don't need to wake up for this.
+    @timers.delete(timer)
+  end
+
+  def max_timeout
+    return nil if @timers.empty?
+    [@timers.collect { |x| x.time_left }.min, 0].max
+  end
+
+  def wake_up
+    @notify_snk.write('.') if sleeping?
+  end
+end
+
+class Symbol
+  def io_state?
+    EventLoop::IO_STATES.include? self
+  end
+end
+
+module EventLoop::Watchable
+  include SignalEmitter
+
+  define_signals :readable, :writable, :exceptional
+
+  def monitor_events (*events)
+    EventLoop.monitor_io(self, *events) end
+  def ignore_events (*events)
+    EventLoop.ignore_io(self, *events) end
+
+  define_soft_aliases \
+    :monitor_event => :monitor_events,
+    :ignore_event  => :ignore_events
+
+  def close ; super
+    ignore_events end
+  def close_read ; super
+    ignore_event :readable end
+  def close_write ; super
+    ignore_event :writable end
+
+  module Automatic
+    include EventLoop::Watchable
+
+    def add_signal_handler (name, &handler) super
+      monitor_event(name) if name.io_state?
+    end
+
+    def remove_signal_handler (name, handler) super
+      if @signal_handlers[name].empty?
+        ignore_event(name) if name.io_state?
+      end
+    end
+  end
+end
+
+class IO
+  def on_readable &block
+    extend EventLoop::Watchable::Automatic
+    on_readable(&block)
+  end
+
+  def on_writable &block
+    extend EventLoop::Watchable::Automatic
+    on_writable(&block)
+  end
+
+  def on_exceptional &block
+    extend EventLoop::Watchable::Automatic
+    on_exceptional(&block)
+  end
+
+  def will_block?
+    require "fcntl"
+    fcntl(Fcntl::F_GETFL, 0) & Fcntl::O_NONBLOCK == 0
+  end
+
+  def will_block= (wants_blocking)
+    require "fcntl"
+    flags = fcntl(Fcntl::F_GETFL, 0)
+    if wants_blocking
+      flags &= ~Fcntl::O_NONBLOCK
+    else
+      flags |= Fcntl::O_NONBLOCK
+    end
+    fcntl(Fcntl::F_SETFL, flags)
+  end
+end
+
+class EventLoop::Timer
+  include SignalEmitter
+
+  DEFAULT_INTERVAL = 0.0
+  DEFAULT_TOLERANCE = 0.001
+
+  def initialize (options={}, &handler)
+    @running = false
+    @start_time = nil
+
+    if options.kind_of? Numeric
+      options = { :interval => options }
+    end
+
+    if options[:interval]
+      @interval = options[:interval].to_f
+    else
+      @interval = DEFAULT_INTERVAL
+    end
+
+    if options[:tolerance]
+      @tolerance = options[:tolerance].to_f
+    elsif DEFAULT_TOLERANCE < @interval
+      @tolerance = DEFAULT_TOLERANCE
+    else
+      @tolerance = 0.0
+    end
+
+    @event_loop = options[:event_loop] || EventLoop.current
+
+    if block_given?
+      add_signal_handler(:alarm, &handler)
+      start unless options[:start?] == false
+    else
+      start if options[:start?]
+    end
+  end
+
+  define_readers :interval, :tolerance
+  define_signal :alarm
+
+  def stopped? ; @start_time == nil end
+  def running? ; @start_time != nil end
+
+  def interval= (new_interval)
+    old_interval = @interval
+    @interval = new_interval
+    if new_interval < old_interval
+      @event_loop.check_timer(self)
+    end
+  end
+
+  def end_time
+    @start_time + @interval end
+  def time_left
+    end_time - Time.now end
+  def ready?
+    time_left <= @tolerance end
+
+  def restart
+    @start_time = Time.now
+  end
+
+  def sound_alarm
+    signal :alarm
+    restart if running?
+  end
+
+  def start
+    @start_time = Time.now
+    @event_loop.monitor_timer(self)
+  end
+
+  def stop
+    @start_time = nil
+    @event_loop.ignore_timer(self)
+  end
+end
+
+if __FILE__ == $0
+  require "test/unit"
+
+  class TimerTest < Test::Unit::TestCase
+    def setup
+      @timer = EventLoop::Timer.new(:interval => 0.001)
+    end
+
+    def test_timer
+      @timer.on_alarm do
+        puts "[#{@timer.time_left} seconds left after alarm]"
+        EventLoop.quit
+      end
+      8.times do
+        t0 = Time.now
+        @timer.start ; EventLoop.run
+        t1 = Time.now
+        assert(t1 - t0 > @timer.interval - @timer.tolerance)
+      end
+    end
+  end
+end
+
+## event-loop.rb ends here.
diff --git a/lib/puppet/external/event-loop/signal-system.rb b/lib/puppet/external/event-loop/signal-system.rb
new file mode 100644
index 000000000..2ca61e2ee
--- /dev/null
+++ b/lib/puppet/external/event-loop/signal-system.rb
@@ -0,0 +1,220 @@
+## signal-system.rb --- simple intra-process signal system
+# Copyright (C) 2005  Daniel Brockman
+
+# This program is free software; you can redistribute it
+# and/or modify it under the terms of the GNU General Public
+# License as published by the Free Software Foundation;
+# either version 2 of the License, or (at your option) any
+# later version.
+
+# This file is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty
+# of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+# See the GNU General Public License for more details.
+
+# You should have received a copy of the GNU General Public
+# License along with this program; if not, write to the Free
+# Software Foundation, 51 Franklin Street, Fifth Floor,
+# Boston, MA 02110-1301, USA.
+
+require "puppet/external/event-loop/better-definers"
+
+module SignalEmitterModule
+  def self.extended (object)
+    if object.kind_of? Module and not object < SignalEmitter
+      if object.respond_to? :fcall
+        # This is the way to call private methods
+        # in Ruby 1.9 as of November 16.
+        object.fcall :include, SignalEmitter
+      else
+        object.__send__ :include, SignalEmitter
+      end
+    end
+  end
+
+  def define_signal (name, slot=:before, &body)
+    # Can't use `define_method' and take a block pre-1.9.
+    class_eval %{ def on_#{name} &block
+                    add_signal_handler(:#{name}, &block) end }
+    define_signal_handler(name, :before, &lambda {|*a|})
+    define_signal_handler(name, :after, &lambda {|*a|})
+    define_signal_handler(name, slot, &body) if block_given?
+  end
+
+  def define_signals (*names, &body)
+    names.each { |x| define_signal(x, &body) }
+  end
+
+  def define_signal_handler (name, slot=:before, &body)
+    case slot
+    when :before
+      define_protected_method "handle_#{name}", &body
+    when :after
+      define_protected_method "after_handle_#{name}", &body
+    else
+      raise ArgumentError, "invalid slot `#{slot.inspect}'; " +
+        "should be `:before' or `:after'", caller(1)
+    end
+  end
+end
+
+# This is an old name for the same thing.
+SignalEmitterClass = SignalEmitterModule
+
+module SignalEmitter
+  def self.included (includer)
+    if not includer.kind_of? SignalEmitterClass
+      includer.extend SignalEmitterClass
+    end
+  end
+
+  def __maybe_initialize_signal_emitter
+    @signal_handlers ||= Hash.new { |h, k| h[k] = Array.new }
+    @allow_dynamic_signals ||= false
+  end
+
+  define_accessors :allow_dynamic_signals?
+
+  def add_signal_handler (name, &handler)
+    __maybe_initialize_signal_emitter
+    @signal_handlers[name] << handler
+    return handler
+  end
+
+  define_soft_aliases [:on, :on_signal] => :add_signal_handler
+
+  def remove_signal_handler (name, handler)
+    __maybe_initialize_signal_emitter
+    @signal_handlers[name].delete(handler)
+  end
+
+  def __signal__ (name, *args, &block)
+    __maybe_initialize_signal_emitter
+    respond_to? "on_#{name}" or allow_dynamic_signals? or
+      fail "undefined signal `#{name}' for #{self}:#{self.class}"
+    __send__("handle_#{name}", *args, &block) if
+      respond_to? "handle_#{name}"
+    @signal_handlers[name].each { |x| x.call(*args, &block) }
+    __send__("after_handle_#{name}", *args, &block) if
+      respond_to? "after_handle_#{name}"
+  end
+
+  define_soft_alias :signal => :__signal__
+end
+
+# This module is indended to be a convenience mixin to be used by
+# classes whose objects need to observe foreign signals.  That is,
+# if you want to observe some signals coming from an object, *you*
+# should mix in this module.
+#
+# You cannot use this module at two different places of the same
+# inheritance chain to observe signals coming from the same object.
+#
+# XXX: This has not seen much use, and I'd like to provide a
+#      better solution for the problem in the future.
+module SignalObserver
+  def __maybe_initialize_signal_observer
+    @observed_signals ||= Hash.new do |signals, object|
+      signals[object] = Hash.new do |handlers, name|
+        handlers[name] = Array.new
+      end
+    end
+  end
+
+  def observe_signal (subject, name, &handler)
+    __maybe_initialize_signal_observer
+    @observed_signals[subject][name] << handler
+    subject.add_signal_handler(name, &handler)
+  end
+
+  def map_signals (source, pairs={})
+    pairs.each do |src_name, dst_name|
+      observe_signal(source, src_name) do |*args|
+        __signal__(dst_name, *args)
+      end
+    end
+  end
+
+  def absorb_signals (subject, *names)
+    names.each do |name|
+      observe_signal(subject, name) do |*args|
+        __signal__(name, *args)
+      end
+    end
+  end
+
+  define_soft_aliases \
+    :map_signal    => :map_signals,
+    :absorb_signal => :absorb_signals
+
+  def ignore_signal (subject, name)
+    __maybe_initialize_signal_observer
+    __ignore_signal_1(subject, name)
+    @observed_signals.delete(subject) if
+      @observed_signals[subject].empty?
+  end
+
+  def ignore_signals (subject, *names)
+    __maybe_initialize_signal_observer
+    names = @observed_signals[subject] if names.empty?
+    names.each { |x| __ignore_signal_1(subject, x) }
+  end
+
+ private
+
+  def __ignore_signal_1(subject, name)
+    @observed_signals[subject][name].each do |handler|
+      subject.remove_signal_handler(name, handler) end
+    @observed_signals[subject].delete(name)
+  end
+end
+
+if __FILE__ == $0
+  require "test/unit"
+  class SignalEmitterTest < Test::Unit::TestCase
+    class X
+      include SignalEmitter
+      define_signal :foo
+    end
+
+    def setup
+      @x = X.new
+    end
+
+    def test_on_signal
+      moomin = 0
+      @x.on_signal(:foo) { moomin = 1 }
+      @x.signal :foo
+      assert moomin == 1
+    end
+
+    def test_on_foo
+      moomin = 0
+      @x.on_foo { moomin = 1 }
+      @x.signal :foo
+      assert moomin == 1
+    end
+
+    def test_multiple_on_signal
+      moomin = 0
+      @x.on_signal(:foo) { moomin += 1 }
+      @x.on_signal(:foo) { moomin += 2 }
+      @x.on_signal(:foo) { moomin += 4 }
+      @x.on_signal(:foo) { moomin += 8 }
+      @x.signal :foo
+      assert moomin == 15
+    end
+
+    def test_multiple_on_foo
+      moomin = 0
+      @x.on_foo { moomin += 1 }
+      @x.on_foo { moomin += 2 }
+      @x.on_foo { moomin += 4 }
+      @x.on_foo { moomin += 8 }
+      @x.signal :foo
+      assert moomin == 15
+    end
+  end
+end
+
+## application-signals.rb ends here.
diff --git a/lib/puppet/external/gratr.rb b/lib/puppet/external/gratr.rb
new file mode 100644
index 000000000..b830caeb4
--- /dev/null
+++ b/lib/puppet/external/gratr.rb
@@ -0,0 +1,33 @@
+#--
+# 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
new file mode 100644
index 000000000..b740c4722
--- /dev/null
+++ b/lib/puppet/external/gratr/adjacency_graph.rb
@@ -0,0 +1,257 @@
+#--
+# 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
new file mode 100644
index 000000000..72dded73f
--- /dev/null
+++ b/lib/puppet/external/gratr/base.rb
@@ -0,0 +1,34 @@
+#--
+# 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
new file mode 100644
index 000000000..c976b2c04
--- /dev/null
+++ b/lib/puppet/external/gratr/biconnected.rb
@@ -0,0 +1,116 @@
+#--
+# 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
new file mode 100644
index 000000000..338a88bed
--- /dev/null
+++ b/lib/puppet/external/gratr/chinese_postman.rb
@@ -0,0 +1,123 @@
+#--
+# 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
new file mode 100644
index 000000000..347250edc
--- /dev/null
+++ b/lib/puppet/external/gratr/common.rb
@@ -0,0 +1,73 @@
+#--
+# 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
new file mode 100644
index 000000000..1546fbefe
--- /dev/null
+++ b/lib/puppet/external/gratr/comparability.rb
@@ -0,0 +1,92 @@
+#--
+# 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
new file mode 100644
index 000000000..1223a65a1
--- /dev/null
+++ b/lib/puppet/external/gratr/digraph.rb
@@ -0,0 +1,116 @@
+#--
+# 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
new file mode 100644
index 000000000..6f90384e7
--- /dev/null
+++ b/lib/puppet/external/gratr/digraph_distance.rb
@@ -0,0 +1,185 @@
+#--
+# 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
new file mode 100644
index 000000000..5b74776aa
--- /dev/null
+++ b/lib/puppet/external/gratr/dot.rb
@@ -0,0 +1,90 @@
+#--
+# 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
new file mode 100644
index 000000000..8470e5458
--- /dev/null
+++ b/lib/puppet/external/gratr/edge.rb
@@ -0,0 +1,145 @@
+#--
+# 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
new file mode 100644
index 000000000..7b73afccc
--- /dev/null
+++ b/lib/puppet/external/gratr/graph.rb
@@ -0,0 +1,303 @@
+#--
+# 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
new file mode 100644
index 000000000..26d18958a
--- /dev/null
+++ b/lib/puppet/external/gratr/graph_api.rb
@@ -0,0 +1,83 @@
+#--
+# 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
new file mode 100644
index 000000000..d3678d8b6
--- /dev/null
+++ b/lib/puppet/external/gratr/import.rb
@@ -0,0 +1,44 @@
+#--
+# 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
new file mode 100644
index 000000000..7e53df404
--- /dev/null
+++ b/lib/puppet/external/gratr/labels.rb
@@ -0,0 +1,90 @@
+#--
+# 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
new file mode 100644
index 000000000..7b3ef9b2f
--- /dev/null
+++ b/lib/puppet/external/gratr/maximum_flow.rb
@@ -0,0 +1,64 @@
+#--
+# 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/rdot.rb b/lib/puppet/external/gratr/rdot.rb
new file mode 100644
index 000000000..4ce545ae6
--- /dev/null
+++ b/lib/puppet/external/gratr/rdot.rb
@@ -0,0 +1,327 @@
+# rdot.rb
+# 
+# $Id$
+#
+# This is a modified version of dot.rb from Dave Thomas's rdoc project.  I [Horst Duchene]
+# renamed it to rdot.rb to avoid collision with an installed rdoc/dot.
+#
+# It also supports undirected edges.
+
+module DOT
+    
+  # These glogal vars are used to make nice graph source.
+
+  $tab  = '    '
+  $tab2 = $tab * 2
+    
+  # if we don't like 4 spaces, we can change it any time
+
+  def change_tab (t)
+    $tab  = t
+    $tab2 = t * 2
+  end
+    
+  # options for node declaration
+
+  NODE_OPTS = [
+    # attributes due to
+    # http://www.graphviz.org/Documentation/dotguide.pdf
+    # March, 26, 2005
+    'bottomlabel', # auxiliary label for nodes of shape M*
+    'color', # default: black; node shape color
+    'comment', # any string (format-dependent)
+    'distortion', # default: 0.0; node distortion for shape=polygon
+    'fillcolor', # default: lightgrey/black; node fill color
+    'fixedsize', # default: false; label text has no affect on node size
+    'fontcolor', # default: black; type face color
+    'fontname', # default: Times-Roman; font family
+    'fontsize', #default: 14; point size of label
+    'group', # name of node�s group
+    'height', # default: .5; height in inches
+    'label', # default: node name; any string
+    'layer', # default: overlay range; all, id or id:id
+    'orientation', # dafault: 0.0; node rotation angle
+    'peripheries', # shape-dependent number of node boundaries
+    'regular', # default:  false; force polygon to be regular
+    'shape', # default: ellipse; node shape; see Section 2.1 and Appendix E
+    'shapefile', # external EPSF or SVG custom shape file
+    'sides', # default: 4; number of sides for shape=polygon
+    'skew' , # default: 0.0; skewing of node for shape=polygon
+    'style', # graphics options, e.g. bold, dotted, filled; cf. Section 2.3
+    'toplabel', # auxiliary label for nodes of shape M*
+    'URL', # URL associated with node (format-dependent)
+    'width', # default: .75; width in inches
+    'z', #default: 0.0; z coordinate for VRML output
+
+    # maintained for backward compatibility or rdot internal
+    'bgcolor',
+    'rank'
+  ]
+    
+  # options for edge declaration
+
+  EDGE_OPTS = [
+    'arrowhead', # default: normal; style of arrowhead at head end
+    'arrowsize', # default: 1.0; scaling factor for arrowheads
+    'arrowtail', # default: normal; style of arrowhead at tail end
+    'color', # default: black; edge stroke color
+    'comment', # any string (format-dependent)
+    'constraint', # default: true use edge to affect node ranking
+    'decorate', # if set, draws a line connecting labels with their edges
+    'dir', # default: forward; forward, back, both, or none
+    'fontcolor', # default: black type face color
+    'fontname', # default: Times-Roman; font family
+    'fontsize', # default: 14; point size of label
+    'headlabel', # label placed near head of edge
+    'headport', # n,ne,e,se,s,sw,w,nw
+    'headURL', # URL attached to head label if output format is ismap
+    'label', # edge label
+    'labelangle', # default: -25.0; angle in degrees which head or tail label is rotated off edge
+    'labeldistance', # default: 1.0; scaling factor for distance of head or tail label from node
+    'labelfloat', # default: false; lessen constraints on edge label placement
+    'labelfontcolor', # default: black; type face color for head and tail labels
+    'labelfontname', # default: Times-Roman; font family for head and tail labels
+    'labelfontsize', # default: 14 point size for head and tail labels
+    'layer', # default: overlay range; all, id or id:id
+    'lhead', # name of cluster to use as head of edge
+    'ltail', # name of cluster to use as tail of edge
+    'minlen', # default: 1 minimum rank distance between head and tail
+    'samehead', # tag for head node; edge heads with the same tag are merged onto the same port
+    'sametail', # tag for tail node; edge tails with the same tag are merged onto the same port
+    'style', # graphics options, e.g. bold, dotted, filled; cf. Section 2.3
+    'taillabel', # label placed near tail of edge
+    'tailport', # n,ne,e,se,s,sw,w,nw
+    'tailURL', # URL attached to tail label if output format is ismap
+    'weight', # default: 1; integer cost of stretching an edge
+
+    # maintained for backward compatibility or rdot internal
+    'id'
+  ]
+    
+  # options for graph declaration
+
+  GRAPH_OPTS = [
+    'bgcolor',
+    'center', 'clusterrank', 'color', 'concentrate',
+    'fontcolor', 'fontname', 'fontsize',
+    'label', 'layerseq',
+    'margin', 'mclimit',
+    'nodesep', 'nslimit',
+    'ordering', 'orientation',
+    'page',
+    'rank', 'rankdir', 'ranksep', 'ratio',
+    'size'
+  ]
+    
+  # a root class for any element in dot notation
+
+  class DOTSimpleElement
+
+    attr_accessor :name
+
+    def initialize (params = {})
+      @label = params['name'] ? params['name'] : ''
+    end
+
+    def to_s
+      @name
+    end
+  end
+    
+  # an element that has options ( node, edge, or graph )
+
+  class DOTElement < DOTSimpleElement
+
+    # attr_reader :parent
+    attr_accessor :name, :options
+
+    def initialize (params = {}, option_list = [])
+      super(params)
+      @name   = params['name']   ? params['name']   : nil 
+      @parent = params['parent'] ? params['parent'] : nil
+      @options = {}
+      option_list.each{ |i|
+        @options[i] = params[i] if params[i]
+      }
+      @options['label'] ||= @name if @name != 'node'
+    end
+        
+    def each_option
+      @options.each{ |i| yield i }
+    end
+
+    def each_option_pair
+      @options.each_pair{ |key, val| yield key, val }
+    end
+
+    #def parent=( thing )
+    #    @parent.delete( self ) if defined?( @parent ) and @parent
+    #    @parent = thing
+    #end
+
+  end
+    
+    
+  # This is used when we build nodes that have shape=record
+  # ports don't have options :)
+
+  class DOTPort < DOTSimpleElement
+
+    attr_accessor :label
+        
+    def initialize (params = {})
+      super(params)
+      @name = params['label'] ? params['label'] : ''
+    end
+
+    def to_s
+      ( @name && @name != "" ? "<#{@name}>" : "" ) + "#{@label}"
+    end
+  end
+    
+  # node element
+
+  class DOTNode < DOTElement
+
+    @ports
+
+    def initialize (params = {}, option_list = NODE_OPTS)
+      super(params, option_list)
+      @ports = params['ports'] ? params['ports'] : []
+    end
+
+    def each_port
+      @ports.each { |i| yield i }
+    end
+
+    def << (thing)
+      @ports << thing
+    end
+
+    def push (thing)
+      @ports.push(thing)
+    end
+
+    def pop
+      @ports.pop
+    end
+
+    def to_s (t = '')
+
+      # This code is totally incomprehensible; it needs to be replaced!
+
+      label = @options['shape'] != 'record' && @ports.length == 0 ?
+                @options['label'] ? 
+                    t + $tab + "label = \"#{@options['label']}\"\n" :
+                    '' :
+                t + $tab + 'label = "' + " \\\n" +
+                t + $tab2 + "#{@options['label']}| \\\n" +
+                @ports.collect{ |i|
+                    t + $tab2 + i.to_s
+                }.join( "| \\\n" ) + " \\\n" +
+                t + $tab + '"' + "\n"
+            
+            t + "#{@name} [\n" +
+            @options.to_a.collect{ |i|
+                i[1] && i[0] != 'label' ? 
+                    t + $tab + "#{i[0]} = #{i[1]}" : nil
+            }.compact.join( ",\n" ) + ( label != '' ? ",\n" : "\n" ) + 
+            label +
+            t + "]\n" 
+      end
+
+  end		# class DOTNode
+
+  # A subgraph element is the same to graph, but has another header in dot
+  # notation.
+
+  class DOTSubgraph < DOTElement
+
+    @nodes
+    @dot_string
+
+    def initialize (params = {}, option_list = GRAPH_OPTS)
+      super(params, option_list)
+      @nodes      = params['nodes'] ? params['nodes'] : []
+      @dot_string = 'graph'
+    end
+
+    def each_node
+      @nodes.each{ |i| yield i }
+    end
+
+    def << (thing)
+      @nodes << thing
+    end
+       
+    def push (thing)
+      @nodes.push( thing )
+    end
+
+    def pop
+      @nodes.pop
+    end
+
+    def to_s (t = '')
+      hdr = t + "#{@dot_string} #{@name} {\n"
+
+      options = @options.to_a.collect{ |name, val|
+        val && name != 'label' ? 
+          t + $tab + "#{name} = #{val}" : 
+          name ? t + $tab + "#{name} = \"#{val}\"" : nil
+      }.compact.join( "\n" ) + "\n"
+
+      nodes = @nodes.collect{ |i|
+        i.to_s( t + $tab )
+      }.join( "\n" ) + "\n" 
+      hdr + options + nodes + t + "}\n"
+    end
+
+  end		# class DOTSubgraph
+
+  # This is a graph.
+
+  class DOTDigraph < DOTSubgraph
+
+    def initialize (params = {}, option_list = GRAPH_OPTS)
+      super(params, option_list)
+      @dot_string = 'digraph'
+    end
+
+  end		# class DOTDigraph
+
+  # This is an edge.
+
+  class DOTEdge < DOTElement
+
+    attr_accessor :from, :to
+
+    def initialize (params = {}, option_list = EDGE_OPTS)
+      super(params, option_list)
+      @from = params['from'] ? params['from'] : nil
+      @to   = params['to'] ? params['to'] : nil
+    end
+       
+    def edge_link
+      '--'
+    end
+
+    def to_s (t = '')
+      t + "#{@from} #{edge_link} #{to} [\n" +
+          @options.to_a.collect{ |i|
+            i[1] && i[0] != 'label' ? 
+              t + $tab + "#{i[0]} = #{i[1]}" : 
+              i[1] ? t + $tab + "#{i[0]} = \"#{i[1]}\"" : nil
+          }.compact.join( "\n" ) + "\n" + t + "]\n"
+    end
+
+  end		# class DOTEdge
+          
+  class DOTDirectedEdge < DOTEdge
+
+    def edge_link
+      '->'
+    end
+
+  end                           # class DOTDirectedEdge
+end                             # module DOT
diff --git a/lib/puppet/external/gratr/search.rb b/lib/puppet/external/gratr/search.rb
new file mode 100644
index 000000000..3206ec5d9
--- /dev/null
+++ b/lib/puppet/external/gratr/search.rb
@@ -0,0 +1,409 @@
+#--
+# 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
new file mode 100644
index 000000000..796ae16bb
--- /dev/null
+++ b/lib/puppet/external/gratr/strong_components.rb
@@ -0,0 +1,127 @@
+#--
+# 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
new file mode 100644
index 000000000..86963d27c
--- /dev/null
+++ b/lib/puppet/external/gratr/undirected_graph.rb
@@ -0,0 +1,153 @@
+#--
+# 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/lock.rb b/lib/puppet/external/lock.rb
new file mode 100644
index 000000000..d873d1bbf
--- /dev/null
+++ b/lib/puppet/external/lock.rb
@@ -0,0 +1,64 @@
+require 'thread'
+require 'sync'
+
+# Gotten from:
+# http://path.berkeley.edu/~vjoel/ruby/solaris-bug.rb
+
+# Extensions to the File class for exception-safe file locking in a
+# environment with multiple user threads.
+
+# This is here because closing a file on solaris unlocks any locks that
+# other threads might have. So we have to make sure that only the last
+# reader thread closes the file.
+#
+# The hash maps inode number to a count of reader threads
+$reader_count = Hash.new(0)
+
+class File
+    # Get an exclusive (i.e., write) lock on the file, and yield to the block.
+    # If the lock is not available, wait for it without blocking other ruby
+    # threads.
+    def lock_exclusive
+        if Thread.list.size == 1
+            flock(LOCK_EX)
+        else
+            # ugly hack because waiting for a lock in a Ruby thread blocks the
+            # process
+            period = 0.001
+            until flock(LOCK_EX|LOCK_NB)
+                sleep period
+                period *= 2 if period < 1
+            end
+        end
+
+        yield self
+    ensure
+        flush
+        flock(LOCK_UN)
+    end
+  
+    # Get a shared (i.e., read) lock on the file, and yield to the block.
+    # If the lock is not available, wait for it without blocking other ruby
+    # threads.
+    def lock_shared
+        if Thread.list.size == 1
+            flock(LOCK_SH)
+        else
+            # ugly hack because waiting for a lock in a Ruby thread blocks the
+            # process
+            period = 0.001
+            until flock(LOCK_SH|LOCK_NB)
+                sleep period
+                period *= 2 if period < 1
+            end
+        end
+
+        yield self
+    ensure
+        Thread.exclusive {flock(LOCK_UN) if $reader_count[self.stat.ino] == 1}
+        ## for solaris, no need to unlock here--closing does it
+        ## but this has no effect on the bug
+    end
+end
+
+# $Id$