dependency sort with detection of cyclic dependencies

Before you start throwing links to wikipedia and blogs in my face, please hear me out.

I'm trying to find the optimal algorithm/function to do a dependency sort on... stuff. Each item has a list of its dependencies.

I would like to have something iterator-based, but that's not very important.

What is important is that the algorithm points out exactly which items are part of the dependency cycle. I'd like to give detailed error inform开发者_StackOverflow中文版ation in this case.

Practically, I'm thinking of subclassing my items from a "dependency node" class, which has the necessary booleans/functions to get the job done. Cool (but descriptive) names are welcome :)

It's normally called a topological sort. Most books/papers/whatever that cover topological sorting will also cover cycle detection as a matter of course.

I don't exactly get why is it so hard to find the dependecy cycle if there is any! you just have to check if there is any node you already passed over while appling bfs algorithm to find out all the dependecies. if there is one you just roll back the way you came down to revisit a node alll the way up and mark all the nodes until you reach the first visit at the specified node. all the ones in your pass will be marked as a cycle. (just leave a comment and i'll give a code to do that if you need)