Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Kosaraju's algorithm to find Strongly Connected Components
package compute_strongly_connected_components;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
public class ComputeSCC {
private int time = 0;
private int s = 0;
private HashMap<Integer, Iterator<Vertex>> iterMap;
private boolean secondIterationFlag = false;
public int[] sccSizeArray;
public void computeSCCs(ArrayList<Vertex> graph) {
if (graph == null) {
throw new IllegalArgumentException("Graph is null");
}
ArrayList<Vertex> reversedGraph = computeReverseGraph(graph);
sccSizeArray = new int[graph.size()];
// first iteration on reversed graph
dfsLoop(reversedGraph);
secondIterationFlag = true;
graph = adjustGraph(graph, reversedGraph);
time = 0;
// second iteration on original graph
dfsLoop(graph);
Arrays.sort(sccSizeArray);
}
/**
* switch finishing times with vertex numbers of the graph
*
* @param graph
* @param reversedGraph
* @return
*/
private ArrayList<Vertex> adjustGraph(ArrayList<Vertex> graph, ArrayList<Vertex> reversedGraph) {
Vertex[] verArray = new Vertex[graph.size()];
for (int i = 0; i < graph.size(); i++) {
graph.get(i).setId(reversedGraph.get(i).getFinishedTime());
verArray[graph.get(i).getId() - 1] = graph.get(i);
}
return new ArrayList<>(Arrays.asList(verArray));
}
/**
* computes and returns the reversed version of send graph
*
* @param graph
* @return
*/
private ArrayList<Vertex> computeReverseGraph(ArrayList<Vertex> graph) {
ArrayList<Vertex> reversedGraph = new ArrayList<>();
// deep copy the graph
for (Vertex vertex : graph) {
reversedGraph.add(new Vertex(vertex.getId()));
}
// adjust adjacency list as reversed
for (Vertex v1 : reversedGraph) {
ArrayList<Vertex> adjList = new ArrayList<>();
for (Vertex v2 : graph) {
for (Vertex adjV : v2.getAdjList()) {
if (adjV.getId() == v1.getId()) {
adjList.add(reversedGraph.get(v2.getId() - 1));
}
}
}
v1.setAdjList(adjList);
}
return reversedGraph;
}
private void dfsLoop(ArrayList<Vertex> graph) {
initHashMap(graph);
for (int i = graph.size() - 1; i >= 0; i--) {
if (!graph.get(i).isExplored()) {
if (secondIterationFlag) {
s = i + 1;
}
dfs(graph, graph.get(i));
}
}
}
private void dfs(ArrayList<Vertex> graph, Vertex source) {
Stack<Vertex> stack = new Stack<>();
source.setExplored(true);
if (secondIterationFlag) {
source.setLeader(graph.get(s - 1));
sccSizeArray[graph.get(s - 1).getId() - 1]++;
}
stack.push(source);
while (!stack.isEmpty()) {
Vertex peek = stack.peek();
Iterator<Vertex> iter = iterMap.get(peek.getId());
if (iter.hasNext()) {
Vertex adjVertex = iter.next();
if (!adjVertex.isExplored()) {
if (secondIterationFlag) {
adjVertex.setLeader(graph.get(s - 1));
sccSizeArray[graph.get(s - 1).getId() - 1]++;
}
adjVertex.setExplored(true);
stack.push(adjVertex);
}
} else {
time = time + 1;
peek.setFinishedTime(time);
stack.pop();
}
}
}
private void initHashMap(ArrayList<Vertex> graph) {
iterMap = new HashMap<>();
for (Vertex vertex : graph) {
iterMap.put(vertex.getId(), vertex.getAdjList().iterator());
}
}
}
package compute_strongly_connected_components;
import static org.junit.Assert.assertEquals;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
public class ComputeSCCTest {
private ArrayList<Vertex> graph;
private ComputeSCC testClass;
private BufferedReader reader;
private static final String FILE_1 = "src/test/resources/computescctextfiles/testGraph_1.txt";
private static final String FILE_2 = "src/test/resources/computescctextfiles/testGraph_2.txt";
@Before
public void setUp() {
graph = new ArrayList<>();
testClass = new ComputeSCC();
}
@Test(expected = IllegalArgumentException.class)
public void testNullGraph() {
testClass.computeSCCs(null);
}
@Test
public void testFirstGraph() {
initGraph();
testClass.computeSCCs(graph);
assertEquals(3, testClass.sccSizeArray[graph.size() - 1]);
assertEquals(3, testClass.sccSizeArray[graph.size() - 2]);
assertEquals(3, testClass.sccSizeArray[graph.size() - 3]);
}
@Test
public void testSecondGraph() throws NumberFormatException, IOException {
reader = new BufferedReader(new FileReader(new File(FILE_1)));
String line = null;
for (int i = 0; i < 8; i++) {
graph.add(new Vertex(i + 1));
}
while ((line = reader.readLine()) != null) {
String[] split = line.split("\\s+");
int from = Integer.parseInt(split[0]);
int to = Integer.parseInt(split[1]);
graph.get(from - 1).getAdjList().add(graph.get(to - 1));
}
testClass.computeSCCs(graph);
assertEquals(3, testClass.sccSizeArray[graph.size() - 1]);
assertEquals(3, testClass.sccSizeArray[graph.size() - 2]);
assertEquals(2, testClass.sccSizeArray[graph.size() - 3]);
}
@Test
public void testThirdGraph() throws NumberFormatException, IOException {
reader = new BufferedReader(new FileReader(new File(FILE_2)));
String line = null;
for (int i = 0; i < 12; i++) {
graph.add(new Vertex(i + 1));
}
while ((line = reader.readLine()) != null) {
String[] split = line.split("\\s+");
int from = Integer.parseInt(split[0]);
int to = Integer.parseInt(split[1]);
graph.get(from - 1).getAdjList().add(graph.get(to - 1));
}
testClass.computeSCCs(graph);
assertEquals(6, testClass.sccSizeArray[graph.size() - 1]);
assertEquals(3, testClass.sccSizeArray[graph.size() - 2]);
assertEquals(2, testClass.sccSizeArray[graph.size() - 3]);
assertEquals(1, testClass.sccSizeArray[graph.size() - 4]);
}
private void initGraph() {
Vertex one = new Vertex(1);
Vertex two = new Vertex(2);
Vertex three = new Vertex(3);
Vertex four = new Vertex(4);
Vertex five = new Vertex(5);
Vertex six = new Vertex(6);
Vertex seven = new Vertex(7);
Vertex eight = new Vertex(8);
Vertex nine = new Vertex(9);
one.setAdjList(new ArrayList<Vertex>(Arrays.asList(four)));
two.setAdjList(new ArrayList<Vertex>(Arrays.asList(eight)));
three.setAdjList(new ArrayList<Vertex>(Arrays.asList(six)));
four.setAdjList(new ArrayList<Vertex>(Arrays.asList(seven)));
five.setAdjList(new ArrayList<Vertex>(Arrays.asList(two)));
six.setAdjList(new ArrayList<Vertex>(Arrays.asList(nine)));
seven.setAdjList(new ArrayList<Vertex>(Arrays.asList(one)));
eight.setAdjList(new ArrayList<Vertex>(Arrays.asList(five, six)));
nine.setAdjList(new ArrayList<Vertex>(Arrays.asList(three, seven)));
graph.add(one);
graph.add(two);
graph.add(three);
graph.add(four);
graph.add(five);
graph.add(six);
graph.add(seven);
graph.add(eight);
graph.add(nine);
}
}
1 2
2 6
2 3
2 4
3 1
3 4
4 5
5 4
6 5
6 7
7 6
7 8
8 5
8 7
1 2
2 3
2 4
2 5
3 6
4 5
4 7
5 2
5 6
5 7
6 3
6 8
7 8
7 10
8 7
9 7
10 9
10 11
11 12
12 10
package compute_strongly_connected_components;
import java.util.ArrayList;
public class Vertex {
private boolean explored;
private ArrayList<Vertex> adjList;
private int id;
private int finishedTime;
private Vertex leader;
public Vertex(int label) {
this.adjList = new ArrayList<>();
this.id = label;
}
public boolean isExplored() {
return explored;
}
public void setExplored(boolean explored) {
this.explored = explored;
}
public ArrayList<Vertex> getAdjList() {
return adjList;
}
public void setAdjList(ArrayList<Vertex> adjList) {
this.adjList = adjList;
}
public int getFinishedTime() {
return finishedTime;
}
public void setFinishedTime(int finishedTime) {
this.finishedTime = finishedTime;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public Vertex getLeader() {
return leader;
}
public void setLeader(Vertex leader) {
this.leader = leader;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment