class Puppet::Graph::SimpleGraph

A hopefully-faster graph class to replace the use of GRATR.

Attributes

use_new_yaml_format[RW]

Public Class Methods

new() click to toggle source

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
27 def initialize
28   @in_to = {}
29   @out_from = {}
30   @upstream_from = {}
31   @downstream_from = {}
32 end

Public Instance Methods

add_edge(e,*a) click to toggle source

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
301 def add_edge(e,*a)
302   return add_relationship(e,*a) unless a.empty?
303   e = Puppet::Relationship.from_data_hash(e) if e.is_a?(Hash)
304   @upstream_from.clear
305   @downstream_from.clear
306   add_vertex(e.source)
307   add_vertex(e.target)
308   # Avoid multiple lookups here. This code is performance critical
309   arr = (@in_to[e.target][e.source] ||= [])
310   arr << e unless arr.include?(e)
311   arr = (@out_from[e.source][e.target] ||= [])
312   arr << e unless arr.include?(e)
313 end

add_relationship(source, target, label = nil) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
315 def add_relationship(source, target, label = nil)
316   add_edge Puppet::Relationship.new(source, target, label)
317 end

add_vertex(vertex) click to toggle source

Add a new vertex to the graph.

    # File lib/puppet/graph/simple_graph.rb
274 def add_vertex(vertex)
275   @in_to[vertex]    ||= {}
276   @out_from[vertex] ||= {}
277 end

adjacent(v, options = {}) click to toggle source

Find adjacent edges.

    # File lib/puppet/graph/simple_graph.rb
348 def adjacent(v, options = {})
349   ns = (options[:direction] == :in) ? @in_to[v] : @out_from[v]
350   return [] unless ns
351   (options[:type] == :edges) ? ns.values.flatten : ns.keys
352 end

clear() click to toggle source

Clear our graph.

   # File lib/puppet/graph/simple_graph.rb
35 def clear
36   @in_to.clear
37   @out_from.clear
38   @upstream_from.clear
39   @downstream_from.clear
40 end

dependencies(resource) click to toggle source

Which resources the given resource depends on.

   # File lib/puppet/graph/simple_graph.rb
43 def dependencies(resource)
44   vertex?(resource) ? upstream_from_vertex(resource).keys : []
45 end

dependents(resource) click to toggle source

Which resources depend upon the given resource.

   # File lib/puppet/graph/simple_graph.rb
48 def dependents(resource)
49   vertex?(resource) ? downstream_from_vertex(resource).keys : []
50 end

direct_dependencies_of(v) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
407 def direct_dependencies_of(v)
408   (@in_to[v] || {}).keys
409 end

direct_dependents_of(v) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
393 def direct_dependents_of(v)
394   (@out_from[v] || {}).keys
395 end

directed?() click to toggle source

Whether our graph is directed. Always true. Used to produce dot files.

   # File lib/puppet/graph/simple_graph.rb
53 def directed?
54   true
55 end

downstream_from_vertex(v) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
383 def downstream_from_vertex(v)
384   return @downstream_from[v] if @downstream_from[v]
385   result = @downstream_from[v] = {}
386   @out_from[v].keys.each do |node|
387     result[node] = 1
388     result.update(downstream_from_vertex(node))
389   end
390   result
391 end

each_edge() { |e| ... } click to toggle source

    # File lib/puppet/graph/simple_graph.rb
333 def each_edge
334   @in_to.each { |t,ns| ns.each { |s,es| es.each { |e| yield e }}}
335 end

edge?(source, target) click to toggle source

Is there an edge between the two vertices?

    # File lib/puppet/graph/simple_graph.rb
325 def edge?(source, target)
326   vertex?(source) and vertex?(target) and @out_from[source][target]
327 end

edges() click to toggle source

    # File lib/puppet/graph/simple_graph.rb
329 def edges
330   @in_to.values.collect { |x| x.values }.flatten
331 end

edges_between(source, target) click to toggle source

Find all matching edges.

    # File lib/puppet/graph/simple_graph.rb
320 def edges_between(source, target)
321   (@out_from[source] || {})[target] || []
322 end

