# Detect Cycle in Directed Graph using DFS in Python

This is a Python program to find if a directed graph contains a cycle using DFS.

Problem Description

The program allows the user to determine whether a directed graph contains a cycle.

Problem Solution

1. Create classes for Graph and Vertex.
2. Create a function is_cycle_present_helper that takes a Vertex object v, a set visited and a set on_stack as arguments.
3. The function works by keeping track of the nodes that are on the stack. That is those nodes whose children are still being traversed. If while performing traversal a node already on the stack is found, then the graph contains a cycle.
4. The set on_stack keeps track of the nodes that are on the stack of the DFS traversal.
5. The functions begins by testing if v is in on_stack and if so, a cycle is present and it returns True.
6. Otherwise, it adds v to on_stack.
7. For each neighbour of v that is not in visited, is_cycle_present_helper is called. If is_cycle_present_helper returns True, a cycle is present and True is returned.
8. After the loop finishes, v is removed from on_stack and added to visited.
9. False is returned to indicate that no cycle is present.
10. Create a function is_cycle_present that takes a Graph object as argument.
11. It creates two empty sets, visited and on_stack.
12. For each vertex v in the graph, if v is not in visited, is_cycle_present_helper is called on v.
13. If is_cycle_present_helper returns True, a cycle is present in the graph and True is returned.
14. If the loop finishes, then no cycle is present and False is returned.
15. Thus, this function returns True if a cycle is present in the graph.

Program/Source Code

Here is the source code of a Python program to find if a directed graph contains a cycle using DFS. The program output is shown below.

```class Graph:
def __init__(self):
# dictionary containing keys that map to the corresponding vertex object
self.vertices = {}

"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex

def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]

def __contains__(self, key):
return key in self.vertices

"""Add edge from src_key to dest_key with given weight."""

def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}

def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key

"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight

def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()

def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]

def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to

def is_cycle_present(graph):
"""Return True if cycle is present in the graph."""
on_stack = set()
visited = set()
for v in graph:
if v not in visited:
if is_cycle_present_helper(v, visited, on_stack):
return True
return False

def is_cycle_present_helper(v, visited, on_stack):
"""Return True if the DFS traversal starting at vertex v detects a
cycle. Uses set visited to keep track of nodes that have been visited. Uses
set on_stack to keep track of nodes that are 'on the stack' of the recursive
calls."""
if v in on_stack:
return True
for dest in v.get_neighbours():
if dest not in visited:
if is_cycle_present_helper(dest, visited, on_stack):
return True
on_stack.remove(v)
return False

g = Graph()
print('cycle')
print('display')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0]
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
else:
elif suboperation == 'edge':
v1 = int(do[2])
v2 = int(do[3])
if v1 not in g:
print('Vertex {} does not exist.'.format(v1))
elif v2 not in g:
print('Vertex {} does not exist.'.format(v2))
else:
if not g.does_edge_exist(v1, v2):
else:

elif operation == 'cycle':
if is_cycle_present(g):
print('Cycle present.')
else:
print('Cycle not present.')

elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()

print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()

elif operation == 'quit':
break```
Program Explanation

1. An instance of Graph is created.
2. A menu is presented to the user to perform various operations on the graph.
3. To determine whether the graph contains a cycle, is_cycle_present is called on the graph.

Runtime Test Cases
```Case 1:
cycle
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add vertex 4
What would you like to do? add vertex 5
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 1 2
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 2 3
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 1 3
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 4 5
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 3 4
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 4 1
What would you like to do? cycle
Cycle present.
What would you like to do? quit

Case 2:
cycle
display
quit
What would you like to do? add vertex 1
What would you like to do? add vertex 2
What would you like to do? add vertex 3
What would you like to do? add edge 1 2
What would you like to do? add edge 3 2
What would you like to do? cycle
Cycle not present.
What would you like to do? add edge 2 3
What would you like to do? cycle
Cycle present.
What would you like to do? quit```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]