Class: Puppet::SimpleGraph
Overview
A hopefully-faster graph class to replace the use of GRATR.
Direct Known Subclasses
Defined Under Namespace
Classes: VertexWrapper
Class Attribute Summary collapse
-
.use_new_yaml_format ⇒ Object
Returns the value of attribute use_new_yaml_format.
Instance Method Summary collapse
-
#add_edge(e, *a) ⇒ Object
Add a new edge.
- #add_relationship(source, target, label = nil) ⇒ Object
-
#add_vertex(vertex) ⇒ Object
Add a new vertex to the graph.
-
#adjacent(v, options = {}) ⇒ Object
Find adjacent edges.
-
#clear ⇒ Object
Clear our graph.
-
#dependencies(resource) ⇒ Object
Which resources depend upon the given resource.
- #dependents(resource) ⇒ Object
- #direct_dependencies_of(v) ⇒ Object
- #direct_dependents_of(v) ⇒ Object
-
#directed? ⇒ Boolean
Whether our graph is directed.
-
#dotty(params = {}, dotfile = 'graph.dot') ⇒ Object
Call
dotty
for the graph which is written to the file ‘graph.dot’ in the # current directory. - #downstream_from_vertex(v) ⇒ Object
- #each_edge ⇒ Object
-
#edge?(source, target) ⇒ Boolean
Is there an edge between the two vertices?.
- #edges ⇒ Object
-
#edges_between(source, target) ⇒ Object
Find all matching edges.
-
#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.
-
#initialize ⇒ SimpleGraph
constructor
All public methods of this class must maintain (assume ^ ensure) the following invariants, where “=~=” means equiv.
-
#instance_variable_get(v) ⇒ Object
instance_variable_get is used by Object.to_zaml to get instance variables.
-
#leaves(vertex, direction = :out) ⇒ Object
Determine all of the leaf nodes below a given vertex.
-
#matching_edges(event, base = nil) ⇒ Object
Collect all of the edges that the passed events match.
-
#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 verticies.
-
#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.
-
#remove_edge!(e) ⇒ Object
Remove an edge from our graph.
-
#remove_vertex!(v) ⇒ Object
Remove a vertex from the graph.
- #report_cycles_in_graph ⇒ Object
-
#reversal ⇒ Object
Return a reversed version of this graph.
-
#size ⇒ Object
Return the size of the graph.
-
#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.
- #to_a ⇒ Object
-
#to_dot(params = {}) ⇒ Object
Output the dot format as a string.
-
#to_dot_graph(params = {}) ⇒ Object
Return a DOT::DOTDigraph for directed graphs or a DOT::DOTSubgraph for an undirected Graph.
- #to_yaml_properties ⇒ Object
-
#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.
- #upstream_from_vertex(v) ⇒ Object
-
#vertex?(v) ⇒ Boolean
Test whether a given vertex is in the graph.
-
#vertices ⇒ Object
Return a list of all vertices.
-
#walk(source, direction) ⇒ Object
Just walk the tree and pass each edge.
- #write_cycles_to_graph(cycles) ⇒ Object
-
#write_graph(name) ⇒ Object
Produce the graph files if requested.
- #yaml_initialize(tag, var) ⇒ Object
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.
24 25 26 27 28 29 |
# File 'lib/vendor/puppet/simple_graph.rb', line 24 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.
480 481 482 |
# File 'lib/vendor/puppet/simple_graph.rb', line 480 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.
291 292 293 294 295 296 297 298 299 |
# File 'lib/vendor/puppet/simple_graph.rb', line 291 def add_edge(e,*a) return add_relationship(e,*a) unless a.empty? @upstream_from.clear @downstream_from.clear add_vertex(e.source) add_vertex(e.target) @in_to[ e.target][e.source] ||= []; @in_to[ e.target][e.source] |= [e] @out_from[e.source][e.target] ||= []; @out_from[e.source][e.target] |= [e] end |
#add_relationship(source, target, label = nil) ⇒ Object
301 302 303 |
# File 'lib/vendor/puppet/simple_graph.rb', line 301 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.
264 265 266 267 |
# File 'lib/vendor/puppet/simple_graph.rb', line 264 def add_vertex(vertex) @in_to[vertex] ||= {} @out_from[vertex] ||= {} end |
#adjacent(v, options = {}) ⇒ Object
Find adjacent edges.
334 335 336 337 |
# File 'lib/vendor/puppet/simple_graph.rb', line 334 def adjacent(v, = {}) return [] unless ns = ([:direction] == :in) ? @in_to[v] : @out_from[v] ([:type] == :edges) ? ns.values.flatten : ns.keys end |
#clear ⇒ Object
Clear our graph.
32 33 34 35 36 37 |
# File 'lib/vendor/puppet/simple_graph.rb', line 32 def clear @in_to.clear @out_from.clear @upstream_from.clear @downstream_from.clear end |
#dependencies(resource) ⇒ Object
Which resources depend upon the given resource.
40 41 42 |
# File 'lib/vendor/puppet/simple_graph.rb', line 40 def dependencies(resource) vertex?(resource) ? upstream_from_vertex(resource).keys : [] end |
#dependents(resource) ⇒ Object
44 45 46 |
# File 'lib/vendor/puppet/simple_graph.rb', line 44 def dependents(resource) vertex?(resource) ? downstream_from_vertex(resource).keys : [] end |
#direct_dependencies_of(v) ⇒ Object
392 393 394 |
# File 'lib/vendor/puppet/simple_graph.rb', line 392 def direct_dependencies_of(v) (@in_to[v] || {}).keys end |
#direct_dependents_of(v) ⇒ Object
378 379 380 |
# File 'lib/vendor/puppet/simple_graph.rb', line 378 def direct_dependents_of(v) (@out_from[v] || {}).keys end |
#directed? ⇒ Boolean
Whether our graph is directed. Always true. Used to produce dot files.
49 50 51 |
# File 'lib/vendor/puppet/simple_graph.rb', line 49 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.
458 459 460 461 |
# File 'lib/vendor/puppet/simple_graph.rb', line 458 def dotty (params = {}, dotfile = 'graph.dot') File.open(dotfile, 'w') {|f| f << to_dot(params) } system('dotty', dotfile) end |
#downstream_from_vertex(v) ⇒ Object
368 369 370 371 372 373 374 375 376 |
# File 'lib/vendor/puppet/simple_graph.rb', line 368 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
319 320 321 |
# File 'lib/vendor/puppet/simple_graph.rb', line 319 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?
311 312 313 |
# File 'lib/vendor/puppet/simple_graph.rb', line 311 def edge?(source, target) vertex?(source) and vertex?(target) and @out_from[source][target] end |
#edges ⇒ Object
315 316 317 |
# File 'lib/vendor/puppet/simple_graph.rb', line 315 def edges @in_to.values.collect { |x| x.values }.flatten end |
#edges_between(source, target) ⇒ Object
Find all matching edges.
306 307 308 |
# File 'lib/vendor/puppet/simple_graph.rb', line 306 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.
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 |
# File 'lib/vendor/puppet/simple_graph.rb', line 160 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| if ! 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 { |c| c.length > 1 }.map {|x| x.sort }.sort end |
#instance_variable_get(v) ⇒ Object
instance_variable_get is used by Object.to_zaml to get instance variables. Override it so that we can simulate the presence of instance variables @edges and @vertices for serialization.
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 |
# File 'lib/vendor/puppet/simple_graph.rb', line 501 def instance_variable_get(v) case v.to_s when '@edges' then edges when '@vertices' then if self.class.use_new_yaml_format vertices else result = {} vertices.each do |vertex| adjacencies = {} [:in, :out].each do |direction| adjacencies[direction] = {} adjacent(vertex, :direction => direction, :type => :edges).each do |edge| other_vertex = direction == :in ? edge.source : edge.target (adjacencies[direction][other_vertex] ||= Set.new).add(edge) end end result[vertex] = Puppet::SimpleGraph::VertexWrapper.new(vertex, adjacencies) end result end else super(v) end end |
#leaves(vertex, direction = :out) ⇒ Object
Determine all of the leaf nodes below a given vertex.
54 55 56 |
# File 'lib/vendor/puppet/simple_graph.rb', line 54 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.
60 61 62 63 64 65 66 67 68 69 70 71 |
# File 'lib/vendor/puppet/simple_graph.rb', line 60 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. @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 verticies. 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.
409 410 411 412 413 414 415 416 417 418 419 420 |
# File 'lib/vendor/puppet/simple_graph.rb', line 409 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
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 |
# File 'lib/vendor/puppet/simple_graph.rb', line 191 def paths_in_cycle(cycle, max_paths = 1) 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 do 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 return found.sort end |
#remove_edge!(e) ⇒ Object
Remove an edge from our graph.
324 325 326 327 328 329 330 331 |
# File 'lib/vendor/puppet/simple_graph.rb', line 324 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.
270 271 272 273 274 275 276 277 |
# File 'lib/vendor/puppet/simple_graph.rb', line 270 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 ⇒ Object
218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 |
# File 'lib/vendor/puppet/simple_graph.rb', line 218 def report_cycles_in_graph cycles = find_cycles_in_graph n = cycles.length # where is "pluralize"? --daniel 2011-01-22 return if n == 0 s = n == 1 ? '' : 's' = "Found #{n} dependency cycle#{s}:\n" cycles.each do |cycle| paths = paths_in_cycle(cycle) += paths.map{ |path| '(' + path.join(" => ") + ')'}.join("\n") + "\n" end if Puppet[:graph] then filename = write_cycles_to_graph(cycles) += "Cycle graph written to #{filename}." else += "Try the '--graph' option and opening the " += "resulting '.dot' file in OmniGraffle or GraphViz" end raise Puppet::Error, end |
#reversal ⇒ Object
Return a reversed version of this graph.
74 75 76 77 78 79 80 81 |
# File 'lib/vendor/puppet/simple_graph.rb', line 74 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.
84 85 86 |
# File 'lib/vendor/puppet/simple_graph.rb', line 84 def size vertices.size 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.
99 100 101 102 103 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 |
# File 'lib/vendor/puppet/simple_graph.rb', line 99 def tarjan(root, s) # initialize the recursion stack we use to work around the nasty lack of a # decent Ruby stack. recur = [{ :node => root }] while not recur.empty? do 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 = [] begin top = s[:stack].pop s[:seen][top] = false this_scc << top end until top == vertex 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
88 89 90 |
# File 'lib/vendor/puppet/simple_graph.rb', line 88 def to_a vertices end |
#to_dot(params = {}) ⇒ Object
Output the dot format as a string
454 |
# File 'lib/vendor/puppet/simple_graph.rb', line 454 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.
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 |
# File 'lib/vendor/puppet/simple_graph.rb', line 428 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 |
#to_yaml_properties ⇒ Object
528 529 530 531 532 533 534 |
# File 'lib/vendor/puppet/simple_graph.rb', line 528 def to_yaml_properties other_vars = instance_variables. map {|v| v.to_s}. reject { |v| %w{@in_to @out_from @upstream_from @downstream_from}.include?(v) } (other_vars + %w{@vertices @edges}).sort.uniq 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.
360 361 362 363 364 365 366 |
# File 'lib/vendor/puppet/simple_graph.rb', line 360 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
382 383 384 385 386 387 388 389 390 |
# File 'lib/vendor/puppet/simple_graph.rb', line 382 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.
280 281 282 |
# File 'lib/vendor/puppet/simple_graph.rb', line 280 def vertex?(v) @in_to.include?(v) end |
#vertices ⇒ Object
Return a list of all vertices.
285 286 287 |
# File 'lib/vendor/puppet/simple_graph.rb', line 285 def vertices @in_to.keys end |
#walk(source, direction) ⇒ Object
Just walk the tree and pass each edge.
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 |
# File 'lib/vendor/puppet/simple_graph.rb', line 340 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
241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 |
# File 'lib/vendor/puppet/simple_graph.rb', line 241 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 Puppet.settings.use(:graphing) 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") File.open(filename, "w") { |f| f.puts graph } return filename end |
#write_graph(name) ⇒ Object
Produce the graph files if requested.
464 465 466 467 468 469 470 471 472 473 |
# File 'lib/vendor/puppet/simple_graph.rb', line 464 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 |
#yaml_initialize(tag, var) ⇒ Object
536 537 538 539 540 541 542 543 544 545 546 547 548 549 |
# File 'lib/vendor/puppet/simple_graph.rb', line 536 def yaml_initialize(tag, var) initialize() vertices = var.delete('vertices') edges = var.delete('edges') if vertices.is_a?(Hash) # Support old (2.6) format vertices = vertices.keys end vertices.each { |v| add_vertex(v) } edges.each { |e| add_edge(e) } var.each do |varname, value| instance_variable_set("@#{varname}", value) end end |