187: def topsort
188: degree = {}
189: zeros = []
190: result = []
191:
192:
193: @vertices.each do |name, wrapper|
194: edges = wrapper.in_edges
195: zeros << wrapper if edges.length == 0
196: degree[wrapper.vertex] = edges
197: end
198:
199:
200:
201: while wrapper = zeros.pop do
202: result << wrapper.vertex
203: wrapper.out_edges.each do |edge|
204: degree[edge.target].delete(edge)
205: zeros << @vertices[edge.target] if degree[edge.target].length == 0
206: end
207: end
208:
209:
210: if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
211: message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
212: raise Puppet::Error, "Found dependency cycles in the following relationships: %s; try using the '--graph' option and open the '.dot' files in OmniGraffle or GraphViz" % message
213: end
214:
215: return result
216: end