class Puppet::Graph::SimpleGraph
A hopefully-faster graph class to replace the use of GRATR.
Attributes
Public Class Methods
All public methods of this class must maintain (assume ^ ensure) the following invariants, where “=~=” means equiv. up to order:
@in_to.keys =~= @out_to.keys =~= all vertices @in_to.values.collect { |x| x.values }.flatten =~= @out_from.values.collect { |x| x.values }.flatten =~= all edges @in_to[v1][v2] =~= @out_from[v2][v1] =~= all edges from v1 to v2 @in_to [v].keys =~= vertices with edges leading to v @out_from[v].keys =~= vertices with edges leading from v no operation may shed reference loops (for gc) recursive operation must scale with the depth of the spanning trees, or better (e.g. no recursion over the set of all vertices, etc.)
This class is intended to be used with DAGs. However, if the graph has a cycle, it will not cause non-termination of any of the algorithms.
# File lib/puppet/graph/simple_graph.rb 26 def initialize 27 @in_to = {} 28 @out_from = {} 29 @upstream_from = {} 30 @downstream_from = {} 31 end
Public Instance Methods
Add a new edge. The graph user has to create the edge instance, since they have to specify what kind of edge it is.
# File lib/puppet/graph/simple_graph.rb 299 def add_edge(e,*a) 300 return add_relationship(e,*a) unless a.empty? 301 e = Puppet::Relationship.from_data_hash(e) if e.is_a?(Hash) 302 @upstream_from.clear 303 @downstream_from.clear 304 add_vertex(e.source) 305 add_vertex(e.target) 306 # Avoid multiple lookups here. This code is performance critical 307 arr = (@in_to[e.target][e.source] ||= []) 308 arr << e unless arr.include?(e) 309 arr = (@out_from[e.source][e.target] ||= []) 310 arr << e unless arr.include?(e) 311 end
# File lib/puppet/graph/simple_graph.rb 313 def add_relationship(source, target, label = nil) 314 add_edge Puppet::Relationship.new(source, target, label) 315 end
Add a new vertex to the graph.
# File lib/puppet/graph/simple_graph.rb 272 def add_vertex(vertex) 273 @in_to[vertex] ||= {} 274 @out_from[vertex] ||= {} 275 end
Find adjacent edges.
# File lib/puppet/graph/simple_graph.rb 346 def adjacent(v, options = {}) 347 ns = (options[:direction] == :in) ? @in_to[v] : @out_from[v] 348 return [] unless ns 349 (options[:type] == :edges) ? ns.values.flatten : ns.keys 350 end
Clear our graph.
# File lib/puppet/graph/simple_graph.rb 34 def clear 35 @in_to.clear 36 @out_from.clear 37 @upstream_from.clear 38 @downstream_from.clear 39 end
Which resources depend upon the given resource.
# File lib/puppet/graph/simple_graph.rb 42 def dependencies(resource) 43 vertex?(resource) ? upstream_from_vertex(resource).keys : [] 44 end
# File lib/puppet/graph/simple_graph.rb 46 def dependents(resource) 47 vertex?(resource) ? downstream_from_vertex(resource).keys : [] 48 end
# File lib/puppet/graph/simple_graph.rb 405 def direct_dependencies_of(v) 406 (@in_to[v] || {}).keys 407 end
# File lib/puppet/graph/simple_graph.rb 391 def direct_dependents_of(v) 392 (@out_from[v] || {}).keys 393 end
Whether our graph is directed. Always true. Used to produce dot files.
# File lib/puppet/graph/simple_graph.rb 51 def directed? 52 true 53 end
# File lib/puppet/graph/simple_graph.rb 381 def downstream_from_vertex(v) 382 return @downstream_from[v] if @downstream_from[v] 383 result = @downstream_from[v] = {} 384 @out_from[v].keys.each do |node| 385 result[node] = 1 386 result.update(downstream_from_vertex(node)) 387 end 388 result 389 end
# File lib/puppet/graph/simple_graph.rb 331 def each_edge 332 @in_to.each { |t,ns| ns.each { |s,es| es.each { |e| yield e }}} 333 end
Is there an edge between the two vertices?
# File lib/puppet/graph/simple_graph.rb 323 def edge?(source, target) 324 vertex?(source) and vertex?(target) and @out_from[source][target] 325 end
# File lib/puppet/graph/simple_graph.rb 327 def edges 328 @in_to.values.collect { |x| x.values }.flatten 329 end
Find all matching edges.
# File lib/puppet/graph/simple_graph.rb 318 def edges_between(source, target) 319 (@out_from[source] || {})[target] || [] 320 end
Find all cycles in the graph by detecting all the strongly connected components, then eliminating everything with a size of one as uninteresting - which it is, because it can't be a cycle. :)
This has an unhealthy relationship with the 'tarjan' method above, which it uses to implement the detection of strongly connected components.
# File lib/puppet/graph/simple_graph.rb 163 def find_cycles_in_graph 164 state = { 165 :number => 0, :index => {}, :lowlink => {}, :scc => [], 166 :stack => [], :seen => {} 167 } 168 169 # we usually have a disconnected graph, must walk all possible roots 170 vertices.each do |vertex| 171 if ! state[:index][vertex] then 172 tarjan vertex, state 173 end 174 end 175 176 # To provide consistent results to the user, given that a hash is never 177 # assured to return the same order, and given our graph processing is 178 # based on hash tables, we need to sort the cycles internally, as well as 179 # the set of cycles. 180 # 181 # Given we are in a failure state here, any extra cost is more or less 182 # irrelevant compared to the cost of a fix - which is on a human 183 # time-scale. 184 state[:scc].select do |component| 185 multi_vertex_component?(component) || single_vertex_referring_to_self?(component) 186 end.map do |component| 187 component.sort 188 end.sort 189 end
# File lib/puppet/graph/simple_graph.rb 493 def initialize_from_hash(hash) 494 initialize 495 vertices = hash['vertices'] 496 edges = hash['edges'] 497 if vertices.is_a?(Hash) 498 # Support old (2.6) format 499 vertices = vertices.keys 500 end 501 vertices.each { |v| add_vertex(v) } unless vertices.nil? 502 edges.each { |e| add_edge(e) } unless edges.nil? 503 end
Determine all of the leaf nodes below a given vertex.
# File lib/puppet/graph/simple_graph.rb 56 def leaves(vertex, direction = :out) 57 tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? } 58 end
Collect all of the edges that the passed events match. Returns an array of edges.
# File lib/puppet/graph/simple_graph.rb 62 def matching_edges(event, base = nil) 63 source = base || event.resource 64 65 unless vertex?(source) 66 Puppet.warning _("Got an event from invalid vertex %{source}") % { source: source.ref } 67 return [] 68 end 69 # Get all of the edges that this vertex should forward events 70 # to, which is the same thing as saying all edges directly below 71 # This vertex in the graph. 72 @out_from[source].values.flatten.find_all { |edge| edge.match?(event.name) } 73 end
Return an array of the edge-sets between a series of n+1 vertices (f=v0,v1,v2…t=vn)
connecting the two given vertices. The ith edge set is an array containing all the edges between v(i) and v(i+1); these are (by definition) never empty. * if f == t, the list is empty * if they are adjacent the result is an array consisting of a single array (the edges from f to t) * and so on by induction on a vertex m between them * if there is no path from f to t, the result is nil
This implementation is not particularly efficient; it's used in testing where clarity
is more important than last-mile efficiency.
# File lib/puppet/graph/simple_graph.rb 422 def path_between(f,t) 423 if f==t 424 [] 425 elsif direct_dependents_of(f).include?(t) 426 [edges_between(f,t)] 427 elsif dependents(f).include?(t) 428 m = (dependents(f) & direct_dependencies_of(t)).first 429 path_between(f,m) + path_between(m,t) 430 else 431 nil 432 end 433 end
Perform a BFS on the sub graph representing the cycle, with a view to generating a sufficient set of paths to report the cycle meaningfully, and ideally usefully, for the end user.
BFS is preferred because it will generally report the shortest paths through the graph first, which are more likely to be interesting to the user. I think; it would be interesting to verify that. –daniel 2011-01-23
# File lib/puppet/graph/simple_graph.rb 198 def paths_in_cycle(cycle, max_paths = 1) 199 #TRANSLATORS "negative or zero" refers to the count of paths 200 raise ArgumentError, _("negative or zero max_paths") if max_paths < 1 201 202 # Calculate our filtered outbound vertex lists... 203 adj = {} 204 cycle.each do |vertex| 205 adj[vertex] = adjacent(vertex).select{|s| cycle.member? s} 206 end 207 208 found = [] 209 210 # frame struct is vertex, [path] 211 stack = [[cycle.first, []]] 212 while frame = stack.shift do #rubocop:disable Lint/AssignmentInCondition 213 if frame[1].member?(frame[0]) then 214 found << frame[1] + [frame[0]] 215 break if found.length >= max_paths 216 else 217 adj[frame[0]].each do |to| 218 stack.push [to, frame[1] + [frame[0]]] 219 end 220 end 221 end 222 223 return found.sort 224 end
Remove an edge from our graph.
# File lib/puppet/graph/simple_graph.rb 336 def remove_edge!(e) 337 if edge?(e.source,e.target) 338 @upstream_from.clear 339 @downstream_from.clear 340 @in_to [e.target].delete e.source if (@in_to [e.target][e.source] -= [e]).empty? 341 @out_from[e.source].delete e.target if (@out_from[e.source][e.target] -= [e]).empty? 342 end 343 end
Remove a vertex from the graph.
# File lib/puppet/graph/simple_graph.rb 278 def remove_vertex!(v) 279 return unless vertex?(v) 280 @upstream_from.clear 281 @downstream_from.clear 282 (@in_to[v].values+@out_from[v].values).flatten.each { |e| remove_edge!(e) } 283 @in_to.delete(v) 284 @out_from.delete(v) 285 end
@return [Array] array of dependency cycles (arrays)
# File lib/puppet/graph/simple_graph.rb 227 def report_cycles_in_graph 228 cycles = find_cycles_in_graph 229 number_of_cycles = cycles.length 230 return if number_of_cycles == 0 231 232 message = n_("Found %{num} dependency cycle:\n", "Found %{num} dependency cycles:\n", number_of_cycles) % { num: number_of_cycles } 233 234 cycles.each do |cycle| 235 paths = paths_in_cycle(cycle) 236 message += paths.map{ |path| '(' + path.join(' => ') + ')'}.join('\n') + '\n' 237 end 238 239 if Puppet[:graph] then 240 filename = write_cycles_to_graph(cycles) 241 message += _("Cycle graph written to %{filename}.") % { filename: filename } 242 else 243 #TRANSLATORS '--graph' refers to a command line option and OmniGraffle and GraphViz are program names and should not be translated 244 message += _("Try the '--graph' option and opening the resulting '.dot' file in OmniGraffle or GraphViz") 245 end 246 Puppet.err(message) 247 cycles 248 end
Return a reversed version of this graph.
# File lib/puppet/graph/simple_graph.rb 76 def reversal 77 result = self.class.new 78 vertices.each { |vertex| result.add_vertex(vertex) } 79 edges.each do |edge| 80 result.add_edge edge.class.new(edge.target, edge.source, edge.label) 81 end 82 result 83 end
Return the size of the graph.
# File lib/puppet/graph/simple_graph.rb 86 def size 87 vertices.size 88 end
# File lib/puppet/graph/simple_graph.rb 466 def stringify(s) 467 %("#{s.gsub('"', '\\"')}") 468 end
This is a simple implementation of Tarjan's algorithm to find strongly connected components in the graph; this is a fairly ugly implementation, because I can't just decorate the vertices themselves.
This method has an unhealthy relationship with the find_cycles_in_graph
method below, which contains the knowledge of how the state object is maintained.
# File lib/puppet/graph/simple_graph.rb 101 def tarjan(root, s) 102 # initialize the recursion stack we use to work around the nasty lack of a 103 # decent Ruby stack. 104 recur = [{ :node => root }] 105 106 while not recur.empty? do 107 frame = recur.last 108 vertex = frame[:node] 109 110 case frame[:step] 111 when nil then 112 s[:index][vertex] = s[:number] 113 s[:lowlink][vertex] = s[:number] 114 s[:number] = s[:number] + 1 115 116 s[:stack].push(vertex) 117 s[:seen][vertex] = true 118 119 frame[:children] = adjacent(vertex) 120 frame[:step] = :children 121 122 when :children then 123 if frame[:children].length > 0 then 124 child = frame[:children].shift 125 if ! s[:index][child] then 126 # Never seen, need to recurse. 127 frame[:step] = :after_recursion 128 frame[:child] = child 129 recur.push({ :node => child }) 130 elsif s[:seen][child] then 131 s[:lowlink][vertex] = [s[:lowlink][vertex], s[:index][child]].min 132 end 133 else 134 if s[:lowlink][vertex] == s[:index][vertex] then 135 this_scc = [] 136 loop do 137 top = s[:stack].pop 138 s[:seen][top] = false 139 this_scc << top 140 break if top == vertex 141 end 142 s[:scc] << this_scc 143 end 144 recur.pop # done with this node, finally. 145 end 146 147 when :after_recursion then 148 s[:lowlink][vertex] = [s[:lowlink][vertex], s[:lowlink][frame[:child]]].min 149 frame[:step] = :children 150 151 else 152 fail "#{frame[:step]} is an unknown step" 153 end 154 end 155 end
# File lib/puppet/graph/simple_graph.rb 90 def to_a 91 vertices 92 end
# File lib/puppet/graph/simple_graph.rb 505 def to_data_hash 506 hash = { 'edges' => edges.map(&:to_data_hash) } 507 hash['vertices'] = if self.class.use_new_yaml_format 508 vertices 509 else 510 # Represented in YAML using the old (version 2.6) format. 511 result = {} 512 vertices.each do |vertex| 513 adjacencies = {} 514 [:in, :out].each do |direction| 515 direction_hash = {} 516 adjacencies[direction.to_s] = direction_hash 517 adjacent(vertex, :direction => direction, :type => :edges).each do |edge| 518 other_vertex = direction == :in ? edge.source : edge.target 519 (direction_hash[other_vertex.to_s] ||= []) << edge 520 end 521 direction_hash.each_pair { |key, edges| direction_hash[key] = edges.uniq.map(&:to_data_hash) } 522 end 523 vname = vertex.to_s 524 result[vname] = { 'adjacencies' => adjacencies, 'vertex' => vname } 525 end 526 result 527 end 528 hash 529 end
Output the dot format as a string
# File lib/puppet/graph/simple_graph.rb 471 def to_dot(params={}) to_dot_graph(params).to_s; end
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.
# File lib/puppet/graph/simple_graph.rb 441 def to_dot_graph(params = {}) 442 params['name'] ||= self.class.name.tr(':','_') 443 fontsize = params['fontsize'] ? params['fontsize'] : '8' 444 graph = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params) 445 edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge 446 vertices.each do |v| 447 name = v.ref 448 params = {'name' => stringify(name), 449 'fontsize' => fontsize, 450 'label' => name} 451 v_label = v.ref 452 params.merge!(v_label) if v_label and v_label.kind_of? Hash 453 graph << DOT::DOTNode.new(params) 454 end 455 edges.each do |e| 456 params = {'from' => stringify(e.source.ref), 457 'to' => stringify(e.target.ref), 458 'fontsize' => fontsize } 459 e_label = e.ref 460 params.merge!(e_label) if e_label and e_label.kind_of? Hash 461 graph << edge_klass.new(params) 462 end 463 graph 464 end
A different way of walking a tree, and a much faster way than the one that comes with GRATR.
# File lib/puppet/graph/simple_graph.rb 373 def tree_from_vertex(start, direction = :out) 374 predecessor={} 375 walk(start, direction) do |parent, child| 376 predecessor[child] = parent 377 end 378 predecessor 379 end
# File lib/puppet/graph/simple_graph.rb 395 def upstream_from_vertex(v) 396 return @upstream_from[v] if @upstream_from[v] 397 result = @upstream_from[v] = {} 398 @in_to[v].keys.each do |node| 399 result[node] = 1 400 result.update(upstream_from_vertex(node)) 401 end 402 result 403 end
Test whether a given vertex is in the graph.
# File lib/puppet/graph/simple_graph.rb 288 def vertex?(v) 289 @in_to.include?(v) 290 end
Return a list of all vertices.
# File lib/puppet/graph/simple_graph.rb 293 def vertices 294 @in_to.keys 295 end
Just walk the tree and pass each edge.
# File lib/puppet/graph/simple_graph.rb 353 def walk(source, direction) 354 # Use an iterative, breadth-first traversal of the graph. One could do 355 # this recursively, but Ruby's slow function calls and even slower 356 # recursion make the shorter, recursive algorithm cost-prohibitive. 357 stack = [source] 358 seen = Set.new 359 until stack.empty? 360 node = stack.shift 361 next if seen.member? node 362 connected = adjacent(node, :direction => direction) 363 connected.each do |target| 364 yield node, target 365 end 366 stack.concat(connected) 367 seen << node 368 end 369 end
# File lib/puppet/graph/simple_graph.rb 250 def write_cycles_to_graph(cycles) 251 # This does not use the DOT graph library, just writes the content 252 # directly. Given the complexity of this, there didn't seem much point 253 # using a heavy library to generate exactly the same content. --daniel 2011-01-27 254 graph = ["digraph Resource_Cycles {"] 255 graph << ' label = "Resource Cycles"' 256 257 cycles.each do |cycle| 258 paths_in_cycle(cycle, 10).each do |path| 259 graph << path.map { |v| '"' + v.to_s.gsub(/"/, '\\"') + '"' }.join(" -> ") 260 end 261 end 262 263 graph << '}' 264 265 filename = File.join(Puppet[:graphdir], "cycles.dot") 266 # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html 267 File.open(filename, "w:UTF-8") { |f| f.puts graph } 268 return filename 269 end
Produce the graph files if requested.
# File lib/puppet/graph/simple_graph.rb 474 def write_graph(name) 475 return unless Puppet[:graph] 476 477 file = File.join(Puppet[:graphdir], "#{name}.dot") 478 # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html 479 File.open(file, "w:UTF-8") { |f| 480 f.puts to_dot("name" => name.to_s.capitalize) 481 } 482 end
Private Instance Methods
# File lib/puppet/graph/simple_graph.rb 531 def multi_vertex_component?(component) 532 component.length > 1 533 end
# File lib/puppet/graph/simple_graph.rb 536 def single_vertex_referring_to_self?(component) 537 if component.length == 1 538 vertex = component[0] 539 adjacent(vertex).include?(vertex) 540 else 541 false 542 end 543 end