-
Notifications
You must be signed in to change notification settings - Fork 0
/
scc_directed_graph.py
74 lines (53 loc) · 1.58 KB
/
scc_directed_graph.py
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
def dfs_comp(graph, start, visited):
component = [start]
visited.add(start)
for adj in graph[start]:
if adj not in visited:
component += dfs_comp(graph, adj, visited)
return component
def dfs_sort(graph, start, visited):
order = []
visited.add(start)
for adj in graph[start]:
if adj not in visited:
order += dfs_sort(graph, adj, visited)
return order + [start]
def topological_sorting(graph, start = None):
visited = set()
order = []
if start:
order += dfs_sort(graph, start, visited)
for vertex in graph.keys():
if vertex not in visited:
order += dfs_sort(graph, vertex, visited)
return order[::-1]
def transpose(graph):
transpose = {node: [] for node in graph}
for node in graph:
for adj in graph[node]:
transpose[adj].append(node)
return transpose
def scc_directed_graph(graph):
topological_order = topological_sorting(graph)
graphT = transpose(graph)
components = []
visited = set()
for vertex in topological_order:
if vertex not in visited:
components.append(dfs_comp(graphT, vertex, visited))
return components
# Example
graph = {
"s": ["w", "v", "t"],
"w": ["x"],
"r": ["s"],
"v": ["r", "w"],
"t": ["u", "x"],
"x": ["w", "y"],
"u": ["t", "y"],
"y": ["y"]
}
components = scc_directed_graph(graph)
print("\nComponents:")
for component in components:
print(*component)