Class: Puppet::SimpleGraph

Inherits:
Object show all
Defined in:
lib/puppet/simple_graph.rb

Overview

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

Direct Known Subclasses

Resource::Catalog

Defined Under Namespace

Classes: VertexWrapper

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SimpleGraph

Returns a new instance of SimpleGraph.



105
106
107
108
 
# File 'lib/puppet/simple_graph.rb', line 105

def initialize
  @vertices = {}
  @edges = []
end

Instance Method Details

#add_edge(source, target = nil, label = nil) ⇒ 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.



243
244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/puppet/simple_graph.rb', line 243

def add_edge(source, target = nil, label = nil)
  @reversal = nil
  if target
    edge = Puppet::Relationship.new(source, target, label)
  else
    edge = source
  end
  [edge.source, edge.target].each { |vertex| setup_vertex(vertex) unless vertex?(vertex) }
  @vertices[edge.source].add_edge :out, edge
  @vertices[edge.target].add_edge :in, edge
  @edges << edge
  true
end

#add_vertex(vertex) ⇒ Object

Add a new vertex to the graph.



215
216
217
218
219
220
 
# File 'lib/puppet/simple_graph.rb', line 215

def add_vertex(vertex)
  @reversal = nil
  return false if vertex?(vertex)
  setup_vertex(vertex)
  true # don't return the VertexWrapper instance.
end

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

Find adjacent edges.



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

def adjacent(vertex, options = {})
  return [] unless wrapper = @vertices[vertex]
  wrapper.adjacent(options)
end

#clear ⇒ Object

Clear our graph.



111
112
113
114
115
 
# File 'lib/puppet/simple_graph.rb', line 111

def clear
  @vertices.each { |vertex, wrapper| wrapper.clear }
  @vertices.clear
  @edges.clear
end

#dependencies(resource) ⇒ Object

Which resources depend upon the given resource.



123
124
125
126
127
128
129
130
131
 
# File 'lib/puppet/simple_graph.rb', line 123

def dependencies(resource)
  # Cache the reversal graph, because it's somewhat expensive
  # to create.
  @reversal ||= reversal
  # Strangely, it's significantly faster to search a reversed
  # tree in the :out direction than to search a normal tree
  # in the :in direction.
  @reversal.tree_from_vertex(resource, :out).keys
end

#dependents(resource) ⇒ Object

Which resources a given resource depends upon.



118
119
120
 
# File 'lib/puppet/simple_graph.rb', line 118

def dependents(resource)
  tree_from_vertex(resource).keys
end

#directed? ⇒ Boolean

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

Returns:

  • (Boolean) 


134
135
136
 
# File 'lib/puppet/simple_graph.rb', line 134

def directed?
  true
end

#dotty(params = {}, dotfile = 'graph.dot') ⇒ Object

Call dotty for the graph which is written to the file ‘graph.dot’ in the # current directory.



424
425
426
427
 
# File 'lib/puppet/simple_graph.rb', line 424

def dotty (params = {}, dotfile = 'graph.dot')
  File.open(dotfile, 'w') {|f| f << to_dot(params) }
  system('dotty', dotfile)
end

#edge(source, target) ⇒ Object

Find a matching edge. Note that this only finds the first edge, not all of them or whatever.



259
260
261
 
# File 'lib/puppet/simple_graph.rb', line 259

def edge(source, target)
  @edges.each_with_index { |test_edge, index| return test_edge if test_edge.source == source and test_edge.target == target }
end

#edge?(source, target) ⇒ Boolean

Is there an edge between the two vertices?

Returns:

  • (Boolean) 


269
270
271
272
273
 
# File 'lib/puppet/simple_graph.rb', line 269

def edge?(source, target)
  return false unless vertex?(source) and vertex?(target)

  @vertices[source].has_edge?(:out, target)
end

#edge_label(source, target) ⇒ Object 



263
264
265
266
 
# File 'lib/puppet/simple_graph.rb', line 263

def edge_label(source, target)
  return nil unless edge = edge(source, target)
  edge.label
end

#edges ⇒ Object 



275
276
277
 
# File 'lib/puppet/simple_graph.rb', line 275

def edges
  @edges.dup
end

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

Determine all of the leaf nodes below a given vertex.



139
140
141
142
 
# File 'lib/puppet/simple_graph.rb', line 139

def leaves(vertex, direction = :out)
  tree = tree_from_vertex(vertex, direction)
  l = tree.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.



146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/puppet/simple_graph.rb', line 146

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

  unless vertex?(source)
    Puppet.warning "Got an event from invalid vertex #{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.
  adjacent(source, :direction => :out, :type => :edges).find_all do |edge|
    edge.match?(event.name)
  end
end

#remove_edge!(edge) ⇒ Object

Remove an edge from our graph.



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

def remove_edge!(edge)
  @vertices[edge.source].remove_edge(:out, edge)
  @vertices[edge.target].remove_edge(:in, edge)

  @edges.delete(edge)
  nil
end

#remove_vertex!(vertex) ⇒ Object

Remove a vertex from the graph.



