PythonAlgorithms/StrongConCom.py at master · IKMalik/PythonAlgorithms · 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
class Graph:

    def __init__(self):

        self.graph = {}

    def addEdge(self,u,v):
        if u not in self.graph:
          self.graph[u] = []
        if v not in self.graph:
          self.graph[v] = []

        self.graph[u].append(v)

    def printscc(self):

      visited = set()
      stack = []

      for vertex in self.graph:
        if vertex not in visited:
          self._dfs(vertex, visited, stack)

      gr = self._invertgraph()

      visited.clear()

      print('finding scc \n')
      while stack:
          curr = stack.pop()
          if curr not in visited:
            gr._getscc(curr, visited)
            print("")

    def _dfs(self, vertex, visited, stack):

      visited.add(vertex)
      for neighbour in self.graph[vertex]:
        if neighbour not in visited:
          self._dfs(neighbour, visited, stack)
      stack.append(vertex)

    def _getscc(self, curr, visited):

      visited.add(curr)
      print(curr)
      for neighbour in self.graph[curr]:
        if neighbour not in visited:
          self._getscc(neighbour, visited)

    def _invertgraph(self):

      gr = Graph()
      print(self.graph)
      for vertex in self.graph:
        for neighbour in self.graph[vertex]:
          gr.addEdge(neighbour, vertex)
      return gr


g = Graph()
g.addEdge(1, 0)
g.addEdge(0, 2)
g.addEdge(2, 1)
g.addEdge(0, 3)
g.addEdge(3, 4)
g.printscc()