diff options
Diffstat (limited to 'lib/puppet')
26 files changed, 86 insertions, 2624 deletions
diff --git a/lib/puppet/external/gratr/rdot.rb b/lib/puppet/external/dot.rb index b94568c12..b94568c12 100644 --- a/lib/puppet/external/gratr/rdot.rb +++ b/lib/puppet/external/dot.rb diff --git a/lib/puppet/external/gratr.rb b/lib/puppet/external/gratr.rb deleted file mode 100644 index b830caeb4..000000000 --- a/lib/puppet/external/gratr.rb +++ /dev/null @@ -1,33 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/base' -require 'puppet/external/gratr/digraph' -require 'puppet/external/gratr/undirected_graph' -require 'puppet/external/gratr/common' diff --git a/lib/puppet/external/gratr/adjacency_graph.rb b/lib/puppet/external/gratr/adjacency_graph.rb deleted file mode 100644 index b740c4722..000000000 --- a/lib/puppet/external/gratr/adjacency_graph.rb +++ /dev/null @@ -1,257 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/edge' -require 'puppet/external/gratr/graph' -require 'set' - -module GRATR - - # This provides the basic routines needed to implement the Digraph, UndirectedGraph, - # PseudoGraph, DirectedPseudoGraph, MultiGraph and DirectedPseudoGraph class. - module AdjacencyGraph - - include Graph - - class ArrayWithAdd < Array # :nodoc: - alias add push - end - - # Initialization parameters can include an Array of edges to add, Graphs to - # copy (will merge if multiple) - # :parallel_edges denotes that duplicate edges are allowed - # :loops denotes that loops are allowed - def initialize(*params) - @vertex_dict = Hash.new - raise ArgumentError if params.any? do |p| - !(p.kind_of? GRATR::Graph or - p.kind_of? Array or - p == :parallel_edges or - p == :loops) - end - clear_all_labels - - # Basic configuration of adjacency - @allow_loops = params.any? {|p| p == :loops} - @parallel_edges = params.any? {|p| p == :parallel_edges} - @edgelist_class = @parallel_edges ? ArrayWithAdd : Set - if @parallel_edges - @edge_number = Hash.new - @next_edge_number = 0 - end - - # Copy any given graph into this graph - params.select {|p| p.kind_of? GRATR::Graph}.each do |g| - g.edges.each do |e| - add_edge!(e) - edge_label_set(e, edge_label(e)) if edge_label(e) - end - g.vertices.each do |v| - vertex_label_set(v, vertex_label(v)) if vertex_label(v) - end - end - - # Add all array edges specified - params.select {|p| p.kind_of? Array}.each do |a| - 0.step(a.size-1, 2) {|i| add_edge!(a[i], a[i+1])} - end - - end - - # Returns true if v is a vertex of this Graph - # An O(1) implementation of vertex? - def vertex?(v) @vertex_dict.has_key?(v); end - - # Returns true if [u,v] or u is an Edge - # An O(1) implementation - def edge?(u, v=nil) - u, v = u.source, u.target if u.kind_of? GRATR::Edge - vertex?(u) and @vertex_dict[u].include?(v) - end - - # Adds a vertex to the graph with an optional label - def add_vertex!(vertex, label=nil) - @vertex_dict[vertex] ||= @edgelist_class.new - self[vertex] = label if label - self - end - - # Adds an edge to the graph - # Can be called in two basic ways, label is optional - # * add_edge!(Edge[source,target], "Label") - # * add_edge!(source,target, "Label") - def add_edge!(u, v=nil, l=nil, n=nil) - if u.class.include? EdgeNumber and n.nil? - n = u.number - end - if u.kind_of? GRATR::Edge - edge = u - u, v, l = u.source, u.target, u.label - end - if not @allow_loops and u == v - return self - end - if @parallel_edges and ! n - n = (@next_edge_number+=1) - end - add_vertex!(u); - add_vertex!(v) - @vertex_dict[u].add(v) - - if @parallel_edges - (@edge_number[u] ||= @edgelist_class.new).add(n) - end - unless directed? - @vertex_dict[v].add(u) - if @parallel_edges - (@edge_number[v] ||= @edgelist_class.new).add(n) - end - end - - if l - unless edge - if n - edge = edge_class[u,v,n] - else - edge = edge_class[u,v] - end - end - self[edge] = l - end - self - end - - # Removes a given vertex from the graph - def remove_vertex!(v) -# FIXME This is broken for multi graphs - @vertex_dict.delete(v) - @vertex_dict.each_value { |adjList| adjList.delete(v) } - @vertex_dict.keys.each do |u| - delete_label(edge_class[u,v]) - delete_label(edge_class[v,u]) - end - delete_label(v) - self - end - - # Removes an edge from the graph, can be called with source and target or with - # and object of GRATR::Edge derivation - def remove_edge!(u, v=nil) - unless u.kind_of? GRATR::Edge - raise ArgumentError if @parallel_edges - u = edge_class[u,v] - end - raise ArgumentError if @parallel_edges and (u.number || 0) == 0 - return self unless @vertex_dict[u.source] # It doesn't exist - delete_label(u) # Get rid of label - if @parallel_edges - index = @edge_number[u.source].index(u.number) - raise NoEdgeError unless index - @vertex_dict[u.source].delete_at(index) - @edge_number[u.source].delete_at(index) - else - @vertex_dict[u.source].delete(u.target) - end - self - end - - # Returns an array of vertices that the graph has - def vertices() @vertex_dict.keys; end - - # Returns an array of edges, most likely of class Edge or UndirectedEdge depending - # upon the type of graph - def edges - @vertex_dict.keys.inject(Set.new) do |a,v| - if @parallel_edges and @edge_number[v] - @vertex_dict[v].zip(@edge_number[v]).each do |w| - s,t,n = v,w[0],w[1] - a.add( edge_class[ s,t,n, edge_label(s,t,n) ] ) - end - else - @vertex_dict[v].each do |w| - a.add(edge_class[v,w,edge_label(v,w)]) - end - end; a - end.to_a - end - - alias graph_adjacent adjacent - def adjacent(x, options={}) - unless @vertex_dict.has_key?(x) - raise ArgumentError, "%s is not a vertex" % x - end - options[:direction] ||= :out - if !x.kind_of?(GRATR::Edge) and (options[:direction] == :out || !directed?) - if options[:type] == :edges - @parallel_edges ? - @vertex_dict[x].map {|v| e=edge_class[x,v,@edge_number[x][v]]; e.label = self[e]; e} : - @vertex_dict[x].map {|v| e=edge_class[x,v]; e.label = self[e]; e} - else - @vertex_dict[x].to_a - end - else - graph_adjacent(x,options) - end - end - - - public - - def self.included(cl) - # Shortcut for creating a Graph - # - # Example: GRATR::Digraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s => - # "(1-2)(2-3)(2-4)(4-5)" - # - # Or as a Hash for specifying lables - # GRATR::Digraph[ [:a,:b] => 3, [:b,:c] => 4 ] (Note: Do not use for Multi or Pseudo graphs) - def cl.[] (*a) - result = new - if a.size == 1 and a[0].kind_of? Hash - # Convert to edge class - a[0].each do |k,v| - if result.edge_class.include? GRATR::EdgeNumber - result.add_edge!(result.edge_class[k[0],k[1],nil,v]) - else - result.add_edge!(result.edge_class[k[0],k[1],v]) - end - end - elsif a[0].kind_of? GRATR::Edge - a.each{|e| result.add_edge!(e); result[e] = e.label} - elsif a.size % 2 == 0 - 0.step(a.size-1, 2) {|i| result.add_edge!(a[i], a[i+1])} - else - raise ArgumentError - end - result - end - end - - end # Adjacency Graph -end # GRATR diff --git a/lib/puppet/external/gratr/base.rb b/lib/puppet/external/gratr/base.rb deleted file mode 100644 index 72dded73f..000000000 --- a/lib/puppet/external/gratr/base.rb +++ /dev/null @@ -1,34 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -GRATR_VERSION = "0.4.1" - -module GRATR - class NoVertexError < IndexError; end - class NoEdgeError < IndexError; end -end diff --git a/lib/puppet/external/gratr/biconnected.rb b/lib/puppet/external/gratr/biconnected.rb deleted file mode 100644 index c976b2c04..000000000 --- a/lib/puppet/external/gratr/biconnected.rb +++ /dev/null @@ -1,116 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'set' - -module GRATR - module Graph - # Biconnected is a module for adding the biconnected algorithm to - # UndirectedGraphs - module Biconnected - - # biconnected computes the biconnected subgraphs - # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan - # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on - # Computing, 1(2):146-160, 1972 - # - # The output of the algorithm is a pair, the first value is an - # array of biconnected subgraphs. The second is the set of - # articulation vertices. - # - # A connected graph is biconnected if the removal of any single vertex - # (and all edges incident on that vertex) cannot disconnect the graph. - # More generally, the biconnected components of a graph are the maximal - # subsets of vertices such that the removal of a vertex from a particular - # component will not disconnect the component. Unlike connected components, - # vertices may belong to multiple biconnected components: those vertices - # that belong to more than one biconnected component are called articulation - # points or, equivalently, cut vertices. Articulation points are vertices - # whose removal would increase the number of connected components in the graph. - # Thus, a graph without articulation points is biconnected. - def biconnected - dfs_num = 0 - number = {}; predecessor = {}; low_point = {} - stack = []; result = []; articulation= [] - - root_vertex = Proc.new {|v| predecessor[v]=v } - enter_vertex = Proc.new {|u| number[u]=low_point[u]=(dfs_num+=1) } - tree_edge = Proc.new do |e| - stack.push(e) - predecessor[e.target] = e.source - end - back_edge = Proc.new do |e| - if e.target != predecessor[e.source] - stack.push(e) - low_point[e.source] = [low_point[e.source], number[e.target]].min - end - end - exit_vertex = Proc.new do |u| - parent = predecessor[u] - is_articulation_point = false - if number[parent] > number[u] - parent = predecessor[parent] - is_articulation_point = true - end - if parent == u - is_articulation_point = false if (number[u] + 1) == number[predecessor[u]] - else - low_point[parent] = [low_point[parent], low_point[u]].min - if low_point[u] >= number[parent] - if number[parent] > number[predecessor[parent]] - predecessor[u] = predecessor[parent] - predecessor[parent] = u - end - result << (component = self.class.new) - while number[stack[-1].source] >= number[u] - component.add_edge!(stack.pop) - end - component.add_edge!(stack.pop) - if stack.empty? - predecessor[u] = parent - predecessor[parent] = u - end - end - end - articulation << u if is_articulation_point - end - - # Execute depth first search - dfs({:root_vertex => root_vertex, - :enter_vertex => enter_vertex, - :tree_edge => tree_edge, - :back_edge => back_edge, - :exit_vertex => exit_vertex}) - - [result, articulation] - end # biconnected - - end # Biconnected - - end # Graph -end # GRATR diff --git a/lib/puppet/external/gratr/chinese_postman.rb b/lib/puppet/external/gratr/chinese_postman.rb deleted file mode 100644 index 338a88bed..000000000 --- a/lib/puppet/external/gratr/chinese_postman.rb +++ /dev/null @@ -1,123 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/digraph_distance' - -module GRATR - module Graph - module ChinesePostman - - # Returns the shortest walk that traverses all arcs at least - # once, returning to the specified start node. - def closed_chinese_postman_tour(start, weight=nil, zero=0) - cost, path, delta = floyd_warshall(weight, zero) - return nil unless cp_valid_least_cost? cost, zero - positive, negative = cp_unbalanced(delta) - f = cp_find_feasible(delta, positive, negative, zero) - while cp_improve(f, positive, negative, cost, zero); end - cp_euler_circuit(start, f, path) - end - - private - - def cp_euler_circuit(start, f, path) # :nodoc: - circuit = [u=v=start] - bridge_taken = Hash.new {|h,k| h[k] = Hash.new} - until v.nil? - if v=f[u].keys.detect {|k| f[u][k] > 0} - f[u][v] -= 1 - circuit << (u = path[u][v]) while u != v - else - unless bridge_taken[u][bridge = path[u][start]] - v = vertices.detect {|v1| v1 != bridge && edge?(u,v1) && !bridge_taken[u][v1]} || bridge - bridge_taken[u][v] = true - circuit << v - end - end - u=v - end; circuit - end - - def cp_cancel_cycle(cost, path, f, start, zero) # :nodoc: - u = start; k = nil - begin - v = path[u][start] - k = f[v][u] if cost[u][v] < zero and (k.nil? || k > f[v][u]) - end until (u=v) != start - u = start - begin - v = path[u][start] - cost[u][v] < zero ? f[v][u] -= k : f[u][v] += k - end until (u=v) != start - true # This routine always returns true to make cp_improve easier - end - - def cp_improve(f, positive, negative, cost, zero) # :nodoc: - residual = self.class.new - negative.each do |u| - positive.each do |v| - residual.add_edge!(u,v,cost[u][v]) - residual.add_edge!(v,u,-cost[u][v]) if f[u][v] != 0 - end - end - r_cost, r_path, r_delta = residual.floyd_warshall(nil, zero) - i = residual.vertices.detect {|v| r_cost[v][v] and r_cost[v][v] < zero} - i ? cp_cancel_cycle(r_cost, r_path, f, i) : false - end - - def cp_find_feasible(delta, positive, negative, zero) # :nodoc: - f = Hash.new {|h,k| h[k] = Hash.new} - negative.each do |i| - positive.each do |j| - f[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j] - delta[i] += f[i][j] - delta[j] -= f[i][j] - end - end; f - end - - def cp_valid_least_cost?(c, zero) # :nodoc: - vertices.each do |i| - vertices.each do |j| - return false unless c[i][j] and c[i][j] >= zero - end - end; true - end - - def cp_unbalanced(delta) # :nodoc: - negative = []; positive = [] - vertices.each do |v| - negative << v if delta[v] < 0 - positive << v if delta[v] > 0 - end; [positive, negative] - end - - end # Chinese Postman - end # Graph -end # GRATR - diff --git a/lib/puppet/external/gratr/common.rb b/lib/puppet/external/gratr/common.rb deleted file mode 100644 index 347250edc..000000000 --- a/lib/puppet/external/gratr/common.rb +++ /dev/null @@ -1,73 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/edge' -require 'puppet/external/gratr/graph' - -module GRATR - # This class defines a cycle graph of size n - # This is easily done by using the base Graph - # class and implemeting the minimum methods needed to - # make it work. This is a good example to look - # at for making one's own graph classes - class Cycle - - def initialize(n) @size = n; end - def directed?() false; end - def vertices() (1..@size).to_a; end - def vertex?(v) v > 0 and v <= @size; end - def edge?(u,v=nil) - u, v = [u.source, v.target] if u.kind_of? GRATR::Edge - vertex?(u) && vertex?(v) && ((v-u == 1) or (u==@size && v=1)) - end - def edges() Array.new(@size) {|i| GRATR::UndirectedEdge[i+1, (i+1)==@size ? 1 : i+2]}; end - end - - # This class defines a complete graph of size n - # This is easily done by using the base Graph - # class and implemeting the minimum methods needed to - # make it work. This is a good example to look - # at for making one's own graph classes - class Complete < Cycle - def initialize(n) @size = n; @edges = nil; end - def edges - return @edges if @edges # Cache edges - @edges = [] - @size.times do |u| - @size.times {|v| @edges << GRATR::UndirectedEdge[u+1, v+1]} - end; @edges - end - def edge?(u,v=nil) - u, v = [u.source, v.target] if u.kind_of? GRATR::Edge - vertex?(u) && vertex?(v) - end - end # Complete - - - -end # GRATR diff --git a/lib/puppet/external/gratr/comparability.rb b/lib/puppet/external/gratr/comparability.rb deleted file mode 100644 index 1546fbefe..000000000 --- a/lib/puppet/external/gratr/comparability.rb +++ /dev/null @@ -1,92 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Graph - module Comparability - - # A comparability graph is an UndirectedGraph that has a transitive - # orientation. This returns a boolean that says if this graph - # is a comparability graph. - def comparability?() gamma_decomposition[1]; end - - # Returns an array with two values, the first being a hash of edges - # with a number containing their class assignment, the second valud - # is a boolean which states whether or not the graph is a - # comparability graph - # - # Complexity in time O(d*|E|) where d is the maximum degree of a vertex - # Complexity in space O(|V|+|E|) - def gamma_decomposition - k = 0; comparability=true; classification={} - edges.map {|edge| [edge.source,edge.target]}.each do |e| - if classification[e].nil? - k += 1 - classification[e] = k; classification[e.reverse] = -k - comparability &&= gratr_comparability_explore(e, k, classification) - end - end; [classification, comparability] - end - - # Returns one of the possible transitive orientations of - # the UndirectedGraph as a Digraph - def transitive_orientation(digraph_class=Digraph) - raise NotImplementError - end - - private - - # Taken from Figure 5.10, on pg. 130 of Martin Golumbic's, _Algorithmic_Graph_ - # _Theory_and_Perfect_Graphs. - def gratr_comparability_explore(edge, k, classification, space='') - ret = gratr_comparability_explore_inner(edge, k, classification, :forward, space) - gratr_comparability_explore_inner(edge.reverse, k, classification, :backward, space) && ret - end - - def gratr_comparability_explore_inner(edge, k, classification, direction,space) - comparability = true - adj_target = adjacent(edge[1]) - adjacent(edge[0]).select do |mt| - (classification[[edge[1],mt]] || k).abs < k or - not adj_target.any? {|adj_t| adj_t == mt} - end.each do |m| - e = (direction == :forward) ? [edge[0], m] : [m,edge[0]] - if classification[e].nil? - classification[e] = k - classification[e.reverse] = -k - comparability = gratr_comparability_explore(e, k, classification, ' '+space) && comparability - elsif classification[e] == -k - classification[e] = k - gratr_comparability_explore(e, k, classification, ' '+space) - comparability = false - end - end; comparability - end # gratr_comparability_explore_inner - - end # Comparability - end # Graph -end # GRATR
\ No newline at end of file diff --git a/lib/puppet/external/gratr/digraph.rb b/lib/puppet/external/gratr/digraph.rb deleted file mode 100644 index 1223a65a1..000000000 --- a/lib/puppet/external/gratr/digraph.rb +++ /dev/null @@ -1,116 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -require 'puppet/external/gratr/edge' -require 'puppet/external/gratr/graph' -require 'puppet/external/gratr/search' -require 'puppet/external/gratr/adjacency_graph' -require 'puppet/external/gratr/strong_components' -require 'puppet/external/gratr/digraph_distance' -require 'puppet/external/gratr/chinese_postman' - -module GRATR - # - # Digraph is a directed graph which is a finite set of vertices - # and a finite set of edges connecting vertices. It cannot contain parallel - # edges going from the same source vertex to the same target. It also - # cannot contain loops, i.e. edges that go have the same vertex for source - # and target. - # - # DirectedPseudoGraph is a class that allows for parallel edges, and a - # DirectedMultiGraph is a class that allows for parallel edges and loops - # as well. - class Digraph - include AdjacencyGraph - include Graph::Search - include Graph::StrongComponents - include Graph::Distance - include Graph::ChinesePostman - - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? GRATR::Graph or p.kind_of? Array) - end if self.class == GRATR::Digraph - super(*params) - end - - # A directed graph is directed by definition - def directed?() true; end - - # A digraph uses the Edge class for edges - def edge_class() @parallel_edges ? GRATR::MultiEdge : GRATR::Edge; end - - # Reverse all edges in a graph - def reversal - return new(self) unless directed? - result = self.class.new - edges.inject(result) {|a,e| a << e.reverse} - vertices.each { |v| result.add_vertex!(v) unless result.vertex?(v) } - result - end - - # Return true if the Graph is oriented. - def oriented? - e = edges - re = e.map {|x| x.reverse} - not e.any? {|x| re.include?(x)} - end - - # Balanced is when the out edge count is equal to the in edge count - def balanced?(v) out_degree(v) == in_degree(v); end - - # Returns out_degree(v) - in_degree(v) - def delta(v) out_degree(v) - in_degree(v); end - - end - - # DirectedGraph is just an alias for Digraph should one desire - DirectedGraph = Digraph - - # This is a Digraph that allows for parallel edges, but does not - # allow loops - class DirectedPseudoGraph < Digraph - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? GRATR::Graph or p.kind_of? Array) - end - super(:parallel_edges, *params) - end - end - - # This is a Digraph that allows for parallel edges and loops - class DirectedMultiGraph < Digraph - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? GRATR::Graph or p.kind_of? Array) - end - super(:parallel_edges, :loops, *params) - end - end - -end diff --git a/lib/puppet/external/gratr/digraph_distance.rb b/lib/puppet/external/gratr/digraph_distance.rb deleted file mode 100644 index 6f90384e7..000000000 --- a/lib/puppet/external/gratr/digraph_distance.rb +++ /dev/null @@ -1,185 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Graph - module Distance - - # Shortest path from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 - # - # Requires that the graph be acyclic. If the graph is not - # acyclic, then see dijkstras_algorithm or bellman_ford_moore - # for possible solutions. - # - # start is the starting vertex - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # Complexity O(n+m) - def shortest_path(start, weight=nil, zero=0) - dist = {start => zero}; path = {} - topsort(start) do |vi| - next if vi == start - dist[vi],path[vi] = adjacent(vi, :direction => :in).map do |vj| - [dist[vj] + cost(vj,vi,weight), vj] - end.min {|a,b| a[0] <=> b[0]} - end; - dist.keys.size == vertices.size ? [dist,path] : nil - end # shortest_path - - # Algorithm from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 - # - # Finds the distances from a given vertex s in a weighted digraph - # to the rest of the vertices, provided all the weights of arcs - # are non-negative. If negative arcs exist in the graph, two - # basic options exist, 1) modify all weights to be positive by - # using an offset, or 2) use the bellman_ford_moore algorithm. - # Also if the graph is acyclic, use the shortest_path algorithm. - # - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # O(n*log(n) + m) complexity - def dijkstras_algorithm(s, weight = nil, zero = 0) - q = vertices; distance = { s => zero }; path = {} - while not q.empty? - v = (q & distance.keys).inject(nil) {|a,k| (!a.nil?) && (distance[a] < distance[k]) ? a : k} - q.delete(v) - (q & adjacent(v)).each do |u| - c = cost(v,u,weight) - if distance[u].nil? or distance[u] > (c+distance[v]) - distance[u] = c + distance[v] - path[u] = v - end - end - end; [distance, path] - end # dijkstras_algorithm - - # Algorithm from Jorgen Band-Jensen and Gregory Gutin, - # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58 - # - # Finds the distances from a given vertex s in a weighted digraph - # to the rest of the vertices, provided the graph has no negative cycle. - # If no negative weights exist, then dijkstras_algorithm is more - # efficient in time and space. Also if the graph is acyclic, use the - # shortest_path algorithm. - # - # weight can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # - # zero is used for math system with a different definition of zero - # - # Returns a hash with the key being a vertex and the value being the - # distance. A missing vertex from the hash is an infinite distance - # - # O(nm) complexity - def bellman_ford_moore(start, weight = nil, zero = 0) - distance = { start => zero }; path = {} - 2.upto(vertices.size) do - edges.each do |e| - u,v = e[0],e[1] - unless distance[u].nil? - c = cost(u, v, weight)+distance[u] - if distance[v].nil? or c < distance[v] - distance[v] = c - path[v] = u - end - end - end - end; [distance, path] - end # bellman_ford_moore - - # This uses the Floyd-Warshall algorithm to efficiently find - # and record shortest paths at the same time as establishing - # the costs for all vertices in a graph. - # See, S.Skiena, "The Algorithm Design Manual", - # Springer Verlag, 1998 for more details. - # - # Returns a pair of matrices and a hash of delta values. - # The matrices will be indexed by two vertices and are - # implemented as a Hash of Hashes. The first matrix is the cost, the second - # matrix is the shortest path spanning tree. The delta (difference of number - # of in edges and out edges) is indexed by vertex. - # - # weight specifies how an edge weight is determined, if it's a - # Proc the Edge is passed to it, if it's nil it will just use - # the value in the label for the Edge, otherwise the weight is - # determined by applying the [] operator to the value in the - # label for the Edge - # - # zero defines the zero value in the math system used. Defaults - # of course, to 0. This allows for no assumptions to be made - # about the math system and fully functional duck typing. - # - # O(n^3) complexity in time. - def floyd_warshall(weight=nil, zero=0) - c = Hash.new {|h,k| h[k] = Hash.new} - path = Hash.new {|h,k| h[k] = Hash.new} - delta = Hash.new {|h,k| h[k] = 0} - edges.each do |e| - delta[e.source] += 1 - delta[e.target] -= 1 - path[e.source][e.target] = e.target - c[e.source][e.target] = cost(e, weight) - end - vertices.each do |k| - vertices.each do |i| - if c[i][k] - vertices.each do |j| - if c[k][j] && - (c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j])) - path[i][j] = path[i][k] - c[i][j] = c[i][k] + c[k][j] - return nil if i == j and c[i][j] < zero - end - end - end - end - end - [c, path, delta] - end # floyd_warshall - - end # Distance - end # Graph -end # GRATR
\ No newline at end of file diff --git a/lib/puppet/external/gratr/dot.rb b/lib/puppet/external/gratr/dot.rb deleted file mode 100644 index 5b74776aa..000000000 --- a/lib/puppet/external/gratr/dot.rb +++ /dev/null @@ -1,90 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ -# -# Minimal Dot support, based on Dave Thomas's dot module (included in rdoc). -# rdot.rb is a modified version which also contains support for undirected -# graphs. - -require 'puppet/external/gratr/rdot' - -module GRATR - module Graph - - # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an - # undirected Graph. _params_ can contain any graph property specified in - # rdot.rb. If an edge or vertex label is a kind of Hash then the keys - # which match +dot+ properties will be used as well. - def to_dot_graph (params = {}) - params['name'] ||= self.class.name.gsub(/:/,'_') - fontsize = params['fontsize'] ? params['fontsize'] : '8' - graph = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params) - edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge - vertices.each do |v| - name = v.to_s - params = {'name' => '"'+name+'"', - 'fontsize' => fontsize, - 'label' => name} - v_label = vertex_label(v) - params.merge!(v_label) if v_label and v_label.kind_of? Hash - graph << DOT::DOTNode.new(params) - end - edges.each do |e| - params = {'from' => '"'+ e.source.to_s + '"', - 'to' => '"'+ e.target.to_s + '"', - 'fontsize' => fontsize } - e_label = edge_label(e) - params.merge!(e_label) if e_label and e_label.kind_of? Hash - graph << edge_klass.new(params) - end - graph - end - - # Output the dot format as a string - def to_dot (params={}) to_dot_graph(params).to_s; end - - # Call +dotty+ for the graph which is written to the file 'graph.dot' - # in the # current directory. - def dotty (params = {}, dotfile = 'graph.dot') - File.open(dotfile, 'w') {|f| f << to_dot(params) } - system('dotty', dotfile) - end - - # Use +dot+ to create a graphical representation of the graph. Returns the - # filename of the graphics file. - def write_to_graphic_file (fmt='png', dotfile='graph') - src = dotfile + '.dot' - dot = dotfile + '.' + fmt - - File.open(src, 'w') {|f| f << self.to_dot << "\n"} - - system( "dot -T#{fmt} #{src} -o #{dot}" ) - dot - end - - end # module Graph -end # module GRATR diff --git a/lib/puppet/external/gratr/edge.rb b/lib/puppet/external/gratr/edge.rb deleted file mode 100644 index 8470e5458..000000000 --- a/lib/puppet/external/gratr/edge.rb +++ /dev/null @@ -1,145 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - - # Edge includes classes for representing egdes of directed and - # undirected graphs. There is no need for a Vertex class, because any ruby - # object can be a vertex of a graph. - # - # Edge's base is a Struct with a :source, a :target and a :label - Struct.new("EdgeBase",:source, :target, :label) - - class Edge < Struct::EdgeBase - - def initialize(p_source,p_target,p_label=nil) - super(p_source, p_target, p_label) - end - - # Ignore labels for equality - def eql?(other) self.class == other.class and target==other.target and source==other.source; end - - # Alias for eql? - alias == eql? - - # Returns (v,u) if self == (u,v). - def reverse() self.class.new(target, source, label); end - - # Sort support - def <=>(rhs) [source,target] <=> [rhs.source,rhs.target]; end - - # Edge.new[1,2].to_s => "(1-2 'label')" - def to_s - l = label ? " '#{label.to_s}'" : '' - "(#{source}-#{target}#{l})" - end - - # Hash is defined in such a way that label is not - # part of the hash value - def hash() source.hash ^ (target.hash+1); end - - # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] - def self.[](p_source, p_target, p_label=nil) - new(p_source, p_target, p_label) - end - - def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{label.inspect}]"; end - - end - - # An undirected edge is simply an undirected pair (source, target) used in - # undirected graphs. UndirectedEdge[u,v] == UndirectedEdge[v,u] - class UndirectedEdge < Edge - - # Equality allows for the swapping of source and target - def eql?(other) super or (self.class == other.class and target==other.source and source==other.target); end - - # Alias for eql? - alias == eql? - - # Hash is defined such that source and target can be reversed and the - # hash value will be the same - # - # This will cause problems with self loops - def hash() source.hash ^ target.hash; end - - # Sort support - def <=>(rhs) - [[source,target].max,[source,target].min] <=> - [[rhs.source,rhs.target].max,[rhs.source,rhs.target].min] - end - - # UndirectedEdge[1,2].to_s == "(1=2 'label)" - def to_s - l = label ? " '#{label.to_s}'" : '' - s = source.to_s - t = target.to_s - "(#{[s,t].min}=#{[s,t].max}#{l})" - end - - end - - # This module provides for internal numbering of edges for differentiating between mutliple edges - module EdgeNumber - - attr_accessor :number # Used to differentiate between mutli-edges - - def initialize(p_source,p_target,p_number,p_label=nil) - self.number = p_number - super(p_source, p_target, p_label) - end - - # Returns (v,u) if self == (u,v). - def reverse() self.class.new(target, source, number, label); end - def hash() super ^ number.hash; end - def to_s() super + "[#{number}]"; end - def <=>(rhs) (result = super(rhs)) == 0 ? number <=> rhs.number : result; end - def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{number.inspect},#{label.inspect}]"; end - def eql?(rhs) super(rhs) and (rhs.number.nil? or number.nil? or number == rhs.number); end - def ==(rhs) eql?(rhs); end - - # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] - def self.included(cl) - - def cl.[](p_source, p_target, p_number=nil, p_label=nil) - new(p_source, p_target, p_number, p_label) - end - end - - end - - class MultiEdge < Edge - include EdgeNumber - end - - class MultiUndirectedEdge < UndirectedEdge - include EdgeNumber - end - -end diff --git a/lib/puppet/external/gratr/graph.rb b/lib/puppet/external/gratr/graph.rb deleted file mode 100644 index 7b73afccc..000000000 --- a/lib/puppet/external/gratr/graph.rb +++ /dev/null @@ -1,303 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/edge' -require 'puppet/external/gratr/labels' -require 'puppet/external/gratr/graph_api' - -module GRATR - - # Using the functions required by the GraphAPI, it implements all the - # basic functions of a Graph class by using only functions in GraphAPI. - # An actual implementation still needs to be done, as in Digraph or - # UndirectedGraph. - module Graph - include Enumerable - include Labels - include GraphAPI - - # Non destructive version of add_vertex!, returns modified copy of Graph - def add_vertex(v, l=nil) x=self.class.new(self); x.add_vertex!(v,l); end - - # Non destructive version add_edge!, returns modified copy of Graph - def add_edge(u, v=nil, l=nil) x=self.class.new(self); x.add_edge!(u,v,l); end - - # Non destructive version of remove_vertex!, returns modified copy of Graph - def remove_vertex(v) x=self.class.new(self); x.remove_vertex!(v); end - - # Non destructive version of remove_edge!, returns modified copy of Graph - def remove_edge(u,v=nil) x=self.class.new(self); x.remove_edge!(u,v); end - - # Return Array of adjacent portions of the Graph - # x can either be a vertex an edge. - # options specifies parameters about the adjacency search - # :type can be either :edges or :vertices (default). - # :direction can be :in, :out(default) or :all. - # - # Note: It is probably more efficently done in implementation. - def adjacent(x, options={}) - d = directed? ? (options[:direction] || :out) : :all - - # Discharge the easy ones first - return [x.source] if x.kind_of? Edge and options[:type] == :vertices and d == :in - return [x.target] if x.kind_of? Edge and options[:type] == :vertices and d == :out - return [x.source, x.target] if x.kind_of? Edge and options[:type] != :edges and d == :all - - (options[:type] == :edges ? edges : to_a).select {|u| adjacent?(x,u,d)} - end - - # Add all objects in _a_ to the vertex set. - def add_vertices!(*a) a.each {|v| add_vertex! v}; self; end - - # See add_vertices! - - def add_vertices(*a) x=self.class.new(self); x.add_vertices(*a); self; end - - # Add all edges in the _edges_ Enumerable to the edge set. Elements of the - # Enumerable can be both two-element arrays or instances of DirectedEdge or - # UnDirectedEdge. - def add_edges!(*args) args.each { |edge| add_edge!(edge) }; self; end - - # See add_edge! - def add_edges(*a) x=self.class.new(self); x.add_edges!(*a); self; end - - # Remove all vertices specified by the Enumerable a from the graph by - # calling remove_vertex!. - def remove_vertices!(*a) a.each { |v| remove_vertex! v }; end - - # See remove_vertices! - def remove_vertices(*a) x=self.class.new(self); x.remove_vertices(*a); end - - # Remove all vertices edges by the Enumerable a from the graph by - # calling remove_edge! - def remove_edges!(*a) a.each { |e| remove_edges! e }; end - - # See remove_edges - def remove_edges(*a) x=self.class.new(self); x.remove_edges(*a); end - - # Execute given block for each vertex, provides for methods in Enumerable - def each(&block) vertices.each(&block); end - - # Returns true if _v_ is a vertex of the graph. - # This is a default implementation that is of O(n) average complexity. - # If a subclass uses a hash to store vertices, then this can be - # made into an O(1) average complexity operation. - def vertex?(v) vertices.include?(v); end - - # Returns true if u or (u,v) is an Edge of the graph. - def edge?(*arg) edges.include?(edge_convert(*args)); end - - # Tests two objects to see if they are adjacent. - # direction parameter specifies direction of adjacency, :in, :out, or :all(default) - # All denotes that if there is any adjacency, then it will return true. - # Note that the default is different than adjacent where one is primarily concerned with finding - # all adjacent objects in a graph to a given object. Here the concern is primarily on seeing - # if two objects touch. For vertexes, any edge between the two will usually do, but the direction - # can be specified if need be. - def adjacent?(source, target, direction=:all) - if source.kind_of? GRATR::Edge - raise NoEdgeError unless edge? source - if target.kind_of? GRATR::Edge - raise NoEdgeError unless edge? target - (direction != :out and source.source == target.target) or (direction != :in and source.target == target.source) - else - raise NoVertexError unless vertex? target - (direction != :out and source.source == target) or (direction != :in and source.target == target) - end - else - raise NoVertexError unless vertex? source - if target.kind_of? GRATR::Edge - raise NoEdgeError unless edge? target - (direction != :out and source == target.target) or (direction != :in and source == target.source) - else - raise NoVertexError unless vertex? target - (direction != :out and edge?(target,source)) or (direction != :in and edge?(source,target)) - end - end - end - - # Returns true if the graph has no vertex, i.e. num_vertices == 0. - def empty?() vertices.size.zero?; end - - # Returns true if the given object is a vertex or Edge in the Graph. - # - def include?(x) x.kind_of?(GRATR::Edge) ? edge?(x) : vertex?(x); end - - # Returns the neighboorhood of the given vertex (or Edge) - # This is equivalent to adjacent, but bases type on the type of object. - # direction can be :all, :in, or :out - def neighborhood(x, direction = :all) - adjacent(x, :direction => direction, :type => ((x.kind_of? GRATR::Edge) ? :edges : :vertices )) - end - - # Union of all neighborhoods of vertices (or edges) in the Enumerable x minus the contents of x - # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 4 - def set_neighborhood(x, direction = :all) - x.inject(Set.new) {|a,v| a.merge(neighborhood(v,direction))}.reject {|v2| x.include?(v2)} - end - - # Union of all set_neighborhoods reachable in p edges - # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46 - def closed_pth_neighborhood(w,p,direction=:all) - if p <= 0 - w - elsif p == 1 - (w + set_neighborhood(w,direction)).uniq - else - n = set_neighborhood(w, direction) - (w + n + closed_pth_neighborhood(n,p-1,direction)).uniq - end - end - - # Returns the neighboorhoods reachable in p steps from every vertex (or edge) - # in the Enumerable x - # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46 - def open_pth_neighborhood(x, p, direction=:all) - if p <= 0 - x - elsif p == 1 - set_neighborhood(x,direction) - else - set_neighborhood(open_pth_neighborhood(x, p-1, direction),direction) - closed_pth_neighborhood(x,p-1,direction) - end - end - - # Returns the number of out-edges (for directed graphs) or the number of - # incident edges (for undirected graphs) of vertex _v_. - def out_degree(v) adjacent(v, :direction => :out).size; end - - # Returns the number of in-edges (for directed graphs) or the number of - # incident edges (for undirected graphs) of vertex _v_. - def in_degree(v) adjacent(v, :direction => :in ).size; end - - # Returns the sum of the number in and out edges for a vertex - def degree(v) in_degree(v) + out_degree(v); end - - # Minimum in-degree - def min_in_degree() to_a.map {|v| in_degree(v)}.min; end - - # Minimum out-degree - def min_out_degree() to_a.map {|v| out_degree(v)}.min; end - - # Minimum degree of all vertexes - def min_degree() [min_in_degree, min_out_degree].min; end - - # Maximum in-degree - def max_in_degree() vertices.map {|v| in_degree(v)}.max; end - - # Maximum out-degree - def max_out_degree() vertices.map {|v| out_degree(v)}.max; end - - # Minimum degree of all vertexes - def max_degree() [max_in_degree, max_out_degree].max; end - - # Regular - def regular?() min_degree == max_degree; end - - # Returns the number of vertices. - def size() vertices.size; end - - # Synonym for size. - def num_vertices() vertices.size; end - - # Returns the number of edges. - def num_edges() edges.size; end - - # Utility method to show a string representation of the edges of the graph. - def to_s() edges.to_s; end - - # Equality is defined to be same set of edges and directed? - def eql?(g) - return false unless g.kind_of? GRATR::Graph - - (g.directed? == self.directed?) and - (vertices.sort == g.vertices.sort) and - (g.edges.sort == edges.sort) - end - - # Synonym for eql? - def ==(rhs) eql?(rhs); end - - # Merge another graph into this one - def merge(other) - other.vertices.each {|v| add_vertex!(v) } - other.edges.each {|e| add_edge!(e) } - other.edges.each {|e| add_edge!(e.reverse) } if directed? and !other.directed? - self - end - - # A synonym for merge, that doesn't modify the current graph - def +(other) - result = self.class.new(self) - case other - when GRATR::Graph : result.merge(other) - when GRATR::Edge : result.add_edge!(other) - else result.add_vertex!(other) - end - end - - # Remove all vertices in the specified right hand side graph - def -(other) - case other - when GRATR::Graph : induced_subgraph(vertices - other.vertices) - when GRATR::Edge : self.class.new(self).remove_edge!(other) - else self.class.new(self).remove_vertex!(other) - end - end - - # A synonym for add_edge! - def <<(edge) add_edge!(edge); end - - # Return the complement of the current graph - def complement - vertices.inject(self.class.new) do |a,v| - a.add_vertex!(v) - vertices.each {|v2| a.add_edge!(v,v2) unless edge?(v,v2) }; a - end - end - - # Given an array of vertices return the induced subgraph - def induced_subgraph(v) - edges.inject(self.class.new) do |a,e| - ( v.include?(e.source) and v.include?(e.target) ) ? (a << e) : a - end; - end - - def inspect - l = vertices.select {|v| self[v]}.map {|u| "vertex_label_set(#{u.inspect},#{self[u].inspect})"}.join('.') - self.class.to_s + '[' + edges.map {|e| e.inspect}.join(', ') + ']' + (l ? '.'+l : '') - end - - private - def edge_convert(*args) args[0].kind_of?(GRATR::Edge) ? args[0] : edge_class[*args]; end - - - end # Graph - -end # GRATR diff --git a/lib/puppet/external/gratr/graph_api.rb b/lib/puppet/external/gratr/graph_api.rb deleted file mode 100644 index 26d18958a..000000000 --- a/lib/puppet/external/gratr/graph_api.rb +++ /dev/null @@ -1,83 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - - # This defines the minimum set of functions required to make a graph class that can - # use the algorithms defined by this library - module GraphAPI - - # Is the graph directed? - # - # This method must be implemented by the specific graph class - def directed?() raise NotImplementedError; end - - # Add a vertex to the Graph and return the Graph - # An additional label l can be specified as well - # - # This method must be implemented by the specific graph class - def add_vertex!(v,l=nil) raise NotImplementedError; end - - # Add an edge to the Graph and return the Graph - # u can be an object of type GRATR::Edge or u,v specifies - # a source, target pair. The last parameter is an optional label - # - # This method must be implemented by the specific graph class - def add_edge!(u,v=nil,l=nil) raise NotImplementedError; end - - # Remove a vertex to the Graph and return the Graph - # - # This method must be implemented by the specific graph class - def remove_vertex!(v) raise NotImplementedError; end - - # Remove an edge from the Graph and return the Graph - # - # Can be a type of GRATR::Edge or a source and target - # This method must be implemented by the specific graph class - def remove_edge!(u,v=nil) raise NotImplementedError; end - - # Return the array of vertices. - # - # This method must be implemented by the specific graph class - def vertices() raise NotImplementedError; end - - # Return the array of edges. - # - # This method must be implemented by the specific graph class - def edges() raise NotImplementedError; end - - # Returns the edge class - def edge_class() raise NotImplementedError; end - - # Return the chromatic number for this graph - # This is currently incomplete and in some cases will be NP-complete - # FIXME: Should this even be here? My gut feeling is no... - def chromatic_number() raise NotImplementedError; end - end -end
\ No newline at end of file diff --git a/lib/puppet/external/gratr/import.rb b/lib/puppet/external/gratr/import.rb deleted file mode 100644 index d3678d8b6..000000000 --- a/lib/puppet/external/gratr/import.rb +++ /dev/null @@ -1,44 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr' - -# Pull all GRATR classes up into the current namespace -Edge = GRATR::Edge -UndirectedEdge = GRATR::UndirectedEdge -MultiEdge = GRATR::MultiEdge -MultiUndirectedEdge = GRATR::MultiUndirectedEdge -Graph = GRATR::Graph -Digraph = GRATR::Digraph -DirectedGraph = GRATR::DirectedGraph -DirectedPseudoGraph = GRATR::DirectedPseudoGraph -DirectedMultiGraph = GRATR::DirectedMultiGraph -UndirectedGraph = GRATR::UndirectedGraph -UndirectedPseudoGraph = GRATR::UndirectedPseudoGraph -UndirectedMultiGraph = GRATR::UndirectedMultiGraph -Complete = GRATR::Complete diff --git a/lib/puppet/external/gratr/labels.rb b/lib/puppet/external/gratr/labels.rb deleted file mode 100644 index 7e53df404..000000000 --- a/lib/puppet/external/gratr/labels.rb +++ /dev/null @@ -1,90 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - module Labels - # Return a label for an edge or vertex - def [](u) (u.kind_of? GRATR::Edge) ? edge_label(u) : vertex_label(u); end - - # Set a label for an edge or vertex - def []= (u, value) (u.kind_of? GRATR::Edge) ? edge_label_set(u,value) : vertex_label_set(u, value); end - - # Delete a label entirely - def delete_label(u) (u.kind_of? GRATR::Edge) ? edge_label_delete(u) : vertex_label_delete(u); end - - # Get the label for an edge - def vertex_label(v) vertex_label_dict[v]; end - - # Set the label for an edge - def vertex_label_set(v, l) vertex_label_dict[v] = l; self; end - - # Get the label for an edge - def edge_label(u,v=nil,n=nil) - u = edge_convert(u,v,n) - edge_label_dict[u] - end - - # Set the label for an edge - def edge_label_set(u, v=nil, l=nil, n=nil) - u.kind_of?(GRATR::Edge) ? l = v : u = edge_convert(u,v,n) - edge_label_dict[u] = l; self - end - - # Delete all graph labels - def clear_all_labels() @vertex_labels = {}; @edge_labels = {}; end - - # Delete an edge label - def edge_label_delete(u, v=nil, n=nil) - u = edge_convert(u,v,n) - edge_label_dict.delete(u) - end - - # Delete a vertex label - def vertex_label_delete(v) vertex_label_dict.delete(v); end - - protected - - def vertex_label_dict() @vertex_labels ||= {}; end - def edge_label_dict() @edge_labels ||= {}; end - - # A generic cost function. It either calls the weight function with and edge - # constructed from the two nodes, or calls the [] operator of the label - # when given a value. If no weight value is specified, the label itself is - # treated as the cost value. - # - # Note: This function will not work for Pseudo or Multi graphs at present. - def cost(u,v=nil,weight=nil) - u.kind_of?(Edge) ? weight = v : u = edge_class[u,v] - case weight - when Proc : weight.call(u) - when nil : self[u] - else self[u][weight] - end - end - - end -end diff --git a/lib/puppet/external/gratr/maximum_flow.rb b/lib/puppet/external/gratr/maximum_flow.rb deleted file mode 100644 index 7b3ef9b2f..000000000 --- a/lib/puppet/external/gratr/maximum_flow.rb +++ /dev/null @@ -1,64 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - -module GRATR - - module Graph - - module MaximumFlow - - # Maximum flow, it returns an array with the maximum flow and a hash of flow per edge - # Currently a highly inefficient implementation, FIXME, This should use Goldberg and Tarjan's method. - def maximum_flow(s, t, capacity = nil, zero = 0) - flow = Hash.new(zero) - available = Hash.new(zero) - total = zero - edges.each {|e| available[e] = cost(e,capacity)} - adj_positive = Proc.new do |u| - adjacent(u).select {|r| available[edge_class[u,r]] > zero} - end - while (tree = bfs_tree_from_vertex(start))[t] - route = [t] - while route[-1] != s - route << tree[route[route[-1]]] - raise ArgumentError, "No route from #{s} to #{t} possible" - end; route.reverse - amt = route.map {|e| available[e]}.min - route.each do |e| - flow[e] += amt - available[e] -= amt - end - total += amt - end - - [total, flow] - end - - end # MaximumFlow - end # Graph -end # GRATR
\ No newline at end of file diff --git a/lib/puppet/external/gratr/search.rb b/lib/puppet/external/gratr/search.rb deleted file mode 100644 index 3206ec5d9..000000000 --- a/lib/puppet/external/gratr/search.rb +++ /dev/null @@ -1,409 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -module GRATR - module Graph - module Search - - # Options are mostly callbacks passed in as a hash. - # The following are valid, anything else is ignored - # :enter_vertex => Proc Called upon entry of a vertex - # :exit_vertex => Proc Called upon exit of a vertex - # :root_vertex => Proc Called when a vertex the a root of a tree - # :start_vertex => Proc Called for the first vertex of the search - # :examine_edge => Proc Called when an edge is examined - # :tree_edge => Proc Called when the edge is a member of the tree - # :back_edge => Proc Called when the edge is a back edge - # :forward_edge => Proc Called when the edge is a forward edge - # :adjacent => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms - # - # :start => Vertex Specifies the vertex to start search from - # - # If a &block is specified it defaults to :enter_vertex - # - # Returns the list of vertexes as reached by enter_vertex - # This allows for calls like, g.bfs.each {|v| ...} - # - # Can also be called like bfs_examine_edge {|e| ... } or - # dfs_back_edge {|e| ... } for any of the callbacks - # - # A full example usage is as follows: - # - # ev = Proc.new {|x| puts "Enter Vertex #{x}"} - # xv = Proc.new {|x| puts "Exit Vertex #{x}"} - # sv = Proc.new {|x| puts "Start Vertex #{x}"} - # ee = Proc.new {|x| puts "Examine Edge #{x}"} - # te = Proc.new {|x| puts "Tree Edge #{x}"} - # be = Proc.new {|x| puts "Back Edge #{x}"} - # fe = Proc.new {|x| puts "Forward Edge #{x}"} - # Digraph[1,2,2,3,3,4].dfs({ - # :enter_vertex => ev, - # :exit_vertex => xv, - # :start_vertex => sv, - # :examine_edge => ee, - # :tree_edge => te, - # :back_edge => be, - # :forward_edge => fe }) - # - # Which outputs: - # - # Start Vertex 1 - # Enter Vertex 1 - # Examine Edge (1=2) - # Tree Edge (1=2) - # Enter Vertex 2 - # Examine Edge (2=3) - # Tree Edge (2=3) - # Enter Vertex 3 - # Examine Edge (3=4) - # Tree Edge (3=4) - # Enter Vertex 4 - # Examine Edge (1=4) - # Back Edge (1=4) - # Exit Vertex 4 - # Exit Vertex 3 - # Exit Vertex 2 - # Exit Vertex 1 - def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end - - # See options for bfs method - def dfs(options={}, &block) gratr_search_helper(:pop, options, &block); end - - # Routine to compute a spanning forest for the given search method - # Returns two values, first is a hash of predecessors and second an array of root nodes - def spanning_forest(start, routine) - predecessor = {} - roots = [] - te = Proc.new {|e| predecessor[e.target] = e.source} - rv = Proc.new {|v| roots << v} - method(routine).call :start => start, :tree_edge => te, :root_vertex => rv - [predecessor, roots] - end - - # Return the dfs spanning forest for the given start node, see spanning_forest - def dfs_spanning_forest(start) spanning_forest(start, :dfs); end - - # Return the bfs spanning forest for the given start node, see spanning_forest - def bfs_spanning_forest(start) spanning_forest(start, :bfs); end - - # Returns a hash of predecessors in a tree rooted at the start node. If this is a connected graph - # then it will be a spanning tree and contain all vertices. An easier way to tell if it's a spanning tree is to - # use a spanning_forest call and check if there is a single root node. - def tree_from_vertex(start, routine) - predecessor={} - correct_tree = false - te = Proc.new {|e| predecessor[e.target] = e.source if correct_tree} - rv = Proc.new {|v| correct_tree = (v == start)} - method(routine).call :start => start, :tree_edge => te, :root_vertex => rv - predecessor - end - - # Returns a hash of predecessors for the depth first search tree rooted at the given node - def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end - - # Returns a hash of predecessors for the depth first search tree rooted at the given node - def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end - - # An inner class used for greater efficiency in lexicograph_bfs - # - # Original desgn taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg, 87-89 - class LexicographicQueue - - # Called with the initial values (array) - def initialize(values) - @node = Struct.new(:back, :forward, :data) - @node.class_eval { def hash() @hash; end; @@cnt=0 } - @set = {} - @tail = @node.new(nil, nil, Array.new(values)) - @tail.instance_eval { @hash = (@@cnt+=1) } - values.each {|a| @set[a] = @tail} - end - - # Pop an entry with maximum lexical value from queue - def pop() - return nil unless @tail - value = @tail[:data].pop - @tail = @tail[:forward] while @tail and @tail[:data].size == 0 - @set.delete(value); value - end - - # Increase lexical value of given values (array) - def add_lexeme(values) - fix = {} - values.select {|v| @set[v]}.each do |w| - sw = @set[w] - if fix[sw] - s_prime = sw[:back] - else - s_prime = @node.new(sw[:back], sw, []) - s_prime.instance_eval { @hash = (@@cnt+=1) } - @tail = s_prime if @tail == sw - sw[:back][:forward] = s_prime if sw[:back] - sw[:back] = s_prime - fix[sw] = true - end - s_prime[:data] << w - sw[:data].delete(w) - @set[w] = s_prime - end - fix.keys.select {|n| n[:data].size == 0}.each do |e| - e[:forward][:back] = e[:back] if e[:forward] - e[:back][:forward] = e[:forward] if e[:back] - end - end - - end - - # Lexicographic breadth-first search, the usual queue of vertices - # is replaced by a queue of unordered subsets of the vertices, - # which is sometimes refined but never reordered. - # - # Originally developed by Rose, Tarjan, and Leuker, "Algorithmic - # aspects of vertex elimination on graphs", SIAM J. Comput. 5, 266-283 - # MR53 #12077 - # - # Implementation taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg, 84-90 - def lexicograph_bfs(&block) - lex_q = GRATR::Graph::Search::LexicographicQueue.new(vertices) - result = [] - num_vertices.times do - v = lex_q.pop - result.unshift(v) - lex_q.add_lexeme(adjacent(v)) - end - result.each {|r| block.call(r)} if block - result - end - - - # A* Heuristic best first search - # - # start is the starting vertex for the search - # - # func is a Proc that when passed a vertex returns the heuristic - # weight of sending the path through that node. It must always - # be equal to or less than the true cost - # - # options are mostly callbacks passed in as a hash, the default block is - # :discover_vertex and weight is assumed to be the label for the Edge. - # The following options are valid, anything else is ignored. - # - # * :weight => can be a Proc, or anything else is accessed using the [] for the - # the label or it defaults to using - # the value stored in the label for the Edge. If it is a Proc it will - # pass the edge to the proc and use the resulting value. - # * :discover_vertex => Proc invoked when a vertex is first discovered - # and is added to the open list. - # * :examine_vertex => Proc invoked when a vertex is popped from the - # queue (i.e., it has the lowest cost on the open list). - # * :examine_edge => Proc invoked on each out-edge of a vertex - # immediately after it is examined. - # * :edge_relaxed => Proc invoked on edge (u,v) if d[u] + w(u,v) < d[v]. - # * :edge_not_relaxed=> Proc invoked if the edge is not relaxed (see above). - # * :black_target => Proc invoked when a vertex that is on the closed - # list is "rediscovered" via a more efficient path, and is re-added - # to the OPEN list. - # * :finish_vertex => Proc invoked on a vertex when it is added to the - # closed list, which happens after all of its out edges have been - # examined. - # - # Returns array of nodes in path, or calls block on all nodes, - # upon failure returns nil - # - # Can also be called like astar_examine_edge {|e| ... } or - # astar_edge_relaxed {|e| ... } for any of the callbacks - # - # The criteria for expanding a vertex on the open list is that it has the - # lowest f(v) = g(v) + h(v) value of all vertices on open. - # - # The time complexity of A* depends on the heuristic. It is exponential - # in the worst case, but is polynomial when the heuristic function h - # meets the following condition: |h(x) - h*(x)| < O(log h*(x)) where h* - # is the optimal heuristic, i.e. the exact cost to get from x to the goal. - # - # Also see: http://en.wikipedia.org/wiki/A-star_search_algorithm - # - def astar(start, goal, func, options, &block) - options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" - options.instance_eval "def handle_edge(sym,u,v) self[sym].call(#{edge_class}[u,v]) if self[sym]; end" - - d = { start => 0 } - f = { start => func.call(start) } - color = {start => :gray} - p = Hash.new {|k| p[k] = k} - queue = [start] - block.call(start) if block - until queue.empty? - u = queue.pop - options.handle_vertex(:examine_vertex, u) - adjacent(u).each do |v| - e = edge_class[u,v] - options.handle_edge(:examine_edge, u, v) - w = cost(e, options[:weight]) - raise ArgumentError unless w - if d[v].nil? or (w + d[u]) < d[v] - options.handle_edge(:edge_relaxed, u, v) - d[v] = w + d[u] - f[v] = d[v] + func.call(u) - p[v] = u - unless color[v] == :gray - options.handle_vertex(:black_target, v) if color[v] == :black - color[v] = :gray - options.handle_vertex(:discover_vertex, v) - queue << v - block.call(v) if block - return [start]+queue if v == goal - end - else - options.handle_edge(:edge_not_relaxed, u, v) - end - end # adjacent(u) - color[u] = :black - options.handle_vertex(:finish_vertex,u) - end # queue.empty? - nil # failure, on fall through - end # astar - - # Best first has all the same options as astar with func set to h(v) = 0. - # There is an additional option zero which should be defined to zero - # for the operation '+' on the objects used in the computation of cost. - # The parameter zero defaults to 0. - def best_first(start, goal, options, zero=0, &block) - func = Proc.new {|v| zero} - astar(start, goal, func, options, &block) - end - - alias_method :pre_search_method_missing, :method_missing # :nodoc: - def method_missing(sym,*args, &block) # :nodoc: - m1=/^dfs_(\w+)$/.match(sym.to_s) - dfs((args[0] || {}).merge({m1.captures[0].to_sym => block})) if m1 - m2=/^bfs_(\w+)$/.match(sym.to_s) - bfs((args[0] || {}).merge({m2.captures[0].to_sym => block})) if m2 - pre_search_method_missing(sym, *args, &block) unless m1 or m2 - end - - private - - def gratr_search_helper(op, options={}, &block) # :nodoc: - return nil if size == 0 - result = [] - # Create options hash that handles callbacks - options = {:enter_vertex => block, :start => to_a[0]}.merge(options) - options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" - options.instance_eval "def handle_edge(sym,e) self[sym].call(e) if self[sym]; end" - # Create waiting list that is a queue or stack depending on op specified. - # First entry is the start vertex. - waiting = [options[:start]] - waiting.instance_eval "def next() #{op.to_s}; end" - # Create color map with all set to unvisited except for start vertex - # will be set to waiting - color_map = vertices.inject({}) {|a,v| a[v] = :unvisited; a} - color_map.merge!(waiting[0] => :waiting) - options.handle_vertex(:start_vertex, waiting[0]) - options.handle_vertex(:root_vertex, waiting[0]) - # Perform the actual search until nothing is waiting - until waiting.empty? - # Loop till the search iterator exhausts the waiting list - visited_edges={} # This prevents retraversing edges in undirected graphs - until waiting.empty? - gratr_search_iteration(options, waiting, color_map, visited_edges, result, op == :pop) - end - # Waiting list is exhausted, see if a new root vertex is available - u=color_map.detect {|key,value| value == :unvisited} - waiting.push(u[0]) if u - options.handle_vertex(:root_vertex, u[0]) if u - end; result - end - - def gratr_search_iteration(options, waiting, color_map, visited_edges, result, recursive=false) # :nodoc: - # Get the next waiting vertex in the list - u = waiting.next - options.handle_vertex(:enter_vertex,u) - result << u - # Examine all adjacent outgoing edges, not previously traversed - adj_proc = options[:adjacent] || self.method(:adjacent).to_proc - adj_proc.call(u,:type => :edges, :direction => :out).reject {|w| visited_edges[w]}.each do |e| - e = e.reverse unless directed? or e.source == u # Preserves directionality where required - v = e.target - options.handle_edge(:examine_edge, e) - visited_edges[e]=true - case color_map[v] - # If it's unvisited it goes into the waiting list - when :unvisited - options.handle_edge(:tree_edge, e) - color_map[v] = :waiting - waiting.push(v) - # If it's recursive (i.e. dfs) then call self - gratr_search_iteration(options, waiting, color_map, visited_edges, result, true) if recursive - when :waiting - options.handle_edge(:back_edge, e) - else - options.handle_edge(:forward_edge, e) - end - end - # Finished with this vertex - options.handle_vertex(:exit_vertex, u) - color_map[u] = :visited - end - - public - # Topological Sort Iterator - # - # The topological sort algorithm creates a linear ordering of the vertices - # such that if edge (u,v) appears in the graph, then u comes before v in - # the ordering. The graph must be a directed acyclic graph (DAG). - # - # The iterator can also be applied to undirected graph or to a DG graph - # which contains a cycle. In this case, the Iterator does not reach all - # vertices. The implementation of acyclic? and cyclic? uses this fact. - # - # Can be called with a block as a standard Ruby iterator, or it can - # be used directly as it will return the result as an Array - def topsort(start = nil, &block) - result = [] - go = true - back = Proc.new {|e| go = false } - push = Proc.new {|v| result.unshift(v) if go} - start ||= vertices[0] - dfs({:exit_vertex => push, :back_edge => back, :start => start}) - result.each {|v| block.call(v)} if block; result - end - - # Returns true if a graph contains no cycles, false otherwise - def acyclic?() topsort.size == size; end - - # Returns false if a graph contains no cycles, true otherwise - def cyclic?() not acyclic?; end - - - end # Search - end # Graph -end # GRATR diff --git a/lib/puppet/external/gratr/strong_components.rb b/lib/puppet/external/gratr/strong_components.rb deleted file mode 100644 index 796ae16bb..000000000 --- a/lib/puppet/external/gratr/strong_components.rb +++ /dev/null @@ -1,127 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'set' - -module GRATR - module Graph - module StrongComponents - # strong_components computes the strongly connected components - # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan - # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on - # Computing, 1(2):146-160, 1972 - # - # The output of the algorithm is an array of components where is - # component is an array of vertices - # - # A strongly connected component of a directed graph G=(V,E) is a maximal - # set of vertices U which is in V such that for every pair of - # vertices u and v in U, we have both a path from u to v - # and path from v to u. That is to say that u and v are reachable - # from each other. - # - def strong_components - - dfs_num = 0 - stack = []; result = []; root = {}; comp = {}; number = {} - - # Enter vertex callback - enter = Proc.new do |v| - root[v] = v - comp[v] = :new - number[v] = (dfs_num += 1) - stack.push(v) - end - - # Exit vertex callback - exit = Proc.new do |v| - adjacent(v).each do |w| - if comp[w] == :new - root[v] = (number[root[v]] < number[root[w]] ? root[v] : root[w]) - end - end - if root[v] == v - component = [] - begin - w = stack.pop - comp[w] = :assigned - component << w - end until w == v - result << component - end - end - - # Execute depth first search - dfs({:enter_vertex => enter, :exit_vertex => exit}); result - - end # strong_components - - # Returns a condensation graph of the strongly connected components - # Each node is an array of nodes from the original graph - def condensation - sc = strong_components - cg = self.class.new - map = sc.inject({}) do |a,c| - c.each {|v| a[v] = c }; a - end - sc.each do |c| - c.each do |v| - adjacent(v).each {|v| cg.add_edge!(c, map[v]) unless c == map[v]} - end - end; cg - end - - # Compute transitive closure of a graph. That is any node that is reachable - # along a path is added as a directed edge. - def transitive_closure! - cgtc = condensation.gratr_inner_transitive_closure! - cgtc.each do |cgv| - cgtc.adjacent(cgv).each do |adj| - cgv.each do |u| - adj.each {|v| add_edge!(u,v)} - end - end - end; self - end - - # This returns the transitive closure of a graph. The original graph - # is not changed. - def transitive_closure() self.class.new(self).transitive_closure!; end - - private - def gratr_inner_transitive_closure! # :nodoc: - topsort.reverse.each do |u| - adjacent(u).each do |v| - adjacent(v).each {|w| add_edge!(u,w) unless edge?(u,w)} - end - end; self - end - end # StrongComponens - - end # Graph -end # GRATR diff --git a/lib/puppet/external/gratr/undirected_graph.rb b/lib/puppet/external/gratr/undirected_graph.rb deleted file mode 100644 index 86963d27c..000000000 --- a/lib/puppet/external/gratr/undirected_graph.rb +++ /dev/null @@ -1,153 +0,0 @@ -#-- -# Copyright (c) 2006 Shawn Patrick Garbett -# Copyright (c) 2002,2004,2005 by Horst Duchene -# -# Redistribution and use in source and binary forms, with or without modification, -# are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright notice(s), -# this list of conditions and the following disclaimer. -# * Redistributions in binary form must reproduce the above copyright notice, -# this list of conditions and the following disclaimer in the documentation -# and/or other materials provided with the distribution. -# * Neither the name of the Shawn Garbett nor the names of its contributors -# may be used to endorse or promote products derived from this software -# without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND -# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED -# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE -# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE -# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR -# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER -# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE -# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -#++ - - -require 'puppet/external/gratr/adjacency_graph' -require 'puppet/external/gratr/search' -require 'puppet/external/gratr/biconnected' -require 'puppet/external/gratr/comparability' -require 'set' - -module GRATR - class UndirectedGraph - include AdjacencyGraph - include Graph::Search - include Graph::Biconnected - include Graph::Comparability - - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? GRATR::Graph or p.kind_of? Array) - end if self.class == GRATR::UndirectedGraph - super(*params) - end - - # UndirectedGraph is by definition undirected, always returns false - def directed?() false; end - - # Redefine degree (default was sum) - def degree(v) in_degree(v); end - - # A vertex of an undirected graph is balanced by definition - def balanced?(v) true; end - - # UndirectedGraph uses UndirectedEdge for the edge class. - def edge_class() @parallel_edges ? GRATR::MultiUndirectedEdge : GRATR::UndirectedEdge; end - - def remove_edge!(u, v=nil) - unless u.kind_of? GRATR::Edge - raise ArgumentError if @parallel_edges - u = edge_class[u,v] - end - super(u.reverse) unless u.source == u.target - super(u) - end - - # A triangulated graph is an undirected perfect graph that every cycle of length greater than - # three possesses a chord. They have also been called chordal, rigid circuit, monotone transitive, - # and perfect elimination graphs. - # - # Implementation taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg. 90 - def triangulated? - a = Hash.new {|h,k| h[k]=Set.new}; sigma=lexicograph_bfs - inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc} - sigma[0..-2].each do |v| - x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] } - unless x.empty? - u = sigma[x.map {|y| inv_sigma[y]}.min] - a[u].merge(x - [u]) - end - return false unless a[v].all? {|z| adjacent?(v,z)} - end - true - end - - def chromatic_number - return triangulated_chromatic_number if triangulated? - raise NotImplementedError - end - - # An interval graph can have its vertices into one-to-one - # correspondence with a set of intervals F of a linearly ordered - # set (like the real line) such that two vertices are connected - # by an edge of G if and only if their corresponding intervals - # have nonempty intersection. - def interval?() triangulated? and complement.comparability?; end - - # A permutation diagram consists of n points on each of two parallel - # lines and n straight line segments matchin the points. The intersection - # graph of the line segments is called a permutation graph. - def permutation?() comparability? and complement.comparability?; end - - # An undirected graph is defined to be split if there is a partition - # V = S + K of its vertex set into a stable set S and a complete set K. - def split?() triangulated? and complement.triangulated?; end - - private - # Implementation taken from Golumbic's, "Algorithmic Graph Theory and - # Perfect Graphs" pg. 99 - def triangulated_chromatic_number - chi = 1; s= Hash.new {|h,k| h[k]=0} - sigma=lexicograph_bfs - inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc} - sigma.each do |v| - x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] } - unless x.empty? - u = sigma[x.map {|y| inv_sigma[y]}.min] - s[u] = [s[u], x.size-1].max - chi = [chi, x.size+1].max if s[v] < x.size - end - end; chi - end - - end # UndirectedGraph - - # This is a UndirectedGraph that allows for parallel edges, but does not - # allow loops - class UndirectedPseudoGraph < UndirectedGraph - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? Graph or p.kind_of? Array) - end - super(:parallel_edges, *params) - end - end - - # This is a UndirectedGraph that allows for parallel edges and loops - class UndirectedMultiGraph < UndirectedGraph - def initialize(*params) - raise ArgumentError if params.any? do |p| - !(p.kind_of? Graph or p.kind_of? Array) - end - super(:parallel_edges, :loops, *params) - end - end - - -end # GRATR diff --git a/lib/puppet/node/catalog.rb b/lib/puppet/node/catalog.rb index c9de2019d..9601309d8 100644 --- a/lib/puppet/node/catalog.rb +++ b/lib/puppet/node/catalog.rb @@ -1,5 +1,4 @@ require 'puppet/indirector' -require 'puppet/external/gratr/digraph' # This class models a node catalog. It is the thing # meant to be passed from server to client, and it contains all @@ -212,9 +211,8 @@ class Puppet::Node::Catalog < Puppet::PGraph # Create a proc for examining edges, which we'll use to build our tree # of TransBuckets and TransObjects. bucket = nil - edges = proc do |edge| + walk(main, :out) do |source, target| # The sources are always non-builtins. - source, target = edge.source, edge.target unless tmp = buckets[source.to_s] if tmp = buckets[source.to_s] = source.to_trans bucket = tmp @@ -239,11 +237,6 @@ class Puppet::Node::Catalog < Puppet::PGraph end end end - dfs(:start => main, :examine_edge => edges) - - unless main - raise Puppet::DevError, "Could not find 'main' class; cannot generate catalog" - end # Retrieve the bucket for the top-level scope and set the appropriate metadata. unless result = buckets[main.to_s] diff --git a/lib/puppet/parser/compile.rb b/lib/puppet/parser/compile.rb index c065e3f38..f76103a28 100644 --- a/lib/puppet/parser/compile.rb +++ b/lib/puppet/parser/compile.rb @@ -1,10 +1,6 @@ # Created by Luke A. Kanies on 2007-08-13. # Copyright (c) 2007. All rights reserved. -require 'puppet/external/gratr/digraph' -require 'puppet/external/gratr/import' -require 'puppet/external/gratr/dot' - require 'puppet/node' require 'puppet/node/catalog' require 'puppet/util/errors' @@ -420,7 +416,7 @@ class Puppet::Parser::Compile @tags = [] # A graph for maintaining scope relationships. - @scope_graph = GRATR::Digraph.new + @scope_graph = Puppet::SimpleGraph.new # For maintaining the relationship between scopes and their resources. @catalog = Puppet::Node::Catalog.new(@node.name) diff --git a/lib/puppet/pgraph.rb b/lib/puppet/pgraph.rb index 49fd21401..54b815b45 100644 --- a/lib/puppet/pgraph.rb +++ b/lib/puppet/pgraph.rb @@ -1,10 +1,6 @@ # Created by Luke A. Kanies on 2006-11-24. # Copyright (c) 2006. All rights reserved. -require 'puppet/external/gratr/digraph' -require 'puppet/external/gratr/import' -require 'puppet/external/gratr/dot' - require 'puppet/relationship' require 'puppet/simple_graph' @@ -45,7 +41,7 @@ class Puppet::PGraph < Puppet::SimpleGraph # Which resources a given resource depends upon. def dependents(resource) - tree_from_vertex2(resource).keys + tree_from_vertex(resource).keys end # Which resources depend upon the given resource. @@ -58,8 +54,7 @@ class Puppet::PGraph < Puppet::SimpleGraph # Strangely, it's significantly faster to search a reversed # tree in the :out direction than to search a normal tree # in the :in direction. - @reversal.tree_from_vertex2(resource, :out).keys - #tree_from_vertex2(resource, :in).keys + @reversal.tree_from_vertex(resource, :out).keys end # Override this method to use our class instead. @@ -68,9 +63,9 @@ class Puppet::PGraph < Puppet::SimpleGraph end # Determine all of the leaf nodes below a given vertex. - def leaves(vertex, type = :dfs) - tree = tree_from_vertex(vertex, type) - l = tree.keys.find_all { |c| adjacent(c, :direction => :out).empty? } + def leaves(vertex, direction = :out) + tree = tree_from_vertex(vertex, direction) + l = tree.keys.find_all { |c| adjacent(c, :direction => direction).empty? } return l end @@ -150,61 +145,14 @@ class Puppet::PGraph < Puppet::SimpleGraph remove_vertex!(container) end end - - # For some reason, unconnected vertices do not show up in - # this graph. - def to_jpg(path, name) - gv = vertices() - Dir.chdir(path) do - induced_subgraph(gv).write_to_graphic_file('jpg', name) - end - end - - # Replace the default method, because we want to throw errors on back edges, - # not just skip them. - def topsort(start = nil, &block) - result = [] - go = true - cycles = [] - back = Proc.new { |e| - cycles << e - go = false - } - push = Proc.new { |v| result.unshift(v) if go} - start ||= vertices[0] - dfs({:exit_vertex => push, :back_edge => back, :start => start}) - if block_given? - result.each {|v| yield(v) } - end - - if cycles.length > 0 - msg = "Found cycles in the following relationships:" - cycles.each { |edge| msg += " %s => %s" % [edge.source, edge.target] } - raise Puppet::Error, msg - end - return result - end - - def to_yaml_properties - instance_variables - end # A different way of walking a tree, and a much faster way than the # one that comes with GRATR. - def tree_from_vertex2(start, direction = :out) + def tree_from_vertex(start, direction = :out) predecessor={} walk(start, direction) do |parent, child| predecessor[child] = parent end predecessor end - - # A support method for tree_from_vertex2. Just walk the tree and pass - # the parents and children. - def walk(source, direction, &block) - adjacent(source, :direction => direction).each do |target| - yield source, target - walk(target, direction, &block) - end - end end diff --git a/lib/puppet/relationship.rb b/lib/puppet/relationship.rb index c611928f2..05b7dc39e 100644 --- a/lib/puppet/relationship.rb +++ b/lib/puppet/relationship.rb @@ -59,7 +59,11 @@ class Puppet::Relationship end def ref - "%s => %s" % [source.ref, target.ref] + "%s => %s" % [source, target] + end + + def to_s + ref end end diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb index c9920e60a..11542ad53 100644 --- a/lib/puppet/simple_graph.rb +++ b/lib/puppet/simple_graph.rb @@ -1,14 +1,11 @@ # Created by Luke A. Kanies on 2007-11-07. # Copyright (c) 2007. All rights reserved. -require 'puppet/external/gratr/dot' +require 'puppet/external/dot' require 'puppet/relationship' -require 'puppet/external/gratr/search' # A hopefully-faster graph class to replace the use of GRATR. class Puppet::SimpleGraph - include GRATR::Graph::Search - # An internal class for handling a vertex's edges. class VertexWrapper attr_accessor :in, :out, :vertex @@ -52,6 +49,17 @@ class Puppet::SimpleGraph return false end + # Create methods for returning the degree and edges. + [:in, :out].each do |direction| + define_method("%s_degree" % direction) do + @adjacencies[direction].length + end + + define_method("%s_edges" % direction) do + @adjacencies[direction].values.flatten + end + end + # The other vertex in the edge. def other_vertex(direction, edge) case direction @@ -66,6 +74,10 @@ class Puppet::SimpleGraph def remove_edge(direction, edge) @adjacencies[direction][other_vertex(direction, edge)].delete(edge) end + + def to_s + vertex.to_s + end end def initialize @@ -80,7 +92,7 @@ class Puppet::SimpleGraph @edges.clear end - # Whether our graph is directed. Always true. (Used by the GRATR search lib.) + # Whether our graph is directed. Always true. Used to produce dot files. def directed? true end @@ -96,16 +108,47 @@ class Puppet::SimpleGraph result end - # Return the size of the graph. Used by GRATR. + # Return the size of the graph. def size @vertices.length end - # Return the graph as an array. Again, used by GRATR. + # Return the graph as an array. def to_a @vertices.keys end + # Provide a topological sort. + def topsort + degree = {} + zeros = [] + result = [] + + # Collect each of our vertices, with the number of in-edges each has. + @vertices.each do |name, wrapper| + zeros << wrapper if wrapper.in_degree == 0 + degree[wrapper.vertex] = wrapper.in_edges + end + + # Iterate over each 0-degree vertex, decrementing the degree of + # each of its out-edges. + while wrapper = zeros.pop do + result << wrapper.vertex + wrapper.out_edges.each do |edge| + degree[edge.target].delete(edge) + zeros << @vertices[edge.target] if degree[edge.target].length == 0 + end + end + + # If we have any vertices left with non-zero in-degrees, then we've found a cycle. + if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0 + message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ") + raise Puppet::Error, "Found dependency cycles in the following relationships: %s" % message + end + + return result + end + # Add a new vertex to the graph. def add_vertex!(vertex) return false if vertex?(vertex) @@ -195,6 +238,27 @@ class Puppet::SimpleGraph end public + +# # For some reason, unconnected vertices do not show up in +# # this graph. +# def to_jpg(path, name) +# gv = vertices() +# Dir.chdir(path) do +# induced_subgraph(gv).write_to_graphic_file('jpg', name) +# end +# end + + def to_yaml_properties + instance_variables + end + + # Just walk the tree and pass each edge. + def walk(source, direction, &block) + adjacent(source, :direction => direction).each do |target| + yield source, target + walk(target, direction, &block) + end + end # LAK:FIXME This is just a paste of the GRATR code with slight modifications. diff --git a/lib/puppet/util/graph.rb b/lib/puppet/util/graph.rb index 028df5539..a9744578b 100644 --- a/lib/puppet/util/graph.rb +++ b/lib/puppet/util/graph.rb @@ -17,20 +17,14 @@ module Puppet::Util::Graph self.each do |child| unless block_given? and ! yield(child) graph.add_edge!(self, child) - - if graph.cyclic? - raise Puppet::Error, "%s created a cyclic graph" % self - end if child.respond_to?(:to_graph) child.to_graph(graph, &block) end end end - - if graph.cyclic? - raise Puppet::Error, "%s created a cyclic graph" % self - end + + # Do a topsort, which will throw an exception if the graph is cyclic. graph end |