Class: Puppet::Graph::SimpleGraph

Inherits:
Object
  • Object
show all
Includes:
Util::PsychSupport
Defined in:
lib/puppet/graph/simple_graph.rb

Overview

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

Direct Known Subclasses

RelationshipGraph, Resource::Catalog

Class Attribute Summary collapse

Instance Method Summary collapse

Methods included from Util::PsychSupport

#encode_with, #init_with

Constructor Details

#initialize ⇒ SimpleGraph

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.



28
29
30
31
32
33
 
# File 'lib/puppet/graph/simple_graph.rb', line 28

def initialize
  @in_to = {}
  @out_from = {}
  @upstream_from = {}
  @downstream_from = {}
end

Class Attribute Details

.use_new_yaml_format ⇒ Object

Returns the value of attribute use_new_yaml_format.



496
497
498
 
# File 'lib/puppet/graph/simple_graph.rb', line 496

def use_new_yaml_format
  @use_new_yaml_format
end

Instance Method Details

#add_edge(e, *a) ⇒ Object

Add a new edge. The graph user has to create the edge instance, since they have to specify what kind of edge it is.



301
302
303
304
305
306
307
308
309
310
311
312
313
314
 
# File 'lib/puppet/graph/simple_graph.rb', line 301

def add_edge(e, *a)
  return add_relationship(e, *a) unless a.empty?

  e = Puppet::Relationship.from_data_hash(e) if e.is_a?(Hash)
  @upstream_from.clear
  @downstream_from.clear
  add_vertex(e.source)
  add_vertex(e.target)
  # Avoid multiple lookups here. This code is performance critical
  arr = (@in_to[e.target][e.source] ||= [])
  arr << e unless arr.include?(e)
  arr = (@out_from[e.source][e.target] ||= [])
  arr << e unless arr.include?(e)
end

#add_relationship(source, target, label = nil) ⇒ Object 



316
317
318
 
# File 'lib/puppet/graph/simple_graph.rb', line 316

def add_relationship(source, target, label = nil)
  add_edge Puppet::Relationship.new(source, target, label)
end

#add_vertex(vertex) ⇒ Object

Add a new vertex to the graph.



273
274
275
276
 
# File 'lib/puppet/graph/simple_graph.rb', line 273

def add_vertex(vertex)
  @in_to[vertex]    ||= {}
  @out_from[vertex] ||= {}
end

#adjacent(v, options = {}) ⇒ Object

Find adjacent edges.



349
350
351
352
353
354
 
# File 'lib/puppet/graph/simple_graph.rb', line 349

def adjacent(v, options = {})
  ns = (options[:direction] == :in) ? @in_to[v] : @out_from[v]
  return [] unless ns

  (options[:type] == :edges) ? ns.values.flatten : ns.keys
end

#clear ⇒ Object

Clear our graph.



36
37
38
39
40
41
 
# File 'lib/puppet/graph/simple_graph.rb', line 36

def clear
  @in_to.clear
  @out_from.clear
  @upstream_from.clear
  @downstream_from.clear
end

#dependencies(resource) ⇒ Object

Which resources the given resource depends on.



44
45
46
 
# File 'lib/puppet/graph/simple_graph.rb', line 44

def dependencies(resource)
  vertex?(resource) ? upstream_from_vertex(resource).keys : []
end

#dependents(resource) ⇒ Object

Which resources depend upon the given resource.



49
50
51
 
# File 'lib/puppet/graph/simple_graph.rb', line 49

def dependents(resource)
  vertex?(resource) ? downstream_from_vertex(resource).keys : []
end

#direct_dependencies_of(v) ⇒ Object 



412
413
414
 
# File 'lib/puppet/graph/simple_graph.rb', line 412

def direct_dependencies_of(v)
  (@in_to[v] || {}).keys
end

#direct_dependents_of(v) ⇒ Object 



397
398
399
 
# File 'lib/puppet/graph/simple_graph.rb', line 397

