<p>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 :</p>

<p>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 ! </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<p>Nathann</p>

CC BY-SA 3.0
2011-08-26T16:39:19.043Z
@Mark: especially if what you would like is the largest **cycle** — as opposed to the largest **circuit** — Nathan's remarks about decreasing the size as much as possible, and determining the strongly connected components, are quite good advice. Even if you discover that you have to do brute-force searching in two large strongly connected components of size 500 thousand, this (while still labor-intensive) is dramatically better than brute-force searching in a single network of 1 million.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-26T11:52:41.203Z
2011-08-26T11:52:41.203Z
Nathann Cohen
<p>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?</p>

CC BY-SA 3.0
2011-08-26T11:36:48.737Z
The longest *cycle* (no repeated nodes), or the longest *circuit* (which may in general repeat nodes, even if you do not double-count them)? If the latter, we will also have to add the restriction that it does not also repeat *edges*, in order to obtain finite results.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-26T18:55:55.683Z
@Niel de Beaudrap I don't believe there is standard terminology for this.
Tyson Williams
CC BY-SA 3.0
2011-08-26T19:03:30.383Z
@Tyson Williams: depending on what Mark is asking about, there may be. For instance, in graph theory (among English speakers) one *does* distinguish between cycles and circuits; and the distinction is precisely whether or not a node is allowed to be revisited (no for cycles, yes for circuits).
Niel de Beaudrap
CC BY-SA 3.0
2011-08-27T00:05:01.277Z
@Niel de Beaudrap This doesn't have anything to do with OP's question.  I am just saying that cycle (no repeated nodes) and circuit (allows repeated nodes) is not standard terminology for these concepts because there is no standard terminology. See http://en.wikipedia.org/wiki/Cycle_(graph_theory)
Tyson Williams
CC BY-SA 3.0
2011-08-27T13:55:42.937Z
@Tyson WIlliams: as you demonstrate, there is no unambiguous meaning across disciplines, fair enough; however, if you look at the second definition, you will see that – as I remarked – among **graph theorists**, the terminology hinges upon whether nodes may be revisited; and certainly this may affect the complexity of the problem.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-27T15:49:39.340Z
@Niel de Beaudrap Exactly...and this is a site for theoretical computer scientists, not graph theorists. You are taking my original comment way too seriously. I was just trying to let the OP know that not everyone uses the terms you suggested.
Tyson Williams
CC BY-SA 3.0
2011-08-27T17:17:37.397Z
@Tyson Williams: though a computer scientist, I've only ever heard the "graph theoretic" definition. So please pardon my surprise at the strength of your response in insisting that there's no consensus. I only meant to indicate that it's a pretty important distinction to make; and whether or not one thinks that it's important enough to embed into the nomenclature, as graph-theorists routinely do, it's worth bearing in mind.
Niel de Beaudrap
CC BY-SA 3.0
2011-08-28T04:02:30.203Z
@Niel de Beaudrap I also agree that the distinction is important.
Tyson Williams
CC BY-SA 3.0
2011-08-28T19:14:03.513Z
Assuming that one wants a cycle in which nodes are not repeated, the problem is of course NP-Hard via a reduction from the Hamiltonian cycle problem. Finding an effective heuristic on a large graph requires a good understanding of the problem instances.
Chandra Chekuri
<ds.algorithms><graph-algorithms>
Longest circuit in a directed graph
Mark
# Longest circuit in a directed graph

(Asked by: username_0 on 2011-08-26)

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?

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: The longest *cycle* (no repeated nodes), or the longest *circuit* (which may in general repeat nodes, even if you do not double-count them)? If the latter, we will also have to add the restriction that it does not also repeat *edges*, in order to obtain finite results.  
> **username_2**: @username_1 I don't believe there is standard terminology for this.  
> **username_1**: @username_2: depending on what username_0 is asking about, there may be. For instance, in graph theory (among English speakers) one *does* distinguish between cycles and circuits; and the distinction is precisely whether or not a node is allowed to be revisited (no for cycles, yes for circuits).  
> **username_2**: @username_1 This doesn't have anything to do with OP's question.  I am just saying that cycle (no repeated nodes) and circuit (allows repeated nodes) is not standard terminology for these concepts because there is no standard terminology. See http://en.wikipedia.org/wiki/Cycle_(graph_theory)  
> **username_1**: @Tyson WIlliams: as you demonstrate, there is no unambiguous meaning across disciplines, fair enough; however, if you look at the second definition, you will see that – as I remarked – among **graph theorists**, the terminology hinges upon whether nodes may be revisited; and certainly this may affect the complexity of the problem.  
> **username_2**: @username_1 Exactly...and this is a site for theoretical computer scientists, not graph theorists. You are taking my original comment way too seriously. I was just trying to let the OP know that not everyone uses the terms you suggested.  
> **username_1**: @username_2: though a computer scientist, I've only ever heard the "graph theoretic" definition. So please pardon my surprise at the strength of your response in insisting that there's no consensus. I only meant to indicate that it's a pretty important distinction to make; and whether or not one thinks that it's important enough to embed into the nomenclature, as graph-theorists routinely do, it's worth bearing in mind.  
> **username_2**: @username_1 I also agree that the distinction is important.  
> **username_3**: Assuming that one wants a cycle in which nodes are not repeated, the problem is of course NP-Hard via a reduction from the Hamiltonian cycle problem. Finding an effective heuristic on a large graph requires a good understanding of the problem instances.  

---

## 1 answers

### Answer by username_4 on 2011-08-26. Score: 1

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

> **Comments:**
> **username_1**: @username_0: especially if what you would like is the largest **cycle** — as opposed to the largest **circuit** — Nathan's remarks about decreasing the size as much as possible, and determining the strongly connected components, are quite good advice. Even if you discover that you have to do brute-force searching in two large strongly connected components of size 500 thousand, this (while still labor-intensive) is dramatically better than brute-force searching in a single network of 1 million.  

---

