• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.

Top