summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/puppet/gratr.rb33
-rw-r--r--lib/puppet/gratr/adjacency_graph.rb229
-rw-r--r--lib/puppet/gratr/base.rb34
-rw-r--r--lib/puppet/gratr/biconnected.rb116
-rw-r--r--lib/puppet/gratr/chinese_postman.rb123
-rw-r--r--lib/puppet/gratr/common.rb73
-rw-r--r--lib/puppet/gratr/comparability.rb92
-rw-r--r--lib/puppet/gratr/digraph.rb113
-rw-r--r--lib/puppet/gratr/digraph_distance.rb185
-rw-r--r--lib/puppet/gratr/dot.rb90
-rw-r--r--lib/puppet/gratr/edge.rb145
-rw-r--r--lib/puppet/gratr/graph.rb303
-rw-r--r--lib/puppet/gratr/graph_api.rb83
-rw-r--r--lib/puppet/gratr/import.rb44
-rw-r--r--lib/puppet/gratr/labels.rb90
-rw-r--r--lib/puppet/gratr/maximum_flow.rb64
-rw-r--r--lib/puppet/gratr/rdot.rb327
-rw-r--r--lib/puppet/gratr/search.rb409
-rw-r--r--lib/puppet/gratr/strong_components.rb127
-rw-r--r--lib/puppet/gratr/undirected_graph.rb153
-rw-r--r--lib/puppet/util/graph.rb58
-rwxr-xr-xtest/util/graph.rb135
22 files changed, 3026 insertions, 0 deletions
diff --git a/lib/puppet/gratr.rb b/lib/puppet/gratr.rb
new file mode 100644
index 000000000..f59315d57
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..930e2abac
--- /dev/null
+++ b/lib/puppet/gratr/adjacency_graph.rb
@@ -0,0 +1,229 @@
+#--
+# 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)
+ n = u.number if u.class.include? EdgeNumber and n.nil?
+ u, v, l = u.source, u.target, u.label if u.kind_of? GRATR::Edge
+ return self if not @allow_loops and u == v
+ n = (@next_edge_number+=1) unless n if @parallel_edges
+ add_vertex!(u); add_vertex!(v)
+ @vertex_dict[u].add(v)
+ (@edge_number[u] ||= @edgelist_class.new).add(n) if @parallel_edges
+ unless directed?
+ @vertex_dict[v].add(u)
+ (@edge_number[v] ||= @edgelist_class.new).add(n) if @parallel_edges
+ end
+ self[n ? edge_class[u,v,n] : edge_class[u,v]] = l if l
+ 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={})
+ 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
new file mode 100644
index 000000000..72dded73f
--- /dev/null
+++ b/lib/puppet/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/gratr/biconnected.rb b/lib/puppet/gratr/biconnected.rb
new file mode 100644
index 000000000..c976b2c04
--- /dev/null
+++ b/lib/puppet/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/gratr/chinese_postman.rb b/lib/puppet/gratr/chinese_postman.rb
new file mode 100644
index 000000000..5a9121e2e
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..72a7ed575
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..1546fbefe
--- /dev/null
+++ b/lib/puppet/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/gratr/digraph.rb b/lib/puppet/gratr/digraph.rb
new file mode 100644
index 000000000..2c4850d43
--- /dev/null
+++ b/lib/puppet/gratr/digraph.rb
@@ -0,0 +1,113 @@
+#--
+# 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?
+ edges.inject(self.class.new) {|a,e| a << e.reverse}
+ 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
new file mode 100644
index 000000000..6f90384e7
--- /dev/null
+++ b/lib/puppet/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/gratr/dot.rb b/lib/puppet/gratr/dot.rb
new file mode 100644
index 000000000..fbf4fb073
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..8470e5458
--- /dev/null
+++ b/lib/puppet/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/gratr/graph.rb b/lib/puppet/gratr/graph.rb
new file mode 100644
index 000000000..44c8bc4d8
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..26d18958a
--- /dev/null
+++ b/lib/puppet/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/gratr/import.rb b/lib/puppet/gratr/import.rb
new file mode 100644
index 000000000..7be8fb3f3
--- /dev/null
+++ b/lib/puppet/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/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
new file mode 100644
index 000000000..7e53df404
--- /dev/null
+++ b/lib/puppet/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/gratr/maximum_flow.rb b/lib/puppet/gratr/maximum_flow.rb
new file mode 100644
index 000000000..7b3ef9b2f
--- /dev/null
+++ b/lib/puppet/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/gratr/rdot.rb b/lib/puppet/gratr/rdot.rb
new file mode 100644
index 000000000..4ce545ae6
--- /dev/null
+++ b/lib/puppet/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 nodes 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
new file mode 100644
index 000000000..3206ec5d9
--- /dev/null
+++ b/lib/puppet/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/gratr/strong_components.rb b/lib/puppet/gratr/strong_components.rb
new file mode 100644
index 000000000..796ae16bb
--- /dev/null
+++ b/lib/puppet/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/gratr/undirected_graph.rb b/lib/puppet/gratr/undirected_graph.rb
new file mode 100644
index 000000000..e96b0f351
--- /dev/null
+++ b/lib/puppet/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/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/util/graph.rb b/lib/puppet/util/graph.rb
new file mode 100644
index 000000000..c32d15cb4
--- /dev/null
+++ b/lib/puppet/util/graph.rb
@@ -0,0 +1,58 @@
+# Created by Luke Kanies on 2006-11-16.
+# Copyright (c) 2006. All rights reserved.
+
+require 'puppet'
+require 'puppet/gratr/digraph'
+require 'puppet/gratr/import'
+require 'puppet/gratr/dot'
+
+class GRATR::Digraph
+ # Determine all of the leaf nodes below a given vertex.
+ def leaves(vertex, type = :dfs)
+ tree = tree_from_vertex(vertex, type)
+ leaves = tree.keys.find_all { |c| adjacent(c, :direction => :out).empty? }
+ return leaves
+ end
+end
+
+# A module that handles the small amount of graph stuff in Puppet.
+module Puppet::Util::Graph
+ # Make a graph where each of our children gets converted to
+ # the receiving end of an edge. Call the same thing on all
+ # of our children, optionally using a block
+ def to_graph(graph = nil, &block)
+ # Allow our calling function to send in a graph, so that we
+ # can call this recursively with one graph.
+ graph ||= GRATR::Digraph.new
+
+ self.each do |child|
+ unless block_given? and ! yield(child)
+ graph.add_edge!(self, child)
+
+ if graph.cyclic?
+ raise Puppet::Error, "%s created a cyclic graph" % self
+ end
+
+ if child.respond_to?(:to_graph)
+ child.to_graph(graph, &block)
+ end
+ end
+ end
+
+ if graph.cyclic?
+ raise Puppet::Error, "%s created a cyclic graph" % self
+ end
+
+ graph
+ end
+
+ def to_jpg(graph = nil)
+ graph ||= to_graph
+ gv = graph.vertices
+ Dir.chdir("/Users/luke/Desktop/pics") do
+ graph.induced_subgraph(gv).write_to_graphic_file('jpg', 'graph')
+ end
+ end
+end
+
+# $Id$ \ No newline at end of file
diff --git a/test/util/graph.rb b/test/util/graph.rb
new file mode 100755
index 000000000..0a331f0e9
--- /dev/null
+++ b/test/util/graph.rb
@@ -0,0 +1,135 @@
+#!/usr/bin/env ruby
+#
+# Created by Luke Kanies on 2006-11-16.
+# Copyright (c) 2006. All rights reserved.
+
+$:.unshift("../lib").unshift("../../lib") if __FILE__ =~ /\.rb$/
+
+require 'puppettest'
+require 'puppet/util/graph'
+
+class TestUtilGraph < Test::Unit::TestCase
+ include PuppetTest
+
+ class Container
+ include Puppet::Util::Graph
+ include Enumerable
+ attr_accessor :name
+ def each
+ @children.each do |c| yield c end
+ end
+
+ def initialize(name, ary)
+ @name = name
+ @children = ary
+ end
+
+ def push(*ary)
+ ary.each { |c| @children.push(c)}
+ end
+
+ def to_s
+ @name
+ end
+ end
+
+ def test_to_graph
+ children = %w{a b c d}
+ list = Container.new("yay", children)
+
+ graph = nil
+ assert_nothing_raised do
+ graph = list.to_graph
+ end
+
+ assert(graph.vertices.include?(list), "wtf?")
+
+ ([list] + children).each do |thing|
+ assert(graph.vertex?(thing), "%s is not a vertex" % thing)
+ end
+ children.each do |child|
+ assert(graph.edge?(list, child),
+ "%s/%s was not added as an edge" % ["yay", child])
+ end
+ end
+
+ def test_recursive_to_graph
+ one = Container.new("one", %w{a b})
+
+ two = Container.new("two", ["c", "d"])
+
+ middle = Container.new("middle", ["e", "f", two])
+
+ top = Container.new("top", ["g", "h", middle, one])
+
+ graph = nil
+ assert_nothing_raised do
+ graph = top.to_graph
+ end
+
+ (%w{a b c d e f g h} + [one, two, middle, top]).each do |v|
+ assert(graph.vertex?(v), "%s is not a vertex" % v)
+ end
+
+ [one, two, middle, top].each do |con|
+ con.each do |child|
+ assert(graph.edge?(con, child), "%s/%s is not an edge" % [con, child])
+ end
+ end
+
+ top.to_jpg(graph)
+
+ # Now make sure we correctly retrieve the leaves from each container
+ {top => %w{a b c d e f g h},
+ one => %w{a b},
+ two => %w{c d},
+ middle => %w{c d e f}}.each do |cont, list|
+ leaves = nil
+ assert_nothing_raised do
+ leaves = graph.leaves(cont)
+ end
+ leaves = leaves.sort
+ assert_equal(list.sort, leaves.sort,
+ "Got incorrect leaf list for %s" % cont.name)
+ %w{a b c d e f g h}.each do |letter|
+ unless list.include?(letter)
+ assert(!leaves.include?(letter),
+ "incorrectly got %s as a leaf of %s" %
+ [letter, cont.to_s])
+ end
+ end
+ end
+ end
+
+ def test_to_graph_with_block
+ middle = Container.new "middle", ["c", "d", 3, 4]
+ top = Container.new "top", ["a", "b", middle, 1, 2]
+
+ graph = nil
+ assert_nothing_raised() {
+ graph = top.to_graph { |c| c.is_a?(String) or c.is_a?(Container) }
+ }
+
+ %w{a b c d}.each do |child|
+ assert(graph.vertex?(child), "%s was not added as a vertex" % child)
+ end
+
+ [1, 2, 3, 4].each do |child|
+ assert(! graph.vertex?(child), "%s is a vertex" % child)
+ end
+ end
+
+ def test_cyclic_graphs
+ one = Container.new "one", %w{a b}
+ two = Container.new "two", %w{c d}
+
+ one.push(two)
+ two.push(one)
+
+ assert_raise(Puppet::Error, "did not fail on cyclic graph") do
+ one.to_graph
+ end
+ end
+end
+
+# $Id$ \ No newline at end of file
generated by cgit (git 2.34.1) at 2025-09-22 21:46:13 +0000