# Find cycles in Graph using Union Find Algorithm on Adjacency List

My code detects if a cycle is present in a graph using Union find algorithm with Weighted tree analysis and path compression.

It works and I have included test cases.

# check cycles in graph using union find

from collections import defaultdict
class graph:

def __init__(self):

self.graph = defaultdict(list)
self.parents = {}
self.size = {}

if key2 not in self.graph:
self.graph[key2] = []

self.graph[key1].append(key2)

def findcycle(self):

for key in self.graph:
self.parents[key] = -1
self.size[key] = 1

for vertex in self.graph:
for neighbour in self.graph[vertex]:
x_par = self.getparent(vertex)
y_par = self.getparent(neighbour)
if x_par == y_par:
return True
self.union(x_par, y_par)

def getparent(self, vertex):

while self.parents[vertex] != -1:
vertex = self.parents[vertex]

return vertex

def union(self, vertex, neighbour):

x_par = self.getparent(vertex)
y_par = self.getparent(neighbour)
if self.size[x_par] <= self.size[y_par]:
self.parents[x_par] = y_par
self.size[y_par] += self.size[x_par]
else:
self.parents[y_par] = x_par
self.size[x_par] += self.size[y_par]

g = graph()

if g.findcycle():
print ("Graph contains cycle")
else :
print ("Graph does not contain cycle ")


## addnode(self, key1, key2, edge=0)

The parameter edge is not used. Either remove it, or use it, but keeping it with a default value and not using it is obfuscation.

self.graph is a defaultdict(list), so testing if key2 is not present, and setting that key’s value to an empty list if it isn’t present, which is the raison d’être for the defaultdict(list), isn’t using that class properly. You want the key to exist, but don’t want to add any values to it. Simply use:

_ = self.graph[key2]


## findcycle(self)

This function returns True or None. It would be much easier to write documentation for the function if it returned only one “kind” of value. Add return False to the end of the function.

## Test cases

Put your test cases inside a __name__ == '__main__' guard. Then you can import this as a module into another file without the tests running, but running this file by itself will still execute the tests.

if __name__ == '__main__':
g = graph()