def direct_dependents_of(v)
  (@out_from[v] || {}).keys
end

#directed? ⇒ Boolean

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

Returns:

  • (Boolean) 


54
55
56
 
# File 'lib/puppet/graph/simple_graph.rb', line 54

def directed?
  true
end

#downstream_from_vertex(v) ⇒ Object 



386
387
388
389
390
391
392
393
394
395
 
# File 'lib/puppet/graph/simple_graph.rb', line 386

def downstream_from_vertex(v)
  return @downstream_from[v] if @downstream_from[v]

  result = @downstream_from[v] = {}
  @out_from[v].keys.each do |node|
    result[node] = 1
    result.update(downstream_from_vertex(node))
  end
  result
end

#each_edge ⇒ Object 



334
335
336
 
# File 'lib/puppet/graph/simple_graph.rb', line 334

def each_edge
  @in_to.each { |_t, ns| ns.each { |_s, es| es.each { |e| yield e } } }
end

#edge?(source, target) ⇒ Boolean

Is there an edge between the two vertices?

Returns:

  • (Boolean) 


326
327
328
 
# File 'lib/puppet/graph/simple_graph.rb', line 326

def edge?(source, target)
  vertex?(source) and vertex?(target) and @out_from[source][target]
end

#edges ⇒ Object 



330
331
332
 
# File 'lib/puppet/graph/simple_graph.rb', line 330

def edges
  @in_to.values.collect(&:values).flatten
end

#edges_between(source, target) ⇒ Object

Find all matching edges.



321
322
323
 
# File 'lib/puppet/graph/simple_graph.rb', line 321

def edges_between(source, target)
  (@out_from[source] || {})[target] || []
end

#find_cycles_in_graph ⇒ Object

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.



166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/puppet/graph/simple_graph.rb', line 166

def find_cycles_in_graph
  state = {
    :number => 0, :index => {}, :lowlink => {}, :scc => [],
    :stack => [], :seen => {}
  }

  # we usually have a disconnected graph, must walk all possible roots
  vertices.each do |vertex|
    unless state[:index][vertex] then
      tarjan vertex, state
    end
  end

  # To provide consistent results to the user, given that a hash is never
  # assured to return the same order, and given our graph processing is
  # based on hash tables, we need to sort the cycles internally, as well as
  # the set of cycles.
  #
  # Given we are in a failure state here, any extra cost is more or less
  # irrelevant compared to the cost of a fix - which is on a human
  # time-scale.
  state[:scc].select do |component|
    multi_vertex_component?(component) || single_vertex_referring_to_self?(component)
  end.map(&:sort).sort
end

#initialize_from_hash(hash) ⇒ Object 



500
501
502
503
504
505
506
507
508
509
510
 
# File 'lib/puppet/graph/simple_graph.rb', line 500

def initialize_from_hash(hash)
  initialize
  vertices = hash['vertices']
  edges = hash['edges']
  if vertices.is_a?(Hash)
    # Support old (2.6) format
    vertices = vertices.keys
  end
  vertices.each { |v| add_vertex(v) } unless vertices.nil?
  edges.each { |e| add_edge(e) } unless edges.nil?
end

#leaves(vertex, direction = :out) ⇒ Object

Determine all of the leaf nodes below a given vertex.



59
60
61
 
# File 'lib/puppet/graph/simple_graph.rb', line 59

def leaves(vertex, direction = :out)
  tree_from_vertex(vertex, direction).keys.find_all { |c| adjacent(c, :direction => direction).empty? }
end

#matching_edges(event, base = nil) ⇒ Object

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



65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/puppet/graph/simple_graph.rb', line 65

def matching_edges(event, base = nil)
  source = base || event.resource

  unless vertex?(source)
    Puppet.warning _("Got an event from invalid vertex %{source}") % { source: source.ref }
    return []
  end
  # Get all of the edges that this vertex should forward events
  # to, which is the same thing as saying all edges directly below
  # This vertex in the graph.
  @out_from[source].values.flatten.find_all { |edge| edge.match?(event.name) }
