SHARE
TWEET

Untitled

a guest Jul 16th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # check cycles in graph using union find
  2. # weighted tree balancing added
  3.  
  4.  
  5. from collections import defaultdict
  6. class graph:
  7.  
  8.   def __init__(self):
  9.  
  10.     self.graph = defaultdict(list)
  11.     self.parents = {}
  12.     self.size = {}
  13.  
  14.   def addnode(self, key1, key2, edge=0):
  15.     if key2 not in self.graph:
  16.       self.graph[key2] = []
  17.  
  18.     self.graph[key1].append(key2)
  19.  
  20.   def findcycle(self):
  21.  
  22.  
  23.     for key in self.graph:
  24.       self.parents[key] = -1
  25.       self.size[key] = 1
  26.  
  27.  
  28.     for vertex in self.graph:
  29.       for neighbour in self.graph[vertex]:
  30.         x_par = self.getparent(vertex)
  31.         y_par = self.getparent(neighbour)
  32.         if x_par == y_par:
  33.           return True
  34.         self.union(x_par, y_par)
  35.  
  36.  
  37.   def getparent(self, vertex):
  38.  
  39.     while self.parents[vertex] != -1:
  40.       vertex = self.parents[vertex]
  41.  
  42.     return vertex
  43.  
  44.  
  45.   def union(self, vertex, neighbour):
  46.  
  47.     x_par = self.getparent(vertex)
  48.     y_par = self.getparent(neighbour)
  49.     if self.size[x_par] <= self.size[y_par]:
  50.       self.parents[x_par] = y_par
  51.       self.size[y_par] += self.size[x_par]
  52.     else:
  53.       self.parents[y_par] = x_par
  54.       self.size[x_par] += self.size[y_par]
  55.  
  56. g = graph()
  57. g.addnode(0, 1)  
  58. g.addnode(2, 3)
  59. g.addnode(4,2)
  60. g.addnode(4,1)
  61.  
  62. if g.findcycle():
  63.     print ("Graph contains cycle")
  64. else :
  65.     print ("Graph does not contain cycle ")
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top