Class: Puppet::SimpleGraph

    # File lib/puppet/simple_graph.rb, line 85
85:     def initialize
86:         @vertices = {}
87:         @edges = []
88:     end

add_edge(source, target = nil, label = nil)

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

[Source]

     # File lib/puppet/simple_graph.rb, line 182
182:     def add_edge(source, target = nil, label = nil)
183:         if target
184:             edge = Puppet::Relationship.new(source, target, label)
185:         else
186:             edge = source
187:         end
188:         [edge.source, edge.target].each { |vertex| setup_vertex(vertex) unless vertex?(vertex) }
189:         @vertices[edge.source].add_edge :out, edge
190:         @vertices[edge.target].add_edge :in, edge
191:         @edges << edge
192:         true
193:     end

add_vertex(vertex)

Add a new vertex to the graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 156
156:     def add_vertex(vertex)
157:         return false if vertex?(vertex)
158:         setup_vertex(vertex)
159:         true # don't return the VertexWrapper instance.
160:     end

adjacent(vertex, options = {})

Find adjacent edges.

[Source]

     # File lib/puppet/simple_graph.rb, line 230
230:     def adjacent(vertex, options = {})
231:         return [] unless wrapper = @vertices[vertex]
232:         return wrapper.adjacent(options)
233:     end

clear()

Clear our graph.

[Source]

    # File lib/puppet/simple_graph.rb, line 91
91:     def clear
92:         @vertices.each { |vertex, wrapper| wrapper.clear }
93:         @vertices.clear
94:         @edges.clear
95:     end

directed?()

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

[Source]

     # File lib/puppet/simple_graph.rb, line 98
 98:     def directed?
 99:         true
100:     end

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

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

[Source]

     # File lib/puppet/simple_graph.rb, line 302
302:     def dotty (params = {}, dotfile = 'graph.dot')
303:       File.open(dotfile, 'w') {|f| f << to_dot(params) }
304:       system('dotty', dotfile)
305:     end

edge(source, target)

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

[Source]

     # File lib/puppet/simple_graph.rb, line 197
197:     def edge(source, target)
198:         @edges.each_with_index { |test_edge, index| return test_edge if test_edge.source == source and test_edge.target == target }
199:     end

edge?(source, target)

Is there an edge between the two vertices?

[Source]

     # File lib/puppet/simple_graph.rb, line 207
207:     def edge?(source, target)
208:         return false unless vertex?(source) and vertex?(target)
209: 
210:         @vertices[source].has_edge?(:out, target)
211:     end

edge_label(source, target)

[Source]

     # File lib/puppet/simple_graph.rb, line 201
201:     def edge_label(source, target)
202:         return nil unless edge = edge(source, target)
203:         edge.label
204:     end

edges()

[Source]

     # File lib/puppet/simple_graph.rb, line 213
213:     def edges
214:         @edges.dup
215:     end

remove_edge!(edge)

Remove an edge from our graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 218
218:     def remove_edge!(edge)
219:         @vertices[edge.source].remove_edge(:out, edge)
220:         @vertices[edge.target].remove_edge(:in, edge)
221:         
222:         # Here we are looking for an exact edge, so we don't want to use ==, because
223:         # it's too darn expensive (in testing, deleting 3000 edges went from 6 seconds to
224:         # 0.05 seconds with this change).
225:         @edges.each_with_index { |test_edge, index| @edges.delete_at(index) and break if edge.equal?(test_edge) }
226:         nil
227:     end

remove_vertex!(vertex)

Remove a vertex from the graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 163
163:     def remove_vertex!(vertex)
164:         return nil unless vertex?(vertex)
165:         @vertices[vertex].edges.each { |edge| remove_edge!(edge) }
166:         @vertices[vertex].clear
167:         @vertices.delete(vertex)
168:     end

reversal()

Return a reversed version of this graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 103
103:     def reversal
104:         result = self.class.new
105:         vertices.each { |vertex| result.add_vertex(vertex) }
106:         edges.each do |edge|
107:             newedge = edge.class.new(edge.target, edge.source, edge.label)
108:             result.add_edge(newedge)
109:         end
110:         result
111:     end

size()

Return the size of the graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 114
114:     def size
115:         @vertices.length
116:     end

to_a()

Return the graph as an array.

[Source]

     # File lib/puppet/simple_graph.rb, line 119
