# File lib/puppet/simple_graph.rb, line 183
183:   def topsort
184:     degree = {}
185:     zeros = []
186:     result = []
187: 
188:     # Collect each of our vertices, with the number of in-edges each has.
189:     @vertices.each do |name, wrapper|
190:       edges = wrapper.in_edges
191:       zeros << wrapper if edges.length == 0
192:       degree[wrapper.vertex] = edges
193:     end
194: 
195:     # Iterate over each 0-degree vertex, decrementing the degree of
196:     # each of its out-edges.
197:     while wrapper = zeros.pop
198:       result << wrapper.vertex
199:       wrapper.out_edges.each do |edge|
200:         degree[edge.target].delete(edge)
201:         zeros << @vertices[edge.target] if degree[edge.target].length == 0
202:       end
203:     end
204: 
205:     # If we have any vertices left with non-zero in-degrees, then we've found a cycle.
206:     if cycles = degree.find_all { |vertex, edges| edges.length > 0 } and cycles.length > 0
207:       message = cycles.collect { |vertex, edges| edges.collect { |e| e.to_s }.join(", ") }.join(", ")
208:       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"
209:     end
210: 
211:     result
212:   end