end

#path_between(f, t) ⇒ Object

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.



429
430
431
432
433
434
435
436
437
438
439
440
 
# File 'lib/puppet/graph/simple_graph.rb', line 429

def path_between(f, t)
  if f == t
    []
  elsif direct_dependents_of(f).include?(t)
    [edges_between(f, t)]
  elsif dependents(f).include?(t)
    m = (dependents(f) & direct_dependencies_of(t)).first
    path_between(f, m) + path_between(m, t)
  else
    nil
  end
end

#paths_in_cycle(cycle, max_paths = 1) ⇒ Object

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

Raises:

  • (ArgumentError) 


199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/puppet/graph/simple_graph.rb', line 199

def paths_in_cycle(cycle, max_paths = 1)
  # TRANSLATORS "negative or zero" refers to the count of paths
  raise ArgumentError, _("negative or zero max_paths") if max_paths < 1

  # Calculate our filtered outbound vertex lists...
  adj = {}
  cycle.each do |vertex|
    adj[vertex] = adjacent(vertex).select { |s| cycle.member? s }
  end

  found = []

  # frame struct is vertex, [path]
  stack = [[cycle.first, []]]
  while frame = stack.shift # rubocop:disable Lint/AssignmentInCondition
    if frame[1].member?(frame[0]) then
      found << frame[1] + [frame[0]]
      break if found.length >= max_paths
    else
      adj[frame[0]].each do |to|
        stack.push [to, frame[1] + [frame[0]]]
      end
    end
  end

  found.sort
end

#remove_edge!(e) ⇒ Object

Remove an edge from our graph.



339
340
341
342
343
344
345
346
 
# File 'lib/puppet/graph/simple_graph.rb', line 339

def remove_edge!(e)
  if edge?(e.source, e.target)
    @upstream_from.clear
    @downstream_from.clear
    @in_to[e.target].delete e.source if (@in_to[e.target][e.source] -= [e]).empty?
    @out_from[e.source].delete e.target if (@out_from[e.source][e.target] -= [e]).empty?
  end
end

#remove_vertex!(v) ⇒ Object

Remove a vertex from the graph.



279
280
281
282
283
284
285
286
287
 
# File 'lib/puppet/graph/simple_graph.rb', line 279

def remove_vertex!(v)
  return unless vertex?(v)

  @upstream_from.clear
  @downstream_from.clear
  (@in_to[v].values + @out_from[v].values).flatten.each { |e| remove_edge!(e) }
  @in_to.delete(v)
  @out_from.delete(v)
end

#report_cycles_in_graph ⇒ Array

Returns array of dependency cycles (arrays).

Returns:

  • (Array) —

    array of dependency cycles (arrays)



228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
 
# File 'lib/puppet/graph/simple_graph.rb', line 228

def report_cycles_in_graph
  cycles = find_cycles_in_graph
  number_of_cycles = cycles.length
  return if number_of_cycles == 0

  message = n_("Found %{num} dependency cycle:\n", "Found %{num} dependency cycles:\n", number_of_cycles) % { num: number_of_cycles }

  cycles.each do |cycle|
    paths = paths_in_cycle(cycle)
    message += paths.map { |path| '(' + path.join(' => ') + ')' }.join('\n') + '\n'
  end

  if Puppet[:graph] then
    filename = write_cycles_to_graph(cycles)
    message += _("Cycle graph written to %{filename}.") % { filename: filename }
  else
    # TRANSLATORS '--graph' refers to a command line option and OmniGraffle and GraphViz are program names and should not be translated
    message += _("Try the '--graph' option and opening the resulting '.dot' file in OmniGraffle or GraphViz")
  end
  Puppet.err(message)
  cycles
end

#reversal ⇒ Object

Return a reversed version of this graph.



79
80
81
82
83
84
85
86
 
# File 'lib/puppet/graph/simple_graph.rb', line 79

