diff --git a/lib/puppet/external/gratr/rdot.rb b/lib/puppet/external/dot.rb similarity index 100% rename from lib/puppet/external/gratr/rdot.rb rename to 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,501 +1,494 @@ 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 # of the information in the catalog, including the resources # and the relationships between them. class Puppet::Node::Catalog < Puppet::PGraph extend Puppet::Indirector indirects :catalog, :terminus_class => :compiler # The host name this is a catalog for. attr_accessor :name # The catalog version. Used for testing whether a catalog # is up to date. attr_accessor :version # How long this catalog took to retrieve. Used for reporting stats. attr_accessor :retrieval_duration # How we should extract the catalog for sending to the client. attr_reader :extraction_format # We need the ability to set this externally, so we can yaml-dump the # catalog. attr_accessor :edgelist_class # Whether this is a host catalog, which behaves very differently. # In particular, reports are sent, graphs are made, and state is # stored in the state database. If this is set incorrectly, then you often # end up in infinite loops, because catalogs are used to make things # that the host catalog needs. attr_accessor :host_config # Whether this graph is another catalog's relationship graph. # We don't want to accidentally create a relationship graph for another # relationship graph. attr_accessor :is_relationship_graph # Whether this catalog was retrieved from the cache, which affects # whether it is written back out again. attr_accessor :from_cache # Add classes to our class list. def add_class(*classes) classes.each do |klass| @classes << klass end # Add the class names as tags, too. tag(*classes) end # Add one or more resources to our graph and to our resource table. def add_resource(*resources) resources.each do |resource| unless resource.respond_to?(:ref) raise ArgumentError, "Can only add objects that respond to :ref" end ref = resource.ref if @resource_table.include?(ref) raise ArgumentError, "Resource %s is already defined" % ref else @resource_table[ref] = resource end resource.catalog = self unless is_relationship_graph add_vertex!(resource) end end # Create an alias for a resource. def alias(resource, name) resource.ref =~ /^(.+)\[/ newref = "%s[%s]" % [$1 || resource.class.name, name] raise(ArgumentError, "Cannot alias %s to %s; resource %s already exists" % [resource.ref, name, newref]) if @resource_table[newref] @resource_table[newref] = resource @aliases[resource.ref] << newref end # Apply our catalog to the local host. Valid options # are: # :tags - set the tags that restrict what resources run # during the transaction # :ignoreschedules - tell the transaction to ignore schedules # when determining the resources to run def apply(options = {}) @applying = true Puppet::Util::Storage.load if host_config? transaction = Puppet::Transaction.new(self) transaction.tags = options[:tags] if options[:tags] transaction.ignoreschedules = true if options[:ignoreschedules] transaction.addtimes :config_retrieval => @retrieval_duration begin transaction.evaluate rescue Puppet::Error => detail Puppet.err "Could not apply complete catalog: %s" % detail rescue => detail puts detail.backtrace if Puppet[:trace] Puppet.err "Got an uncaught exception of type %s: %s" % [detail.class, detail] ensure # Don't try to store state unless we're a host config # too recursive. Puppet::Util::Storage.store if host_config? end yield transaction if block_given? transaction.send_report if host_config and (Puppet[:report] or Puppet[:summarize]) return transaction ensure @applying = false cleanup() transaction.cleanup if defined? transaction and transaction end # Are we in the middle of applying the catalog? def applying? @applying end def clear(remove_resources = true) super() # We have to do this so that the resources clean themselves up. @resource_table.values.each { |resource| resource.remove } if remove_resources @resource_table.clear if defined?(@relationship_graph) and @relationship_graph @relationship_graph.clear(false) @relationship_graph = nil end end def classes @classes.dup end # Create an implicit resource, meaning that it will lose out # to any explicitly defined resources. This method often returns # nil. # The quirk of this method is that it's not possible to create # an implicit resource before an explicit resource of the same name, # because all explicit resources are created before any generate() # methods are called on the individual resources. Thus, this # method can safely just check if an explicit resource already exists # and toss this implicit resource if so. def create_implicit_resource(type, options) unless options.include?(:implicit) options[:implicit] = true end # This will return nil if an equivalent explicit resource already exists. # When resource classes no longer retain references to resource instances, # this will need to be modified to catch that conflict and discard # implicit resources. if resource = create_resource(type, options) resource.implicit = true return resource else return nil end end # Create a new resource and register it in the catalog. def create_resource(type, options) unless klass = Puppet::Type.type(type) raise ArgumentError, "Unknown resource type %s" % type end return unless resource = klass.create(options) @transient_resources << resource if applying? add_resource(resource) if @relationship_graph @relationship_graph.add_resource(resource) unless @relationship_graph.resource(resource.ref) end resource end # Make sure we support the requested extraction format. def extraction_format=(value) unless respond_to?("extract_to_%s" % value) raise ArgumentError, "Invalid extraction format %s" % value end @extraction_format = value end # Turn our catalog graph into whatever the client is expecting. def extract send("extract_to_%s" % extraction_format) end # Create the traditional TransBuckets and TransObjects from our catalog # graph. This will hopefully be deprecated soon. def extract_to_transportable top = nil current = nil buckets = {} unless main = vertices.find { |res| res.type == "Class" and res.title == :main } raise Puppet::DevError, "Could not find 'main' class; cannot generate catalog" end # 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 else # This is because virtual resources return nil. If a virtual # container resource contains realized resources, we still need to get # to them. So, we keep a reference to the last valid bucket # we returned and use that if the container resource is virtual. end end bucket = tmp || bucket if child = target.to_trans unless bucket raise "No bucket created for %s" % source end bucket.push child # It's important that we keep a reference to any TransBuckets we've created, so # we don't create multiple buckets for children. unless target.builtin? buckets[target.to_s] = child 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] # This only happens when the catalog is entirely empty. result = buckets[main.to_s] = main.to_trans end result.classes = classes # Clear the cache to encourage the GC buckets.clear return result end # Make sure all of our resources are "finished". def finalize make_default_resources @resource_table.values.each { |resource| resource.finish } write_graph(:resources) end def host_config? host_config || false end def initialize(name = nil) super() @name = name if name @extraction_format ||= :transportable @tags = [] @classes = [] @resource_table = {} @transient_resources = [] @applying = false @relationship_graph = nil @aliases = Hash.new { |hash, key| hash[key] = [] } if block_given? yield(self) finalize() end end # Make the default objects necessary for function. def make_default_resources # We have to add the resources to the catalog, or else they won't get cleaned up after # the transaction. # First create the default scheduling objects Puppet::Type.type(:schedule).mkdefaultschedules.each { |res| add_resource(res) unless resource(res.ref) } # And filebuckets if bucket = Puppet::Type.type(:filebucket).mkdefaultbucket add_resource(bucket) end end # Create a graph of all of the relationships in our catalog. def relationship_graph raise(Puppet::DevError, "Tried get a relationship graph for a relationship graph") if self.is_relationship_graph unless defined? @relationship_graph and @relationship_graph # It's important that we assign the graph immediately, because # the debug messages below use the relationships in the # relationship graph to determine the path to the resources # spitting out the messages. If this is not set, # then we get into an infinite loop. @relationship_graph = Puppet::Node::Catalog.new @relationship_graph.host_config = host_config? @relationship_graph.is_relationship_graph = true # First create the dependency graph self.vertices.each do |vertex| @relationship_graph.add_vertex! vertex vertex.builddepends.each do |edge| @relationship_graph.add_edge!(edge) end end # Lastly, add in any autorequires @relationship_graph.vertices.each do |vertex| vertex.autorequire.each do |edge| unless @relationship_graph.edge?(edge.source, edge.target) # don't let automatic relationships conflict with manual ones. unless @relationship_graph.edge?(edge.target, edge.source) vertex.debug "Autorequiring %s" % [edge.source] @relationship_graph.add_edge!(edge) else vertex.debug "Skipping automatic relationship with %s" % (edge.source == vertex ? edge.target : edge.source) end end end end @relationship_graph.write_graph(:relationships) # Then splice in the container information @relationship_graph.splice!(self, Puppet::Type::Component) @relationship_graph.write_graph(:expanded_relationships) end @relationship_graph end # Remove the resource from our catalog. Notice that we also call # 'remove' on the resource, at least until resource classes no longer maintain # references to the resource instances. def remove_resource(*resources) resources.each do |resource| @resource_table.delete(resource.ref) @aliases[resource.ref].each { |res_alias| @resource_table.delete(res_alias) } @aliases[resource.ref].clear remove_vertex!(resource) if vertex?(resource) @relationship_graph.remove_vertex!(resource) if @relationship_graph and @relationship_graph.vertex?(resource) resource.remove end end # Look a resource up by its reference (e.g., File[/etc/passwd]). def resource(type, title = nil) # Always create a resource reference, so that it always canonizes how we # are referring to them. if title ref = Puppet::ResourceReference.new(type, title).to_s else # If they didn't provide a title, then we expect the first # argument to be of the form 'Class[name]', which our # Reference class canonizes for us. ref = Puppet::ResourceReference.new(nil, type).to_s end if resource = @resource_table[ref] return resource elsif defined?(@relationship_graph) and @relationship_graph @relationship_graph.resource(ref) end end # Return an array of all resources. def resources @resource_table.keys end # Add a tag. def tag(*names) names.each do |name| name = name.to_s @tags << name unless @tags.include?(name) if name.include?("::") name.split("::").each do |sub| @tags << sub unless @tags.include?(sub) end end end nil end # Return the list of tags. def tags @tags.dup end # Convert our catalog into a RAL catalog. def to_ral to_catalog :to_type end # Turn our parser catalog into a transportable catalog. def to_transportable to_catalog :to_transobject end # Produce the graph files if requested. def write_graph(name) # We only want to graph the main host catalog. return unless host_config? return unless Puppet[:graph] Puppet.settings.use(:graphing) file = File.join(Puppet[:graphdir], "%s.dot" % name.to_s) File.open(file, "w") { |f| f.puts to_dot("name" => name.to_s.capitalize) } end # LAK:NOTE We cannot yaml-dump the class in the edgelist_class, because classes cannot be # dumped by default, nor does yaml-dumping # the edge-labels work at this point (I don't # know why). # Neither of these matters right now, but I suppose it could at some point. # We also have to have the vertex_dict dumped after the resource table, because yaml can't # seem to handle the output of yaml-dumping the vertex_dict. def to_yaml_properties props = instance_variables.reject { |v| %w{@edgelist_class @edge_labels @vertex_dict}.include?(v) } props << "@vertex_dict" props end private def cleanup unless @transient_resources.empty? remove_resource(*@transient_resources) @transient_resources.clear @relationship_graph = nil end end # An abstracted method for converting one catalog into another type of catalog. # This pretty much just converts all of the resources from one class to another, using # a conversion method. def to_catalog(convert) result = self.class.new(self.name) map = {} vertices.each do |resource| next if resource.respond_to?(:virtual?) and resource.virtual? newres = resource.send(convert) # We can't guarantee that resources don't munge their names # (like files do with trailing slashes), so we have to keep track # of what a resource got converted to. map[resource.ref] = newres result.add_resource newres end message = convert.to_s.gsub "_", " " edges.each do |edge| # Skip edges between virtual resources. next if edge.source.respond_to?(:virtual?) and edge.source.virtual? next if edge.target.respond_to?(:virtual?) and edge.target.virtual? unless source = map[edge.source.ref] raise Puppet::DevError, "Could not find resource %s when converting %s resources" % [edge.source.ref, message] end unless target = map[edge.target.ref] raise Puppet::DevError, "Could not find resource %s when converting %s resources" % [edge.target.ref, message] end result.add_edge!(source, target, edge.label) end map.clear result.add_class *self.classes result.tag(*self.tags) return result end end 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,512 +1,508 @@ # 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' # Maintain a graph of scopes, along with a bunch of data # about the individual catalog we're compiling. class Puppet::Parser::Compile include Puppet::Util include Puppet::Util::Errors attr_reader :parser, :node, :facts, :collections, :catalog, :node_scope # Add a collection to the global list. def add_collection(coll) @collections << coll end # Do we use nodes found in the code, vs. the external node sources? def ast_nodes? parser.nodes.length > 0 end # Store the fact that we've evaluated a class, and store a reference to # the scope in which it was evaluated, so that we can look it up later. def class_set(name, scope) if existing = @class_scopes[name] if existing.nodescope? or scope.nodescope? raise Puppet::ParseError, "Cannot have classes, nodes, or definitions with the same name" else raise Puppet::DevError, "Somehow evaluated the same class twice" end end @class_scopes[name] = scope @catalog.add_class(name) unless name == "" end # Return the scope associated with a class. This is just here so # that subclasses can set their parent scopes to be the scope of # their parent class, and it's also used when looking up qualified # variables. def class_scope(klass) # They might pass in either the class or class name if klass.respond_to?(:classname) @class_scopes[klass.classname] else @class_scopes[klass] end end # Return a list of all of the defined classes. def classlist return @catalog.classes end # Compile our catalog. This mostly revolves around finding and evaluating classes. # This is the main entry into our catalog. def compile # Set the client's parameters into the top scope. set_node_parameters() evaluate_main() evaluate_ast_node() evaluate_node_classes() evaluate_generators() fail_on_unevaluated() finish() if Puppet[:storeconfigs] store() end return @catalog end # LAK:FIXME There are no tests for this. def delete_collection(coll) @collections.delete(coll) if @collections.include?(coll) end # LAK:FIXME There are no tests for this. def delete_resource(resource) @resource_table.delete(resource.ref) if @resource_table.include?(resource.ref) end # Return the node's environment. def environment unless defined? @environment if node.environment and node.environment != "" @environment = node.environment else @environment = nil end end @environment end # Evaluate all of the classes specified by the node. def evaluate_node_classes evaluate_classes(@node.classes, topscope) end # Evaluate each specified class in turn. If there are any classes we can't # find, just tag the catalog and move on. This method really just # creates resource objects that point back to the classes, and then the # resources are themselves evaluated later in the process. def evaluate_classes(classes, scope, lazy_evaluate = true) unless scope.source raise Puppet::DevError, "No source for scope passed to evaluate_classes" end found = [] classes.each do |name| # If we can find the class, then make a resource that will evaluate it. if klass = scope.findclass(name) found << name and next if class_scope(klass) # Create a resource to model this class, and then add it to the list # of resources. resource = Puppet::Parser::Resource.new(:type => "class", :title => klass.classname, :scope => scope, :source => scope.source) store_resource(scope, resource) # If they've disabled lazy evaluation (which the :include function does), # then evaluate our resource immediately. resource.evaluate unless lazy_evaluate @catalog.tag(klass.classname) found << name else Puppet.info "Could not find class %s for %s" % [name, node.name] @catalog.tag(name) end end found end # Return a resource by either its ref or its type and title. def findresource(string, name = nil) string = "%s[%s]" % [string.capitalize, name] if name @resource_table[string] end # Set up our compile. We require a parser # and a node object; the parser is so we can look up classes # and AST nodes, and the node has all of the client's info, # like facts and environment. def initialize(node, parser, options = {}) @node = node @parser = parser options.each do |param, value| begin send(param.to_s + "=", value) rescue NoMethodError raise ArgumentError, "Compile objects do not accept %s" % param end end initvars() init_main() end # Create a new scope, with either a specified parent scope or # using the top scope. Adds an edge between the scope and # its parent to the graph. def newscope(parent, options = {}) parent ||= topscope options[:compile] = self options[:parser] ||= self.parser scope = Puppet::Parser::Scope.new(options) @scope_graph.add_edge!(parent, scope) scope end # Find the parent of a given scope. Assumes scopes only ever have # one in edge, which will always be true. def parent(scope) if ary = @scope_graph.adjacent(scope, :direction => :in) and ary.length > 0 ary[0] else nil end end # Return any overrides for the given resource. def resource_overrides(resource) @resource_overrides[resource.ref] end # Return a list of all resources. def resources @resource_table.values end # Store a resource override. def store_override(override) override.override = true # If possible, merge the override in immediately. if resource = @resource_table[override.ref] resource.merge(override) else # Otherwise, store the override for later; these # get evaluated in Resource#finish. @resource_overrides[override.ref] << override end end # Store a resource in our resource table. def store_resource(scope, resource) # This might throw an exception verify_uniqueness(resource) # Store it in the global table. @resource_table[resource.ref] = resource # And in the resource graph. At some point, this might supercede # the global resource table, but the table is a lot faster # so it makes sense to maintain for now. @catalog.add_edge!(scope.resource, resource) end # The top scope is usually the top-level scope, but if we're using AST nodes, # then it is instead the node's scope. def topscope node_scope || @topscope end private # If ast nodes are enabled, then see if we can find and evaluate one. def evaluate_ast_node return unless ast_nodes? # Now see if we can find the node. astnode = nil @node.names.each do |name| break if astnode = @parser.nodes[name.to_s.downcase] end unless (astnode ||= @parser.nodes["default"]) raise Puppet::ParseError, "Could not find default node or by name with '%s'" % node.names.join(", ") end # Create a resource to model this node, and then add it to the list # of resources. resource = Puppet::Parser::Resource.new(:type => "node", :title => astnode.classname, :scope => topscope, :source => topscope.source) store_resource(topscope, resource) @catalog.tag(astnode.classname) resource.evaluate # Now set the node scope appropriately, so that :topscope can # behave differently. @node_scope = class_scope(astnode) end # Evaluate our collections and return true if anything returned an object. # The 'true' is used to continue a loop, so it's important. def evaluate_collections return false if @collections.empty? found_something = false exceptwrap do # We have to iterate over a dup of the array because # collections can delete themselves from the list, which # changes its length and causes some collections to get missed. @collections.dup.each do |collection| found_something = true if collection.evaluate end end return found_something end # Make sure all of our resources have been evaluated into native resources. # We return true if any resources have, so that we know to continue the # evaluate_generators loop. def evaluate_definitions exceptwrap do if ary = unevaluated_resources ary.each do |resource| resource.evaluate end # If we evaluated, let the loop know. return true else return false end end end # Iterate over collections and resources until we're sure that the whole # compile is evaluated. This is necessary because both collections # and defined resources can generate new resources, which themselves could # be defined resources. def evaluate_generators count = 0 loop do done = true # Call collections first, then definitions. done = false if evaluate_collections done = false if evaluate_definitions break if done if count > 1000 raise Puppet::ParseError, "Somehow looped more than 1000 times while evaluating host catalog" end end end # Find and evaluate our main object, if possible. def evaluate_main @main = @parser.findclass("", "") || @parser.newclass("") @topscope.source = @main @main_resource = Puppet::Parser::Resource.new(:type => "class", :title => :main, :scope => @topscope, :source => @main) @topscope.resource = @main_resource @catalog.add_vertex!(@main_resource) @resource_table["Class[main]"] = @main_resource @main_resource.evaluate end # Make sure the entire catalog is evaluated. def fail_on_unevaluated fail_on_unevaluated_overrides fail_on_unevaluated_resource_collections end # If there are any resource overrides remaining, then we could # not find the resource they were supposed to override, so we # want to throw an exception. def fail_on_unevaluated_overrides remaining = [] @resource_overrides.each do |name, overrides| remaining += overrides end unless remaining.empty? fail Puppet::ParseError, "Could not find object(s) %s" % remaining.collect { |o| o.ref }.join(", ") end end # Make sure we don't have any remaining collections that specifically # look for resources, because we want to consider those to be # parse errors. def fail_on_unevaluated_resource_collections remaining = [] @collections.each do |coll| # We're only interested in the 'resource' collections, # which result from direct calls of 'realize'. Anything # else is allowed not to return resources. # Collect all of them, so we have a useful error. if r = coll.resources if r.is_a?(Array) remaining += r else remaining << r end end end unless remaining.empty? raise Puppet::ParseError, "Failed to realize virtual resources %s" % remaining.join(', ') end end # Make sure all of our resources and such have done any last work # necessary. def finish @resource_table.each { |name, resource| resource.finish if resource.respond_to?(:finish) } end # Initialize the top-level scope, class, and resource. def init_main # Create our initial scope and a resource that will evaluate main. @topscope = Puppet::Parser::Scope.new(:compile => self, :parser => self.parser) @scope_graph.add_vertex!(@topscope) end # Set up all of our internal variables. def initvars # The table for storing class singletons. This will only actually # be used by top scopes and node scopes. @class_scopes = {} # The table for all defined resources. @resource_table = {} # The list of objects that will available for export. @exported_resources = {} # The list of overrides. This is used to cache overrides on objects # that don't exist yet. We store an array of each override. @resource_overrides = Hash.new do |overs, ref| overs[ref] = [] end # The list of collections that have been created. This is a global list, # but they each refer back to the scope that created them. @collections = [] # A list of tags we've generated; most class names. @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) @catalog.version = @parser.version end # Set the node's parameters into the top-scope as variables. def set_node_parameters node.parameters.each do |param, value| @topscope.setvar(param, value) end end # Store the catalog into the database. def store unless Puppet.features.rails? raise Puppet::Error, "storeconfigs is enabled but rails is unavailable" end unless ActiveRecord::Base.connected? Puppet::Rails.connect end # We used to have hooks here for forking and saving, but I don't # think it's worth retaining at this point. store_to_active_record(@node, @resource_table.values) end # Do the actual storage. def store_to_active_record(node, resources) begin # We store all of the objects, even the collectable ones benchmark(:info, "Stored catalog for #{node.name}") do Puppet::Rails::Host.transaction do Puppet::Rails::Host.store(node, resources) end end rescue => detail if Puppet[:trace] puts detail.backtrace end Puppet.err "Could not store configs: %s" % detail.to_s end end # Return an array of all of the unevaluated resources. These will be definitions, # which need to get evaluated into native resources. def unevaluated_resources ary = @resource_table.find_all do |name, object| ! object.builtin? and ! object.evaluated? end.collect { |name, object| object } if ary.empty? return nil else return ary end end # Verify that the given resource isn't defined elsewhere. def verify_uniqueness(resource) # Short-curcuit the common case, unless existing_resource = @resource_table[resource.ref] return true end if typeclass = Puppet::Type.type(resource.type) and ! typeclass.isomorphic? Puppet.info "Allowing duplicate %s" % typeclass.name return true end # Either it's a defined type, which are never # isomorphic, or it's a non-isomorphic type, so # we should throw an exception. msg = "Duplicate definition: %s is already defined" % resource.ref if existing_resource.file and existing_resource.line msg << " in file %s at line %s" % [existing_resource.file, existing_resource.line] end if resource.line or resource.file msg << "; cannot redefine" end raise Puppet::ParseError.new(msg) end end 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,210 +1,158 @@ # 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' # This class subclasses a graph class in order to handle relationships # among resources. class Puppet::PGraph < Puppet::SimpleGraph # This is the type used for splicing. attr_accessor :container_type include Puppet::Util def add_edge!(*args) @reversal = nil super end def add_vertex!(*args) @reversal = nil super end # Make sure whichever edge has a label keeps the label def copy_label(source, target, label) # 'require' relationships will not have a label, # and all 'subscribe' relationships have the same # label, at least for now. # Labels default to {}, so we can't just test for nil. newlabel = label || {} oldlabel = edge_label(source, target) || {} if ! newlabel.empty? and oldlabel.empty? edge_label_set(source, target, label) # We should probably check to see if the labels both exist # and don't match, but we'd just throw an error which the user # couldn't do anyting about. end end # 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. def dependencies(resource) # Cache the reversal graph, because it's somewhat expensive # to create. unless defined? @reversal and @reversal @reversal = reversal end # 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. def edge_class() Puppet::Relationship 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 # Collect all of the edges that the passed events match. Returns # an array of edges. def matching_edges(events, base = nil) events.collect do |event| source = base || event.source unless vertex?(source) Puppet.warning "Got an event from invalid vertex %s" % source.ref next end # Get all of the edges that this vertex should forward events # to, which is the same thing as saying all edges directly below # This vertex in the graph. adjacent(source, :direction => :out, :type => :edges).find_all do |edge| edge.match?(event.event) end end.compact.flatten end # Take container information from another graph and use it # to replace any container vertices with their respective leaves. # This creates direct relationships where there were previously # indirect relationships through the containers. def splice!(other, type) # We have to get the container list via a topological sort on the # configuration graph, because otherwise containers that contain # other containers will add those containers back into the # graph. We could get a similar affect by only setting relationships # to container leaves, but that would result in many more # relationships. containers = other.topsort.find_all { |v| v.is_a?(type) and vertex?(v) } containers.each do |container| # Get the list of children from the other graph. children = other.adjacent(container, :direction => :out) # Just remove the container if it's empty. if children.empty? remove_vertex!(container) next end # First create new edges for each of the :in edges [:in, :out].each do |dir| edges = adjacent(container, :direction => dir, :type => :edges) edges.each do |edge| children.each do |child| if dir == :in s = edge.source t = child else s = child t = edge.target end # We don't want to add multiple copies of the # same edge, but we *do* want to make sure we # keep labels around. # XXX This will *not* work when we support multiple # types of labels, and only works now because # you can only do simple subscriptions. if edge?(s, t) copy_label(s, t, edge.label) next end add_edge!(s, t, edge.label) end # Now get rid of the edge, so remove_vertex! works correctly. remove_edge!(edge) Puppet.debug "%s: %s => %s: %s" % [container, edge.source, edge.target, edge?(edge.source, edge.target)] end end 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 @@ -1,65 +1,69 @@ #!/usr/bin/env ruby # # Created by Luke A. Kanies on 2006-11-24. # Copyright (c) 2006. All rights reserved. # subscriptions are permanent associations determining how different # objects react to an event # This is Puppet's class for modeling edges in its configuration graph. # It used to be a subclass of GRATR::Edge, but that class has weird hash # overrides that dramatically slow down the graphing. class Puppet::Relationship attr_accessor :source, :target, :label # Return the callback def callback if label label[:callback] else nil end end # Return our event. def event if label label[:event] else nil end end def initialize(source, target, label = {}) if label unless label.is_a?(Hash) raise ArgumentError, "Relationship labels must be a hash" end if label[:event] and label[:event] != :NONE and ! label[:callback] raise ArgumentError, "You must pass a callback for non-NONE events" end else label = {} end @source, @target, @label = source, target, label end # Does the passed event match our event? This is where the meaning # of :NONE comes from. def match?(event) if self.event.nil? or event == :NONE or self.event == :NONE return false elsif self.event == :ALL_EVENTS or event == self.event return true else return false end 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,251 +1,315 @@ # 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 # Remove all references to everything. def clear @adjacencies[:in].clear @adjacencies[:out].clear @vertex = nil end def initialize(vertex) @vertex = vertex @adjacencies = {:in => Hash.new { |h,k| h[k] = [] }, :out => Hash.new { |h,k| h[k] = [] }} #@adjacencies = {:in => [], :out => []} end # Find adjacent vertices or edges. def adjacent(options) direction = options[:direction] || :out options[:type] ||= :vertices return @adjacencies[direction].values.flatten if options[:type] == :edges return @adjacencies[direction].keys end # Add an edge to our list. def add_edge(direction, edge) @adjacencies[direction][other_vertex(direction, edge)] << edge end # Return all known edges. def edges [:in, :out].collect { |dir| @adjacencies[dir].values }.flatten end # Test whether we share an edge with a given vertex. def has_edge?(direction, vertex) return true if @adjacencies[direction][vertex].length > 0 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 when :in: edge.source else edge.target end end # Remove an edge from our list. Assumes that we've already checked # that the edge is valid. def remove_edge(direction, edge) @adjacencies[direction][other_vertex(direction, edge)].delete(edge) end + + def to_s + vertex.to_s + end end def initialize @vertices = {} @edges = [] end # Clear our graph. def clear @vertices.each { |vertex, wrapper| wrapper.clear } @vertices.clear @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 # Return a reversed version of this graph. def reversal result = self.class.new vertices.each { |vertex| result.add_vertex!(vertex) } edges.each do |edge| newedge = edge.class.new(edge.target, edge.source, edge.label) result.add_edge!(newedge) end 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) setup_vertex(vertex) true # don't return the VertexWrapper instance. end # Remove a vertex from the graph. def remove_vertex!(vertex) return nil unless vertex?(vertex) @vertices[vertex].edges.each { |edge| remove_edge!(edge) } @vertices[vertex].clear @vertices.delete(vertex) end # Test whether a given vertex is in the graph. def vertex?(vertex) @vertices.include?(vertex) end # Return a list of all vertices. def vertices @vertices.keys end # Add a new edge. The graph user has to create the edge instance, # since they have to specify what kind of edge it is. def add_edge!(source, target = nil, label = nil) if target edge = Puppet::Relationship.new(source, target, label) else edge = source end [edge.source, edge.target].each { |vertex| setup_vertex(vertex) unless vertex?(vertex) } @vertices[edge.source].add_edge :out, edge @vertices[edge.target].add_edge :in, edge @edges << edge true end # Find a matching edge. Note that this only finds the first edge, # not all of them or whatever. def edge(source, target) @edges.each_with_index { |test_edge, index| return test_edge if test_edge.source == source and test_edge.target == target } end def edge_label(source, target) return nil unless edge = edge(source, target) edge.label end # Is there an edge between the two vertices? def edge?(source, target) return false unless vertex?(source) and vertex?(target) @vertices[source].has_edge?(:out, target) end def edges @edges.dup end # Remove an edge from our graph. def remove_edge!(edge) @vertices[edge.source].remove_edge(:out, edge) @vertices[edge.target].remove_edge(:in, edge) # Here we are looking for an exact edge, so we don't want to use ==, because # it's too darn expensive (in testing, deleting 3000 edges went from 6 seconds to # 0.05 seconds with this change). @edges.each_with_index { |test_edge, index| @edges.delete_at(index) and break if edge.equal?(test_edge) } nil end # Find adjacent edges. def adjacent(vertex, options = {}) return [] unless wrapper = @vertices[vertex] return wrapper.adjacent(options) end private # An internal method that skips the validation, so we don't have # duplicate validation calls. def setup_vertex(vertex) @vertices[vertex] = VertexWrapper.new(vertex) 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. # 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 = v.to_s 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 = e.to_s 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 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 @@ -1,38 +1,32 @@ # Created by Luke Kanies on 2006-11-16. # Copyright (c) 2006. All rights reserved. require 'puppet' require 'puppet/pgraph' # A module that handles the small amount of graph stuff in Puppet. module Puppet::Util::Graph # Make a graph where each of our children gets converted to # the receiving end of an edge. Call the same thing on all # of our children, optionally using a block def to_graph(graph = nil, &block) # Allow our calling function to send in a graph, so that we # can call this recursively with one graph. graph ||= Puppet::PGraph.new self.each do |child| unless block_given? and ! yield(child) graph.add_edge!(self, child) - - if graph.cyclic? - raise Puppet::Error, "%s created a cyclic graph" % self - end if child.respond_to?(:to_graph) child.to_graph(graph, &block) end end end - - if graph.cyclic? - raise Puppet::Error, "%s created a cyclic graph" % self - end + + # Do a topsort, which will throw an exception if the graph is cyclic. graph end end diff --git a/spec/unit/other/pgraph.rb b/spec/unit/other/pgraph.rb index 41835ebc7..252a807ec 100755 --- a/spec/unit/other/pgraph.rb +++ b/spec/unit/other/pgraph.rb @@ -1,245 +1,209 @@ #!/usr/bin/env ruby # # Created by Luke Kanies on 2007-9-12. # Copyright (c) 2006. All rights reserved. require File.dirname(__FILE__) + '/../../spec_helper' require 'puppet/util/graph' class Container include Puppet::Util::Graph include Enumerable attr_accessor :name def each @children.each do |c| yield c end end def initialize(name, ary) @name = name @children = ary end def push(*ary) ary.each { |c| @children.push(c)} end def to_s @name end end describe Puppet::PGraph do before do @graph = Puppet::PGraph.new end it "should correctly clear vertices and edges when asked" do @graph.add_edge!("a", "b") @graph.add_vertex! "c" @graph.clear @graph.vertices.should be_empty @graph.edges.should be_empty end end describe Puppet::PGraph, " when matching edges" do before do @graph = Puppet::PGraph.new @event = Puppet::Event.new(:source => "a", :event => :yay) @none = Puppet::Event.new(:source => "a", :event => :NONE) @edges = {} @edges["a/b"] = Puppet::Relationship.new("a", "b", {:event => :yay, :callback => :refresh}) @edges["a/c"] = Puppet::Relationship.new("a", "c", {:event => :yay, :callback => :refresh}) @graph.add_edge!(@edges["a/b"]) end it "should match edges whose source matches the source of the event" do @graph.matching_edges([@event]).should == [@edges["a/b"]] end it "should match always match nothing when the event is :NONE" do @graph.matching_edges([@none]).should be_empty end it "should match multiple edges" do @graph.add_edge!(@edges["a/c"]) edges = @graph.matching_edges([@event]) edges.should be_include(@edges["a/b"]) edges.should be_include(@edges["a/c"]) end end describe Puppet::PGraph, " when determining dependencies" do before do @graph = Puppet::PGraph.new @graph.add_edge!("a", "b") @graph.add_edge!("a", "c") @graph.add_edge!("b", "d") end it "should find all dependents when they are on multiple levels" do @graph.dependents("a").sort.should == %w{b c d}.sort end it "should find single dependents" do @graph.dependents("b").sort.should == %w{d}.sort end it "should return an empty array when there are no dependents" do @graph.dependents("c").sort.should == [].sort end it "should find all dependencies when they are on multiple levels" do @graph.dependencies("d").sort.should == %w{a b} end it "should find single dependencies" do @graph.dependencies("c").sort.should == %w{a} end it "should return an empty array when there are no dependencies" do @graph.dependencies("a").sort.should == [] end end describe Puppet::PGraph, " when splicing the relationship graph" do def container_graph @one = Container.new("one", %w{a b}) @two = Container.new("two", ["c", "d"]) @three = Container.new("three", ["i", "j"]) @middle = Container.new("middle", ["e", "f", @two]) @top = Container.new("top", ["g", "h", @middle, @one, @three]) @empty = Container.new("empty", []) @contgraph = @top.to_graph # We have to add the container to the main graph, else it won't # be spliced in the dependency graph. @contgraph.add_vertex!(@empty) end def dependency_graph @depgraph = Puppet::PGraph.new @contgraph.vertices.each do |v| @depgraph.add_vertex!(v) end # We have to specify a relationship to our empty container, else it # never makes it into the dep graph in the first place. {@one => @two, "f" => "c", "h" => @middle, "c" => @empty}.each do |source, target| @depgraph.add_edge!(source, target, :callback => :refresh) end end def splice @depgraph.splice!(@contgraph, Container) end before do container_graph dependency_graph splice end - it "should not create a cyclic graph" do - @depgraph.should_not be_cyclic - end - # This is the real heart of splicing -- replacing all containers in # our relationship and exploding their relationships so that each # relationship to a container gets copied to all of its children. it "should remove all Container objects from the dependency graph" do @depgraph.vertices.find_all { |v| v.is_a?(Container) }.should be_empty end it "should add container relationships to contained objects" do @contgraph.leaves(@middle).each do |leaf| @depgraph.should be_edge("h", leaf) end end it "should explode container-to-container relationships, making edges between all respective contained objects" do @one.each do |oobj| @two.each do |tobj| @depgraph.should be_edge(oobj, tobj) end end end it "should no longer contain anything but the non-container objects" do @depgraph.vertices.find_all { |v| ! v.is_a?(String) }.should be_empty end it "should copy labels" do @depgraph.edges.each do |edge| edge.label.should == {:callback => :refresh} end end it "should not add labels to edges that have none" do @depgraph.add_edge!(@two, @three) splice @depgraph.edge_label("c", "i").should == {} end it "should copy labels over edges that have none" do @depgraph.add_edge!("c", @three, {:callback => :refresh}) splice # And make sure the label got copied. @depgraph.edge_label("c", "i").should == {:callback => :refresh} end it "should not replace a label with a nil label" do # Lastly, add some new label-less edges and make sure the label stays. @depgraph.add_edge!(@middle, @three) @depgraph.add_edge!("c", @three, {:callback => :refresh}) splice @depgraph.edge_label("c", "i").should == {:callback => :refresh} end it "should copy labels to all created edges" do @depgraph.add_edge!(@middle, @three) @depgraph.add_edge!("c", @three, {:callback => :refresh}) splice @three.each do |child| edge = @depgraph.edge_class.new("c", child) @depgraph.should be_edge(edge.source, edge.target) @depgraph.edge_label(edge.source, edge.target).should == {:callback => :refresh} end end end - -describe Puppet::PGraph, " when sorting the graph" do - before do - @graph = Puppet::PGraph.new - end - - def add_edges(hash) - hash.each do |a,b| - @graph.add_edge!(a, b) - end - end - - it "should fail on two-vertex loops" do - add_edges :a => :b, :b => :a - proc { @graph.topsort }.should raise_error(Puppet::Error) - end - - it "should fail on multi-vertex loops" do - add_edges :a => :b, :b => :c, :c => :a - proc { @graph.topsort }.should raise_error(Puppet::Error) - end - - it "should fail when a larger tree contains a small cycle" do - add_edges :a => :b, :b => :a, :c => :a, :d => :c - proc { @graph.topsort }.should raise_error(Puppet::Error) - end - - it "should succeed on trees with no cycles" do - add_edges :a => :b, :b => :e, :c => :a, :d => :c - proc { @graph.topsort }.should_not raise_error - end -end diff --git a/spec/unit/relationship.rb b/spec/unit/relationship.rb index 5d90a9349..5f96cdf8c 100755 --- a/spec/unit/relationship.rb +++ b/spec/unit/relationship.rb @@ -1,149 +1,149 @@ #!/usr/bin/env ruby # # Created by Luke Kanies on 2007-11-1. # Copyright (c) 2006. All rights reserved. require File.dirname(__FILE__) + '/../spec_helper' require 'puppet/relationship' describe Puppet::Relationship do before do @edge = Puppet::Relationship.new(:a, :b) end it "should have a :source attribute" do @edge.should respond_to(:source) end it "should have a :target attribute" do @edge.should respond_to(:target) end it "should have a :label attribute" do @edge.should respond_to(:label) end it "should provide a :ref method that describes the edge" do - @edge = Puppet::Relationship.new(stub("a", :ref => "a"), stub("b", :ref => "b")) + @edge = Puppet::Relationship.new("a", "b") @edge.ref.should == "a => b" end end describe Puppet::Relationship, " when initializing" do before do @edge = Puppet::Relationship.new(:a, :b, :testing => :foo) end it "should use the first argument as the source" do @edge.source.should == :a end it "should use the second argument as the target" do @edge.target.should == :b end it "should use the third argument as the label" do @edge.label.should == {:testing => :foo} end it "should require a callback if a non-NONE event is specified" do proc { Puppet::Relationship.new(:a, :b, :event => :something) }.should raise_error(ArgumentError) end it "should require the label to be a hash" do proc { Puppet::Relationship.new(:a, :b, :event) }.should raise_error(ArgumentError) end end describe Puppet::Relationship, " when interpreting the label" do it "should default to an event of nil" do @edge = Puppet::Relationship.new(:a, :b) @edge.event.should be_nil end it "should expose a provided event via the :event method" do @edge = Puppet::Relationship.new(:a, :b, :event => :something, :callback => :whatever) @edge.event.should == :something end it "should default to a nil callback" do @edge = Puppet::Relationship.new(:a, :b) @edge.callback.should be_nil end it "should expose a provided callback via the :callback method" do @edge = Puppet::Relationship.new(:a, :b, :callback => :testing) @edge.callback.should == :testing end end describe Puppet::Relationship, " when matching edges with no specified event" do before do @edge = Puppet::Relationship.new(:a, :b) end it "should not match :NONE" do @edge.should_not be_match(:NONE) end it "should not match :ALL_EVENTS" do @edge.should_not be_match(:NONE) end it "should not match any other events" do @edge.should_not be_match(:whatever) end end describe Puppet::Relationship, " when matching edges with :NONE as the event" do before do @edge = Puppet::Relationship.new(:a, :b, :event => :NONE) end it "should not match :NONE" do @edge.should_not be_match(:NONE) end it "should not match :ALL_EVENTS" do @edge.should_not be_match(:ALL_EVENTS) end it "should not match other events" do @edge.should_not be_match(:yayness) end end describe Puppet::Relationship, " when matching edges with :ALL as the event" do before do @edge = Puppet::Relationship.new(:a, :b, :event => :ALL_EVENTS, :callback => :whatever) end it "should not match :NONE" do @edge.should_not be_match(:NONE) end it "should match :ALL_EVENTS" do @edge.should be_match(:ALLEVENTS) end it "should match all other events" do @edge.should be_match(:foo) end end describe Puppet::Relationship, " when matching edges with a non-standard event" do before do @edge = Puppet::Relationship.new(:a, :b, :event => :random, :callback => :whatever) end it "should not match :NONE" do @edge.should_not be_match(:NONE) end it "should not match :ALL_EVENTS" do @edge.should_not be_match(:ALL_EVENTS) end it "should match events with the same name" do @edge.should be_match(:random) end end diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb index 88873663c..061a07458 100755 --- a/spec/unit/simple_graph.rb +++ b/spec/unit/simple_graph.rb @@ -1,229 +1,269 @@ #!/usr/bin/env ruby # # Created by Luke Kanies on 2007-11-1. # Copyright (c) 2006. All rights reserved. require File.dirname(__FILE__) + '/../spec_helper' require 'puppet/simple_graph' describe Puppet::SimpleGraph do it "should return the number of its vertices as its length" do @graph = Puppet::SimpleGraph.new @graph.add_vertex!("one") @graph.add_vertex!("two") @graph.size.should == 2 end it "should consider itself a directed graph" do Puppet::SimpleGraph.new.directed?.should be_true end it "should provide a method for reversing the graph" do @graph = Puppet::SimpleGraph.new @graph.add_edge!(:one, :two) @graph.reversal.edge?(:two, :one).should be_true end it "should be able to produce a dot graph" do @graph = Puppet::SimpleGraph.new @graph.add_edge!(:one, :two) proc { @graph.to_dot_graph }.should_not raise_error end end describe Puppet::SimpleGraph, " when managing vertices" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method to add a vertex" do @graph.add_vertex!(:test) @graph.vertex?(:test).should be_true end it "should ignore already-present vertices when asked to add a vertex" do @graph.add_vertex!(:test) proc { @graph.add_vertex!(:test) }.should_not raise_error end it "should return true when asked if a vertex is present" do @graph.add_vertex!(:test) @graph.vertex?(:test).should be_true end it "should return false when asked if a non-vertex is present" do @graph.vertex?(:test).should be_false end it "should return all set vertices when asked" do @graph.add_vertex!(:one) @graph.add_vertex!(:two) @graph.vertices.length.should == 2 @graph.vertices.should include(:one) @graph.vertices.should include(:two) end it "should remove a given vertex when asked" do @graph.add_vertex!(:one) @graph.remove_vertex!(:one) @graph.vertex?(:one).should be_false end it "should do nothing when a non-vertex is asked to be removed" do proc { @graph.remove_vertex!(:one) }.should_not raise_error end end describe Puppet::SimpleGraph, " when managing edges" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method to test whether a given vertex pair is an edge" do @graph.should respond_to(:edge?) end it "should provide a method to add an edge as an instance of the edge class" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge!(edge) @graph.edge?(:one, :two).should be_true end it "should provide a method to add an edge by specifying the two vertices" do @graph.add_edge!(:one, :two) @graph.edge?(:one, :two).should be_true end it "should provide a method to add an edge by specifying the two vertices and a label" do @graph.add_edge!(:one, :two, :stuff => :awesome) @graph.edge?(:one, :two).should be_true end it "should provide a method for retrieving an edge label" do edge = Puppet::Relationship.new(:one, :two, :stuff => :awesome) @graph.add_edge!(edge) @graph.edge_label(:one, :two).should == {:stuff => :awesome} end it "should provide a method for retrieving an edge" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge!(edge) @graph.edge(:one, :two).should equal(edge) end it "should add the edge source as a vertex if it is not already" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge!(edge) @graph.vertex?(:one).should be_true end it "should add the edge target as a vertex if it is not already" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge!(edge) @graph.vertex?(:two).should be_true end it "should return all edges as edge instances when asked" do one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge!(one) @graph.add_edge!(two) edges = @graph.edges edges.length.should == 2 edges.should include(one) edges.should include(two) end it "should remove an edge when asked" do edge = Puppet::Relationship.new(:one, :two) @graph.add_edge!(edge) @graph.remove_edge!(edge) @graph.edge?(edge.source, edge.target).should be_false end it "should remove all related edges when a vertex is removed" do one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge!(one) @graph.add_edge!(two) @graph.remove_vertex!(:two) @graph.edge?(:one, :two).should be_false @graph.edge?(:two, :three).should be_false @graph.edges.length.should == 0 end end describe Puppet::SimpleGraph, " when finding adjacent vertices" do before do @graph = Puppet::SimpleGraph.new @one_two = Puppet::Relationship.new(:one, :two) @two_three = Puppet::Relationship.new(:two, :three) @one_three = Puppet::Relationship.new(:one, :three) @graph.add_edge!(@one_two) @graph.add_edge!(@one_three) @graph.add_edge!(@two_three) end it "should return adjacent vertices" do adj = @graph.adjacent(:one) adj.should be_include(:three) adj.should be_include(:two) end it "should default to finding :out vertices" do @graph.adjacent(:two).should == [:three] end it "should support selecting :in vertices" do @graph.adjacent(:two, :direction => :in).should == [:one] end it "should default to returning the matching vertices as an array of vertices" do @graph.adjacent(:two).should == [:three] end it "should support returning an array of matching edges" do @graph.adjacent(:two, :type => :edges).should == [@two_three] end end describe Puppet::SimpleGraph, " when clearing" do before do @graph = Puppet::SimpleGraph.new one = Puppet::Relationship.new(:one, :two) two = Puppet::Relationship.new(:two, :three) @graph.add_edge!(one) @graph.add_edge!(two) @graph.clear end it "should remove all vertices" do @graph.vertices.should be_empty end it "should remove all edges" do @graph.edges.should be_empty end end describe Puppet::SimpleGraph, " when reversing graphs" do before do @graph = Puppet::SimpleGraph.new end it "should provide a method for reversing the graph" do @graph.add_edge!(:one, :two) @graph.reversal.edge?(:two, :one).should be_true end it "should add all vertices to the reversed graph" do + @graph.add_edge!(:one, :two) + @graph.vertex?(:one).should be_true + @graph.vertex?(:two).should be_true end it "should retain labels on edges" do @graph.add_edge!(:one, :two, :stuff => :awesome) edge = @graph.reversal.edge(:two, :one) edge.label.should == {:stuff => :awesome} end end + +describe Puppet::SimpleGraph, " when sorting the graph" do + before do + @graph = Puppet::SimpleGraph.new + end + + def add_edges(hash) + hash.each do |a,b| + @graph.add_edge!(a, b) + end + end + + it "should sort the graph topologically" do + add_edges :a => :b, :b => :c + @graph.topsort.should == [:a, :b, :c] + end + + it "should fail on two-vertex loops" do + add_edges :a => :b, :b => :a + proc { @graph.topsort }.should raise_error(Puppet::Error) + end + + it "should fail on multi-vertex loops" do + add_edges :a => :b, :b => :c, :c => :a + proc { @graph.topsort }.should raise_error(Puppet::Error) + end + + it "should fail when a larger tree contains a small cycle" do + add_edges :a => :b, :b => :a, :c => :a, :d => :c + proc { @graph.topsort }.should raise_error(Puppet::Error) + end + + it "should succeed on trees with no cycles" do + add_edges :a => :b, :b => :e, :c => :a, :d => :c + proc { @graph.topsort }.should_not raise_error + end +end diff --git a/test/ral/providers/package.rb b/test/ral/providers/package.rb index 90c862178..f2d28d0f0 100755 --- a/test/ral/providers/package.rb +++ b/test/ral/providers/package.rb @@ -1,279 +1,279 @@ #!/usr/bin/env ruby require File.dirname(__FILE__) + '/../../lib/puppettest' require 'puppettest' require 'etc' class TestPackageProvider < Test::Unit::TestCase include PuppetTest def setup super Puppet.info @method_name end # Load the testpackages hash. def self.load_test_packages require 'yaml' file = File.join(PuppetTest.datadir(), "providers", "package", "testpackages.yaml") unless FileTest.exists?(file) raise "Could not find file %s" % file end array = YAML::load(File.read(file)).collect { |hash| # Stupid ruby 1.8.1. YAML is sometimes broken such that # symbols end up being strings with the : in them. hash.each do |name, value| if name.is_a?(String) and name =~ /^:/ hash.delete(name) name = name.sub(/^:/, '').intern hash[name] = value end if value.is_a?(String) and value =~ /^:/ hash[name] = value.sub(/^:/, '').intern end end } return array end def self.suitable_test_packages list = load_test_packages providers = {} Puppet::Type.type(:package).suitableprovider.each do |provider| providers[provider.name] = provider end facts = {} Facter.to_hash.each do |fact, value| - facts[fact.downcase.intern] = value.downcase.intern + facts[fact.to_s.downcase.intern] = value.to_s.downcase.intern end list.find_all { |hash| # First find the matching providers hash.include?(:provider) and providers.include?(hash[:provider]) }.reject { |hash| # Then find matching fact sets facts.detect do |fact, value| # We're detecting unmatched facts, but we also want to # delete the facts so they don't show up later. if fval = hash[fact] hash.delete(fact) fval = [fval] unless fval.is_a?(Array) fval = fval.collect { |v| v.downcase.intern } ! fval.include?(value) end end } end def assert_absent(provider, msg = "package not absent") result = nil assert_nothing_raised("Could not query provider") do result = provider.query end if result.nil? assert_nil(result) elsif result.is_a?(Hash) assert (result[:ensure] == :absent or result[:ensure] == :purged), msg else raise "dunno how to handle %s" % result.inspect end end def assert_not_absent(provider, msg = "package not installed") result = nil assert_nothing_raised("Could not query provider") do result = provider.query end assert((result == :listed or result.is_a?(Hash)), "query did not return hash or :listed") if result == :listed assert(provider.resource.is(:ensure) != :absent, msg) else assert(result[:ensure] != :absent, msg) end end # Run a package through all of its paces. FIXME This should use the # provider, not the package, duh. def run_package_installation_test(hash) # Turn the hash into a package if files = hash[:files] hash.delete(:files) if files.is_a?(Array) hash[:source] = files.shift else hash[:source] = files files = [] end else files = [] end if versions = hash[:versions] hash.delete(:versions) else versions = [] end # Start out by just making sure it's installed if versions.empty? hash[:ensure] = :present else hash[:ensure] = versions.shift end if hash[:source] unless FileTest.exists?(hash[:source]) $stderr.puts "Create a package at %s for testing" % hash[:source] return end end if cleancmd = hash[:cleanup] hash.delete(:cleanup) end pkg = nil assert_nothing_raised( "Could not turn %s into a package" % hash.inspect ) do pkg = Puppet::Type.newpackage(hash) end # Make any necessary modifications. modpkg(pkg) provider = pkg.provider assert(provider, "Could not retrieve provider") return if result = provider.query and ! [:absent, :purged].include?(result[:ensure]) assert_absent(provider) if Process.uid != 0 Puppet.info "Run as root for full package tests" return end cleanup do if pkg.provider.respond_to?(:uninstall) pkg.provider.flush if pkg.provider.properties[:ensure] != :absent assert_nothing_raised("Could not clean up package") do pkg.provider.uninstall end end else if cleancmd system(cleancmd) end end end # Now call 'latest' after the package is installed if provider.respond_to?(:latest) assert_nothing_raised("Could not call 'latest'") do provider.latest end end assert_nothing_raised("Could not install package") do provider.install end assert_not_absent(provider, "package did not install") # If there are any remaining files, then test upgrading from there unless files.empty? pkg[:source] = files.shift current = provider.properties assert_nothing_raised("Could not upgrade") do provider.update end provider.flush new = provider.properties assert(current != new, "package was not upgraded: %s did not change" % current.inspect) end unless versions.empty? pkg[:ensure] = versions.shift current = provider.properties assert_nothing_raised("Could not upgrade") do provider.update end provider.flush new = provider.properties assert(current != new, "package was not upgraded: %s did not change" % current.inspect) end # Now call 'latest' after the package is installed if provider.respond_to?(:latest) assert_nothing_raised("Could not call 'latest'") do provider.latest end end # Now remove the package if provider.respond_to?(:uninstall) assert_nothing_raised do provider.uninstall end assert_absent(provider) end end # Now create a separate test method for each package suitable_test_packages.each do |hash| mname = ["test", hash[:name].to_s, hash[:provider].to_s].join("_").intern if method_defined?(mname) warn "Already a test method defined for %s" % mname else define_method(mname) do run_package_installation_test(hash) end end end def modpkg(pkg) case pkg[:provider] when :sun: pkg[:adminfile] = "/usr/local/pkg/admin_file" end end # Make sure providers throw an error when you tell them to install a # non-existent package. def test_no_such_package Puppet::Type.type(:package).suitableprovider.each do |provider| assert_raise(ArgumentError, Puppet::Error, Puppet::ExecutionFailure, "Successfully installed nonexistent package with %s" % provider.name) { pkg = Puppet::Type.newpackage :name => "nosuch%s" % provider.name.to_s, :provider => provider.name provider = pkg.provider provider.install } end end # Make sure all of the suitable providers on our platform can successfully # list. def test_instances Puppet::Type.type(:package).suitableprovider.each do |provider| result = nil assert_nothing_raised("Could not list %s packages" % provider.name) do result = provider.instances end result.each do |pkg| assert_instance_of(provider, pkg, "%s returned non-provider" % provider.name) assert_equal(provider.name, pkg.class.name, "Provider %s returned an instance of a different provider" % provider.name) end end end end