223
224
225
226
227
228
229
 
# File 'lib/puppet/simple_graph.rb', line 223

def remove_vertex!(vertex)
  return nil unless vertex?(vertex)
  @vertices[vertex].edges.each { |edge| remove_edge!(edge) }
  @edges -= @vertices[vertex].edges
  @vertices[vertex].clear
  @vertices.delete(vertex)
end

#reversal ⇒ Object

Return a reversed version of this graph.



162
163
164
165
166
167
168
169
170
 
# File 'lib/puppet/simple_graph.rb', line 162

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

#size ⇒ Object

Return the size of the graph.



173
174
175
 
# File 'lib/puppet/simple_graph.rb', line 173

def size
  @vertices.length
end

#splice!(other, type) ⇒ Object

Take container information from another graph and use it to replace any container vertices with their respective leaves. This creates direct relationships where there were previously indirect relationships through the containers.



317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
 
# File 'lib/puppet/simple_graph.rb', line 317

def splice!(other, type)
  # We have to get the container list via a topological sort on the
  # configuration graph, because otherwise containers that contain
  # other containers will add those containers back into the
  # graph.  We could get a similar affect by only setting relationships
  # to container leaves, but that would result in many more
  # relationships.
  stage_class = Puppet::Type.type(:stage)
  whit_class  = Puppet::Type.type(:whit)
  containers = other.topsort.find_all { |v| (v.is_a?(type) or v.is_a?(stage_class)) and vertex?(v) }
  containers.each do |container|
    # Get the list of children from the other graph.
    children = other.adjacent(container, :direction => :out)

    # MQR TODO: Luke suggests that it should be possible to refactor the system so that
    #           container nodes are retained, thus obviating the need for the whit.
    children = [whit_class.new(:name => container.name, :catalog => other)] if children.empty?

    # First create new edges for each of the :in edges
    [:in, :out].each do |dir|
      edges = adjacent(container, :direction => dir, :type => :edges)
      edges.each do |edge|
        children.each do |child|
          if dir == :in
            s = edge.source
            t = child
          else
            s = child
            t = edge.target
          end

          add_edge(s, t, edge.label)
        end

        # Now get rid of the edge, so remove_vertex! works correctly.
        remove_edge!(edge)
      end
    end
    remove_vertex!(container)
  end
end

#to_a ⇒ Object

Return the graph as an array.



178
179
180
 
# File 'lib/puppet/simple_graph.rb', line 178

def to_a
  @vertices.keys
end

#to_dot(params = {}) ⇒ Object

Output the dot format as a string



420
 
# File 'lib/puppet/simple_graph.rb', line 420

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.



394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
 
# File 'lib/puppet/simple_graph.rb', line 394

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 = v.to_s
    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 = e.to_s
    params.merge!(e_label) if e_label and e_label.kind_of? Hash
    graph << edge_klass.new(params)
  end
  graph
end

#topsort ⇒ Object

Provide a topological sort.



183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/puppet/simple_graph.rb', line 183

def topsort
  degree = {}
  zeros = []
  result = []

  # Collect each of our vertices, with the number of in-edges each has.
  @vertices.each do |name, wrapper|
    edges = wrapper.in_edges
    zeros << wrapper if edges.length == 0
    degree[wrapper.vertex] = edges
  end

  # Iterate over each 0-degree vertex, decrementing the degree of
  # each of its out-edges.
  while wrapper = zeros.pop
    result << wrapper.vertex
    wrapper.out_edges.each do |edge|
      degree[edge.target].delete(edge)
      zeros << @vertices[edge.target] if degree[edge.target].length == 0
    end
  end

  # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
  if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
    message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
    raise Puppet::Error, "Found dependency cycles in the following relationships: #{message}; try using the '--graph' option and open the '.dot' files in OmniGraffle or GraphViz"
  end

  result
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.



380
381
382
383
384
385
386
 
# File 'lib/puppet/simple_graph.rb', line 380

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

#vertex?(vertex) ⇒ Boolean

Test whether a given vertex is in the graph.

Returns:

  • (Boolean) 


232
233
234
 
# File 'lib/puppet/simple_graph.rb', line 232

def vertex?(vertex)
  @vertices.include?(vertex)
end

#vertices ⇒ Object

Return a list of all vertices.



237
238
239
 
# File 'lib/puppet/simple_graph.rb', line 237

def vertices
  @vertices.keys
end

#walk(source, direction) ⇒ Object

Just walk the tree and pass each edge.



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

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_graph(name) ⇒ Object

Produce the graph files if requested.



442
443
444
445
446
447
448
449
450
451
 
# File 'lib/puppet/simple_graph.rb', line 442

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

  Puppet.settings.use(:graphing)

  file = File.join(Puppet[:graphdir], "#{name}.dot")
  File.open(file, "w") { |f|
    f.puts to_dot("name" => name.to_s.capitalize)
  }
end

#write_to_graphic_file(fmt = 'png', dotfile = 'graph') ⇒ Object

Use dot to create a graphical representation of the graph. Returns the filename of the graphics file.



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

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