119:     def to_a
120:         @vertices.keys
121:     end

to_dot(params={})

Output the dot format as a string

[Source]

     # File lib/puppet/simple_graph.rb, line 298
298:     def to_dot (params={}) to_dot_graph(params).to_s; end

to_dot_graph(params = {})

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.

[Source]

     # File lib/puppet/simple_graph.rb, line 272
272:     def to_dot_graph (params = {})
273:       params['name'] ||= self.class.name.gsub(/:/,'_')
274:       fontsize   = params['fontsize'] ? params['fontsize'] : '8'
275:       graph      = (directed? ? DOT::DOTDigraph : DOT::DOTSubgraph).new(params)
276:       edge_klass = directed? ? DOT::DOTDirectedEdge : DOT::DOTEdge
277:       vertices.each do |v|
278:         name = v.to_s
279:         params = {'name'     => '"'+name+'"',
280:                   'fontsize' => fontsize,
281:                   'label'    => name}
282:         v_label = v.to_s
283:         params.merge!(v_label) if v_label and v_label.kind_of? Hash
284:         graph << DOT::DOTNode.new(params)
285:       end
286:       edges.each do |e|
287:         params = {'from'     => '"'+ e.source.to_s + '"',
288:                   'to'       => '"'+ e.target.to_s + '"',
289:                   'fontsize' => fontsize }
290:         e_label = e.to_s
291:         params.merge!(e_label) if e_label and e_label.kind_of? Hash
292:         graph << edge_klass.new(params)
293:       end
294:       graph
295:     end

to_yaml_properties()

# For some reason, unconnected vertices do not show up in # this graph. def to_jpg(path, name)

    gv = vertices()
    Dir.chdir(path) do
        induced_subgraph(gv).write_to_graphic_file('jpg', name)
    end

end

[Source]

     # File lib/puppet/simple_graph.rb, line 254
254:     def to_yaml_properties
255:         instance_variables
256:     end

topsort()

Provide a topological sort.

[Source]

     # File lib/puppet/simple_graph.rb, line 124
124:     def topsort
125:         degree = {}
126:         zeros = []
127:         result = []
128: 
129:         # Collect each of our vertices, with the number of in-edges each has.
130:         @vertices.each do |name, wrapper|
131:             edges = wrapper.in_edges
132:             zeros << wrapper if edges.length == 0
133:             degree[wrapper.vertex] = edges
134:         end
135: 
136:         # Iterate over each 0-degree vertex, decrementing the degree of
137:         # each of its out-edges.
138:         while wrapper = zeros.pop do
139:             result << wrapper.vertex
140:             wrapper.out_edges.each do |edge|
141:                 degree[edge.target].delete(edge)
142:                 zeros << @vertices[edge.target] if degree[edge.target].length == 0
143:             end
144:         end
145: 
146:         # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
147:         if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
148:             message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
149:             raise Puppet::Error, "Found dependency cycles in the following relationships: %s" % message
150:         end
151: 
152:         return result
153:     end

vertex?(vertex)

Test whether a given vertex is in the graph.

[Source]

     # File lib/puppet/simple_graph.rb, line 171
171:     def vertex?(vertex)
172:         @vertices.include?(vertex)
173:     end

vertices()

Return a list of all vertices.

[Source]

     # File lib/puppet/simple_graph.rb, line 176
176:     def vertices
177:         @vertices.keys
178:     end

walk(source, direction) {|source, target| ...}

Just walk the tree and pass each edge.

[Source]

     # File lib/puppet/simple_graph.rb, line 259
259:     def walk(source, direction, &block)
260:         adjacent(source, :direction => direction).each do |target|
261:             yield source, target
262:             walk(target, direction, &block)
263:         end
264:     end

write_to_graphic_file(fmt='png', dotfile='graph')

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

[Source]

     # File lib/puppet/simple_graph.rb, line 309
309:     def write_to_graphic_file (fmt='png', dotfile='graph')
310:       src = dotfile + '.dot'
311:       dot = dotfile + '.' + fmt
312:       
313:       File.open(src, 'w') {|f| f << self.to_dot << "\n"}
314:       
315:       system( "dot -T#{fmt} #{src} -o #{dot}" )
316:       dot
317:     end

Methods

Classes and Modules

Public Class methods

Public Instance methods