3
\$\begingroup\$

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
# weighted tree balancing added


from collections import defaultdict
class graph:

  def __init__(self):

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

  def addnode(self, key1, key2, edge=0):
    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() 
g.addnode(0, 1)  
g.addnode(2, 3) 
g.addnode(4,2)
g.addnode(4,1)

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

1 Answer 1

Reset to default
3
\$\begingroup\$

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()
    g.addnode(0, 1)
    # ...

PEP8

Follow the PEP8 standard guidelines. Put a space after all commas, don’t put a space before the parentheses in function calls. Use an automatic checker (pylint, pyflakes, ...) to ensure you don’t violate these guidelines.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.