def reversal
  result = self.class.new
  vertices.each { |vertex| result.add_vertex(vertex) }
  edges.each do |edge|
    result.add_edge edge.class.new(edge.target, edge.source, edge.label)
  end
  result
end

#size ⇒ Object

Return the size of the graph.



89
90
91
 
# File 'lib/puppet/graph/simple_graph.rb', line 89

def size
  vertices.size
end

#stringify(s) ⇒ Object 



473
474
475
 
# File 'lib/puppet/graph/simple_graph.rb', line 473

def stringify(s)
  %("#{s.gsub('"', '\\"')}")
end

#tarjan(root, s) ⇒ Object

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.



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/puppet/graph/simple_graph.rb', line 104

def tarjan(root, s)
  # initialize the recursion stack we use to work around the nasty lack of a
  # decent Ruby stack.
  recur = [{ :node => root }]

  until recur.empty?
    frame = recur.last
    vertex = frame[:node]

    case frame[:step]
    when nil then
      s[:index][vertex]   = s[:number]
      s[:lowlink][vertex] = s[:number]
      s[:number]          = s[:number] + 1

      s[:stack].push(vertex)
      s[:seen][vertex] = true

      frame[:children] = adjacent(vertex)
      frame[:step]     = :children

    when :children then
      if frame[:children].length > 0 then
        child = frame[:children].shift
        if !s[:index][child] then
          # Never seen, need to recurse.
          frame[:step] = :after_recursion
          frame[:child] = child
          recur.push({ :node => child })
        elsif s[:seen][child] then
          s[:lowlink][vertex] = [s[:lowlink][vertex], s[:index][child]].min
        end
      else
        if s[:lowlink][vertex] == s[:index][vertex] then
          this_scc = []
          loop do
            top = s[:stack].pop
            s[:seen][top] = false
            this_scc << top
            break if top == vertex
          end
          s[:scc] << this_scc
        end
        recur.pop # done with this node, finally.
      end

    when :after_recursion then
      s[:lowlink][vertex] = [s[:lowlink][vertex], s[:lowlink][frame[:child]]].min
      frame[:step] = :children

    else
      fail "#{frame[:step]} is an unknown step"
    end
  end
end

#to_a ⇒ Object 



93
94
95
 
# File 'lib/puppet/graph/simple_graph.rb', line 93

def to_a
  vertices
end

#to_data_hash ⇒ Object 



512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
 
# File 'lib/puppet/graph/simple_graph.rb', line 512

def to_data_hash
  hash = { 'edges' => edges.map(&:to_data_hash) }
  hash['vertices'] = if self.class.use_new_yaml_format
                       vertices
                     else
                       # Represented in YAML using the old (version 2.6) format.
                       result = {}
                       vertices.each do |vertex|
                         adjacencies = {}
                         [:in, :out].each do |direction|
                           direction_hash = {}
                           adjacencies[direction.to_s] = direction_hash
                           adjacent(vertex, :direction => direction, :type => :edges).each do |edge|
                             other_vertex = direction == :in ? edge.source : edge.target
                             (direction_hash[other_vertex.to_s] ||= []) << edge
                           end
                           direction_hash.each_pair { |key, edges| direction_hash[key] = edges.uniq.map(&:to_data_hash) }
                         end
                         vname = vertex.to_s
                         result[vname] = { 'adjacencies' => adjacencies, 'vertex' => vname }
                       end
                       result
                     end
  hash
end

#to_dot(params = {}) ⇒ Object

Output the dot format as a string



478
 
# File 'lib/puppet/graph/simple_graph.rb', line 478

def to_dot(params = {}) to_dot_graph(params).to_s; end

#to_dot_graph(params = {}) ⇒ Object

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.



448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
 
# File 'lib/puppet/graph/simple_graph.rb', line 448

