import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
class KosarajuSharirSCC {
private boolean[] visited; // visited[v] = true if v connected to s
private int[] scc; // id[v] = id of component containing v
private int count;
/** find connected components in G */
public KosarajuSharirSCC(Digraph G) {
// initialize data structures
this.visited = new boolean[G.V()];
this.scc = new int[G.V()];
this.count = 0; // number of components
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G.reverse());
// run DFS from for topological order of depthFirstOrder.reversePost
Stack reversePost_copy = depthFirstOrder.reversePost();
while(!reversePost_copy.isEmpty()) {
int v = reversePost_copy.pop();
if(!visited[v]) {
dfs(G, v);
count++;
}
}
}
/** are v and w connected? */
boolean isStronglyConnected(int v, int w) {
return scc[v] == scc[w];
}
/** number of connected components */
int count() {
return count;
}
/** component identifier for v */
int id(int v) {
return scc[v];
}
private void dfs(Digraph G, int v) {
// all vertices discovered in same call of dfs have same id
visited[v] = true;
scc[v] = count;
for (int w : G.adj(v)) {
if(!visited[w]) {
dfs(G, w);
}
}
}
private static class DepthFirstOrder {
private boolean[] visited; // visited[v] = true if v connected to s
private Stack reversePost; // all vertices in reverse DFS porst order
public DepthFirstOrder(Digraph G) {
// initialize data structures
this.visited = new boolean[G.V()];
this.reversePost = new Stack<>();
for(int v = 0; v < G.V(); v++) {
if(!visited[v]) {
dfs(G, v);
}
}
}
// is there a path from s to v?
public boolean isVisited(int v) {
return visited[v];
}
private void dfs(Digraph G, int v) {
// recursive DFS does the work
visited[v] = true;
for (int w : G.adj(v))
if(!visited[w])
dfs(G, w);
reversePost.push(v);
}
/** returns all vertices in “reverse DFS postorder” */
public Stack reversePost() {
return reversePost;
}
}
private static class Digraph {
private final int V; // number of vertices
private final List[] adj; // adjacency lists... 0 to V-1
/** create an empty digraph with V vertices */
public Digraph(int V) {
this.V = V;
this.adj = new ArrayList[V]; // create empty graph with V vertices
for(int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
/** add a directed edge v→w */
public void addEdge(int v, int w) {
// add edge v-w
adj[v].add(w);
}
/** Iterator for vertices pointing from v */
public Iterable adj(int v) {
return adj[v];
}
/** number of vertices */
public int V() {
return V;
}
/** number of edges */
public int E() {
int countEdges = 0;
for(int v = 0; v < V; v++) {
countEdges += adj[v].size();
}
return countEdges;
}
/** reverse of this digraph */
Digraph reverse() {
Digraph reverseDigraph = new Digraph(V);
for(int v = 0; v < V; v++) {
for(int w : adj(v)) {
reverseDigraph.addEdge(w, v);
}
}
return reverseDigraph;
}
/** string representation */
public String toString() {
return "TODO";
}
static Digraph prepareGraph() {
int[][] edges = new int[][] {
{0, 5}, {0, 1},
{2, 0}, {2, 3},
{3, 5}, {3, 2},
{4, 3}, {4, 2},
{5, 4},
{6, 0}, {6, 4}, {6, 8}, {6, 9},
{7, 6}, {7, 9},
{8, 6},
{9, 10}, {9, 11},
{10, 12},
{11, 4}, {11, 12},
{12, 9}
};
Digraph G = new Digraph(13);
// add all edges
for(int i = 0; i < edges.length; i++) {
int v = edges[i][0];
int w = edges[i][1];
G.addEdge(v, w);
}
return G;
}
}
public static void main (String[] args) {
System.out.println("Test strongly connected components ");
KosarajuSharirSCC stronglyConnectedComponent = new KosarajuSharirSCC(Digraph.prepareGraph());
System.out.println("Number of connected components: " + stronglyConnectedComponent.count());
System.out.println("Id of 1 = " + stronglyConnectedComponent.id(1));
System.out.println("Id of 0 = " + stronglyConnectedComponent.id(0));
System.out.println("Id of 11 = " + stronglyConnectedComponent.id(11));
System.out.println("Id of 6 = " + stronglyConnectedComponent.id(6));
System.out.println("Id of 7 = " + stronglyConnectedComponent.id(7));
System.out.println("Is 0 & 1 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(0, 1)); // false
System.out.println("Is 2 & 5 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(2, 5)); // true
System.out.println("Is 2 & 6 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(2, 6)); // false
System.out.println("Is 6 & 8 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(6, 8)); // true
System.out.println("Is 12 & 9 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(12, 9)); // true
System.out.println("Is 10 & 7 isStronglyConnected? " + stronglyConnectedComponent.isStronglyConnected(10, 7)); // false
}
}
Output
Test strongly connected components
Number of connected components: 5
Id of 1 = 0
Id of 0 = 1
Id of 11 = 2
Id of 6 = 3
Id of 7 = 4
Is 0 & 1 isStronglyConnected? false
Is 2 & 5 isStronglyConnected? true
Is 2 & 6 isStronglyConnected? false
Is 6 & 8 isStronglyConnected? true
Is 12 & 9 isStronglyConnected? true
Is 10 & 7 isStronglyConnected? false
Comments
Post a Comment