I have a directed graph with 562 vertices and 3961 edges (the edges are http://a3nm.net/share/raw_graph_284374.txt if you are curious) and I would like to find a cycle in this graph which does not go twice through the same vertex and is as long as possible.
I am aware that this problem is NP-hard (by reduction from the hamiltonian cycle problem), but I don't really care about finding the longest cycle, just a reasonably long cycle. A naive DFS implementation can find cycles of length 100-200, but I'm sure that there are many heuristics and improvements that one could use to find a longer one.
Is there any (open-source) program or library that I could use to find a longer cycle in a graph of this size?
I think you can simplify your problem. Note that when a cycle loses an edge it turns into a path. So, basically, you can do as follows
1) consider each pair of nodes u,v.
2) remove the edge between the two nodes.
3) find the longest path (or approximate longest path) https://en.wikipedia.org/wiki/Longest_path_problem
4) the combination of the removed edge and the path will provide you a long cycle.
And I think if you try to make your graph a DAG (directed acyclic graph) using a BFS then you can solve the problem of longest path in linear time and exact (with no approximation).