find_cycles_in_graph() click to toggle source

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
165 def find_cycles_in_graph
166   state = {
167     :number => 0, :index => {}, :lowlink => {}, :scc => [],
168     :stack => [], :seen => {}
169   }
170 
171   # we usually have a disconnected graph, must walk all possible roots
172   vertices.each do |vertex|
173     if ! state[:index][vertex] then
174       tarjan vertex, state
175     end
176   end
177 
178   # To provide consistent results to the user, given that a hash is never
179   # assured to return the same order, and given our graph processing is
180   # based on hash tables, we need to sort the cycles internally, as well as
181   # the set of cycles.
182   #
183   # Given we are in a failure state here, any extra cost is more or less
184   # irrelevant compared to the cost of a fix - which is on a human
185   # time-scale.
186   state[:scc].select do |component|
187     multi_vertex_component?(component) || single_vertex_referring_to_self?(component)
188   end.map do |component|
189     component.sort
190   end.sort
191 end

initialize_from_hash(hash) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
495 def initialize_from_hash(hash)
496   initialize
497   vertices = hash['vertices']
498   edges = hash['edges']
499   if vertices.is_a?(Hash)
500     # Support old (2.6) format
501     vertices = vertices.keys
502   end
503   vertices.each { |v| add_vertex(v) } unless vertices.nil?
504   edges.each { |e| add_edge(e) } unless edges.nil?
505 end

leaves(vertex, direction = :out) click to toggle source

Determine all of the leaf nodes below a given vertex.

   # File lib/puppet/graph/simple_graph.rb
58 def leaves(vertex, direction = :out)
59   tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? }
60 end

matching_edges(event, base = nil) click to toggle source

Collect all of the edges that the passed events match. Returns an array of edges.

   # File lib/puppet/graph/simple_graph.rb
64 def matching_edges(event, base = nil)
65   source = base || event.resource
66 
67   unless vertex?(source)
68     Puppet.warning _("Got an event from invalid vertex %{source}") % { source: source.ref }
69     return []
70   end
71   # Get all of the edges that this vertex should forward events
72   # to, which is the same thing as saying all edges directly below
73   # This vertex in the graph.
74   @out_from[source].values.flatten.find_all { |edge| edge.match?(event.name) }
75 end

path_between(f,t) click to toggle source

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
424 def path_between(f,t)
425   if f==t
426     []
427   elsif direct_dependents_of(f).include?(t)
428     [edges_between(f,t)]
429   elsif dependents(f).include?(t)
430     m = (dependents(f) & direct_dependencies_of(t)).first
431     path_between(f,m) + path_between(m,t)
432   else
433     nil
434   end
435 end

paths_in_cycle(cycle, max_paths = 1) click to toggle source

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
200 def paths_in_cycle(cycle, max_paths = 1)
201   #TRANSLATORS "negative or zero" refers to the count of paths
202   raise ArgumentError, _("negative or zero max_paths") if max_paths < 1
203 
204   # Calculate our filtered outbound vertex lists...
205   adj = {}
206   cycle.each do |vertex|
207     adj[vertex] = adjacent(vertex).select{|s| cycle.member? s}
208   end
209 
210   found = []
211 
212   # frame struct is vertex, [path]
213   stack = [[cycle.first, []]]
214   while frame = stack.shift do #rubocop:disable Lint/AssignmentInCondition
215     if frame[1].member?(frame[0]) then
216       found << frame[1] + [frame[0]]
217       break if found.length >= max_paths
218     else
219       adj[frame[0]].each do |to|
220         stack.push [to, frame[1] + [frame[0]]]
221       end
222     end
223   end
224 
225   return found.sort
226 end

remove_edge!(e) click to toggle source

Remove an edge from our graph.

    # File lib/puppet/graph/simple_graph.rb
338 def remove_edge!(e)
339   if edge?(e.source,e.target)
340     @upstream_from.clear
341     @downstream_from.clear
342     @in_to   [e.target].delete e.source if (@in_to   [e.target][e.source] -= [e]).empty?
343     @out_from[e.source].delete e.target if (@out_from[e.source][e.target] -= [e]).empty?
344   end
345 end

remove_vertex!(v) click to toggle source

Remove a vertex from the graph.

    # File lib/puppet/graph/simple_graph.rb
280 def remove_vertex!(v)
281   return unless vertex?(v)
282   @upstream_from.clear
283   @downstream_from.clear
284   (@in_to[v].values+@out_from[v].values).flatten.each { |e| remove_edge!(e) }
285   @in_to.delete(v)
286   @out_from.delete(v)
287 end

report_cycles_in_graph() click to toggle source

@return [Array] array of dependency cycles (arrays)

    # File lib/puppet/graph/simple_graph.rb
