From 01ec5ba96f8bf53f77974785d60ef79553488f08 Mon Sep 17 00:00:00 2001 From: luke Date: Tue, 30 Jan 2007 05:27:56 +0000 Subject: Moving code from external sources into an external/ directory git-svn-id: https://reductivelabs.com/svn/puppet/trunk@2119 980ebf18-57e1-0310-9a29-db15c13687c0 --- lib/puppet.rb | 2 +- lib/puppet/base64.rb | 19 - lib/puppet/event-loop.rb | 1 - lib/puppet/event-loop/better-definers.rb | 367 ------------------- lib/puppet/event-loop/event-loop.rb | 355 ------------------- lib/puppet/event-loop/signal-system.rb | 220 ------------ lib/puppet/external/base64.rb | 19 + lib/puppet/external/event-loop.rb | 1 + lib/puppet/external/event-loop/better-definers.rb | 367 +++++++++++++++++++ lib/puppet/external/event-loop/event-loop.rb | 355 +++++++++++++++++++ lib/puppet/external/event-loop/signal-system.rb | 220 ++++++++++++ lib/puppet/external/gratr.rb | 33 ++ lib/puppet/external/gratr/adjacency_graph.rb | 257 ++++++++++++++ lib/puppet/external/gratr/base.rb | 34 ++ lib/puppet/external/gratr/biconnected.rb | 116 ++++++ lib/puppet/external/gratr/chinese_postman.rb | 123 +++++++ lib/puppet/external/gratr/common.rb | 73 ++++ lib/puppet/external/gratr/comparability.rb | 92 +++++ lib/puppet/external/gratr/digraph.rb | 116 ++++++ lib/puppet/external/gratr/digraph_distance.rb | 185 ++++++++++ lib/puppet/external/gratr/dot.rb | 90 +++++ lib/puppet/external/gratr/edge.rb | 145 ++++++++ lib/puppet/external/gratr/graph.rb | 303 ++++++++++++++++ lib/puppet/external/gratr/graph_api.rb | 83 +++++ lib/puppet/external/gratr/import.rb | 44 +++ lib/puppet/external/gratr/labels.rb | 90 +++++ lib/puppet/external/gratr/maximum_flow.rb | 64 ++++ lib/puppet/external/gratr/rdot.rb | 327 +++++++++++++++++ lib/puppet/external/gratr/search.rb | 409 ++++++++++++++++++++++ lib/puppet/external/gratr/strong_components.rb | 127 +++++++ lib/puppet/external/gratr/undirected_graph.rb | 153 ++++++++ lib/puppet/external/lock.rb | 64 ++++ lib/puppet/gratr.rb | 33 -- lib/puppet/gratr/adjacency_graph.rb | 257 -------------- lib/puppet/gratr/base.rb | 34 -- lib/puppet/gratr/biconnected.rb | 116 ------ lib/puppet/gratr/chinese_postman.rb | 123 ------- lib/puppet/gratr/common.rb | 73 ---- lib/puppet/gratr/comparability.rb | 92 ----- lib/puppet/gratr/digraph.rb | 116 ------ lib/puppet/gratr/digraph_distance.rb | 185 ---------- lib/puppet/gratr/dot.rb | 90 ----- lib/puppet/gratr/edge.rb | 145 -------- lib/puppet/gratr/graph.rb | 303 ---------------- lib/puppet/gratr/graph_api.rb | 83 ----- lib/puppet/gratr/import.rb | 44 --- lib/puppet/gratr/labels.rb | 90 ----- lib/puppet/gratr/maximum_flow.rb | 64 ---- lib/puppet/gratr/rdot.rb | 327 ----------------- lib/puppet/gratr/search.rb | 409 ---------------------- lib/puppet/gratr/strong_components.rb | 127 ------- lib/puppet/gratr/undirected_graph.rb | 153 -------- lib/puppet/lock.rb | 64 ---- lib/puppet/networkclient.rb | 2 +- lib/puppet/pgraph.rb | 6 +- lib/puppet/relationship.rb | 2 +- lib/puppet/server/filebucket.rb | 2 +- lib/puppet/util.rb | 2 +- 58 files changed, 3898 insertions(+), 3898 deletions(-) delete mode 100755 lib/puppet/base64.rb delete mode 100644 lib/puppet/event-loop.rb delete mode 100644 lib/puppet/event-loop/better-definers.rb delete mode 100644 lib/puppet/event-loop/event-loop.rb delete mode 100644 lib/puppet/event-loop/signal-system.rb create mode 100755 lib/puppet/external/base64.rb create mode 100644 lib/puppet/external/event-loop.rb create mode 100644 lib/puppet/external/event-loop/better-definers.rb create mode 100644 lib/puppet/external/event-loop/event-loop.rb create mode 100644 lib/puppet/external/event-loop/signal-system.rb create mode 100644 lib/puppet/external/gratr.rb create mode 100644 lib/puppet/external/gratr/adjacency_graph.rb create mode 100644 lib/puppet/external/gratr/base.rb create mode 100644 lib/puppet/external/gratr/biconnected.rb create mode 100644 lib/puppet/external/gratr/chinese_postman.rb create mode 100644 lib/puppet/external/gratr/common.rb create mode 100644 lib/puppet/external/gratr/comparability.rb create mode 100644 lib/puppet/external/gratr/digraph.rb create mode 100644 lib/puppet/external/gratr/digraph_distance.rb create mode 100644 lib/puppet/external/gratr/dot.rb create mode 100644 lib/puppet/external/gratr/edge.rb create mode 100644 lib/puppet/external/gratr/graph.rb create mode 100644 lib/puppet/external/gratr/graph_api.rb create mode 100644 lib/puppet/external/gratr/import.rb create mode 100644 lib/puppet/external/gratr/labels.rb create mode 100644 lib/puppet/external/gratr/maximum_flow.rb create mode 100644 lib/puppet/external/gratr/rdot.rb create mode 100644 lib/puppet/external/gratr/search.rb create mode 100644 lib/puppet/external/gratr/strong_components.rb create mode 100644 lib/puppet/external/gratr/undirected_graph.rb create mode 100644 lib/puppet/external/lock.rb delete mode 100644 lib/puppet/gratr.rb delete mode 100644 lib/puppet/gratr/adjacency_graph.rb delete mode 100644 lib/puppet/gratr/base.rb delete mode 100644 lib/puppet/gratr/biconnected.rb delete mode 100644 lib/puppet/gratr/chinese_postman.rb delete mode 100644 lib/puppet/gratr/common.rb delete mode 100644 lib/puppet/gratr/comparability.rb delete mode 100644 lib/puppet/gratr/digraph.rb delete mode 100644 lib/puppet/gratr/digraph_distance.rb delete mode 100644 lib/puppet/gratr/dot.rb delete mode 100644 lib/puppet/gratr/edge.rb delete mode 100644 lib/puppet/gratr/graph.rb delete mode 100644 lib/puppet/gratr/graph_api.rb delete mode 100644 lib/puppet/gratr/import.rb delete mode 100644 lib/puppet/gratr/labels.rb delete mode 100644 lib/puppet/gratr/maximum_flow.rb delete mode 100644 lib/puppet/gratr/rdot.rb delete mode 100644 lib/puppet/gratr/search.rb delete mode 100644 lib/puppet/gratr/strong_components.rb delete mode 100644 lib/puppet/gratr/undirected_graph.rb delete mode 100644 lib/puppet/lock.rb diff --git a/lib/puppet.rb b/lib/puppet.rb index fd94424c0..6d73fe61e 100644 --- a/lib/puppet.rb +++ b/lib/puppet.rb @@ -2,7 +2,7 @@ require 'singleton' require 'facter' require 'puppet/error' -require 'puppet/event-loop' +require 'puppet/external/event-loop' require 'puppet/util' require 'puppet/log' require 'puppet/autoload' diff --git a/lib/puppet/base64.rb b/lib/puppet/base64.rb deleted file mode 100755 index 4030ad358..000000000 --- a/lib/puppet/base64.rb +++ /dev/null @@ -1,19 +0,0 @@ -# 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/event-loop.rb b/lib/puppet/event-loop.rb deleted file mode 100644 index 9d98cf0ee..000000000 --- a/lib/puppet/event-loop.rb +++ /dev/null @@ -1 +0,0 @@ -require "puppet/event-loop/event-loop" diff --git a/lib/puppet/event-loop/better-definers.rb b/lib/puppet/event-loop/better-definers.rb deleted file mode 100644 index 0af37da62..000000000 --- a/lib/puppet/event-loop/better-definers.rb +++ /dev/null @@ -1,367 +0,0 @@ -## 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/event-loop/event-loop.rb b/lib/puppet/event-loop/event-loop.rb deleted file mode 100644 index 5d78844ef..000000000 --- a/lib/puppet/event-loop/event-loop.rb +++ /dev/null @@ -1,355 +0,0 @@ -## 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/event-loop/better-definers" -require "puppet/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/event-loop/signal-system.rb b/lib/puppet/event-loop/signal-system.rb deleted file mode 100644 index f7fe9b52c..000000000 --- a/lib/puppet/event-loop/signal-system.rb +++ /dev/null @@ -1,220 +0,0 @@ -## 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/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/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$ diff --git a/lib/puppet/gratr.rb b/lib/puppet/gratr.rb deleted file mode 100644 index f59315d57..000000000 --- a/lib/puppet/gratr.rb +++ /dev/null @@ -1,33 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/gratr/base' -require 'puppet/gratr/digraph' -require 'puppet/gratr/undirected_graph' -require 'puppet/gratr/common' diff --git a/lib/puppet/gratr/adjacency_graph.rb b/lib/puppet/gratr/adjacency_graph.rb deleted file mode 100644 index a02ed0b2f..000000000 --- a/lib/puppet/gratr/adjacency_graph.rb +++ /dev/null @@ -1,257 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/gratr/edge' -require 'puppet/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/gratr/base.rb b/lib/puppet/gratr/base.rb deleted file mode 100644 index 72dded73f..000000000 --- a/lib/puppet/gratr/base.rb +++ /dev/null @@ -1,34 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -GRATR_VERSION = "0.4.1" - -module GRATR - class NoVertexError < IndexError; end - class NoEdgeError < IndexError; end -end diff --git a/lib/puppet/gratr/biconnected.rb b/lib/puppet/gratr/biconnected.rb deleted file mode 100644 index c976b2c04..000000000 --- a/lib/puppet/gratr/biconnected.rb +++ /dev/null @@ -1,116 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'set' - -module GRATR - module Graph - # Biconnected is a module for adding the biconnected algorithm to - # UndirectedGraphs - module Biconnected - - # biconnected computes the biconnected subgraphs - # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan - # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on - # Computing, 1(2):146-160, 1972 - # - # The output of the algorithm is a pair, the first value is an - # array of biconnected subgraphs. The second is the set of - # articulation vertices. - # - # A connected graph is biconnected if the removal of any single vertex - # (and all edges incident on that vertex) cannot disconnect the graph. - # More generally, the biconnected components of a graph are the maximal - # subsets of vertices such that the removal of a vertex from a particular - # component will not disconnect the component. Unlike connected components, - # vertices may belong to multiple biconnected components: those vertices - # that belong to more than one biconnected component are called articulation - # points or, equivalently, cut vertices. Articulation points are vertices - # whose removal would increase the number of connected components in the graph. - # Thus, a graph without articulation points is biconnected. - def biconnected - dfs_num = 0 - number = {}; predecessor = {}; low_point = {} - stack = []; result = []; articulation= [] - - root_vertex = Proc.new {|v| predecessor[v]=v } - enter_vertex = Proc.new {|u| number[u]=low_point[u]=(dfs_num+=1) } - tree_edge = Proc.new do |e| - stack.push(e) - predecessor[e.target] = e.source - end - back_edge = Proc.new do |e| - if e.target != predecessor[e.source] - stack.push(e) - low_point[e.source] = [low_point[e.source], number[e.target]].min - end - end - exit_vertex = Proc.new do |u| - parent = predecessor[u] - is_articulation_point = false - if number[parent] > number[u] - parent = predecessor[parent] - is_articulation_point = true - end - if parent == u - is_articulation_point = false if (number[u] + 1) == number[predecessor[u]] - else - low_point[parent] = [low_point[parent], low_point[u]].min - if low_point[u] >= number[parent] - if number[parent] > number[predecessor[parent]] - predecessor[u] = predecessor[parent] - predecessor[parent] = u - end - result << (component = self.class.new) - while number[stack[-1].source] >= number[u] - component.add_edge!(stack.pop) - end - component.add_edge!(stack.pop) - if stack.empty? - predecessor[u] = parent - predecessor[parent] = u - end - end - end - articulation << u if is_articulation_point - end - - # Execute depth first search - dfs({:root_vertex => root_vertex, - :enter_vertex => enter_vertex, - :tree_edge => tree_edge, - :back_edge => back_edge, - :exit_vertex => exit_vertex}) - - [result, articulation] - end # biconnected - - end # Biconnected - - end # Graph -end # GRATR diff --git a/lib/puppet/gratr/chinese_postman.rb b/lib/puppet/gratr/chinese_postman.rb deleted file mode 100644 index 5a9121e2e..000000000 --- a/lib/puppet/gratr/chinese_postman.rb +++ /dev/null @@ -1,123 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/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 - \ No newline at end of file diff --git a/lib/puppet/gratr/common.rb b/lib/puppet/gratr/common.rb deleted file mode 100644 index 72a7ed575..000000000 --- a/lib/puppet/gratr/common.rb +++ /dev/null @@ -1,73 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/gratr/edge' -require 'puppet/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 \ No newline at end of file diff --git a/lib/puppet/gratr/comparability.rb b/lib/puppet/gratr/comparability.rb deleted file mode 100644 index 1546fbefe..000000000 --- a/lib/puppet/gratr/comparability.rb +++ /dev/null @@ -1,92 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Graph - module Comparability - - # A comparability graph is an UndirectedGraph that has a transitive - # orientation. This returns a boolean that says if this graph - # is a comparability graph. - def comparability?() gamma_decomposition[1]; end - - # Returns an array with two values, the first being a hash of edges - # with a number containing their class assignment, the second valud - # is a boolean which states whether or not the graph is a - # comparability graph - # - # Complexity in time O(d*|E|) where d is the maximum degree of a vertex - # Complexity in space O(|V|+|E|) - def gamma_decomposition - k = 0; comparability=true; classification={} - edges.map {|edge| [edge.source,edge.target]}.each do |e| - if classification[e].nil? - k += 1 - classification[e] = k; classification[e.reverse] = -k - comparability &&= gratr_comparability_explore(e, k, classification) - end - end; [classification, comparability] - end - - # Returns one of the possible transitive orientations of - # the UndirectedGraph as a Digraph - def transitive_orientation(digraph_class=Digraph) - raise NotImplementError - end - - private - - # Taken from Figure 5.10, on pg. 130 of Martin Golumbic's, _Algorithmic_Graph_ - # _Theory_and_Perfect_Graphs. - def gratr_comparability_explore(edge, k, classification, space='') - ret = gratr_comparability_explore_inner(edge, k, classification, :forward, space) - gratr_comparability_explore_inner(edge.reverse, k, classification, :backward, space) && ret - end - - def gratr_comparability_explore_inner(edge, k, classification, direction,space) - comparability = true - adj_target = adjacent(edge[1]) - adjacent(edge[0]).select do |mt| - (classification[[edge[1],mt]] || k).abs < k or - not adj_target.any? {|adj_t| adj_t == mt} - end.each do |m| - e = (direction == :forward) ? [edge[0], m] : [m,edge[0]] - if classification[e].nil? - classification[e] = k - classification[e.reverse] = -k - comparability = gratr_comparability_explore(e, k, classification, ' '+space) && comparability - elsif classification[e] == -k - classification[e] = k - gratr_comparability_explore(e, k, classification, ' '+space) - comparability = false - end - end; comparability - end # gratr_comparability_explore_inner - - end # Comparability - end # Graph -end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/digraph.rb b/lib/puppet/gratr/digraph.rb deleted file mode 100644 index ae875376d..000000000 --- a/lib/puppet/gratr/digraph.rb +++ /dev/null @@ -1,116 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -require 'puppet/gratr/edge' -require 'puppet/gratr/graph' -require 'puppet/gratr/search' -require 'puppet/gratr/adjacency_graph' -require 'puppet/gratr/strong_components' -require 'puppet/gratr/digraph_distance' -require 'puppet/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/gratr/digraph_distance.rb b/lib/puppet/gratr/digraph_distance.rb deleted file mode 100644 index 6f90384e7..000000000 --- a/lib/puppet/gratr/digraph_distance.rb +++ /dev/null @@ -1,185 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Graph - module Distance - - # Shortest path from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 - # - # Requires that the graph be acyclic. If the graph is not - # acyclic, then see dijkstras_algorithm or bellman_ford_moore - # for possible solutions. - # - # start is the starting vertex - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # Complexity O(n+m) - def shortest_path(start, weight=nil, zero=0) - dist = {start => zero}; path = {} - topsort(start) do |vi| - next if vi == start - dist[vi],path[vi] = adjacent(vi, :direction => :in).map do |vj| - [dist[vj] + cost(vj,vi,weight), vj] - end.min {|a,b| a[0] <=> b[0]} - end; - dist.keys.size == vertices.size ? [dist,path] : nil - end # shortest_path - - # Algorithm from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 - # - # Finds the distances from a given vertex s in a weighted digraph - # to the rest of the vertices, provided all the weights of arcs - # are non-negative. If negative arcs exist in the graph, two - # basic options exist, 1) modify all weights to be positive by - # using an offset, or 2) use the bellman_ford_moore algorithm. - # Also if the graph is acyclic, use the shortest_path algorithm. - # - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # O(n*log(n) + m) complexity - def dijkstras_algorithm(s, weight = nil, zero = 0) - q = vertices; distance = { s => zero }; path = {} - while not q.empty? - v = (q & distance.keys).inject(nil) {|a,k| (!a.nil?) && (distance[a] < distance[k]) ? a : k} - q.delete(v) - (q & adjacent(v)).each do |u| - c = cost(v,u,weight) - if distance[u].nil? or distance[u] > (c+distance[v]) - distance[u] = c + distance[v] - path[u] = v - end - end - end; [distance, path] - end # dijkstras_algorithm - - # Algorithm from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58 - # - # Finds the distances from a given vertex s in a weighted digraph - # to the rest of the vertices, provided the graph has no negative cycle. - # If no negative weights exist, then dijkstras_algorithm is more - # efficient in time and space. Also if the graph is acyclic, use the - # shortest_path algorithm. - # - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # O(nm) complexity - def bellman_ford_moore(start, weight = nil, zero = 0) - distance = { start => zero }; path = {} - 2.upto(vertices.size) do - edges.each do |e| - u,v = e[0],e[1] - unless distance[u].nil? - c = cost(u, v, weight)+distance[u] - if distance[v].nil? or c < distance[v] - distance[v] = c - path[v] = u - end - end - end - end; [distance, path] - end # bellman_ford_moore - - # This uses the Floyd-Warshall algorithm to efficiently find - # and record shortest paths at the same time as establishing - # the costs for all vertices in a graph. - # See, S.Skiena, "The Algorithm Design Manual", - # Springer Verlag, 1998 for more details. - # - # Returns a pair of matrices and a hash of delta values. - # The matrices will be indexed by two vertices and are - # implemented as a Hash of Hashes. The first matrix is the cost, the second - # matrix is the shortest path spanning tree. The delta (difference of number - # of in edges and out edges) is indexed by vertex. - # - # weight specifies how an edge weight is determined, if it's a - # Proc the Edge is passed to it, if it's nil it will just use - # the value in the label for the Edge, otherwise the weight is - # determined by applying the [] operator to the value in the - # label for the Edge - # - # zero defines the zero value in the math system used. Defaults - # of course, to 0. This allows for no assumptions to be made - # about the math system and fully functional duck typing. - # - # O(n^3) complexity in time. - def floyd_warshall(weight=nil, zero=0) - c = Hash.new {|h,k| h[k] = Hash.new} - path = Hash.new {|h,k| h[k] = Hash.new} - delta = Hash.new {|h,k| h[k] = 0} - edges.each do |e| - delta[e.source] += 1 - delta[e.target] -= 1 - path[e.source][e.target] = e.target - c[e.source][e.target] = cost(e, weight) - end - vertices.each do |k| - vertices.each do |i| - if c[i][k] - vertices.each do |j| - if c[k][j] && - (c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j])) - path[i][j] = path[i][k] - c[i][j] = c[i][k] + c[k][j] - return nil if i == j and c[i][j] < zero - end - end - end - end - end - [c, path, delta] - end # floyd_warshall - - end # Distance - end # Graph -end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/dot.rb b/lib/puppet/gratr/dot.rb deleted file mode 100644 index fbf4fb073..000000000 --- a/lib/puppet/gratr/dot.rb +++ /dev/null @@ -1,90 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ -# -# Minimal Dot support, based on Dave Thomas's dot module (included in rdoc). -# rdot.rb is a modified version which also contains support for undirected -# graphs. - -require 'puppet/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/gratr/edge.rb b/lib/puppet/gratr/edge.rb deleted file mode 100644 index 8470e5458..000000000 --- a/lib/puppet/gratr/edge.rb +++ /dev/null @@ -1,145 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - - # Edge includes classes for representing egdes of directed and - # undirected graphs. There is no need for a Vertex class, because any ruby - # object can be a vertex of a graph. - # - # Edge's base is a Struct with a :source, a :target and a :label - Struct.new("EdgeBase",:source, :target, :label) - - class Edge < Struct::EdgeBase - - def initialize(p_source,p_target,p_label=nil) - super(p_source, p_target, p_label) - end - - # Ignore labels for equality - def eql?(other) self.class == other.class and target==other.target and source==other.source; end - - # Alias for eql? - alias == eql? - - # Returns (v,u) if self == (u,v). - def reverse() self.class.new(target, source, label); end - - # Sort support - def <=>(rhs) [source,target] <=> [rhs.source,rhs.target]; end - - # Edge.new[1,2].to_s => "(1-2 'label')" - def to_s - l = label ? " '#{label.to_s}'" : '' - "(#{source}-#{target}#{l})" - end - - # Hash is defined in such a way that label is not - # part of the hash value - def hash() source.hash ^ (target.hash+1); end - - # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] - def self.[](p_source, p_target, p_label=nil) - new(p_source, p_target, p_label) - end - - def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{label.inspect}]"; end - - end - - # An undirected edge is simply an undirected pair (source, target) used in - # undirected graphs. UndirectedEdge[u,v] == UndirectedEdge[v,u] - class UndirectedEdge < Edge - - # Equality allows for the swapping of source and target - def eql?(other) super or (self.class == other.class and target==other.source and source==other.target); end - - # Alias for eql? - alias == eql? - - # Hash is defined such that source and target can be reversed and the - # hash value will be the same - # - # This will cause problems with self loops - def hash() source.hash ^ target.hash; end - - # Sort support - def <=>(rhs) - [[source,target].max,[source,target].min] <=> - [[rhs.source,rhs.target].max,[rhs.source,rhs.target].min] - end - - # UndirectedEdge[1,2].to_s == "(1=2 'label)" - def to_s - l = label ? " '#{label.to_s}'" : '' - s = source.to_s - t = target.to_s - "(#{[s,t].min}=#{[s,t].max}#{l})" - end - - end - - # This module provides for internal numbering of edges for differentiating between mutliple edges - module EdgeNumber - - attr_accessor :number # Used to differentiate between mutli-edges - - def initialize(p_source,p_target,p_number,p_label=nil) - self.number = p_number - super(p_source, p_target, p_label) - end - - # Returns (v,u) if self == (u,v). - def reverse() self.class.new(target, source, number, label); end - def hash() super ^ number.hash; end - def to_s() super + "[#{number}]"; end - def <=>(rhs) (result = super(rhs)) == 0 ? number <=> rhs.number : result; end - def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{number.inspect},#{label.inspect}]"; end - def eql?(rhs) super(rhs) and (rhs.number.nil? or number.nil? or number == rhs.number); end - def ==(rhs) eql?(rhs); end - - # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] - def self.included(cl) - - def cl.[](p_source, p_target, p_number=nil, p_label=nil) - new(p_source, p_target, p_number, p_label) - end - end - - end - - class MultiEdge < Edge - include EdgeNumber - end - - class MultiUndirectedEdge < UndirectedEdge - include EdgeNumber - end - -end diff --git a/lib/puppet/gratr/graph.rb b/lib/puppet/gratr/graph.rb deleted file mode 100644 index 44c8bc4d8..000000000 --- a/lib/puppet/gratr/graph.rb +++ /dev/null @@ -1,303 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/gratr/edge' -require 'puppet/gratr/labels' -require 'puppet/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/gratr/graph_api.rb b/lib/puppet/gratr/graph_api.rb deleted file mode 100644 index 26d18958a..000000000 --- a/lib/puppet/gratr/graph_api.rb +++ /dev/null @@ -1,83 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - - # This defines the minimum set of functions required to make a graph class that can - # use the algorithms defined by this library - module GraphAPI - - # Is the graph directed? - # - # This method must be implemented by the specific graph class - def directed?() raise NotImplementedError; end - - # Add a vertex to the Graph and return the Graph - # An additional label l can be specified as well - # - # This method must be implemented by the specific graph class - def add_vertex!(v,l=nil) raise NotImplementedError; end - - # Add an edge to the Graph and return the Graph - # u can be an object of type GRATR::Edge or u,v specifies - # a source, target pair. The last parameter is an optional label - # - # This method must be implemented by the specific graph class - def add_edge!(u,v=nil,l=nil) raise NotImplementedError; end - - # Remove a vertex to the Graph and return the Graph - # - # This method must be implemented by the specific graph class - def remove_vertex!(v) raise NotImplementedError; end - - # Remove an edge from the Graph and return the Graph - # - # Can be a type of GRATR::Edge or a source and target - # This method must be implemented by the specific graph class - def remove_edge!(u,v=nil) raise NotImplementedError; end - - # Return the array of vertices. - # - # This method must be implemented by the specific graph class - def vertices() raise NotImplementedError; end - - # Return the array of edges. - # - # This method must be implemented by the specific graph class - def edges() raise NotImplementedError; end - - # Returns the edge class - def edge_class() raise NotImplementedError; end - - # Return the chromatic number for this graph - # This is currently incomplete and in some cases will be NP-complete - # FIXME: Should this even be here? My gut feeling is no... - def chromatic_number() raise NotImplementedError; end - end -end \ No newline at end of file diff --git a/lib/puppet/gratr/import.rb b/lib/puppet/gratr/import.rb deleted file mode 100644 index 7be8fb3f3..000000000 --- a/lib/puppet/gratr/import.rb +++ /dev/null @@ -1,44 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/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/gratr/labels.rb b/lib/puppet/gratr/labels.rb deleted file mode 100644 index 7e53df404..000000000 --- a/lib/puppet/gratr/labels.rb +++ /dev/null @@ -1,90 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Labels - # Return a label for an edge or vertex - def [](u) (u.kind_of? GRATR::Edge) ? edge_label(u) : vertex_label(u); end - - # Set a label for an edge or vertex - def []= (u, value) (u.kind_of? GRATR::Edge) ? edge_label_set(u,value) : vertex_label_set(u, value); end - - # Delete a label entirely - def delete_label(u) (u.kind_of? GRATR::Edge) ? edge_label_delete(u) : vertex_label_delete(u); end - - # Get the label for an edge - def vertex_label(v) vertex_label_dict[v]; end - - # Set the label for an edge - def vertex_label_set(v, l) vertex_label_dict[v] = l; self; end - - # Get the label for an edge - def edge_label(u,v=nil,n=nil) - u = edge_convert(u,v,n) - edge_label_dict[u] - end - - # Set the label for an edge - def edge_label_set(u, v=nil, l=nil, n=nil) - u.kind_of?(GRATR::Edge) ? l = v : u = edge_convert(u,v,n) - edge_label_dict[u] = l; self - end - - # Delete all graph labels - def clear_all_labels() @vertex_labels = {}; @edge_labels = {}; end - - # Delete an edge label - def edge_label_delete(u, v=nil, n=nil) - u = edge_convert(u,v,n) - edge_label_dict.delete(u) - end - - # Delete a vertex label - def vertex_label_delete(v) vertex_label_dict.delete(v); end - - protected - - def vertex_label_dict() @vertex_labels ||= {}; end - def edge_label_dict() @edge_labels ||= {}; end - - # A generic cost function. It either calls the weight function with and edge - # constructed from the two nodes, or calls the [] operator of the label - # when given a value. If no weight value is specified, the label itself is - # treated as the cost value. - # - # Note: This function will not work for Pseudo or Multi graphs at present. - def cost(u,v=nil,weight=nil) - u.kind_of?(Edge) ? weight = v : u = edge_class[u,v] - case weight - when Proc : weight.call(u) - when nil : self[u] - else self[u][weight] - end - end - - end -end diff --git a/lib/puppet/gratr/maximum_flow.rb b/lib/puppet/gratr/maximum_flow.rb deleted file mode 100644 index 7b3ef9b2f..000000000 --- a/lib/puppet/gratr/maximum_flow.rb +++ /dev/null @@ -1,64 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - - module Graph - - module MaximumFlow - - # Maximum flow, it returns an array with the maximum flow and a hash of flow per edge - # Currently a highly inefficient implementation, FIXME, This should use Goldberg and Tarjan's method. - def maximum_flow(s, t, capacity = nil, zero = 0) - flow = Hash.new(zero) - available = Hash.new(zero) - total = zero - edges.each {|e| available[e] = cost(e,capacity)} - adj_positive = Proc.new do |u| - adjacent(u).select {|r| available[edge_class[u,r]] > zero} - end - while (tree = bfs_tree_from_vertex(start))[t] - route = [t] - while route[-1] != s - route << tree[route[route[-1]]] - raise ArgumentError, "No route from #{s} to #{t} possible" - end; route.reverse - amt = route.map {|e| available[e]}.min - route.each do |e| - flow[e] += amt - available[e] -= amt - end - total += amt - end - - [total, flow] - end - - end # MaximumFlow - end # Graph -end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/rdot.rb b/lib/puppet/gratr/rdot.rb deleted file mode 100644 index 4ce545ae6..000000000 --- a/lib/puppet/gratr/rdot.rb +++ /dev/null @@ -1,327 +0,0 @@ -# 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/gratr/search.rb b/lib/puppet/gratr/search.rb deleted file mode 100644 index 3206ec5d9..000000000 --- a/lib/puppet/gratr/search.rb +++ /dev/null @@ -1,409 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - module Graph - module Search - - # Options are mostly callbacks passed in as a hash. - # The following are valid, anything else is ignored - # :enter_vertex => Proc Called upon entry of a vertex - # :exit_vertex => Proc Called upon exit of a vertex - # :root_vertex => Proc Called when a vertex the a root of a tree - # :start_vertex => Proc Called for the first vertex of the search - # :examine_edge => Proc Called when an edge is examined - # :tree_edge => Proc Called when the edge is a member of the tree - # :back_edge => Proc Called when the edge is a back edge - # :forward_edge => Proc Called when the edge is a forward edge - # :adjacent => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms - # - # :start => Vertex Specifies the vertex to start search from - # - # If a &block is specified it defaults to :enter_vertex - # - # Returns the list of vertexes as reached by enter_vertex - # This allows for calls like, g.bfs.each {|v| ...} - # - # Can also be called like bfs_examine_edge {|e| ... } or - # dfs_back_edge {|e| ... } for any of the callbacks - # - # A full example usage is as follows: - # - # ev = Proc.new {|x| puts "Enter Vertex #{x}"} - # xv = Proc.new {|x| puts "Exit Vertex #{x}"} - # sv = Proc.new {|x| puts "Start Vertex #{x}"} - # ee = Proc.new {|x| puts "Examine Edge #{x}"} - # te = Proc.new {|x| puts "Tree Edge #{x}"} - # be = Proc.new {|x| puts "Back Edge #{x}"} - # fe = Proc.new {|x| puts "Forward Edge #{x}"} - # Digraph[1,2,2,3,3,4].dfs({ - # :enter_vertex => ev, - # :exit_vertex => xv, - # :start_vertex => sv, - # :examine_edge => ee, - # :tree_edge => te, - # :back_edge => be, - # :forward_edge => fe }) - # - # Which outputs: - # - # Start Vertex 1 - # Enter Vertex 1 - # Examine Edge (1=2) - # Tree Edge (1=2) - # Enter Vertex 2 - # Examine Edge (2=3) - # Tree Edge (2=3) - # Enter Vertex 3 - # Examine Edge (3=4) - # Tree Edge (3=4) - # Enter Vertex 4 - # Examine Edge (1=4) - # Back Edge (1=4) - # Exit Vertex 4 - # Exit Vertex 3 - # Exit Vertex 2 - # Exit Vertex 1 - def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end - - # See options for bfs method - def dfs(options={}, &block) gratr_search_helper(:pop, options, &block); end - - # Routine to compute a spanning forest for the given search method - # Returns two values, first is a hash of predecessors and second an array of root nodes - def spanning_forest(start, routine) - predecessor = {} - roots = [] - te = Proc.new {|e| predecessor[e.target] = e.source} - rv = Proc.new {|v| roots << v} - method(routine).call :start => start, :tree_edge => te, :root_vertex => rv - [predecessor, roots] - end - - # Return the dfs spanning forest for the given start node, see spanning_forest - def dfs_spanning_forest(start) spanning_forest(start, :dfs); end - - # Return the bfs spanning forest for the given start node, see spanning_forest - def bfs_spanning_forest(start) spanning_forest(start, :bfs); end - - # Returns a hash of predecessors in a tree rooted at the start node. If this is a connected graph - # then it will be a spanning tree and contain all vertices. An easier way to tell if it's a spanning tree is to - # use a spanning_forest call and check if there is a single root node. - def tree_from_vertex(start, routine) - predecessor={} - correct_tree = false - te = Proc.new {|e| predecessor[e.target] = e.source if correct_tree} - rv = Proc.new {|v| correct_tree = (v == start)} - method(routine).call :start => start, :tree_edge => te, :root_vertex => rv - predecessor - end - - # Returns a hash of predecessors for the depth first search tree rooted at the given node - def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end - - # Returns a hash of predecessors for the depth first search tree rooted at the given node - def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end - - # An inner class used for greater efficiency in lexicograph_bfs - # - # Original desgn taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg, 87-89 - class LexicographicQueue - - # Called with the initial values (array) - def initialize(values) - @node = Struct.new(:back, :forward, :data) - @node.class_eval { def hash() @hash; end; @@cnt=0 } - @set = {} - @tail = @node.new(nil, nil, Array.new(values)) - @tail.instance_eval { @hash = (@@cnt+=1) } - values.each {|a| @set[a] = @tail} - end - - # Pop an entry with maximum lexical value from queue - def pop() - return nil unless @tail - value = @tail[:data].pop - @tail = @tail[:forward] while @tail and @tail[:data].size == 0 - @set.delete(value); value - end - - # Increase lexical value of given values (array) - def add_lexeme(values) - fix = {} - values.select {|v| @set[v]}.each do |w| - sw = @set[w] - if fix[sw] - s_prime = sw[:back] - else - s_prime = @node.new(sw[:back], sw, []) - s_prime.instance_eval { @hash = (@@cnt+=1) } - @tail = s_prime if @tail == sw - sw[:back][:forward] = s_prime if sw[:back] - sw[:back] = s_prime - fix[sw] = true - end - s_prime[:data] << w - sw[:data].delete(w) - @set[w] = s_prime - end - fix.keys.select {|n| n[:data].size == 0}.each do |e| - e[:forward][:back] = e[:back] if e[:forward] - e[:back][:forward] = e[:forward] if e[:back] - end - end - - end - - # Lexicographic breadth-first search, the usual queue of vertices - # is replaced by a queue of unordered subsets of the vertices, - # which is sometimes refined but never reordered. - # - # Originally developed by Rose, Tarjan, and Leuker, "Algorithmic - # aspects of vertex elimination on graphs", SIAM J. Comput. 5, 266-283 - # MR53 #12077 - # - # Implementation taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg, 84-90 - def lexicograph_bfs(&block) - lex_q = GRATR::Graph::Search::LexicographicQueue.new(vertices) - result = [] - num_vertices.times do - v = lex_q.pop - result.unshift(v) - lex_q.add_lexeme(adjacent(v)) - end - result.each {|r| block.call(r)} if block - result - end - - - # A* Heuristic best first search - # - # start is the starting vertex for the search - # - # func is a Proc that when passed a vertex returns the heuristic - # weight of sending the path through that node. It must always - # be equal to or less than the true cost - # - # options are mostly callbacks passed in as a hash, the default block is - # :discover_vertex and weight is assumed to be the label for the Edge. - # The following options are valid, anything else is ignored. - # - # * :weight => can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # * :discover_vertex => Proc invoked when a vertex is first discovered - # and is added to the open list. - # * :examine_vertex => Proc invoked when a vertex is popped from the - # queue (i.e., it has the lowest cost on the open list). - # * :examine_edge => Proc invoked on each out-edge of a vertex - # immediately after it is examined. - # * :edge_relaxed => Proc invoked on edge (u,v) if d[u] + w(u,v) < d[v]. - # * :edge_not_relaxed=> Proc invoked if the edge is not relaxed (see above). - # * :black_target => Proc invoked when a vertex that is on the closed - # list is "rediscovered" via a more efficient path, and is re-added - # to the OPEN list. - # * :finish_vertex => Proc invoked on a vertex when it is added to the - # closed list, which happens after all of its out edges have been - # examined. - # - # Returns array of nodes in path, or calls block on all nodes, - # upon failure returns nil - # - # Can also be called like astar_examine_edge {|e| ... } or - # astar_edge_relaxed {|e| ... } for any of the callbacks - # - # The criteria for expanding a vertex on the open list is that it has the - # lowest f(v) = g(v) + h(v) value of all vertices on open. - # - # The time complexity of A* depends on the heuristic. It is exponential - # in the worst case, but is polynomial when the heuristic function h - # meets the following condition: |h(x) - h*(x)| < O(log h*(x)) where h* - # is the optimal heuristic, i.e. the exact cost to get from x to the goal. - # - # Also see: http://en.wikipedia.org/wiki/A-star_search_algorithm - # - def astar(start, goal, func, options, &block) - options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" - options.instance_eval "def handle_edge(sym,u,v) self[sym].call(#{edge_class}[u,v]) if self[sym]; end" - - d = { start => 0 } - f = { start => func.call(start) } - color = {start => :gray} - p = Hash.new {|k| p[k] = k} - queue = [start] - block.call(start) if block - until queue.empty? - u = queue.pop - options.handle_vertex(:examine_vertex, u) - adjacent(u).each do |v| - e = edge_class[u,v] - options.handle_edge(:examine_edge, u, v) - w = cost(e, options[:weight]) - raise ArgumentError unless w - if d[v].nil? or (w + d[u]) < d[v] - options.handle_edge(:edge_relaxed, u, v) - d[v] = w + d[u] - f[v] = d[v] + func.call(u) - p[v] = u - unless color[v] == :gray - options.handle_vertex(:black_target, v) if color[v] == :black - color[v] = :gray - options.handle_vertex(:discover_vertex, v) - queue << v - block.call(v) if block - return [start]+queue if v == goal - end - else - options.handle_edge(:edge_not_relaxed, u, v) - end - end # adjacent(u) - color[u] = :black - options.handle_vertex(:finish_vertex,u) - end # queue.empty? - nil # failure, on fall through - end # astar - - # Best first has all the same options as astar with func set to h(v) = 0. - # There is an additional option zero which should be defined to zero - # for the operation '+' on the objects used in the computation of cost. - # The parameter zero defaults to 0. - def best_first(start, goal, options, zero=0, &block) - func = Proc.new {|v| zero} - astar(start, goal, func, options, &block) - end - - alias_method :pre_search_method_missing, :method_missing # :nodoc: - def method_missing(sym,*args, &block) # :nodoc: - m1=/^dfs_(\w+)$/.match(sym.to_s) - dfs((args[0] || {}).merge({m1.captures[0].to_sym => block})) if m1 - m2=/^bfs_(\w+)$/.match(sym.to_s) - bfs((args[0] || {}).merge({m2.captures[0].to_sym => block})) if m2 - pre_search_method_missing(sym, *args, &block) unless m1 or m2 - end - - private - - def gratr_search_helper(op, options={}, &block) # :nodoc: - return nil if size == 0 - result = [] - # Create options hash that handles callbacks - options = {:enter_vertex => block, :start => to_a[0]}.merge(options) - options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" - options.instance_eval "def handle_edge(sym,e) self[sym].call(e) if self[sym]; end" - # Create waiting list that is a queue or stack depending on op specified. - # First entry is the start vertex. - waiting = [options[:start]] - waiting.instance_eval "def next() #{op.to_s}; end" - # Create color map with all set to unvisited except for start vertex - # will be set to waiting - color_map = vertices.inject({}) {|a,v| a[v] = :unvisited; a} - color_map.merge!(waiting[0] => :waiting) - options.handle_vertex(:start_vertex, waiting[0]) - options.handle_vertex(:root_vertex, waiting[0]) - # Perform the actual search until nothing is waiting - until waiting.empty? - # Loop till the search iterator exhausts the waiting list - visited_edges={} # This prevents retraversing edges in undirected graphs - until waiting.empty? - gratr_search_iteration(options, waiting, color_map, visited_edges, result, op == :pop) - end - # Waiting list is exhausted, see if a new root vertex is available - u=color_map.detect {|key,value| value == :unvisited} - waiting.push(u[0]) if u - options.handle_vertex(:root_vertex, u[0]) if u - end; result - end - - def gratr_search_iteration(options, waiting, color_map, visited_edges, result, recursive=false) # :nodoc: - # Get the next waiting vertex in the list - u = waiting.next - options.handle_vertex(:enter_vertex,u) - result << u - # Examine all adjacent outgoing edges, not previously traversed - adj_proc = options[:adjacent] || self.method(:adjacent).to_proc - adj_proc.call(u,:type => :edges, :direction => :out).reject {|w| visited_edges[w]}.each do |e| - e = e.reverse unless directed? or e.source == u # Preserves directionality where required - v = e.target - options.handle_edge(:examine_edge, e) - visited_edges[e]=true - case color_map[v] - # If it's unvisited it goes into the waiting list - when :unvisited - options.handle_edge(:tree_edge, e) - color_map[v] = :waiting - waiting.push(v) - # If it's recursive (i.e. dfs) then call self - gratr_search_iteration(options, waiting, color_map, visited_edges, result, true) if recursive - when :waiting - options.handle_edge(:back_edge, e) - else - options.handle_edge(:forward_edge, e) - end - end - # Finished with this vertex - options.handle_vertex(:exit_vertex, u) - color_map[u] = :visited - end - - public - # Topological Sort Iterator - # - # The topological sort algorithm creates a linear ordering of the vertices - # such that if edge (u,v) appears in the graph, then u comes before v in - # the ordering. The graph must be a directed acyclic graph (DAG). - # - # The iterator can also be applied to undirected graph or to a DG graph - # which contains a cycle. In this case, the Iterator does not reach all - # vertices. The implementation of acyclic? and cyclic? uses this fact. - # - # Can be called with a block as a standard Ruby iterator, or it can - # be used directly as it will return the result as an Array - def topsort(start = nil, &block) - result = [] - go = true - back = Proc.new {|e| go = false } - push = Proc.new {|v| result.unshift(v) if go} - start ||= vertices[0] - dfs({:exit_vertex => push, :back_edge => back, :start => start}) - result.each {|v| block.call(v)} if block; result - end - - # Returns true if a graph contains no cycles, false otherwise - def acyclic?() topsort.size == size; end - - # Returns false if a graph contains no cycles, true otherwise - def cyclic?() not acyclic?; end - - - end # Search - end # Graph -end # GRATR diff --git a/lib/puppet/gratr/strong_components.rb b/lib/puppet/gratr/strong_components.rb deleted file mode 100644 index 796ae16bb..000000000 --- a/lib/puppet/gratr/strong_components.rb +++ /dev/null @@ -1,127 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'set' - -module GRATR - module Graph - module StrongComponents - # strong_components computes the strongly connected components - # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan - # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on - # Computing, 1(2):146-160, 1972 - # - # The output of the algorithm is an array of components where is - # component is an array of vertices - # - # A strongly connected component of a directed graph G=(V,E) is a maximal - # set of vertices U which is in V such that for every pair of - # vertices u and v in U, we have both a path from u to v - # and path from v to u. That is to say that u and v are reachable - # from each other. - # - def strong_components - - dfs_num = 0 - stack = []; result = []; root = {}; comp = {}; number = {} - - # Enter vertex callback - enter = Proc.new do |v| - root[v] = v - comp[v] = :new - number[v] = (dfs_num += 1) - stack.push(v) - end - - # Exit vertex callback - exit = Proc.new do |v| - adjacent(v).each do |w| - if comp[w] == :new - root[v] = (number[root[v]] < number[root[w]] ? root[v] : root[w]) - end - end - if root[v] == v - component = [] - begin - w = stack.pop - comp[w] = :assigned - component << w - end until w == v - result << component - end - end - - # Execute depth first search - dfs({:enter_vertex => enter, :exit_vertex => exit}); result - - end # strong_components - - # Returns a condensation graph of the strongly connected components - # Each node is an array of nodes from the original graph - def condensation - sc = strong_components - cg = self.class.new - map = sc.inject({}) do |a,c| - c.each {|v| a[v] = c }; a - end - sc.each do |c| - c.each do |v| - adjacent(v).each {|v| cg.add_edge!(c, map[v]) unless c == map[v]} - end - end; cg - end - - # Compute transitive closure of a graph. That is any node that is reachable - # along a path is added as a directed edge. - def transitive_closure! - cgtc = condensation.gratr_inner_transitive_closure! - cgtc.each do |cgv| - cgtc.adjacent(cgv).each do |adj| - cgv.each do |u| - adj.each {|v| add_edge!(u,v)} - end - end - end; self - end - - # This returns the transitive closure of a graph. The original graph - # is not changed. - def transitive_closure() self.class.new(self).transitive_closure!; end - - private - def gratr_inner_transitive_closure! # :nodoc: - topsort.reverse.each do |u| - adjacent(u).each do |v| - adjacent(v).each {|w| add_edge!(u,w) unless edge?(u,w)} - end - end; self - end - end # StrongComponens - - end # Graph -end # GRATR diff --git a/lib/puppet/gratr/undirected_graph.rb b/lib/puppet/gratr/undirected_graph.rb deleted file mode 100644 index e96b0f351..000000000 --- a/lib/puppet/gratr/undirected_graph.rb +++ /dev/null @@ -1,153 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/gratr/adjacency_graph' -require 'puppet/gratr/search' -require 'puppet/gratr/biconnected' -require 'puppet/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/lock.rb b/lib/puppet/lock.rb deleted file mode 100644 index d873d1bbf..000000000 --- a/lib/puppet/lock.rb +++ /dev/null @@ -1,64 +0,0 @@ -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$ diff --git a/lib/puppet/networkclient.rb b/lib/puppet/networkclient.rb index c419431be..8951c3ccb 100644 --- a/lib/puppet/networkclient.rb +++ b/lib/puppet/networkclient.rb @@ -8,7 +8,7 @@ require 'puppet/transportable' require 'puppet/metric' require 'puppet/daemon' require 'puppet/server' -require 'puppet/base64' +require 'puppet/external/base64' $noclientnetworking = false begin diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb index f247f4391..af8e720cb 100644 --- a/lib/puppet/pgraph.rb +++ b/lib/puppet/pgraph.rb @@ -3,9 +3,9 @@ # Created by Luke A. Kanies on 2006-11-24. # Copyright (c) 2006. All rights reserved. -require 'puppet/gratr/digraph' -require 'puppet/gratr/import' -require 'puppet/gratr/dot' +require 'puppet/external/gratr/digraph' +require 'puppet/external/gratr/import' +require 'puppet/external/gratr/dot' require 'puppet/relationship' # This class subclasses a graph class in order to handle relationships diff --git a/lib/puppet/relationship.rb b/lib/puppet/relationship.rb index 15f67b384..c848340d7 100644 --- a/lib/puppet/relationship.rb +++ b/lib/puppet/relationship.rb @@ -3,7 +3,7 @@ # Created by Luke A. Kanies on 2006-11-24. # Copyright (c) 2006. All rights reserved. -require 'puppet/gratr' +require 'puppet/external/gratr' # subscriptions are permanent associations determining how different # objects react to an event diff --git a/lib/puppet/server/filebucket.rb b/lib/puppet/server/filebucket.rb index 020c42518..56d994366 100755 --- a/lib/puppet/server/filebucket.rb +++ b/lib/puppet/server/filebucket.rb @@ -7,7 +7,7 @@ require 'xmlrpc/server' require 'xmlrpc/client' require 'facter' require 'digest/md5' -require 'puppet/base64' +require 'puppet/external/base64' module Puppet class Server diff --git a/lib/puppet/util.rb b/lib/puppet/util.rb index 9e40251e2..1242372ac 100644 --- a/lib/puppet/util.rb +++ b/lib/puppet/util.rb @@ -1,7 +1,7 @@ # A module to collect utility functions. require 'sync' -require 'puppet/lock' +require 'puppet/external/lock' module Puppet # A command failed to execute. -- cgit