Finding the longest cycle in a directed graph using DFS

I need to find the longest cycle in a directed graph using DFS.

I once saw this Wikipedia article describing the way of doing this, and I think it approached the problem something like marking the node with one of three states: Node not yet visited, Finished searching the node, and Node visited, but not yet finished visiting.

I would be grateful if anyone could share the link with me. By the way, it isn't Tarjan's Algorithm.

开发者_Python百科

The problem below is what I'm trying to solve, in case you'd like to know.

The two digits given in the first line is N and M, each representing the number of nodes and the number of directed edges.

From the second line is given M sets of two digits A and B, which means that node A and B are connected but you can only traverse the node from A to B.

input.txt:

7 9  
1 2  
2 3  
3 1  
3 4  
4 5  
5 1  
5 6  
6 7  
7 2  

The answer in this case is 6, since 2>3>4>5>6>7>2.

---

I think that longest elementary cycle (or circuit) is better terminology than longest cycle.

Anyway, this pdf may be helpful: Finding All the Elementary Circuits of a Directed Graph

This one year old stackoverflow question has also many links to related problems and algorithms: Finding all cycles in a directed graph

---

It can indeed be shown that you can reduce Hamiltonian cycle into this problem in polynomial time, so it ends up NP-complete. Regardless whether the graph is directed or undirected.

As far as the algorithm, the easy way to solve the problem is to backtrack---start in nodes i=1 to n, and always explore all cycles starting in the particular node i. Once this is done, you eliminate the node i and continue for the rest of the graph, starting in node i+1. You may want to do something like node-coloring in DFS, to distinguish nodes that you never want to visit again and those that you visited along the path in this particular pass. You may also want to put something like a time-stamp on the nodes, similar to discovery times, but in this case you need to write these times everytime you discover a node, as most nodes will be discovered many times. The papers listed above could be helpful, and there are more ways to do this for sure.

---

This problem is NP-Complete and there haven't been a polynomial time algorithm for it. What is the size of your problem? I mean how many nodes will be in the input graph?

longest cycle problem reduces to Hamiltonian cycle problem: http://mathworld.wolfram.com/HamiltonianCycle.html

---

I have an answer explaining an easy way to find all cycles in a directed graph using Python and networkX in another post. Finding all cycles in a directed graph

The solution will output a list containing all cycles of the directed graph.

You can use this output to find the longest cycle ans it is shown bellow:

import networkx as nx

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["1","2","3","4","5","6","7","9"])

# Add a list of edges:
G.add_edges_from([("7","9"),("1","2"),("2","3"),("3","1"),("3","4"),("4","5"),("5","1"),("5","6"),("6","7"),("7","2")])

#Return a list of cycles described as a list o nodes
all_cycles = list(nx.simple_cycles(G))

#Find longest cycle
answer = []
longest_cycle_len = 0
for cycle in all_cycles:
    cycle_len = len(cycle)
    if cycle_len>longest_cycle_len:
        answer =cycle
        longest_cycle_len = cycle_len

print "Longest Cycle is {} with length {}.".format(answer,longest_cycle_len)

Answer: Longest Cycle is ['3', '4', '5', '6', '7', '2'] with length 6.

If you find it interesting upvote up the original answer too. It is an old discussion with many answers and it will help bringing the new solution up.