229 def report_cycles_in_graph
230   cycles = find_cycles_in_graph
231   number_of_cycles = cycles.length
232   return if number_of_cycles == 0
233 
234   message = n_("Found %{num} dependency cycle:\n", "Found %{num} dependency cycles:\n", number_of_cycles) % { num: number_of_cycles }
235 
236   cycles.each do |cycle|
237     paths = paths_in_cycle(cycle)
238     message += paths.map{ |path| '(' + path.join(' => ') + ')'}.join('\n') + '\n'
239   end
240 
241   if Puppet[:graph] then
242     filename = write_cycles_to_graph(cycles)
243     message += _("Cycle graph written to %{filename}.") % { filename: filename }
244   else
245     #TRANSLATORS '--graph' refers to a command line option and OmniGraffle and GraphViz are program names and should not be translated
246     message += _("Try the '--graph' option and opening the resulting '.dot' file in OmniGraffle or GraphViz")
247   end
248   Puppet.err(message)
249   cycles
250 end

reversal() click to toggle source

Return a reversed version of this graph.

   # File lib/puppet/graph/simple_graph.rb
78 def reversal
79   result = self.class.new
80   vertices.each { |vertex| result.add_vertex(vertex) }
81   edges.each do |edge|
82     result.add_edge edge.class.new(edge.target, edge.source, edge.label)
83   end
84   result
85 end

size() click to toggle source

Return the size of the graph.

   # File lib/puppet/graph/simple_graph.rb
88 def size
89   vertices.size
90 end

stringify(s) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
468 def stringify(s)
469   %("#{s.gsub('"', '\\"')}")
470 end

tarjan(root, s) click to toggle source

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
103 def tarjan(root, s)
104   # initialize the recursion stack we use to work around the nasty lack of a
105   # decent Ruby stack.
106   recur = [{ :node => root }]
107 
108   while not recur.empty? do
109     frame = recur.last
110     vertex = frame[:node]
111 
112     case frame[:step]
113     when nil then
114       s[:index][vertex]   = s[:number]
115       s[:lowlink][vertex] = s[:number]
116       s[:number]          = s[:number] + 1
117 
118       s[:stack].push(vertex)
119       s[:seen][vertex] = true
120 
121       frame[:children] = adjacent(vertex)
122       frame[:step]     = :children
123 
124     when :children then
125       if frame[:children].length > 0 then
126         child = frame[:children].shift
127         if ! s[:index][child] then
128           # Never seen, need to recurse.
129           frame[:step] = :after_recursion
130           frame[:child] = child
131           recur.push({ :node => child })
132         elsif s[:seen][child] then
133           s[:lowlink][vertex] = [s[:lowlink][vertex], s[:index][child]].min
134         end
135       else
136         if s[:lowlink][vertex] == s[:index][vertex] then
137           this_scc = []
138           loop do
139             top = s[:stack].pop
140             s[:seen][top] = false
141             this_scc << top
142             break if top == vertex
143           end
144           s[:scc] << this_scc
145         end
146         recur.pop               # done with this node, finally.
147       end
148 
149     when :after_recursion then
150       s[:lowlink][vertex] = [s[:lowlink][vertex], s[:lowlink][frame[:child]]].min
151       frame[:step] = :children
152 
153     else
154       fail "#{frame[:step]} is an unknown step"
155     end
156   end
157 end

to_a() click to toggle source

   # File lib/puppet/graph/simple_graph.rb
92 def to_a
93   vertices
94 end

to_data_hash() click to toggle source

    # File lib/puppet/graph/simple_graph.rb
507 def to_data_hash
508   hash = { 'edges' => edges.map(&:to_data_hash) }
509   hash['vertices'] = if self.class.use_new_yaml_format
510     vertices
511   else
512     # Represented in YAML using the old (version 2.6) format.
513     result = {}
514     vertices.each do |vertex|
515       adjacencies = {}
516       [:in, :out].each do |direction|
517         direction_hash = {}
518         adjacencies[direction.to_s] = direction_hash
519         adjacent(vertex, :direction => direction, :type => :edges).each do |edge|
520           other_vertex = direction == :in ? edge.source : edge.target
521           (direction_hash[other_vertex.to_s] ||= []) << edge
522         end
523         direction_hash.each_pair { |key, edges| direction_hash[key] = edges.uniq.map(&:to_data_hash) }
524       end
525       vname = vertex.to_s
526       result[vname] = { 'adjacencies' => adjacencies, 'vertex' => vname }
527     end
528     result
529   end
530   hash
531 end

