algorithms-in-python/graph/tarjan-algorithm.py at 15151d37aeb9a0f1cca3d016bb2d3237c05895e8 · harrypotter0/algorithms-in-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from collections import defaultdict
class Graph:

	def __init__(self,vertices):
		self.V= vertices

		self.graph = defaultdict(list)

		self.Time = 0

	def addEdge(self,u,v):
		self.graph[u].append(v)

	def SCCUtil(self,u, low, disc, stackMember, st):

		disc[u] = self.Time
		low[u] = self.Time
		self.Time += 1
		stackMember[u] = True
		st.append(u)

		for v in self.graph[u]:

			if disc[v] == -1 :

				self.SCCUtil(v, low, disc, stackMember, st)

				low[u] = min(low[u], low[v])

			elif stackMember[v] == True:

				low[u] = min(low[u], disc[v])

		w = -1 #To store stack extracted vertices
		if low[u] == disc[u]:
			while w != u:
				w = st.pop()
				print w,
				stackMember[w] = False

			print""

	def SCC(self):

		disc = [-1] * (self.V)
		low = [-1] * (self.V)
		stackMember = [False] * (self.V)
		st =[]

		for i in range(self.V):
			if disc[i] == -1:
				self.SCCUtil(i, low, disc, stackMember, st)


# Create a graph given in the above diagram
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
print "SSC in first graph "
g1.SCC()

g2 = Graph(4)
g2.addEdge(0, 1)
g2.addEdge(1, 2)
g2.addEdge(2, 3)
print "nSSC in second graph "
g2.SCC()


g3 = Graph(7)
g3.addEdge(0, 1)
g3.addEdge(1, 2)
g3.addEdge(2, 0)
g3.addEdge(1, 3)
g3.addEdge(1, 4)
g3.addEdge(1, 6)
g3.addEdge(3, 5)
g3.addEdge(4, 5)
print "nSSC in third graph "
g3.SCC()

g4 = Graph(11)
g4.addEdge(0, 1)
g4.addEdge(0, 3)
g4.addEdge(1, 2)
g4.addEdge(1, 4)
g4.addEdge(2, 0)
g4.addEdge(2, 6)
g4.addEdge(3, 2)
g4.addEdge(4, 5)
g4.addEdge(4, 6)
g4.addEdge(5, 6)
g4.addEdge(5, 7)
g4.addEdge(5, 8)
g4.addEdge(5, 9)
g4.addEdge(6, 4)
g4.addEdge(7, 9)
g4.addEdge(8, 9)
g4.addEdge(9, 8)
print "nSSC in fourth graph "
g4.SCC();


g5 = Graph (5)
g5.addEdge(0, 1)
g5.addEdge(1, 2)
g5.addEdge(2, 3)
g5.addEdge(2, 4)
g5.addEdge(3, 0)
g5.addEdge(4, 2)
print "nSSC in fifth graph "
g5.SCC();