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
26 def initialize
27   @in_to = {}
28   @out_from = {}
29   @upstream_from = {}
30   @downstream_from = {}
31 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
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
add_relationship(source, target, label = nil) click to toggle source
    # 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_vertex(vertex) click to toggle source

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
adjacent(v, options = {}) click to toggle source

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() click to toggle source

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
dependencies(resource) click to toggle source

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
dependents(resource) click to toggle source
   # File lib/puppet/graph/simple_graph.rb
46 def dependents(resource)
47   vertex?(resource) ? downstream_from_vertex(resource).keys : []
48 end
direct_dependencies_of(v) click to toggle source
    # File lib/puppet/graph/simple_graph.rb
405 def direct_dependencies_of(v)
406   (@in_to[v] || {}).keys
407 end
direct_dependents_of(v) click to toggle source
    # File lib/puppet/graph/simple_graph.rb
391 def direct_dependents_of(v)
392   (@out_from[v] || {}).keys
393 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
51 def directed?
52   true
53 end
downstream_from_vertex(v) click to toggle source
    # 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
each_edge() { |e| ... } click to toggle source
    # 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
edge?(source, target) click to toggle source

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
edges() click to toggle source
    # File lib/puppet/graph/simple_graph.rb
327 def edges
328   @in_to.values.collect { |x| x.values }.flatten
329 end
edges_between(source, target) click to toggle source

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_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
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
initialize_from_hash(hash) click to toggle source
    # 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
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
56 def leaves(vertex, direction = :out)
57   tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? }
58 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
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
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
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
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
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_edge!(e) click to toggle source

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_vertex!(v) click to toggle source

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
report_cycles_in_graph() click to toggle source

@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
reversal() click to toggle source

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
size() click to toggle source

Return the size of the graph.

   # File lib/puppet/graph/simple_graph.rb
86 def size
87   vertices.size
88 end
stringify(s) click to toggle source
    # File lib/puppet/graph/simple_graph.rb
466 def stringify(s)
467   %("#{s.gsub('"', '\\"')}")
468 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
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
to_a() click to toggle source
   # File lib/puppet/graph/simple_graph.rb
90 def to_a
91   vertices
92 end
to_data_hash() click to toggle source
    # 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
to_dot(params={}) click to toggle source

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
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
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
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
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
upstream_from_vertex(v) click to toggle source
    # 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
vertex?(v) click to toggle source

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
vertices() click to toggle source

Return a list of all vertices.

    # File lib/puppet/graph/simple_graph.rb
293 def vertices
294   @in_to.keys
295 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
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
write_cycles_to_graph(cycles) click to toggle source
    # 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
write_graph(name) click to toggle source

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

multi_vertex_component?(component) click to toggle source
    # File lib/puppet/graph/simple_graph.rb
531 def multi_vertex_component?(component)
532   component.length > 1
533 end
single_vertex_referring_to_self?(component) click to toggle source
    # 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