def to_dot_graph(params = {})
  params['name'] ||= self.class.name.tr(':', '_')
  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.ref
    params = { 'name' => stringify(name),
               'fontsize' => fontsize,
               'label' => name }
    v_label = v.ref
    params.merge!(v_label) if v_label and v_label.is_a? Hash
    graph << DOT::DOTNode.new(params)
  end
  edges.each do |e|
    params = { 'from' => stringify(e.source.ref),
               'to' => stringify(e.target.ref),
               'fontsize' => fontsize }
    e_label = e.ref
    params.merge!(e_label) if e_label and e_label.is_a? Hash
    graph << edge_klass.new(params)
  end
  graph
end

#tree_from_vertex(start, direction = :out) ⇒ Object

A different way of walking a tree, and a much faster way than the one that comes with GRATR.



378
379
380
381
382
383
384
 
# File 'lib/puppet/graph/simple_graph.rb', line 378

def tree_from_vertex(start, direction = :out)
  predecessor = {}
  walk(start, direction) do |parent, child|
    predecessor[child] = parent
  end
  predecessor
end

#upstream_from_vertex(v) ⇒ Object 



401
402
403
404
405
406
407
408
409
410
 
# File 'lib/puppet/graph/simple_graph.rb', line 401

def upstream_from_vertex(v)
  return @upstream_from[v] if @upstream_from[v]

  result = @upstream_from[v] = {}
  @in_to[v].keys.each do |node|
    result[node] = 1
    result.update(upstream_from_vertex(node))
  end
  result
end

#vertex?(v) ⇒ Boolean

Test whether a given vertex is in the graph.

Returns:

  • (Boolean) 


290
291
292
 
# File 'lib/puppet/graph/simple_graph.rb', line 290

def vertex?(v)
  @in_to.include?(v)
end

#vertices ⇒ Object

Return a list of all vertices.



295
296
297
 
# File 'lib/puppet/graph/simple_graph.rb', line 295

def vertices
  @in_to.keys
end

#walk(source, direction) ⇒ Object

Just walk the tree and pass each edge.



357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
 
# File 'lib/puppet/graph/simple_graph.rb', line 357

def walk(source, direction)
  # Use an iterative, breadth-first traversal of the graph. One could do
  # this recursively, but Ruby's slow function calls and even slower
  # recursion make the shorter, recursive algorithm cost-prohibitive.
  stack = [source]
  seen = Set.new
  until stack.empty?
    node = stack.shift
    next if seen.member? node

    connected = adjacent(node, :direction => direction)
    connected.each do |target|
      yield node, target
    end
    stack.concat(connected)
    seen << node
  end
end

#write_cycles_to_graph(cycles) ⇒ Object 



251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
 
# File 'lib/puppet/graph/simple_graph.rb', line 251

def write_cycles_to_graph(cycles)
  # This does not use the DOT graph library, just writes the content
  # directly.  Given the complexity of this, there didn't seem much point
  # using a heavy library to generate exactly the same content. --daniel 2011-01-27
  graph = ["digraph Resource_Cycles {"]
  graph << '  label = "Resource Cycles"'

  cycles.each do |cycle|
    paths_in_cycle(cycle, 10).each do |path|
      graph << path.map { |v| '"' + v.to_s.gsub(/"/, '\\"') + '"' }.join(" -> ")
    end
  end

  graph << '}'

  filename = File.join(Puppet[:graphdir], "cycles.dot")
  # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html
  File.open(filename, "w:UTF-8") { |f| f.puts graph }
  filename
end

#write_graph(name) ⇒ Object

Produce the graph files if requested.



481
482
483
484
485
486
487
488
489
 
# File 'lib/puppet/graph/simple_graph.rb', line 481

def write_graph(name)
  return unless Puppet[:graph]

  file = File.join(Puppet[:graphdir], "#{name}.dot")
  # DOT files are assumed to be UTF-8 by default - http://www.graphviz.org/doc/info/lang.html
  File.open(file, "w:UTF-8") { |f|
    f.puts to_dot("name" => name.to_s.capitalize)
  }
end