-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStronglyConnectedComponents.java
More file actions
152 lines (128 loc) · 4.4 KB
/
Copy pathStronglyConnectedComponents.java
File metadata and controls
152 lines (128 loc) · 4.4 KB
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package CodeJam2008;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import com.google.common.graph.Graphs;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;
/*
* Implementaion of Kosaraju's algorithm to find strongly connected components in a Graph
* wiki :https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
* A strongly connected component of a graph G=(V,E) is Gsc=(Vsc,Esc) such that for each pair of vertices in Gsc (u,v)
* u~v and v~u hat is both u and v are reachable from each other.
* The code uses MutableValueGraph from Google Guava Libraries .
*
* @author: Debapriya Biswas
* */
public class StronglyConnectedComponents {
private static int time = 0;
private Deque<GraphNode> stack = new ArrayDeque<GraphNode>();
private List<HashSet<GraphNode>> components = new ArrayList<HashSet<GraphNode>>();
enum COLOR {
WHITE, GRAY, BLACK
};
// node structure
static class GraphNode {
int d;
int f;
String name;
GraphNode pie = null;
COLOR color;
GraphNode(String name) {
this.name = name;
}
public String toString() {
return name;
}
}
// Implementation of DFS algorithm from CLRS book . The nodes are pushed
// into a stack based on fished time .
private MutableValueGraph<GraphNode, Integer> dfs(MutableValueGraph<GraphNode, Integer> graph) {
for (GraphNode node : graph.nodes())
node.color = COLOR.WHITE;
for (GraphNode node : graph.nodes()) {
if (node.color == COLOR.WHITE)
dfs_visit(graph, node, stack);
}
return graph;
}
private List<HashSet<GraphNode>> dfsOnTranspose(MutableValueGraph<GraphNode, Integer> graph) {
for (GraphNode node : graph.nodes())
node.color = COLOR.WHITE;
while (!stack.isEmpty()) {
GraphNode node = stack.pop();
if (node.color == COLOR.WHITE) {
HashSet<GraphNode> component = new HashSet<GraphNode>();
components.add(dfs_visit_on_transpose(graph, node, component));
}
}
return components;
}
private HashSet<GraphNode> dfs_visit_on_transpose(MutableValueGraph<GraphNode, Integer> graph, GraphNode node,
HashSet<GraphNode> set) {
node.color = COLOR.GRAY;
set.add(node);
node.d = ++time;
for (GraphNode adj : graph.adjacentNodes(node)) {
if (adj.color == COLOR.WHITE && graph.edgeValueOrDefault(node, adj, -1) != null) {
adj.pie = node;
dfs_visit_on_transpose(graph, adj, set);
}
}
node.f = ++time;
node.color = COLOR.BLACK;
stack.push(node);
return set;
}
private void dfs_visit(MutableValueGraph<GraphNode, Integer> graph, GraphNode node, Deque<GraphNode> stack) {
node.color = COLOR.GRAY;
node.d = ++time;
for (GraphNode adj : graph.adjacentNodes(node)) {
if (adj.color == COLOR.WHITE && graph.edgeValueOrDefault(node, adj, -1) != null) {
adj.pie = node;
adj.color = COLOR.GRAY;
dfs_visit(graph, adj, stack);
}
}
node.f = ++time;
node.color = COLOR.BLACK;
stack.push(node);
}
public static void main(String[] args) {
GraphNode A = new GraphNode("A");
GraphNode B = new GraphNode("B");
GraphNode C = new GraphNode("C");
GraphNode D = new GraphNode("D");
GraphNode E = new GraphNode("E");
GraphNode F = new GraphNode("F");
GraphNode G = new GraphNode("G");
GraphNode H = new GraphNode("H");
GraphNode I = new GraphNode("I");
GraphNode J = new GraphNode("J");
GraphNode K = new GraphNode("K");
MutableValueGraph<GraphNode, Integer> graph = ValueGraphBuilder.directed().build();
graph.putEdgeValue(A, B, 1);
graph.putEdgeValue(B, C, 1);
graph.putEdgeValue(C, A, 1);
graph.putEdgeValue(B, D, 1);
graph.putEdgeValue(D, E, 1);
graph.putEdgeValue(E, F, 1);
graph.putEdgeValue(F, D, 1);
graph.putEdgeValue(G, F, 1);
graph.putEdgeValue(G, H, 1);
graph.putEdgeValue(H, I, 1);
graph.putEdgeValue(I, J, 1);
graph.putEdgeValue(J, G, 1);
graph.putEdgeValue(J, K, 1);
// graph.putEdgeValue(G, F, 1);
StronglyConnectedComponents scc = new StronglyConnectedComponents();
// First pass DFS
graph = scc.dfs(graph);
// System.out.println(dfs.stack);
MutableValueGraph<GraphNode, Integer> transposeGraph = Graphs.copyOf(Graphs.transpose(graph));
// Second pass DFS on the transpose graph
System.out.println(scc.dfsOnTranspose(transposeGraph));
}
}