to_dot(params={}) click to toggle source

Output the dot format as a string

    # File lib/puppet/graph/simple_graph.rb
473 def to_dot(params={}) to_dot_graph(params).to_s; end

to_dot_graph(params = {}) click to toggle source

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
443 def to_dot_graph(params = {})
444   params['name'] ||= self.class.name.tr(':','_')
445   fontsize   = params['fontsize'] ? params['fontsize'] : '8'
446   graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
447   edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge
448   vertices.each do |v|
449     name = v.ref
450     params = {'name'     => stringify(name),
451       'fontsize' => fontsize,
452       'label'    => name}
453     v_label = v.ref
454     params.merge!(v_label) if v_label and v_label.kind_of? Hash
455     graph << DOT::DOTNode.new(params)
456   end
457   edges.each do |e|
458     params = {'from'     => stringify(e.source.ref),
459       'to'       => stringify(e.target.ref),
460       'fontsize' => fontsize }
461     e_label = e.ref
462     params.merge!(e_label) if e_label and e_label.kind_of? Hash
463     graph << edge_klass.new(params)
464   end
465   graph
466 end

tree_from_vertex(start, direction = :out) click to toggle source

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
375 def tree_from_vertex(start, direction = :out)
376   predecessor={}
377   walk(start, direction) do |parent, child|
378     predecessor[child] = parent
379   end
380   predecessor
381 end

upstream_from_vertex(v) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
397 def upstream_from_vertex(v)
398   return @upstream_from[v] if @upstream_from[v]
399   result = @upstream_from[v] = {}
400   @in_to[v].keys.each do |node|
401     result[node] = 1
402     result.update(upstream_from_vertex(node))
403   end
404   result
405 end

vertex?(v) click to toggle source

Test whether a given vertex is in the graph.

    # File lib/puppet/graph/simple_graph.rb
290 def vertex?(v)
291   @in_to.include?(v)
292 end

vertices() click to toggle source

Return a list of all vertices.

    # File lib/puppet/graph/simple_graph.rb
295 def vertices
296   @in_to.keys
297 end

walk(source, direction) { |node, target| ... } click to toggle source

Just walk the tree and pass each edge.

    # File lib/puppet/graph/simple_graph.rb
355 def walk(source, direction)
356   # Use an iterative, breadth-first traversal of the graph. One could do
357   # this recursively, but Ruby's slow function calls and even slower
358   # recursion make the shorter, recursive algorithm cost-prohibitive.
359   stack = [source]
360   seen = Set.new
361   until stack.empty?
362     node = stack.shift
363     next if seen.member? node
364     connected = adjacent(node, :direction => direction)
365     connected.each do |target|
366       yield node, target
367     end
368     stack.concat(connected)
369     seen << node
370   end
371 end

write_cycles_to_graph(cycles) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
252 def write_cycles_to_graph(cycles)
253   # This does not use the DOT graph library, just writes the content
254   # directly.  Given the complexity of this, there didn't seem much point
255   # using a heavy library to generate exactly the same content. --daniel 2011-01-27
256   graph = ["digraph Resource_Cycles {"]
257   graph << '  label = "Resource Cycles"'
258 
259   cycles.each do |cycle|
260     paths_in_cycle(cycle, 10).each do |path|
261       graph << path.map { |v| '"' + v.to_s.gsub(/"/, '\\"') + '"' }.join(" -> ")
262     end
263   end
264 
265   graph << '}'
266 
267   filename = File.join(Puppet[:graphdir], "cycles.dot")
268   # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html
269   File.open(filename, "w:UTF-8") { |f| f.puts graph }
270   return filename
271 end

write_graph(name) click to toggle source

Produce the graph files if requested.

    # File lib/puppet/graph/simple_graph.rb
476 def write_graph(name)
477   return unless Puppet[:graph]
478 
479   file = File.join(Puppet[:graphdir], "#{name}.dot")
480   # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html
481   File.open(file, "w:UTF-8") { |f|
482     f.puts to_dot("name" => name.to_s.capitalize)
483   }
484 end

Private Instance Methods

multi_vertex_component?(component) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
533 def multi_vertex_component?(component)
534   component.length > 1
535 end

single_vertex_referring_to_self?(component) click to toggle source

    # File lib/puppet/graph/simple_graph.rb
538 def single_vertex_referring_to_self?(component)
539   if component.length == 1
540     vertex = component[0]
541     adjacent(vertex).include?(vertex)
542   else
543     false
544   end
545 end