Longest circuit in a directed graph I have a very large directed graph (1M nodes) I am wondering what is the best algorithm for finding the longest (most number of nodes) cycle in the graph?
One million nodes is far too much for any exact method that I know. This being said, I expect your graph does not have a very large number of edges, so the best is to begin by applying repeatedly this algorithm :

If you have a vertex in your graph that has not outgoing edge, or that has no incoming edge, remove it from your graph as no cycle can go through it. Take care, as removing such vertices can lead to remove other vertices that had edges in both direction before ! 

This should reduce dramatically the size of your graph (look at what is called "topological sort"). Once this is done, you can compute the different strongly connected componets, as your cycle is included in one of them. Then, you can do the computations separatedly. Perhaps the splitting of your graph will have created new vertices that you can remove.

Iterate through these two algorithms until you can do no other operation in your graph. When it is done, come back here and ask your question again giving the new number of vertices.

When you do so, do not count the number of vertices having exactly one incoming edge and one outgoing edge. They do not change the complexity of the problem.

If after all this your graph is still 1M vertices large, it begins to really be desperate :-)

Nathann