#5. Strongly Connected Component

  1. What is connected graph ?

    • A graph is connected if there is a path between each pair of vertices.
  2. What is strongly connected graph ?

    • A directed graph is strongly connected iff there is a path between each pair of vertices.
    • Strongly connected的概念只存在于Directed Graph

[Notes]

Strongly connected components in G are the same as they are in reversed G!

#5.1 Kosaraju’s Algorithm

  • Algorithm:
    1. Topological sort on reversed G!
    2. Run DFS based on the order from step 1

#Proof of Kosaraju’s Algorithm:

  1. What is Kernel DAG?

    • Kernel DAG是将一个graph里的每个strongly connected component变成一个vertex, 然后把所有这些SCCs给连起来. 得到的结果一定是一个DAG. 比如Tushar视频里的这个图:
      • Reference: Strongly Connected Components Kosaraju’s Algorithm Graph Algorithm from Tushar Roy
    • 4个SCCs连起来的一定是一个DAG. 假设有一条边从(DEF)到(ABC),那么很容易证明(ABCDEF)是一个SCC而不是两个.
  2. Why Kernal DAG ?

Kernel DAG解释了为什么我们要先把G到倒过来求topological order.

  • 用上图的例子来看, 这个order保证了在第二遍找SCCs的DFS的时候我们会从(DEF)中任何一个结点或者(K)来开始DFS, 假设从(DEF)中任何一个结点开始, 根据上面的图很显然我们没有办法走到ABC或者GHIJ. 假设从K开始也很显然没有办法走到GHIJ.
  • 这样就能找到(DEF)和(K)两个strongly connected component. 接下来无论从(ABC)还是(GHIJ)中任意一个结点开始都能顺利找到自己的strongly connected component. 这样就证明了这个算法的可行性.

Java Kosaraju’a Algorithm

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
public class StronglyConnectedComponent {
public static List<Set<Integer>> scc(final Map<Integer, Set<Integer>> graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
final List<Set<Integer>> res = new ArrayList<>();
final Map<Integer, Set<Integer>> reversedGraph = reverseGraph(graph);
final List<Integer> sorted = TopologicalSort.topoDFS(graph);
final Set<Integer> visited = new HashSet<>();
for (final int v : sorted) {
if (!visited.contains(v)) {
final Set<Integer> currentComponent = new HashSet<>();
getSCCByDFS(v, graph, visited, currentComponent);
res.add(new HashSet<>(currentComponent));
}
}
return res;
}
private static Map<Integer, Set<Integer>> reverseGraph(final Map<Integer, Set<Integer>> graph) {
final Map<Integer, Set<Integer>> reversedGraph = new HashMap<>();
for (final int v : graph.keySet()) {
reversedGraph.putIfAbsent(v, new HashSet<>());
for (final int adj : graph.get(v)) {
reversedGraph.putIfAbsent(adj, new HashSet<>());
reversedGraph.get(adj).add(v);
}
}
return reversedGraph;
}
private static void getSCCByDFS(final int v, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final Set<Integer> scc) {
scc.add(v);
visited.add(v);
for (final int adj : graph.keySet()) {
if (!visited.contains(adj)) {
scc.add(adj);
visited.add(adj);
getSCCByDFS(adj, graph, visited, scc);
}
}
}
}

Python Kosaraju’s Algorithm

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
# Problem: Find strongly connected component in a directed graph
# Algorithm
# 1. Reverse the given graph
# 2. Run topologoical sort on the reversed graph
# 3. Run dfs on the original graph, based on the topological order on the reversed graph
import toposort
def kosaraju(graph):
"""
:type graph: Dict[int, List[int]]
:rtype: List[tuple(int)], a list of tuples, each tuple is a strongly connected component
"""
if not graph:
raise Exception("invalid graph")
reversed_graph = reverse(graph)
order = toposort.topo_sort_dfs(graph)
res = []
visited = set()
for v in order:
if v not in visited:
scc = []
dfs(v, graph, visited, scc)
res.append(tuple(scc))
return res
def dfs(v, graph, visited, scc):
"""
:type v: int
:type graph: Dict[int, List[int]]
:type visited: Set[int]
:type scc: List[int]
"""
visited.add(v)
scc.append(v)
for adj in graph[v]:
if adj not in visited:
dfs(adj, graph, visited, scc)
# Reverse a directed graph
def reverse(graph):
"""
:type graph: Dict[int, List[int]]
:rtype: Dict[int, List[int]]
"""
res = {}
if not graph:
return res
for v in graph:
for adj in graph[v]:
if adj not in res:
res[adj] = []
res[adj].append(v)
return res

#5.2 Tarjan’s Algorithm

  1. What is low-link value?

    • Low-link value: low-link value of a node is the smallest node id reachable from that node when doing a dfs, including itself.

  2. How to update low-link value to find Strongly Connected Component?

    • If there is an edge from v to w in the graph, to update the low-link value of v by lowlink[v] = min(lowlink[v], lowlink[w]), the following 2 conditions must be met in order to find the strongly connected component:
      1. there is a path from v to w
      2. w must be on the stack
    • If a node v is the starting point of a strongly connected component, then it’s id(v) == lowlink(v)
  3. Algorithms:

    1. Maintains a stack, node is added to the stack when they’re visited the first time
    2. Nodes are removed from the stack when a complete SCC is found
    3. If (v, w) is an edge in the graph, to update lowlink value of v, w must be on the stack.
    4. If a node is the starting point the a SCC, it’s value (or id) must be equal to it’s lowlink value

Python Tarjan’s Algorithm

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
# Problem: Tarjan's alogrithm is used to find strongly connected component in a directed graph
# Alogorithm:
# 1. maintains a stack, node is added to the stack when they're explored the first time
# 2. nodes are removed from the stack when a complete SCC is found
# 3. if (u, v) is an edge in the graph, to update lowlink value of u, v must be on the stack.
# 4. if a node is the starting point the a SCC, it's value (or id) must be equal to it's lowlink value
def tarjan(graph):
"""
:type graph: Dict[int, Dict[int]]
:rtype: List[tuple(int)], list of tuples, each tuple is a strongly connected component
"""
if not graph:
raise Exception("invalid graph")
res = []
stack = []
on_stack = set()
visited = set()
nodes = set()
lowlink = {}
for v in graph:
for w in graph[v]:
nodes.add(v)
nodes.add(w)
lowlink[v] = v
lowlink[w] = w
for v in nodes:
if v not in visited:
dfs(v, graph, stack, on_stack, lowlink, visited, res)
return res
def dfs(v, graph, stack, on_stack, lowlink, visited, res):
"""
:type v: int
:type graph: Dict[int, Dict[int]]
:type stack: List[int]
:type on_stack: Set[int]
:type lowlink: Dict[int, int]
:type visited: Set[int]
:type res: List[tuple(int)]
"""
visited.add(v)
stack.append(v)
on_stack.add(v)
for adj in graph[v]:
if adj not in visited:
dfs(adj, graph, stack, lowlink, visited, res)
if adj in on_stack:
lowlink[v] = min(lowlink[v], lowlink[adj])
# Find a SCC
if lowlink[v] == v:
scc = []
while stack:
top = stack.pop()
on_stack.remove(top)
scc.append(top)
if top == v:
break
res.append(tuple(scc))

Comments

01/03/2020