diff --git a/lib/puppet/gratr.rb b/lib/puppet/gratr.rb new file mode 100644 index 000000000..f59315d57 --- /dev/null +++ b/lib/puppet/gratr.rb @@ -0,0 +1,33 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/base' +require 'puppet/gratr/digraph' +require 'puppet/gratr/undirected_graph' +require 'puppet/gratr/common' diff --git a/lib/puppet/gratr/adjacency_graph.rb b/lib/puppet/gratr/adjacency_graph.rb new file mode 100644 index 000000000..930e2abac --- /dev/null +++ b/lib/puppet/gratr/adjacency_graph.rb @@ -0,0 +1,229 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/edge' +require 'puppet/gratr/graph' +require 'set' + +module GRATR + + # This provides the basic routines needed to implement the Digraph, UndirectedGraph, + # PseudoGraph, DirectedPseudoGraph, MultiGraph and DirectedPseudoGraph class. + module AdjacencyGraph + + include Graph + + class ArrayWithAdd < Array # :nodoc: + alias add push + end + + # Initialization parameters can include an Array of edges to add, Graphs to + # copy (will merge if multiple) + # :parallel_edges denotes that duplicate edges are allowed + # :loops denotes that loops are allowed + def initialize(*params) + @vertex_dict = Hash.new + raise ArgumentError if params.any? do |p| + !(p.kind_of? GRATR::Graph or + p.kind_of? Array or + p == :parallel_edges or + p == :loops) + end + clear_all_labels + + # Basic configuration of adjacency + @allow_loops = params.any? {|p| p == :loops} + @parallel_edges = params.any? {|p| p == :parallel_edges} + @edgelist_class = @parallel_edges ? ArrayWithAdd : Set + if @parallel_edges + @edge_number = Hash.new + @next_edge_number = 0 + end + + # Copy any given graph into this graph + params.select {|p| p.kind_of? GRATR::Graph}.each do |g| + g.edges.each do |e| + add_edge!(e) + edge_label_set(e, edge_label(e)) if edge_label(e) + end + g.vertices.each do |v| + vertex_label_set(v, vertex_label(v)) if vertex_label(v) + end + end + + # Add all array edges specified + params.select {|p| p.kind_of? Array}.each do |a| + 0.step(a.size-1, 2) {|i| add_edge!(a[i], a[i+1])} + end + + end + + # Returns true if v is a vertex of this Graph + # An O(1) implementation of vertex? + def vertex?(v) @vertex_dict.has_key?(v); end + + # Returns true if [u,v] or u is an Edge + # An O(1) implementation + def edge?(u, v=nil) + u, v = u.source, u.target if u.kind_of? GRATR::Edge + vertex?(u) and @vertex_dict[u].include?(v) + end + + # Adds a vertex to the graph with an optional label + def add_vertex!(vertex, label=nil) + @vertex_dict[vertex] ||= @edgelist_class.new + self[vertex] = label if label + self + end + + # Adds an edge to the graph + # Can be called in two basic ways, label is optional + # * add_edge!(Edge[source,target], "Label") + # * add_edge!(source,target, "Label") + def add_edge!(u, v=nil, l=nil, n=nil) + n = u.number if u.class.include? EdgeNumber and n.nil? + u, v, l = u.source, u.target, u.label if u.kind_of? GRATR::Edge + return self if not @allow_loops and u == v + n = (@next_edge_number+=1) unless n if @parallel_edges + add_vertex!(u); add_vertex!(v) + @vertex_dict[u].add(v) + (@edge_number[u] ||= @edgelist_class.new).add(n) if @parallel_edges + unless directed? + @vertex_dict[v].add(u) + (@edge_number[v] ||= @edgelist_class.new).add(n) if @parallel_edges + end + self[n ? edge_class[u,v,n] : edge_class[u,v]] = l if l + self + end + + # Removes a given vertex from the graph + def remove_vertex!(v) +# FIXME This is broken for multi graphs + @vertex_dict.delete(v) + @vertex_dict.each_value { |adjList| adjList.delete(v) } + @vertex_dict.keys.each do |u| + delete_label(edge_class[u,v]) + delete_label(edge_class[v,u]) + end + delete_label(v) + self + end + + # Removes an edge from the graph, can be called with source and target or with + # and object of GRATR::Edge derivation + def remove_edge!(u, v=nil) + unless u.kind_of? GRATR::Edge + raise ArgumentError if @parallel_edges + u = edge_class[u,v] + end + raise ArgumentError if @parallel_edges and (u.number || 0) == 0 + return self unless @vertex_dict[u.source] # It doesn't exist + delete_label(u) # Get rid of label + if @parallel_edges + index = @edge_number[u.source].index(u.number) + raise NoEdgeError unless index + @vertex_dict[u.source].delete_at(index) + @edge_number[u.source].delete_at(index) + else + @vertex_dict[u.source].delete(u.target) + end + self + end + + # Returns an array of vertices that the graph has + def vertices() @vertex_dict.keys; end + + # Returns an array of edges, most likely of class Edge or UndirectedEdge depending + # upon the type of graph + def edges + @vertex_dict.keys.inject(Set.new) do |a,v| + if @parallel_edges and @edge_number[v] + @vertex_dict[v].zip(@edge_number[v]).each do |w| + s,t,n = v,w[0],w[1] + a.add( edge_class[ s,t,n, edge_label(s,t,n) ] ) + end + else + @vertex_dict[v].each do |w| + a.add(edge_class[v,w,edge_label(v,w)]) + end + end; a + end.to_a + end + + alias graph_adjacent adjacent + def adjacent(x, options={}) + options[:direction] ||= :out + if !x.kind_of?(GRATR::Edge) and (options[:direction] == :out || !directed?) + if options[:type] == :edges + @parallel_edges ? + @vertex_dict[x].map {|v| e=edge_class[x,v,@edge_number[x][v]]; e.label = self[e]; e} : + @vertex_dict[x].map {|v| e=edge_class[x,v]; e.label = self[e]; e} + else + @vertex_dict[x].to_a + end + else + graph_adjacent(x,options) + end + end + + + public + + def self.included(cl) + # Shortcut for creating a Graph + # + # Example: GRATR::Digraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s => + # "(1-2)(2-3)(2-4)(4-5)" + # + # Or as a Hash for specifying lables + # GRATR::Digraph[ [:a,:b] => 3, [:b,:c] => 4 ] (Note: Do not use for Multi or Pseudo graphs) + def cl.[] (*a) + result = new + if a.size == 1 and a[0].kind_of? Hash + # Convert to edge class + a[0].each do |k,v| + if result.edge_class.include? GRATR::EdgeNumber + result.add_edge!(result.edge_class[k[0],k[1],nil,v]) + else + result.add_edge!(result.edge_class[k[0],k[1],v]) + end + end + elsif a[0].kind_of? GRATR::Edge + a.each{|e| result.add_edge!(e); result[e] = e.label} + elsif a.size % 2 == 0 + 0.step(a.size-1, 2) {|i| result.add_edge!(a[i], a[i+1])} + else + raise ArgumentError + end + result + end + end + + end # Adjacency Graph +end # GRATR diff --git a/lib/puppet/gratr/base.rb b/lib/puppet/gratr/base.rb new file mode 100644 index 000000000..72dded73f --- /dev/null +++ b/lib/puppet/gratr/base.rb @@ -0,0 +1,34 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +GRATR_VERSION = "0.4.1" + +module GRATR + class NoVertexError < IndexError; end + class NoEdgeError < IndexError; end +end diff --git a/lib/puppet/gratr/biconnected.rb b/lib/puppet/gratr/biconnected.rb new file mode 100644 index 000000000..c976b2c04 --- /dev/null +++ b/lib/puppet/gratr/biconnected.rb @@ -0,0 +1,116 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'set' + +module GRATR + module Graph + # Biconnected is a module for adding the biconnected algorithm to + # UndirectedGraphs + module Biconnected + + # biconnected computes the biconnected subgraphs + # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan + # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on + # Computing, 1(2):146-160, 1972 + # + # The output of the algorithm is a pair, the first value is an + # array of biconnected subgraphs. The second is the set of + # articulation vertices. + # + # A connected graph is biconnected if the removal of any single vertex + # (and all edges incident on that vertex) cannot disconnect the graph. + # More generally, the biconnected components of a graph are the maximal + # subsets of vertices such that the removal of a vertex from a particular + # component will not disconnect the component. Unlike connected components, + # vertices may belong to multiple biconnected components: those vertices + # that belong to more than one biconnected component are called articulation + # points or, equivalently, cut vertices. Articulation points are vertices + # whose removal would increase the number of connected components in the graph. + # Thus, a graph without articulation points is biconnected. + def biconnected + dfs_num = 0 + number = {}; predecessor = {}; low_point = {} + stack = []; result = []; articulation= [] + + root_vertex = Proc.new {|v| predecessor[v]=v } + enter_vertex = Proc.new {|u| number[u]=low_point[u]=(dfs_num+=1) } + tree_edge = Proc.new do |e| + stack.push(e) + predecessor[e.target] = e.source + end + back_edge = Proc.new do |e| + if e.target != predecessor[e.source] + stack.push(e) + low_point[e.source] = [low_point[e.source], number[e.target]].min + end + end + exit_vertex = Proc.new do |u| + parent = predecessor[u] + is_articulation_point = false + if number[parent] > number[u] + parent = predecessor[parent] + is_articulation_point = true + end + if parent == u + is_articulation_point = false if (number[u] + 1) == number[predecessor[u]] + else + low_point[parent] = [low_point[parent], low_point[u]].min + if low_point[u] >= number[parent] + if number[parent] > number[predecessor[parent]] + predecessor[u] = predecessor[parent] + predecessor[parent] = u + end + result << (component = self.class.new) + while number[stack[-1].source] >= number[u] + component.add_edge!(stack.pop) + end + component.add_edge!(stack.pop) + if stack.empty? + predecessor[u] = parent + predecessor[parent] = u + end + end + end + articulation << u if is_articulation_point + end + + # Execute depth first search + dfs({:root_vertex => root_vertex, + :enter_vertex => enter_vertex, + :tree_edge => tree_edge, + :back_edge => back_edge, + :exit_vertex => exit_vertex}) + + [result, articulation] + end # biconnected + + end # Biconnected + + end # Graph +end # GRATR diff --git a/lib/puppet/gratr/chinese_postman.rb b/lib/puppet/gratr/chinese_postman.rb new file mode 100644 index 000000000..5a9121e2e --- /dev/null +++ b/lib/puppet/gratr/chinese_postman.rb @@ -0,0 +1,123 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/digraph_distance' + +module GRATR + module Graph + module ChinesePostman + + # Returns the shortest walk that traverses all arcs at least + # once, returning to the specified start node. + def closed_chinese_postman_tour(start, weight=nil, zero=0) + cost, path, delta = floyd_warshall(weight, zero) + return nil unless cp_valid_least_cost? cost, zero + positive, negative = cp_unbalanced(delta) + f = cp_find_feasible(delta, positive, negative, zero) + while cp_improve(f, positive, negative, cost, zero); end + cp_euler_circuit(start, f, path) + end + + private + + def cp_euler_circuit(start, f, path) # :nodoc: + circuit = [u=v=start] + bridge_taken = Hash.new {|h,k| h[k] = Hash.new} + until v.nil? + if v=f[u].keys.detect {|k| f[u][k] > 0} + f[u][v] -= 1 + circuit << (u = path[u][v]) while u != v + else + unless bridge_taken[u][bridge = path[u][start]] + v = vertices.detect {|v1| v1 != bridge && edge?(u,v1) && !bridge_taken[u][v1]} || bridge + bridge_taken[u][v] = true + circuit << v + end + end + u=v + end; circuit + end + + def cp_cancel_cycle(cost, path, f, start, zero) # :nodoc: + u = start; k = nil + begin + v = path[u][start] + k = f[v][u] if cost[u][v] < zero and (k.nil? || k > f[v][u]) + end until (u=v) != start + u = start + begin + v = path[u][start] + cost[u][v] < zero ? f[v][u] -= k : f[u][v] += k + end until (u=v) != start + true # This routine always returns true to make cp_improve easier + end + + def cp_improve(f, positive, negative, cost, zero) # :nodoc: + residual = self.class.new + negative.each do |u| + positive.each do |v| + residual.add_edge!(u,v,cost[u][v]) + residual.add_edge!(v,u,-cost[u][v]) if f[u][v] != 0 + end + end + r_cost, r_path, r_delta = residual.floyd_warshall(nil, zero) + i = residual.vertices.detect {|v| r_cost[v][v] and r_cost[v][v] < zero} + i ? cp_cancel_cycle(r_cost, r_path, f, i) : false + end + + def cp_find_feasible(delta, positive, negative, zero) # :nodoc: + f = Hash.new {|h,k| h[k] = Hash.new} + negative.each do |i| + positive.each do |j| + f[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j] + delta[i] += f[i][j] + delta[j] -= f[i][j] + end + end; f + end + + def cp_valid_least_cost?(c, zero) # :nodoc: + vertices.each do |i| + vertices.each do |j| + return false unless c[i][j] and c[i][j] >= zero + end + end; true + end + + def cp_unbalanced(delta) # :nodoc: + negative = []; positive = [] + vertices.each do |v| + negative << v if delta[v] < 0 + positive << v if delta[v] > 0 + end; [positive, negative] + end + + end # Chinese Postman + end # Graph +end # GRATR + \ No newline at end of file diff --git a/lib/puppet/gratr/common.rb b/lib/puppet/gratr/common.rb new file mode 100644 index 000000000..72a7ed575 --- /dev/null +++ b/lib/puppet/gratr/common.rb @@ -0,0 +1,73 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/edge' +require 'puppet/gratr/graph' + +module GRATR + # This class defines a cycle graph of size n + # This is easily done by using the base Graph + # class and implemeting the minimum methods needed to + # make it work. This is a good example to look + # at for making one's own graph classes + class Cycle + + def initialize(n) @size = n; end + def directed?() false; end + def vertices() (1..@size).to_a; end + def vertex?(v) v > 0 and v <= @size; end + def edge?(u,v=nil) + u, v = [u.source, v.target] if u.kind_of? GRATR::Edge + vertex?(u) && vertex?(v) && ((v-u == 1) or (u==@size && v=1)) + end + def edges() Array.new(@size) {|i| GRATR::UndirectedEdge[i+1, (i+1)==@size ? 1 : i+2]}; end + end + + # This class defines a complete graph of size n + # This is easily done by using the base Graph + # class and implemeting the minimum methods needed to + # make it work. This is a good example to look + # at for making one's own graph classes + class Complete < Cycle + def initialize(n) @size = n; @edges = nil; end + def edges + return @edges if @edges # Cache edges + @edges = [] + @size.times do |u| + @size.times {|v| @edges << GRATR::UndirectedEdge[u+1, v+1]} + end; @edges + end + def edge?(u,v=nil) + u, v = [u.source, v.target] if u.kind_of? GRATR::Edge + vertex?(u) && vertex?(v) + end + end # Complete + + + +end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/comparability.rb b/lib/puppet/gratr/comparability.rb new file mode 100644 index 000000000..1546fbefe --- /dev/null +++ b/lib/puppet/gratr/comparability.rb @@ -0,0 +1,92 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +module GRATR + module Graph + module Comparability + + # A comparability graph is an UndirectedGraph that has a transitive + # orientation. This returns a boolean that says if this graph + # is a comparability graph. + def comparability?() gamma_decomposition[1]; end + + # Returns an array with two values, the first being a hash of edges + # with a number containing their class assignment, the second valud + # is a boolean which states whether or not the graph is a + # comparability graph + # + # Complexity in time O(d*|E|) where d is the maximum degree of a vertex + # Complexity in space O(|V|+|E|) + def gamma_decomposition + k = 0; comparability=true; classification={} + edges.map {|edge| [edge.source,edge.target]}.each do |e| + if classification[e].nil? + k += 1 + classification[e] = k; classification[e.reverse] = -k + comparability &&= gratr_comparability_explore(e, k, classification) + end + end; [classification, comparability] + end + + # Returns one of the possible transitive orientations of + # the UndirectedGraph as a Digraph + def transitive_orientation(digraph_class=Digraph) + raise NotImplementError + end + + private + + # Taken from Figure 5.10, on pg. 130 of Martin Golumbic's, _Algorithmic_Graph_ + # _Theory_and_Perfect_Graphs. + def gratr_comparability_explore(edge, k, classification, space='') + ret = gratr_comparability_explore_inner(edge, k, classification, :forward, space) + gratr_comparability_explore_inner(edge.reverse, k, classification, :backward, space) && ret + end + + def gratr_comparability_explore_inner(edge, k, classification, direction,space) + comparability = true + adj_target = adjacent(edge[1]) + adjacent(edge[0]).select do |mt| + (classification[[edge[1],mt]] || k).abs < k or + not adj_target.any? {|adj_t| adj_t == mt} + end.each do |m| + e = (direction == :forward) ? [edge[0], m] : [m,edge[0]] + if classification[e].nil? + classification[e] = k + classification[e.reverse] = -k + comparability = gratr_comparability_explore(e, k, classification, ' '+space) && comparability + elsif classification[e] == -k + classification[e] = k + gratr_comparability_explore(e, k, classification, ' '+space) + comparability = false + end + end; comparability + end # gratr_comparability_explore_inner + + end # Comparability + end # Graph +end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/digraph.rb b/lib/puppet/gratr/digraph.rb new file mode 100644 index 000000000..2c4850d43 --- /dev/null +++ b/lib/puppet/gratr/digraph.rb @@ -0,0 +1,113 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +require 'puppet/gratr/edge' +require 'puppet/gratr/graph' +require 'puppet/gratr/search' +require 'puppet/gratr/adjacency_graph' +require 'puppet/gratr/strong_components' +require 'puppet/gratr/digraph_distance' +require 'puppet/gratr/chinese_postman' + +module GRATR + # + # Digraph is a directed graph which is a finite set of vertices + # and a finite set of edges connecting vertices. It cannot contain parallel + # edges going from the same source vertex to the same target. It also + # cannot contain loops, i.e. edges that go have the same vertex for source + # and target. + # + # DirectedPseudoGraph is a class that allows for parallel edges, and a + # DirectedMultiGraph is a class that allows for parallel edges and loops + # as well. + class Digraph + include AdjacencyGraph + include Graph::Search + include Graph::StrongComponents + include Graph::Distance + include Graph::ChinesePostman + + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? GRATR::Graph or p.kind_of? Array) + end if self.class == GRATR::Digraph + super(*params) + end + + # A directed graph is directed by definition + def directed?() true; end + + # A digraph uses the Edge class for edges + def edge_class() @parallel_edges ? GRATR::MultiEdge : GRATR::Edge; end + + # Reverse all edges in a graph + def reversal + return new(self) unless directed? + edges.inject(self.class.new) {|a,e| a << e.reverse} + end + + # Return true if the Graph is oriented. + def oriented? + e = edges + re = e.map {|x| x.reverse} + not e.any? {|x| re.include?(x)} + end + + # Balanced is when the out edge count is equal to the in edge count + def balanced?(v) out_degree(v) == in_degree(v); end + + # Returns out_degree(v) - in_degree(v) + def delta(v) out_degree(v) - in_degree(v); end + + end + + # DirectedGraph is just an alias for Digraph should one desire + DirectedGraph = Digraph + + # This is a Digraph that allows for parallel edges, but does not + # allow loops + class DirectedPseudoGraph < Digraph + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? GRATR::Graph or p.kind_of? Array) + end + super(:parallel_edges, *params) + end + end + + # This is a Digraph that allows for parallel edges and loops + class DirectedMultiGraph < Digraph + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? GRATR::Graph or p.kind_of? Array) + end + super(:parallel_edges, :loops, *params) + end + end + +end diff --git a/lib/puppet/gratr/digraph_distance.rb b/lib/puppet/gratr/digraph_distance.rb new file mode 100644 index 000000000..6f90384e7 --- /dev/null +++ b/lib/puppet/gratr/digraph_distance.rb @@ -0,0 +1,185 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +module GRATR + module Graph + module Distance + + # Shortest path from Jorgen Band-Jensen and Gregory Gutin, + # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 + # + # Requires that the graph be acyclic. If the graph is not + # acyclic, then see dijkstras_algorithm or bellman_ford_moore + # for possible solutions. + # + # start is the starting vertex + # weight can be a Proc, or anything else is accessed using the [] for the + # the label or it defaults to using + # the value stored in the label for the Edge. If it is a Proc it will + # pass the edge to the proc and use the resulting value. + # zero is used for math system with a different definition of zero + # + # Returns a hash with the key being a vertex and the value being the + # distance. A missing vertex from the hash is an infinite distance + # + # Complexity O(n+m) + def shortest_path(start, weight=nil, zero=0) + dist = {start => zero}; path = {} + topsort(start) do |vi| + next if vi == start + dist[vi],path[vi] = adjacent(vi, :direction => :in).map do |vj| + [dist[vj] + cost(vj,vi,weight), vj] + end.min {|a,b| a[0] <=> b[0]} + end; + dist.keys.size == vertices.size ? [dist,path] : nil + end # shortest_path + + # Algorithm from Jorgen Band-Jensen and Gregory Gutin, + # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 53-54 + # + # Finds the distances from a given vertex s in a weighted digraph + # to the rest of the vertices, provided all the weights of arcs + # are non-negative. If negative arcs exist in the graph, two + # basic options exist, 1) modify all weights to be positive by + # using an offset, or 2) use the bellman_ford_moore algorithm. + # Also if the graph is acyclic, use the shortest_path algorithm. + # + # weight can be a Proc, or anything else is accessed using the [] for the + # the label or it defaults to using + # the value stored in the label for the Edge. If it is a Proc it will + # pass the edge to the proc and use the resulting value. + # + # zero is used for math system with a different definition of zero + # + # Returns a hash with the key being a vertex and the value being the + # distance. A missing vertex from the hash is an infinite distance + # + # O(n*log(n) + m) complexity + def dijkstras_algorithm(s, weight = nil, zero = 0) + q = vertices; distance = { s => zero }; path = {} + while not q.empty? + v = (q & distance.keys).inject(nil) {|a,k| (!a.nil?) && (distance[a] < distance[k]) ? a : k} + q.delete(v) + (q & adjacent(v)).each do |u| + c = cost(v,u,weight) + if distance[u].nil? or distance[u] > (c+distance[v]) + distance[u] = c + distance[v] + path[u] = v + end + end + end; [distance, path] + end # dijkstras_algorithm + + # Algorithm from Jorgen Band-Jensen and Gregory Gutin, + # _DIGRAPHS:_Theory,_Algorithms_and_Applications, pg 56-58 + # + # Finds the distances from a given vertex s in a weighted digraph + # to the rest of the vertices, provided the graph has no negative cycle. + # If no negative weights exist, then dijkstras_algorithm is more + # efficient in time and space. Also if the graph is acyclic, use the + # shortest_path algorithm. + # + # weight can be a Proc, or anything else is accessed using the [] for the + # the label or it defaults to using + # the value stored in the label for the Edge. If it is a Proc it will + # pass the edge to the proc and use the resulting value. + # + # zero is used for math system with a different definition of zero + # + # Returns a hash with the key being a vertex and the value being the + # distance. A missing vertex from the hash is an infinite distance + # + # O(nm) complexity + def bellman_ford_moore(start, weight = nil, zero = 0) + distance = { start => zero }; path = {} + 2.upto(vertices.size) do + edges.each do |e| + u,v = e[0],e[1] + unless distance[u].nil? + c = cost(u, v, weight)+distance[u] + if distance[v].nil? or c < distance[v] + distance[v] = c + path[v] = u + end + end + end + end; [distance, path] + end # bellman_ford_moore + + # This uses the Floyd-Warshall algorithm to efficiently find + # and record shortest paths at the same time as establishing + # the costs for all vertices in a graph. + # See, S.Skiena, "The Algorithm Design Manual", + # Springer Verlag, 1998 for more details. + # + # Returns a pair of matrices and a hash of delta values. + # The matrices will be indexed by two vertices and are + # implemented as a Hash of Hashes. The first matrix is the cost, the second + # matrix is the shortest path spanning tree. The delta (difference of number + # of in edges and out edges) is indexed by vertex. + # + # weight specifies how an edge weight is determined, if it's a + # Proc the Edge is passed to it, if it's nil it will just use + # the value in the label for the Edge, otherwise the weight is + # determined by applying the [] operator to the value in the + # label for the Edge + # + # zero defines the zero value in the math system used. Defaults + # of course, to 0. This allows for no assumptions to be made + # about the math system and fully functional duck typing. + # + # O(n^3) complexity in time. + def floyd_warshall(weight=nil, zero=0) + c = Hash.new {|h,k| h[k] = Hash.new} + path = Hash.new {|h,k| h[k] = Hash.new} + delta = Hash.new {|h,k| h[k] = 0} + edges.each do |e| + delta[e.source] += 1 + delta[e.target] -= 1 + path[e.source][e.target] = e.target + c[e.source][e.target] = cost(e, weight) + end + vertices.each do |k| + vertices.each do |i| + if c[i][k] + vertices.each do |j| + if c[k][j] && + (c[i][j].nil? or c[i][j] > (c[i][k] + c[k][j])) + path[i][j] = path[i][k] + c[i][j] = c[i][k] + c[k][j] + return nil if i == j and c[i][j] < zero + end + end + end + end + end + [c, path, delta] + end # floyd_warshall + + end # Distance + end # Graph +end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/dot.rb b/lib/puppet/gratr/dot.rb new file mode 100644 index 000000000..fbf4fb073 --- /dev/null +++ b/lib/puppet/gratr/dot.rb @@ -0,0 +1,90 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ +# +# Minimal Dot support, based on Dave Thomas's dot module (included in rdoc). +# rdot.rb is a modified version which also contains support for undirected +# graphs. + +require 'puppet/gratr/rdot' + +module GRATR + module Graph + + # Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an + # undirected Graph. _params_ can contain any graph property specified in + # rdot.rb. If an edge or vertex label is a kind of Hash then the keys + # which match +dot+ properties will be used as well. + def to_dot_graph (params = {}) + params['name'] ||= self.class.name.gsub(/:/,'_') + fontsize = params['fontsize'] ? params['fontsize'] : '8' + graph = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params) + edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge + vertices.each do |v| + name = v.to_s + params = {'name' => '"'+name+'"', + 'fontsize' => fontsize, + 'label' => name} + v_label = vertex_label(v) + params.merge!(v_label) if v_label and v_label.kind_of? Hash + graph << DOT::DOTNode.new(params) + end + edges.each do |e| + params = {'from' => '"'+ e.source.to_s + '"', + 'to' => '"'+ e.target.to_s + '"', + 'fontsize' => fontsize } + e_label = edge_label(e) + params.merge!(e_label) if e_label and e_label.kind_of? Hash + graph << edge_klass.new(params) + end + graph + end + + # Output the dot format as a string + def to_dot (params={}) to_dot_graph(params).to_s; end + + # Call +dotty+ for the graph which is written to the file 'graph.dot' + # in the # current directory. + def dotty (params = {}, dotfile = 'graph.dot') + File.open(dotfile, 'w') {|f| f << to_dot(params) } + system('dotty', dotfile) + end + + # Use +dot+ to create a graphical representation of the graph. Returns the + # filename of the graphics file. + def write_to_graphic_file (fmt='png', dotfile='graph') + src = dotfile + '.dot' + dot = dotfile + '.' + fmt + + File.open(src, 'w') {|f| f << self.to_dot << "\n"} + + system( "dot -T#{fmt} #{src} -o #{dot}" ) + dot + end + + end # module Graph +end # module GRATR diff --git a/lib/puppet/gratr/edge.rb b/lib/puppet/gratr/edge.rb new file mode 100644 index 000000000..8470e5458 --- /dev/null +++ b/lib/puppet/gratr/edge.rb @@ -0,0 +1,145 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +module GRATR + + # Edge includes classes for representing egdes of directed and + # undirected graphs. There is no need for a Vertex class, because any ruby + # object can be a vertex of a graph. + # + # Edge's base is a Struct with a :source, a :target and a :label + Struct.new("EdgeBase",:source, :target, :label) + + class Edge < Struct::EdgeBase + + def initialize(p_source,p_target,p_label=nil) + super(p_source, p_target, p_label) + end + + # Ignore labels for equality + def eql?(other) self.class == other.class and target==other.target and source==other.source; end + + # Alias for eql? + alias == eql? + + # Returns (v,u) if self == (u,v). + def reverse() self.class.new(target, source, label); end + + # Sort support + def <=>(rhs) [source,target] <=> [rhs.source,rhs.target]; end + + # Edge.new[1,2].to_s => "(1-2 'label')" + def to_s + l = label ? " '#{label.to_s}'" : '' + "(#{source}-#{target}#{l})" + end + + # Hash is defined in such a way that label is not + # part of the hash value + def hash() source.hash ^ (target.hash+1); end + + # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] + def self.[](p_source, p_target, p_label=nil) + new(p_source, p_target, p_label) + end + + def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{label.inspect}]"; end + + end + + # An undirected edge is simply an undirected pair (source, target) used in + # undirected graphs. UndirectedEdge[u,v] == UndirectedEdge[v,u] + class UndirectedEdge < Edge + + # Equality allows for the swapping of source and target + def eql?(other) super or (self.class == other.class and target==other.source and source==other.target); end + + # Alias for eql? + alias == eql? + + # Hash is defined such that source and target can be reversed and the + # hash value will be the same + # + # This will cause problems with self loops + def hash() source.hash ^ target.hash; end + + # Sort support + def <=>(rhs) + [[source,target].max,[source,target].min] <=> + [[rhs.source,rhs.target].max,[rhs.source,rhs.target].min] + end + + # UndirectedEdge[1,2].to_s == "(1=2 'label)" + def to_s + l = label ? " '#{label.to_s}'" : '' + s = source.to_s + t = target.to_s + "(#{[s,t].min}=#{[s,t].max}#{l})" + end + + end + + # This module provides for internal numbering of edges for differentiating between mutliple edges + module EdgeNumber + + attr_accessor :number # Used to differentiate between mutli-edges + + def initialize(p_source,p_target,p_number,p_label=nil) + self.number = p_number + super(p_source, p_target, p_label) + end + + # Returns (v,u) if self == (u,v). + def reverse() self.class.new(target, source, number, label); end + def hash() super ^ number.hash; end + def to_s() super + "[#{number}]"; end + def <=>(rhs) (result = super(rhs)) == 0 ? number <=> rhs.number : result; end + def inspect() "#{self.class.to_s}[#{source.inspect},#{target.inspect},#{number.inspect},#{label.inspect}]"; end + def eql?(rhs) super(rhs) and (rhs.number.nil? or number.nil? or number == rhs.number); end + def ==(rhs) eql?(rhs); end + + # Shortcut constructor. Instead of Edge.new(1,2) one can use Edge[1,2] + def self.included(cl) + + def cl.[](p_source, p_target, p_number=nil, p_label=nil) + new(p_source, p_target, p_number, p_label) + end + end + + end + + class MultiEdge < Edge + include EdgeNumber + end + + class MultiUndirectedEdge < UndirectedEdge + include EdgeNumber + end + +end diff --git a/lib/puppet/gratr/graph.rb b/lib/puppet/gratr/graph.rb new file mode 100644 index 000000000..44c8bc4d8 --- /dev/null +++ b/lib/puppet/gratr/graph.rb @@ -0,0 +1,303 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/edge' +require 'puppet/gratr/labels' +require 'puppet/gratr/graph_api' + +module GRATR + + # Using the functions required by the GraphAPI, it implements all the + # basic functions of a Graph class by using only functions in GraphAPI. + # An actual implementation still needs to be done, as in Digraph or + # UndirectedGraph. + module Graph + include Enumerable + include Labels + include GraphAPI + + # Non destructive version of add_vertex!, returns modified copy of Graph + def add_vertex(v, l=nil) x=self.class.new(self); x.add_vertex!(v,l); end + + # Non destructive version add_edge!, returns modified copy of Graph + def add_edge(u, v=nil, l=nil) x=self.class.new(self); x.add_edge!(u,v,l); end + + # Non destructive version of remove_vertex!, returns modified copy of Graph + def remove_vertex(v) x=self.class.new(self); x.remove_vertex!(v); end + + # Non destructive version of remove_edge!, returns modified copy of Graph + def remove_edge(u,v=nil) x=self.class.new(self); x.remove_edge!(u,v); end + + # Return Array of adjacent portions of the Graph + # x can either be a vertex an edge. + # options specifies parameters about the adjacency search + # :type can be either :edges or :vertices (default). + # :direction can be :in, :out(default) or :all. + # + # Note: It is probably more efficently done in implementation. + def adjacent(x, options={}) + d = directed? ? (options[:direction] || :out) : :all + + # Discharge the easy ones first + return [x.source] if x.kind_of? Edge and options[:type] == :vertices and d == :in + return [x.target] if x.kind_of? Edge and options[:type] == :vertices and d == :out + return [x.source, x.target] if x.kind_of? Edge and options[:type] != :edges and d == :all + + (options[:type] == :edges ? edges : to_a).select {|u| adjacent?(x,u,d)} + end + + # Add all objects in _a_ to the vertex set. + def add_vertices!(*a) a.each {|v| add_vertex! v}; self; end + + # See add_vertices! + + def add_vertices(*a) x=self.class.new(self); x.add_vertices(*a); self; end + + # Add all edges in the _edges_ Enumerable to the edge set. Elements of the + # Enumerable can be both two-element arrays or instances of DirectedEdge or + # UnDirectedEdge. + def add_edges!(*args) args.each { |edge| add_edge!(edge) }; self; end + + # See add_edge! + def add_edges(*a) x=self.class.new(self); x.add_edges!(*a); self; end + + # Remove all vertices specified by the Enumerable a from the graph by + # calling remove_vertex!. + def remove_vertices!(*a) a.each { |v| remove_vertex! v }; end + + # See remove_vertices! + def remove_vertices(*a) x=self.class.new(self); x.remove_vertices(*a); end + + # Remove all vertices edges by the Enumerable a from the graph by + # calling remove_edge! + def remove_edges!(*a) a.each { |e| remove_edges! e }; end + + # See remove_edges + def remove_edges(*a) x=self.class.new(self); x.remove_edges(*a); end + + # Execute given block for each vertex, provides for methods in Enumerable + def each(&block) vertices.each(&block); end + + # Returns true if _v_ is a vertex of the graph. + # This is a default implementation that is of O(n) average complexity. + # If a subclass uses a hash to store vertices, then this can be + # made into an O(1) average complexity operation. + def vertex?(v) vertices.include?(v); end + + # Returns true if u or (u,v) is an Edge of the graph. + def edge?(*arg) edges.include?(edge_convert(*args)); end + + # Tests two objects to see if they are adjacent. + # direction parameter specifies direction of adjacency, :in, :out, or :all(default) + # All denotes that if there is any adjacency, then it will return true. + # Note that the default is different than adjacent where one is primarily concerned with finding + # all adjacent objects in a graph to a given object. Here the concern is primarily on seeing + # if two objects touch. For vertexes, any edge between the two will usually do, but the direction + # can be specified if need be. + def adjacent?(source, target, direction=:all) + if source.kind_of? GRATR::Edge + raise NoEdgeError unless edge? source + if target.kind_of? GRATR::Edge + raise NoEdgeError unless edge? target + (direction != :out and source.source == target.target) or (direction != :in and source.target == target.source) + else + raise NoVertexError unless vertex? target + (direction != :out and source.source == target) or (direction != :in and source.target == target) + end + else + raise NoVertexError unless vertex? source + if target.kind_of? GRATR::Edge + raise NoEdgeError unless edge? target + (direction != :out and source == target.target) or (direction != :in and source == target.source) + else + raise NoVertexError unless vertex? target + (direction != :out and edge?(target,source)) or (direction != :in and edge?(source,target)) + end + end + end + + # Returns true if the graph has no vertex, i.e. num_vertices == 0. + def empty?() vertices.size.zero?; end + + # Returns true if the given object is a vertex or Edge in the Graph. + # + def include?(x) x.kind_of?(GRATR::Edge) ? edge?(x) : vertex?(x); end + + # Returns the neighboorhood of the given vertex (or Edge) + # This is equivalent to adjacent, but bases type on the type of object. + # direction can be :all, :in, or :out + def neighborhood(x, direction = :all) + adjacent(x, :direction => direction, :type => ((x.kind_of? GRATR::Edge) ? :edges : :vertices )) + end + + # Union of all neighborhoods of vertices (or edges) in the Enumerable x minus the contents of x + # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 4 + def set_neighborhood(x, direction = :all) + x.inject(Set.new) {|a,v| a.merge(neighborhood(v,direction))}.reject {|v2| x.include?(v2)} + end + + # Union of all set_neighborhoods reachable in p edges + # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46 + def closed_pth_neighborhood(w,p,direction=:all) + if p <= 0 + w + elsif p == 1 + (w + set_neighborhood(w,direction)).uniq + else + n = set_neighborhood(w, direction) + (w + n + closed_pth_neighborhood(n,p-1,direction)).uniq + end + end + + # Returns the neighboorhoods reachable in p steps from every vertex (or edge) + # in the Enumerable x + # Definition taken from Jorgen Bang-Jensen, Gregory Gutin, _Digraphs: Theory, Algorithms and Applications_, pg 46 + def open_pth_neighborhood(x, p, direction=:all) + if p <= 0 + x + elsif p == 1 + set_neighborhood(x,direction) + else + set_neighborhood(open_pth_neighborhood(x, p-1, direction),direction) - closed_pth_neighborhood(x,p-1,direction) + end + end + + # Returns the number of out-edges (for directed graphs) or the number of + # incident edges (for undirected graphs) of vertex _v_. + def out_degree(v) adjacent(v, :direction => :out).size; end + + # Returns the number of in-edges (for directed graphs) or the number of + # incident edges (for undirected graphs) of vertex _v_. + def in_degree(v) adjacent(v, :direction => :in ).size; end + + # Returns the sum of the number in and out edges for a vertex + def degree(v) in_degree(v) + out_degree(v); end + + # Minimum in-degree + def min_in_degree() to_a.map {|v| in_degree(v)}.min; end + + # Minimum out-degree + def min_out_degree() to_a.map {|v| out_degree(v)}.min; end + + # Minimum degree of all vertexes + def min_degree() [min_in_degree, min_out_degree].min; end + + # Maximum in-degree + def max_in_degree() vertices.map {|v| in_degree(v)}.max; end + + # Maximum out-degree + def max_out_degree() vertices.map {|v| out_degree(v)}.max; end + + # Minimum degree of all vertexes + def max_degree() [max_in_degree, max_out_degree].max; end + + # Regular + def regular?() min_degree == max_degree; end + + # Returns the number of vertices. + def size() vertices.size; end + + # Synonym for size. + def num_vertices() vertices.size; end + + # Returns the number of edges. + def num_edges() edges.size; end + + # Utility method to show a string representation of the edges of the graph. + def to_s() edges.to_s; end + + # Equality is defined to be same set of edges and directed? + def eql?(g) + return false unless g.kind_of? GRATR::Graph + + (g.directed? == self.directed?) and + (vertices.sort == g.vertices.sort) and + (g.edges.sort == edges.sort) + end + + # Synonym for eql? + def ==(rhs) eql?(rhs); end + + # Merge another graph into this one + def merge(other) + other.vertices.each {|v| add_vertex!(v) } + other.edges.each {|e| add_edge!(e) } + other.edges.each {|e| add_edge!(e.reverse) } if directed? and !other.directed? + self + end + + # A synonym for merge, that doesn't modify the current graph + def +(other) + result = self.class.new(self) + case other + when GRATR::Graph : result.merge(other) + when GRATR::Edge : result.add_edge!(other) + else result.add_vertex!(other) + end + end + + # Remove all vertices in the specified right hand side graph + def -(other) + case other + when GRATR::Graph : induced_subgraph(vertices - other.vertices) + when GRATR::Edge : self.class.new(self).remove_edge!(other) + else self.class.new(self).remove_vertex!(other) + end + end + + # A synonym for add_edge! + def <<(edge) add_edge!(edge); end + + # Return the complement of the current graph + def complement + vertices.inject(self.class.new) do |a,v| + a.add_vertex!(v) + vertices.each {|v2| a.add_edge!(v,v2) unless edge?(v,v2) }; a + end + end + + # Given an array of vertices return the induced subgraph + def induced_subgraph(v) + edges.inject(self.class.new) do |a,e| + ( v.include?(e.source) and v.include?(e.target) ) ? (a << e) : a + end; + end + + def inspect + l = vertices.select {|v| self[v]}.map {|u| "vertex_label_set(#{u.inspect},#{self[u].inspect})"}.join('.') + self.class.to_s + '[' + edges.map {|e| e.inspect}.join(', ') + ']' + (l ? '.'+l : '') + end + + private + def edge_convert(*args) args[0].kind_of?(GRATR::Edge) ? args[0] : edge_class[*args]; end + + + end # Graph + +end # GRATR diff --git a/lib/puppet/gratr/graph_api.rb b/lib/puppet/gratr/graph_api.rb new file mode 100644 index 000000000..26d18958a --- /dev/null +++ b/lib/puppet/gratr/graph_api.rb @@ -0,0 +1,83 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +module GRATR + + # This defines the minimum set of functions required to make a graph class that can + # use the algorithms defined by this library + module GraphAPI + + # Is the graph directed? + # + # This method must be implemented by the specific graph class + def directed?() raise NotImplementedError; end + + # Add a vertex to the Graph and return the Graph + # An additional label l can be specified as well + # + # This method must be implemented by the specific graph class + def add_vertex!(v,l=nil) raise NotImplementedError; end + + # Add an edge to the Graph and return the Graph + # u can be an object of type GRATR::Edge or u,v specifies + # a source, target pair. The last parameter is an optional label + # + # This method must be implemented by the specific graph class + def add_edge!(u,v=nil,l=nil) raise NotImplementedError; end + + # Remove a vertex to the Graph and return the Graph + # + # This method must be implemented by the specific graph class + def remove_vertex!(v) raise NotImplementedError; end + + # Remove an edge from the Graph and return the Graph + # + # Can be a type of GRATR::Edge or a source and target + # This method must be implemented by the specific graph class + def remove_edge!(u,v=nil) raise NotImplementedError; end + + # Return the array of vertices. + # + # This method must be implemented by the specific graph class + def vertices() raise NotImplementedError; end + + # Return the array of edges. + # + # This method must be implemented by the specific graph class + def edges() raise NotImplementedError; end + + # Returns the edge class + def edge_class() raise NotImplementedError; end + + # Return the chromatic number for this graph + # This is currently incomplete and in some cases will be NP-complete + # FIXME: Should this even be here? My gut feeling is no... + def chromatic_number() raise NotImplementedError; end + end +end \ No newline at end of file diff --git a/lib/puppet/gratr/import.rb b/lib/puppet/gratr/import.rb new file mode 100644 index 000000000..7be8fb3f3 --- /dev/null +++ b/lib/puppet/gratr/import.rb @@ -0,0 +1,44 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr' + +# Pull all GRATR classes up into the current namespace +Edge = GRATR::Edge +UndirectedEdge = GRATR::UndirectedEdge +MultiEdge = GRATR::MultiEdge +MultiUndirectedEdge = GRATR::MultiUndirectedEdge +Graph = GRATR::Graph +Digraph = GRATR::Digraph +DirectedGraph = GRATR::DirectedGraph +DirectedPseudoGraph = GRATR::DirectedPseudoGraph +DirectedMultiGraph = GRATR::DirectedMultiGraph +UndirectedGraph = GRATR::UndirectedGraph +UndirectedPseudoGraph = GRATR::UndirectedPseudoGraph +UndirectedMultiGraph = GRATR::UndirectedMultiGraph +Complete = GRATR::Complete diff --git a/lib/puppet/gratr/labels.rb b/lib/puppet/gratr/labels.rb new file mode 100644 index 000000000..7e53df404 --- /dev/null +++ b/lib/puppet/gratr/labels.rb @@ -0,0 +1,90 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +module GRATR + module Labels + # Return a label for an edge or vertex + def [](u) (u.kind_of? GRATR::Edge) ? edge_label(u) : vertex_label(u); end + + # Set a label for an edge or vertex + def []= (u, value) (u.kind_of? GRATR::Edge) ? edge_label_set(u,value) : vertex_label_set(u, value); end + + # Delete a label entirely + def delete_label(u) (u.kind_of? GRATR::Edge) ? edge_label_delete(u) : vertex_label_delete(u); end + + # Get the label for an edge + def vertex_label(v) vertex_label_dict[v]; end + + # Set the label for an edge + def vertex_label_set(v, l) vertex_label_dict[v] = l; self; end + + # Get the label for an edge + def edge_label(u,v=nil,n=nil) + u = edge_convert(u,v,n) + edge_label_dict[u] + end + + # Set the label for an edge + def edge_label_set(u, v=nil, l=nil, n=nil) + u.kind_of?(GRATR::Edge) ? l = v : u = edge_convert(u,v,n) + edge_label_dict[u] = l; self + end + + # Delete all graph labels + def clear_all_labels() @vertex_labels = {}; @edge_labels = {}; end + + # Delete an edge label + def edge_label_delete(u, v=nil, n=nil) + u = edge_convert(u,v,n) + edge_label_dict.delete(u) + end + + # Delete a vertex label + def vertex_label_delete(v) vertex_label_dict.delete(v); end + + protected + + def vertex_label_dict() @vertex_labels ||= {}; end + def edge_label_dict() @edge_labels ||= {}; end + + # A generic cost function. It either calls the weight function with and edge + # constructed from the two nodes, or calls the [] operator of the label + # when given a value. If no weight value is specified, the label itself is + # treated as the cost value. + # + # Note: This function will not work for Pseudo or Multi graphs at present. + def cost(u,v=nil,weight=nil) + u.kind_of?(Edge) ? weight = v : u = edge_class[u,v] + case weight + when Proc : weight.call(u) + when nil : self[u] + else self[u][weight] + end + end + + end +end diff --git a/lib/puppet/gratr/maximum_flow.rb b/lib/puppet/gratr/maximum_flow.rb new file mode 100644 index 000000000..7b3ef9b2f --- /dev/null +++ b/lib/puppet/gratr/maximum_flow.rb @@ -0,0 +1,64 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + +module GRATR + + module Graph + + module MaximumFlow + + # Maximum flow, it returns an array with the maximum flow and a hash of flow per edge + # Currently a highly inefficient implementation, FIXME, This should use Goldberg and Tarjan's method. + def maximum_flow(s, t, capacity = nil, zero = 0) + flow = Hash.new(zero) + available = Hash.new(zero) + total = zero + edges.each {|e| available[e] = cost(e,capacity)} + adj_positive = Proc.new do |u| + adjacent(u).select {|r| available[edge_class[u,r]] > zero} + end + while (tree = bfs_tree_from_vertex(start))[t] + route = [t] + while route[-1] != s + route << tree[route[route[-1]]] + raise ArgumentError, "No route from #{s} to #{t} possible" + end; route.reverse + amt = route.map {|e| available[e]}.min + route.each do |e| + flow[e] += amt + available[e] -= amt + end + total += amt + end + + [total, flow] + end + + end # MaximumFlow + end # Graph +end # GRATR \ No newline at end of file diff --git a/lib/puppet/gratr/rdot.rb b/lib/puppet/gratr/rdot.rb new file mode 100644 index 000000000..4ce545ae6 --- /dev/null +++ b/lib/puppet/gratr/rdot.rb @@ -0,0 +1,327 @@ +# rdot.rb +# +# $Id$ +# +# This is a modified version of dot.rb from Dave Thomas's rdoc project. I [Horst Duchene] +# renamed it to rdot.rb to avoid collision with an installed rdoc/dot. +# +# It also supports undirected edges. + +module DOT + + # These glogal vars are used to make nice graph source. + + $tab = ' ' + $tab2 = $tab * 2 + + # if we don't like 4 spaces, we can change it any time + + def change_tab (t) + $tab = t + $tab2 = t * 2 + end + + # options for node declaration + + NODE_OPTS = [ + # attributes due to + # http://www.graphviz.org/Documentation/dotguide.pdf + # March, 26, 2005 + 'bottomlabel', # auxiliary label for nodes of shape M* + 'color', # default: black; node shape color + 'comment', # any string (format-dependent) + 'distortion', # default: 0.0; node distortion for shape=polygon + 'fillcolor', # default: lightgrey/black; node fill color + 'fixedsize', # default: false; label text has no affect on node size + 'fontcolor', # default: black; type face color + 'fontname', # default: Times-Roman; font family + 'fontsize', #default: 14; point size of label + 'group', # name of node’s group + 'height', # default: .5; height in inches + 'label', # default: node name; any string + 'layer', # default: overlay range; all, id or id:id + 'orientation', # dafault: 0.0; node rotation angle + 'peripheries', # shape-dependent number of node boundaries + 'regular', # default: false; force polygon to be regular + 'shape', # default: ellipse; node shape; see Section 2.1 and Appendix E + 'shapefile', # external EPSF or SVG custom shape file + 'sides', # default: 4; number of sides for shape=polygon + 'skew' , # default: 0.0; skewing of node for shape=polygon + 'style', # graphics options, e.g. bold, dotted, filled; cf. Section 2.3 + 'toplabel', # auxiliary label for nodes of shape M* + 'URL', # URL associated with node (format-dependent) + 'width', # default: .75; width in inches + 'z', #default: 0.0; z coordinate for VRML output + + # maintained for backward compatibility or rdot internal + 'bgcolor', + 'rank' + ] + + # options for edge declaration + + EDGE_OPTS = [ + 'arrowhead', # default: normal; style of arrowhead at head end + 'arrowsize', # default: 1.0; scaling factor for arrowheads + 'arrowtail', # default: normal; style of arrowhead at tail end + 'color', # default: black; edge stroke color + 'comment', # any string (format-dependent) + 'constraint', # default: true use edge to affect node ranking + 'decorate', # if set, draws a line connecting labels with their edges + 'dir', # default: forward; forward, back, both, or none + 'fontcolor', # default: black type face color + 'fontname', # default: Times-Roman; font family + 'fontsize', # default: 14; point size of label + 'headlabel', # label placed near head of edge + 'headport', # n,ne,e,se,s,sw,w,nw + 'headURL', # URL attached to head label if output format is ismap + 'label', # edge label + 'labelangle', # default: -25.0; angle in degrees which head or tail label is rotated off edge + 'labeldistance', # default: 1.0; scaling factor for distance of head or tail label from node + 'labelfloat', # default: false; lessen constraints on edge label placement + 'labelfontcolor', # default: black; type face color for head and tail labels + 'labelfontname', # default: Times-Roman; font family for head and tail labels + 'labelfontsize', # default: 14 point size for head and tail labels + 'layer', # default: overlay range; all, id or id:id + 'lhead', # name of cluster to use as head of edge + 'ltail', # name of cluster to use as tail of edge + 'minlen', # default: 1 minimum rank distance between head and tail + 'samehead', # tag for head node; edge heads with the same tag are merged onto the same port + 'sametail', # tag for tail node; edge tails with the same tag are merged onto the same port + 'style', # graphics options, e.g. bold, dotted, filled; cf. Section 2.3 + 'taillabel', # label placed near tail of edge + 'tailport', # n,ne,e,se,s,sw,w,nw + 'tailURL', # URL attached to tail label if output format is ismap + 'weight', # default: 1; integer cost of stretching an edge + + # maintained for backward compatibility or rdot internal + 'id' + ] + + # options for graph declaration + + GRAPH_OPTS = [ + 'bgcolor', + 'center', 'clusterrank', 'color', 'concentrate', + 'fontcolor', 'fontname', 'fontsize', + 'label', 'layerseq', + 'margin', 'mclimit', + 'nodesep', 'nslimit', + 'ordering', 'orientation', + 'page', + 'rank', 'rankdir', 'ranksep', 'ratio', + 'size' + ] + + # a root class for any element in dot notation + + class DOTSimpleElement + + attr_accessor :name + + def initialize (params = {}) + @label = params['name'] ? params['name'] : '' + end + + def to_s + @name + end + end + + # an element that has options ( node, edge, or graph ) + + class DOTElement < DOTSimpleElement + + # attr_reader :parent + attr_accessor :name, :options + + def initialize (params = {}, option_list = []) + super(params) + @name = params['name'] ? params['name'] : nil + @parent = params['parent'] ? params['parent'] : nil + @options = {} + option_list.each{ |i| + @options[i] = params[i] if params[i] + } + @options['label'] ||= @name if @name != 'node' + end + + def each_option + @options.each{ |i| yield i } + end + + def each_option_pair + @options.each_pair{ |key, val| yield key, val } + end + + #def parent=( thing ) + # @parent.delete( self ) if defined?( @parent ) and @parent + # @parent = thing + #end + + end + + + # This is used when we build nodes that have shape=record + # ports don't have options :) + + class DOTPort < DOTSimpleElement + + attr_accessor :label + + def initialize (params = {}) + super(params) + @name = params['label'] ? params['label'] : '' + end + + def to_s + ( @name && @name != "" ? "<#{@name}>" : "" ) + "#{@label}" + end + end + + # node element + + class DOTNode < DOTElement + + @ports + + def initialize (params = {}, option_list = NODE_OPTS) + super(params, option_list) + @ports = params['ports'] ? params['ports'] : [] + end + + def each_port + @ports.each { |i| yield i } + end + + def << (thing) + @ports << thing + end + + def push (thing) + @ports.push(thing) + end + + def pop + @ports.pop + end + + def to_s (t = '') + + # This code is totally incomprehensible; it needs to be replaced! + + label = @options['shape'] != 'record' && @ports.length == 0 ? + @options['label'] ? + t + $tab + "label = \"#{@options['label']}\"\n" : + '' : + t + $tab + 'label = "' + " \\\n" + + t + $tab2 + "#{@options['label']}| \\\n" + + @ports.collect{ |i| + t + $tab2 + i.to_s + }.join( "| \\\n" ) + " \\\n" + + t + $tab + '"' + "\n" + + t + "#{@name} [\n" + + @options.to_a.collect{ |i| + i[1] && i[0] != 'label' ? + t + $tab + "#{i[0]} = #{i[1]}" : nil + }.compact.join( ",\n" ) + ( label != '' ? ",\n" : "\n" ) + + label + + t + "]\n" + end + + end # class DOTNode + + # A subgraph element is the same to graph, but has another header in dot + # notation. + + class DOTSubgraph < DOTElement + + @nodes + @dot_string + + def initialize (params = {}, option_list = GRAPH_OPTS) + super(params, option_list) + @nodes = params['nodes'] ? params['nodes'] : [] + @dot_string = 'graph' + end + + def each_node + @nodes.each{ |i| yield i } + end + + def << (thing) + @nodes << thing + end + + def push (thing) + @nodes.push( thing ) + end + + def pop + @nodes.pop + end + + def to_s (t = '') + hdr = t + "#{@dot_string} #{@name} {\n" + + options = @options.to_a.collect{ |name, val| + val && name != 'label' ? + t + $tab + "#{name} = #{val}" : + name ? t + $tab + "#{name} = \"#{val}\"" : nil + }.compact.join( "\n" ) + "\n" + + nodes = @nodes.collect{ |i| + i.to_s( t + $tab ) + }.join( "\n" ) + "\n" + hdr + options + nodes + t + "}\n" + end + + end # class DOTSubgraph + + # This is a graph. + + class DOTDigraph < DOTSubgraph + + def initialize (params = {}, option_list = GRAPH_OPTS) + super(params, option_list) + @dot_string = 'digraph' + end + + end # class DOTDigraph + + # This is an edge. + + class DOTEdge < DOTElement + + attr_accessor :from, :to + + def initialize (params = {}, option_list = EDGE_OPTS) + super(params, option_list) + @from = params['from'] ? params['from'] : nil + @to = params['to'] ? params['to'] : nil + end + + def edge_link + '--' + end + + def to_s (t = '') + t + "#{@from} #{edge_link} #{to} [\n" + + @options.to_a.collect{ |i| + i[1] && i[0] != 'label' ? + t + $tab + "#{i[0]} = #{i[1]}" : + i[1] ? t + $tab + "#{i[0]} = \"#{i[1]}\"" : nil + }.compact.join( "\n" ) + "\n" + t + "]\n" + end + + end # class DOTEdge + + class DOTDirectedEdge < DOTEdge + + def edge_link + '->' + end + + end # class DOTDirectedEdge +end # module DOT diff --git a/lib/puppet/gratr/search.rb b/lib/puppet/gratr/search.rb new file mode 100644 index 000000000..3206ec5d9 --- /dev/null +++ b/lib/puppet/gratr/search.rb @@ -0,0 +1,409 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +module GRATR + module Graph + module Search + + # Options are mostly callbacks passed in as a hash. + # The following are valid, anything else is ignored + # :enter_vertex => Proc Called upon entry of a vertex + # :exit_vertex => Proc Called upon exit of a vertex + # :root_vertex => Proc Called when a vertex the a root of a tree + # :start_vertex => Proc Called for the first vertex of the search + # :examine_edge => Proc Called when an edge is examined + # :tree_edge => Proc Called when the edge is a member of the tree + # :back_edge => Proc Called when the edge is a back edge + # :forward_edge => Proc Called when the edge is a forward edge + # :adjacent => Proc that given a vertex returns adjacent nodes, defaults to adjacent call of graph useful for changing the definition of adjacent in some algorithms + # + # :start => Vertex Specifies the vertex to start search from + # + # If a &block is specified it defaults to :enter_vertex + # + # Returns the list of vertexes as reached by enter_vertex + # This allows for calls like, g.bfs.each {|v| ...} + # + # Can also be called like bfs_examine_edge {|e| ... } or + # dfs_back_edge {|e| ... } for any of the callbacks + # + # A full example usage is as follows: + # + # ev = Proc.new {|x| puts "Enter Vertex #{x}"} + # xv = Proc.new {|x| puts "Exit Vertex #{x}"} + # sv = Proc.new {|x| puts "Start Vertex #{x}"} + # ee = Proc.new {|x| puts "Examine Edge #{x}"} + # te = Proc.new {|x| puts "Tree Edge #{x}"} + # be = Proc.new {|x| puts "Back Edge #{x}"} + # fe = Proc.new {|x| puts "Forward Edge #{x}"} + # Digraph[1,2,2,3,3,4].dfs({ + # :enter_vertex => ev, + # :exit_vertex => xv, + # :start_vertex => sv, + # :examine_edge => ee, + # :tree_edge => te, + # :back_edge => be, + # :forward_edge => fe }) + # + # Which outputs: + # + # Start Vertex 1 + # Enter Vertex 1 + # Examine Edge (1=2) + # Tree Edge (1=2) + # Enter Vertex 2 + # Examine Edge (2=3) + # Tree Edge (2=3) + # Enter Vertex 3 + # Examine Edge (3=4) + # Tree Edge (3=4) + # Enter Vertex 4 + # Examine Edge (1=4) + # Back Edge (1=4) + # Exit Vertex 4 + # Exit Vertex 3 + # Exit Vertex 2 + # Exit Vertex 1 + def bfs(options={}, &block) gratr_search_helper(:shift, options, &block); end + + # See options for bfs method + def dfs(options={}, &block) gratr_search_helper(:pop, options, &block); end + + # Routine to compute a spanning forest for the given search method + # Returns two values, first is a hash of predecessors and second an array of root nodes + def spanning_forest(start, routine) + predecessor = {} + roots = [] + te = Proc.new {|e| predecessor[e.target] = e.source} + rv = Proc.new {|v| roots << v} + method(routine).call :start => start, :tree_edge => te, :root_vertex => rv + [predecessor, roots] + end + + # Return the dfs spanning forest for the given start node, see spanning_forest + def dfs_spanning_forest(start) spanning_forest(start, :dfs); end + + # Return the bfs spanning forest for the given start node, see spanning_forest + def bfs_spanning_forest(start) spanning_forest(start, :bfs); end + + # Returns a hash of predecessors in a tree rooted at the start node. If this is a connected graph + # then it will be a spanning tree and contain all vertices. An easier way to tell if it's a spanning tree is to + # use a spanning_forest call and check if there is a single root node. + def tree_from_vertex(start, routine) + predecessor={} + correct_tree = false + te = Proc.new {|e| predecessor[e.target] = e.source if correct_tree} + rv = Proc.new {|v| correct_tree = (v == start)} + method(routine).call :start => start, :tree_edge => te, :root_vertex => rv + predecessor + end + + # Returns a hash of predecessors for the depth first search tree rooted at the given node + def dfs_tree_from_vertex(start) tree_from_vertex(start, :dfs); end + + # Returns a hash of predecessors for the depth first search tree rooted at the given node + def bfs_tree_from_vertex(start) tree_from_vertex(start, :bfs); end + + # An inner class used for greater efficiency in lexicograph_bfs + # + # Original desgn taken from Golumbic's, "Algorithmic Graph Theory and + # Perfect Graphs" pg, 87-89 + class LexicographicQueue + + # Called with the initial values (array) + def initialize(values) + @node = Struct.new(:back, :forward, :data) + @node.class_eval { def hash() @hash; end; @@cnt=0 } + @set = {} + @tail = @node.new(nil, nil, Array.new(values)) + @tail.instance_eval { @hash = (@@cnt+=1) } + values.each {|a| @set[a] = @tail} + end + + # Pop an entry with maximum lexical value from queue + def pop() + return nil unless @tail + value = @tail[:data].pop + @tail = @tail[:forward] while @tail and @tail[:data].size == 0 + @set.delete(value); value + end + + # Increase lexical value of given values (array) + def add_lexeme(values) + fix = {} + values.select {|v| @set[v]}.each do |w| + sw = @set[w] + if fix[sw] + s_prime = sw[:back] + else + s_prime = @node.new(sw[:back], sw, []) + s_prime.instance_eval { @hash = (@@cnt+=1) } + @tail = s_prime if @tail == sw + sw[:back][:forward] = s_prime if sw[:back] + sw[:back] = s_prime + fix[sw] = true + end + s_prime[:data] << w + sw[:data].delete(w) + @set[w] = s_prime + end + fix.keys.select {|n| n[:data].size == 0}.each do |e| + e[:forward][:back] = e[:back] if e[:forward] + e[:back][:forward] = e[:forward] if e[:back] + end + end + + end + + # Lexicographic breadth-first search, the usual queue of vertices + # is replaced by a queue of unordered subsets of the vertices, + # which is sometimes refined but never reordered. + # + # Originally developed by Rose, Tarjan, and Leuker, "Algorithmic + # aspects of vertex elimination on graphs", SIAM J. Comput. 5, 266-283 + # MR53 #12077 + # + # Implementation taken from Golumbic's, "Algorithmic Graph Theory and + # Perfect Graphs" pg, 84-90 + def lexicograph_bfs(&block) + lex_q = GRATR::Graph::Search::LexicographicQueue.new(vertices) + result = [] + num_vertices.times do + v = lex_q.pop + result.unshift(v) + lex_q.add_lexeme(adjacent(v)) + end + result.each {|r| block.call(r)} if block + result + end + + + # A* Heuristic best first search + # + # start is the starting vertex for the search + # + # func is a Proc that when passed a vertex returns the heuristic + # weight of sending the path through that node. It must always + # be equal to or less than the true cost + # + # options are mostly callbacks passed in as a hash, the default block is + # :discover_vertex and weight is assumed to be the label for the Edge. + # The following options are valid, anything else is ignored. + # + # * :weight => can be a Proc, or anything else is accessed using the [] for the + # the label or it defaults to using + # the value stored in the label for the Edge. If it is a Proc it will + # pass the edge to the proc and use the resulting value. + # * :discover_vertex => Proc invoked when a vertex is first discovered + # and is added to the open list. + # * :examine_vertex => Proc invoked when a vertex is popped from the + # queue (i.e., it has the lowest cost on the open list). + # * :examine_edge => Proc invoked on each out-edge of a vertex + # immediately after it is examined. + # * :edge_relaxed => Proc invoked on edge (u,v) if d[u] + w(u,v) < d[v]. + # * :edge_not_relaxed=> Proc invoked if the edge is not relaxed (see above). + # * :black_target => Proc invoked when a vertex that is on the closed + # list is "rediscovered" via a more efficient path, and is re-added + # to the OPEN list. + # * :finish_vertex => Proc invoked on a vertex when it is added to the + # closed list, which happens after all of its out edges have been + # examined. + # + # Returns array of nodes in path, or calls block on all nodes, + # upon failure returns nil + # + # Can also be called like astar_examine_edge {|e| ... } or + # astar_edge_relaxed {|e| ... } for any of the callbacks + # + # The criteria for expanding a vertex on the open list is that it has the + # lowest f(v) = g(v) + h(v) value of all vertices on open. + # + # The time complexity of A* depends on the heuristic. It is exponential + # in the worst case, but is polynomial when the heuristic function h + # meets the following condition: |h(x) - h*(x)| < O(log h*(x)) where h* + # is the optimal heuristic, i.e. the exact cost to get from x to the goal. + # + # Also see: http://en.wikipedia.org/wiki/A-star_search_algorithm + # + def astar(start, goal, func, options, &block) + options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" + options.instance_eval "def handle_edge(sym,u,v) self[sym].call(#{edge_class}[u,v]) if self[sym]; end" + + d = { start => 0 } + f = { start => func.call(start) } + color = {start => :gray} + p = Hash.new {|k| p[k] = k} + queue = [start] + block.call(start) if block + until queue.empty? + u = queue.pop + options.handle_vertex(:examine_vertex, u) + adjacent(u).each do |v| + e = edge_class[u,v] + options.handle_edge(:examine_edge, u, v) + w = cost(e, options[:weight]) + raise ArgumentError unless w + if d[v].nil? or (w + d[u]) < d[v] + options.handle_edge(:edge_relaxed, u, v) + d[v] = w + d[u] + f[v] = d[v] + func.call(u) + p[v] = u + unless color[v] == :gray + options.handle_vertex(:black_target, v) if color[v] == :black + color[v] = :gray + options.handle_vertex(:discover_vertex, v) + queue << v + block.call(v) if block + return [start]+queue if v == goal + end + else + options.handle_edge(:edge_not_relaxed, u, v) + end + end # adjacent(u) + color[u] = :black + options.handle_vertex(:finish_vertex,u) + end # queue.empty? + nil # failure, on fall through + end # astar + + # Best first has all the same options as astar with func set to h(v) = 0. + # There is an additional option zero which should be defined to zero + # for the operation '+' on the objects used in the computation of cost. + # The parameter zero defaults to 0. + def best_first(start, goal, options, zero=0, &block) + func = Proc.new {|v| zero} + astar(start, goal, func, options, &block) + end + + alias_method :pre_search_method_missing, :method_missing # :nodoc: + def method_missing(sym,*args, &block) # :nodoc: + m1=/^dfs_(\w+)$/.match(sym.to_s) + dfs((args[0] || {}).merge({m1.captures[0].to_sym => block})) if m1 + m2=/^bfs_(\w+)$/.match(sym.to_s) + bfs((args[0] || {}).merge({m2.captures[0].to_sym => block})) if m2 + pre_search_method_missing(sym, *args, &block) unless m1 or m2 + end + + private + + def gratr_search_helper(op, options={}, &block) # :nodoc: + return nil if size == 0 + result = [] + # Create options hash that handles callbacks + options = {:enter_vertex => block, :start => to_a[0]}.merge(options) + options.instance_eval "def handle_vertex(sym,u) self[sym].call(u) if self[sym]; end" + options.instance_eval "def handle_edge(sym,e) self[sym].call(e) if self[sym]; end" + # Create waiting list that is a queue or stack depending on op specified. + # First entry is the start vertex. + waiting = [options[:start]] + waiting.instance_eval "def next() #{op.to_s}; end" + # Create color map with all set to unvisited except for start vertex + # will be set to waiting + color_map = vertices.inject({}) {|a,v| a[v] = :unvisited; a} + color_map.merge!(waiting[0] => :waiting) + options.handle_vertex(:start_vertex, waiting[0]) + options.handle_vertex(:root_vertex, waiting[0]) + # Perform the actual search until nothing is waiting + until waiting.empty? + # Loop till the search iterator exhausts the waiting list + visited_edges={} # This prevents retraversing edges in undirected graphs + until waiting.empty? + gratr_search_iteration(options, waiting, color_map, visited_edges, result, op == :pop) + end + # Waiting list is exhausted, see if a new root vertex is available + u=color_map.detect {|key,value| value == :unvisited} + waiting.push(u[0]) if u + options.handle_vertex(:root_vertex, u[0]) if u + end; result + end + + def gratr_search_iteration(options, waiting, color_map, visited_edges, result, recursive=false) # :nodoc: + # Get the next waiting vertex in the list + u = waiting.next + options.handle_vertex(:enter_vertex,u) + result << u + # Examine all adjacent outgoing edges, not previously traversed + adj_proc = options[:adjacent] || self.method(:adjacent).to_proc + adj_proc.call(u,:type => :edges, :direction => :out).reject {|w| visited_edges[w]}.each do |e| + e = e.reverse unless directed? or e.source == u # Preserves directionality where required + v = e.target + options.handle_edge(:examine_edge, e) + visited_edges[e]=true + case color_map[v] + # If it's unvisited it goes into the waiting list + when :unvisited + options.handle_edge(:tree_edge, e) + color_map[v] = :waiting + waiting.push(v) + # If it's recursive (i.e. dfs) then call self + gratr_search_iteration(options, waiting, color_map, visited_edges, result, true) if recursive + when :waiting + options.handle_edge(:back_edge, e) + else + options.handle_edge(:forward_edge, e) + end + end + # Finished with this vertex + options.handle_vertex(:exit_vertex, u) + color_map[u] = :visited + end + + public + # Topological Sort Iterator + # + # The topological sort algorithm creates a linear ordering of the vertices + # such that if edge (u,v) appears in the graph, then u comes before v in + # the ordering. The graph must be a directed acyclic graph (DAG). + # + # The iterator can also be applied to undirected graph or to a DG graph + # which contains a cycle. In this case, the Iterator does not reach all + # vertices. The implementation of acyclic? and cyclic? uses this fact. + # + # Can be called with a block as a standard Ruby iterator, or it can + # be used directly as it will return the result as an Array + def topsort(start = nil, &block) + result = [] + go = true + back = Proc.new {|e| go = false } + push = Proc.new {|v| result.unshift(v) if go} + start ||= vertices[0] + dfs({:exit_vertex => push, :back_edge => back, :start => start}) + result.each {|v| block.call(v)} if block; result + end + + # Returns true if a graph contains no cycles, false otherwise + def acyclic?() topsort.size == size; end + + # Returns false if a graph contains no cycles, true otherwise + def cyclic?() not acyclic?; end + + + end # Search + end # Graph +end # GRATR diff --git a/lib/puppet/gratr/strong_components.rb b/lib/puppet/gratr/strong_components.rb new file mode 100644 index 000000000..796ae16bb --- /dev/null +++ b/lib/puppet/gratr/strong_components.rb @@ -0,0 +1,127 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'set' + +module GRATR + module Graph + module StrongComponents + # strong_components computes the strongly connected components + # of a graph using Tarjan's algorithm based on DFS. See: Robert E. Tarjan + # _Depth_First_Search_and_Linear_Graph_Algorithms_. SIAM Journal on + # Computing, 1(2):146-160, 1972 + # + # The output of the algorithm is an array of components where is + # component is an array of vertices + # + # A strongly connected component of a directed graph G=(V,E) is a maximal + # set of vertices U which is in V such that for every pair of + # vertices u and v in U, we have both a path from u to v + # and path from v to u. That is to say that u and v are reachable + # from each other. + # + def strong_components + + dfs_num = 0 + stack = []; result = []; root = {}; comp = {}; number = {} + + # Enter vertex callback + enter = Proc.new do |v| + root[v] = v + comp[v] = :new + number[v] = (dfs_num += 1) + stack.push(v) + end + + # Exit vertex callback + exit = Proc.new do |v| + adjacent(v).each do |w| + if comp[w] == :new + root[v] = (number[root[v]] < number[root[w]] ? root[v] : root[w]) + end + end + if root[v] == v + component = [] + begin + w = stack.pop + comp[w] = :assigned + component << w + end until w == v + result << component + end + end + + # Execute depth first search + dfs({:enter_vertex => enter, :exit_vertex => exit}); result + + end # strong_components + + # Returns a condensation graph of the strongly connected components + # Each node is an array of nodes from the original graph + def condensation + sc = strong_components + cg = self.class.new + map = sc.inject({}) do |a,c| + c.each {|v| a[v] = c }; a + end + sc.each do |c| + c.each do |v| + adjacent(v).each {|v| cg.add_edge!(c, map[v]) unless c == map[v]} + end + end; cg + end + + # Compute transitive closure of a graph. That is any node that is reachable + # along a path is added as a directed edge. + def transitive_closure! + cgtc = condensation.gratr_inner_transitive_closure! + cgtc.each do |cgv| + cgtc.adjacent(cgv).each do |adj| + cgv.each do |u| + adj.each {|v| add_edge!(u,v)} + end + end + end; self + end + + # This returns the transitive closure of a graph. The original graph + # is not changed. + def transitive_closure() self.class.new(self).transitive_closure!; end + + private + def gratr_inner_transitive_closure! # :nodoc: + topsort.reverse.each do |u| + adjacent(u).each do |v| + adjacent(v).each {|w| add_edge!(u,w) unless edge?(u,w)} + end + end; self + end + end # StrongComponens + + end # Graph +end # GRATR diff --git a/lib/puppet/gratr/undirected_graph.rb b/lib/puppet/gratr/undirected_graph.rb new file mode 100644 index 000000000..e96b0f351 --- /dev/null +++ b/lib/puppet/gratr/undirected_graph.rb @@ -0,0 +1,153 @@ +#-- +# Copyright (c) 2006 Shawn Patrick Garbett +# Copyright (c) 2002,2004,2005 by Horst Duchene +# +# Redistribution and use in source and binary forms, with or without modification, +# are permitted provided that the following conditions are met: +# +# * Redistributions of source code must retain the above copyright notice(s), +# this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright notice, +# this list of conditions and the following disclaimer in the documentation +# and/or other materials provided with the distribution. +# * Neither the name of the Shawn Garbett nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED +# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE +# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +#++ + + +require 'puppet/gratr/adjacency_graph' +require 'puppet/gratr/search' +require 'puppet/gratr/biconnected' +require 'puppet/gratr/comparability' +require 'set' + +module GRATR + class UndirectedGraph + include AdjacencyGraph + include Graph::Search + include Graph::Biconnected + include Graph::Comparability + + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? GRATR::Graph or p.kind_of? Array) + end if self.class == GRATR::UndirectedGraph + super(*params) + end + + # UndirectedGraph is by definition undirected, always returns false + def directed?() false; end + + # Redefine degree (default was sum) + def degree(v) in_degree(v); end + + # A vertex of an undirected graph is balanced by definition + def balanced?(v) true; end + + # UndirectedGraph uses UndirectedEdge for the edge class. + def edge_class() @parallel_edges ? GRATR::MultiUndirectedEdge : GRATR::UndirectedEdge; end + + def remove_edge!(u, v=nil) + unless u.kind_of? GRATR::Edge + raise ArgumentError if @parallel_edges + u = edge_class[u,v] + end + super(u.reverse) unless u.source == u.target + super(u) + end + + # A triangulated graph is an undirected perfect graph that every cycle of length greater than + # three possesses a chord. They have also been called chordal, rigid circuit, monotone transitive, + # and perfect elimination graphs. + # + # Implementation taken from Golumbic's, "Algorithmic Graph Theory and + # Perfect Graphs" pg. 90 + def triangulated? + a = Hash.new {|h,k| h[k]=Set.new}; sigma=lexicograph_bfs + inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc} + sigma[0..-2].each do |v| + x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] } + unless x.empty? + u = sigma[x.map {|y| inv_sigma[y]}.min] + a[u].merge(x - [u]) + end + return false unless a[v].all? {|z| adjacent?(v,z)} + end + true + end + + def chromatic_number + return triangulated_chromatic_number if triangulated? + raise NotImplementedError + end + + # An interval graph can have its vertices into one-to-one + # correspondence with a set of intervals F of a linearly ordered + # set (like the real line) such that two vertices are connected + # by an edge of G if and only if their corresponding intervals + # have nonempty intersection. + def interval?() triangulated? and complement.comparability?; end + + # A permutation diagram consists of n points on each of two parallel + # lines and n straight line segments matchin the points. The intersection + # graph of the line segments is called a permutation graph. + def permutation?() comparability? and complement.comparability?; end + + # An undirected graph is defined to be split if there is a partition + # V = S + K of its vertex set into a stable set S and a complete set K. + def split?() triangulated? and complement.triangulated?; end + + private + # Implementation taken from Golumbic's, "Algorithmic Graph Theory and + # Perfect Graphs" pg. 99 + def triangulated_chromatic_number + chi = 1; s= Hash.new {|h,k| h[k]=0} + sigma=lexicograph_bfs + inv_sigma = sigma.inject({}) {|acc,val| acc[val] = sigma.index(val); acc} + sigma.each do |v| + x = adjacent(v).select {|w| inv_sigma[v] < inv_sigma[w] } + unless x.empty? + u = sigma[x.map {|y| inv_sigma[y]}.min] + s[u] = [s[u], x.size-1].max + chi = [chi, x.size+1].max if s[v] < x.size + end + end; chi + end + + end # UndirectedGraph + + # This is a UndirectedGraph that allows for parallel edges, but does not + # allow loops + class UndirectedPseudoGraph < UndirectedGraph + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? Graph or p.kind_of? Array) + end + super(:parallel_edges, *params) + end + end + + # This is a UndirectedGraph that allows for parallel edges and loops + class UndirectedMultiGraph < UndirectedGraph + def initialize(*params) + raise ArgumentError if params.any? do |p| + !(p.kind_of? Graph or p.kind_of? Array) + end + super(:parallel_edges, :loops, *params) + end + end + + +end # GRATR diff --git a/lib/puppet/util/graph.rb b/lib/puppet/util/graph.rb new file mode 100644 index 000000000..c32d15cb4 --- /dev/null +++ b/lib/puppet/util/graph.rb @@ -0,0 +1,58 @@ +# Created by Luke Kanies on 2006-11-16. +# Copyright (c) 2006. All rights reserved. + +require 'puppet' +require 'puppet/gratr/digraph' +require 'puppet/gratr/import' +require 'puppet/gratr/dot' + +class GRATR::Digraph + # Determine all of the leaf nodes below a given vertex. + def leaves(vertex, type = :dfs) + tree = tree_from_vertex(vertex, type) + leaves = tree.keys.find_all { |c| adjacent(c, :direction => :out).empty? } + return leaves + end +end + +# A module that handles the small amount of graph stuff in Puppet. +module Puppet::Util::Graph + # Make a graph where each of our children gets converted to + # the receiving end of an edge. Call the same thing on all + # of our children, optionally using a block + def to_graph(graph = nil, &block) + # Allow our calling function to send in a graph, so that we + # can call this recursively with one graph. + graph ||= GRATR::Digraph.new + + self.each do |child| + unless block_given? and ! yield(child) + graph.add_edge!(self, child) + + if graph.cyclic? + raise Puppet::Error, "%s created a cyclic graph" % self + end + + if child.respond_to?(:to_graph) + child.to_graph(graph, &block) + end + end + end + + if graph.cyclic? + raise Puppet::Error, "%s created a cyclic graph" % self + end + + graph + end + + def to_jpg(graph = nil) + graph ||= to_graph + gv = graph.vertices + Dir.chdir("/Users/luke/Desktop/pics") do + graph.induced_subgraph(gv).write_to_graphic_file('jpg', 'graph') + end + end +end + +# $Id$ \ No newline at end of file diff --git a/test/util/graph.rb b/test/util/graph.rb new file mode 100755 index 000000000..0a331f0e9 --- /dev/null +++ b/test/util/graph.rb @@ -0,0 +1,135 @@ +#!/usr/bin/env ruby +# +# Created by Luke Kanies on 2006-11-16. +# Copyright (c) 2006. All rights reserved. + +$:.unshift("../lib").unshift("../../lib") if __FILE__ =~ /\.rb$/ + +require 'puppettest' +require 'puppet/util/graph' + +class TestUtilGraph < Test::Unit::TestCase + include PuppetTest + + class Container + include Puppet::Util::Graph + include Enumerable + attr_accessor :name + def each + @children.each do |c| yield c end + end + + def initialize(name, ary) + @name = name + @children = ary + end + + def push(*ary) + ary.each { |c| @children.push(c)} + end + + def to_s + @name + end + end + + def test_to_graph + children = %w{a b c d} + list = Container.new("yay", children) + + graph = nil + assert_nothing_raised do + graph = list.to_graph + end + + assert(graph.vertices.include?(list), "wtf?") + + ([list] + children).each do |thing| + assert(graph.vertex?(thing), "%s is not a vertex" % thing) + end + children.each do |child| + assert(graph.edge?(list, child), + "%s/%s was not added as an edge" % ["yay", child]) + end + end + + def test_recursive_to_graph + one = Container.new("one", %w{a b}) + + two = Container.new("two", ["c", "d"]) + + middle = Container.new("middle", ["e", "f", two]) + + top = Container.new("top", ["g", "h", middle, one]) + + graph = nil + assert_nothing_raised do + graph = top.to_graph + end + + (%w{a b c d e f g h} + [one, two, middle, top]).each do |v| + assert(graph.vertex?(v), "%s is not a vertex" % v) + end + + [one, two, middle, top].each do |con| + con.each do |child| + assert(graph.edge?(con, child), "%s/%s is not an edge" % [con, child]) + end + end + + top.to_jpg(graph) + + # Now make sure we correctly retrieve the leaves from each container + {top => %w{a b c d e f g h}, + one => %w{a b}, + two => %w{c d}, + middle => %w{c d e f}}.each do |cont, list| + leaves = nil + assert_nothing_raised do + leaves = graph.leaves(cont) + end + leaves = leaves.sort + assert_equal(list.sort, leaves.sort, + "Got incorrect leaf list for %s" % cont.name) + %w{a b c d e f g h}.each do |letter| + unless list.include?(letter) + assert(!leaves.include?(letter), + "incorrectly got %s as a leaf of %s" % + [letter, cont.to_s]) + end + end + end + end + + def test_to_graph_with_block + middle = Container.new "middle", ["c", "d", 3, 4] + top = Container.new "top", ["a", "b", middle, 1, 2] + + graph = nil + assert_nothing_raised() { + graph = top.to_graph { |c| c.is_a?(String) or c.is_a?(Container) } + } + + %w{a b c d}.each do |child| + assert(graph.vertex?(child), "%s was not added as a vertex" % child) + end + + [1, 2, 3, 4].each do |child| + assert(! graph.vertex?(child), "%s is a vertex" % child) + end + end + + def test_cyclic_graphs + one = Container.new "one", %w{a b} + two = Container.new "two", %w{c d} + + one.push(two) + two.push(one) + + assert_raise(Puppet::Error, "did not fail on cyclic graph") do + one.to_graph + end + end +end + +# $Id$ \ No newline at end of file