# File lib/puppet/simple_graph.rb, line 187
187:     def topsort
188:         degree = {}
189:         zeros = []
190:         result = []
191: 
192:         # Collect each of our vertices, with the number of in-edges each has.
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:         # Iterate over each 0-degree vertex, decrementing the degree of
200:         # each of its out-edges.
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:         # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
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