Check cycles in directed graphs

[pradkrish]

It should be possible to use topological sort to detect cycles in a graph. Can you assign this to me? Thanks.

[fhamonic]

Hi, thank you for contributing.
I think that topological_sort is fulfilling its responsibilities in its current form and should not be expanded. It's true that the topological sort can identify if the graph contains cycles or not (if not all vertices are visited, it does) but identifying which vertices and arcs are forming cycles is less trivial. I think that this algorithm based on DFS is more simple and efficient for both these problems. If it suits you, I suggest implementing it under the name oriented_cycle_detection ?
The basic thing is returning true at the first cycle found and false at the end of the algorithm.
Now, the tricky part is providing a method .found_cycle() that allows iterating on the arcs of the cycle found with a view. You can find an example of how I think its feasible in the method .path() of the Dijkstra's algorithm.