How to detect a cycle in a directed graph with Python?

Question

I have some input like: [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]. I want to look for if the existence of a cycle in a directed graph represented by this edgeList.

I read a discussion: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/, however it has some errors when the case is:

g = Graph(3)
g.addEdge('A', 'B')
g.addEdge('B', 'C')
g.addEdge('C', 'A')

Its result is 'Graph has no cycle'. This is clearly wrong. Can you help me to solve this problem?

Answer 1

Using the networkx library, we can use the simple_cycles function to find all simple cycles of a directed Graph.

Example Code:

import networkx as nx

edges = [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]

G = nx.DiGraph(edges)

for cycle in nx.simple_cycles(G):
    print(cycle)

G = nx.DiGraph()

G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'A')

for cycle in nx.simple_cycles(G):
    print(cycle)

Output:

['D', 'C']
['B', 'C', 'A']

Answer 2

The issue is the example given at [1]: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ works for integers only because they use the range() function to create a list of nodes,see the line

for node in range(self.V):

That makes the assumption that not only will all the nodes be integers but also that they will be a contiguous set i.e. [0,1,2,3] is okay but [0,3,10] is not.

You can fix the example if you like to work with any nodes by swapping the line given above with

for node in self.graph.keys():

which will loop through all the nodes instead of a range of numbers :)