Kosaraju's algorithm to find Strongly Connected Components

ComputeSCC.java

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());
        }
    }
}

ComputeSCCTest.java

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);
    }
}

testGraph_1.txt

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

testGraph_2.txt

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

Vertex.java

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;
    }
}