Computing strongly connected components (SCCs)

Graph.java

package org.coursera.algo;

import java.util.*;

public abstract class Graph<V extends AbstractVertex<E>, E extends AbstractEdge<V>> {

    private final TreeMap<Integer, V> vertices = new TreeMap<Integer, V>(
            new Comparator<Integer>() {
                //for pretty printing
                @Override
                public int compare( Integer arg0, Integer arg1 ) {
                    return arg0.compareTo( arg1 );
                }
            } );

    //need list for random access
    private final List<E> edges = new ArrayList<E>();
    
    private VertexFactory<V, E> f;
    
    public Graph( VertexFactory<V, E> f ) {
        if( f == null )
            throw new IllegalArgumentException( "Vertex factory needs to be specified" );
        this.f = f;
    }
    
    public void addVertex( V v ) {
        vertices.put( v.getLbl(), v );
    }

    public void addEdge( E e ) {
        edges.add( e );
    }
    
    public V getVertex( int lbl ) {
        V v;
        if ( ( v = vertices.get( lbl ) ) == null ) {
            v = f.newInstance( lbl );
            addVertex( v );
        }
        return v;
    }
    
    /**
     * @return the vertices
     */
    public Map<Integer, V> getVertices() {
        return vertices;
    }

    public Map<Integer, V> getVerticesInReversedOrder() {
        return vertices.descendingMap();
    }

    /**
     * @return the edges
     */
    public List<E> getEdges() {
        return edges;
    }

    public void reset() {
        for ( V v : vertices.values() ) {
            v.reset();
        }
    }
    
}

class UndirectedGraph extends Graph<Vertex, Edge> {

    public UndirectedGraph() {
        super( Vertex.getFactory() );
    }
}

class DirectedGraph extends Graph<DirectedVertex, DirectedEdge> {

    public interface EdgeTraversalPolicy {
        public Set<DirectedEdge> edges( DirectedVertex v );
        
        public DirectedVertex vertex( DirectedEdge e );
    }
    
    public final static EdgeTraversalPolicy FORWARD_TRAVERSAL = new EdgeTraversalPolicy() {

        @Override
        public Set<DirectedEdge> edges( DirectedVertex v ) {
            return v.getOutgoingEdges();
        }

        @Override
        public DirectedVertex vertex( DirectedEdge e ) {
            return e.getHead();
        }
    };
    
    public final static EdgeTraversalPolicy BACKWARD_TRAVERSAL = new EdgeTraversalPolicy() {

        @Override
        public Set<DirectedEdge> edges( DirectedVertex v ) {
            return v.getIncomingEdges();
        }

        @Override
        public DirectedVertex vertex( DirectedEdge e ) {
            return e.getTail();
        }
    };
    
    public DirectedGraph() {
        super( DirectedVertex.getFactory() );
    }
}

interface VertexFactory<V extends AbstractVertex<E>, E extends AbstractEdge<V>> {
    public V newInstance( int _lbl );
}

class AbstractVertex<E extends AbstractEdge<? extends AbstractVertex<?>>> {

    private final int lbl;
    private final Set<E> edges = new HashSet<E>();

    public AbstractVertex( int lbl ) {
        this.lbl = lbl;
    }

    public void addEdge( E edge ) {
        edges.add( edge );
    }

    public E getEdgeTo( AbstractVertex<E> v2 ) {
        for ( E edge : edges ) {
            if ( edge.contains( this, v2 ) )
                return edge;
        }
        return null;
    }

    /**
     * @return the lbl
     */
    public int getLbl() {
        return lbl;
    }

    /**
     * @return the edges
     */
    public Set<E> getEdges() {
        return edges;
    }
    
    public void reset() {}
    
    @Override
    public String toString() {
        return Integer.toString( getLbl() );
    }
}

class Vertex extends AbstractVertex<Edge> {

    private final static VertexFactory<Vertex, Edge> factory = new VertexFactory<Vertex, Edge>() {

        @Override
        public Vertex newInstance( int _lbl ) {
            return new Vertex( _lbl );
        }
    };
    
    public Vertex( int lbl ) {
        super( lbl );
    }
    
    public static VertexFactory<Vertex, Edge> getFactory() {
        return factory;
    }

}

class Edge extends AbstractEdge<Vertex> {

    public Edge( Vertex fst, Vertex snd ) {
        super( fst, snd );
    }
    
}

abstract class AbstractEdge<V extends AbstractVertex<? extends AbstractEdge<?>>> {

    private final List<V> ends = new ArrayList<V>();

    public AbstractEdge( V fst, V snd ) {
        if ( fst == null || snd == null ) {
            throw new IllegalArgumentException(
                    "Both vertices are required" );
        }
        ends.add( fst );
        ends.add( snd );
    }

    public boolean contains( AbstractVertex<? extends AbstractEdge<?>> v1, AbstractVertex<? extends AbstractEdge<?>> v2 ) {
        return ends.contains( v1 ) && ends.contains( v2 );
    }

    public V getOppositeVertex( V v ) {
        if ( !ends.contains( v ) ) {
            throw new IllegalArgumentException( "Vertex " + v.getLbl() );
        }
        return ends.get( 1 - ends.indexOf( v ) );
    }

    public void replaceVertex( V oldV, V newV ) {
        if ( !ends.contains( oldV ) ) {
            throw new IllegalArgumentException( "Vertex " + oldV.getLbl() );
        }
        ends.remove( oldV );
        ends.add( newV );
    }
    
    public V getFirst() {
        return ends.get( 0 );
    }
    
    public V getSecond() {
        return ends.get( 1 );
    }
}

class DirectedVertex extends AbstractVertex<DirectedEdge> {
    
    private final static VertexFactory<DirectedVertex, DirectedEdge> factory = new VertexFactory<DirectedVertex, DirectedEdge>() {

        @Override
        public DirectedVertex newInstance( int _lbl ) {
            return new DirectedVertex( _lbl );
        }
    };
    
    private final Set<DirectedEdge> incomingEdges = new HashSet<DirectedEdge>();
    private boolean visited;
    private int f;
    
    public DirectedVertex( int lbl ) {
        super( lbl );
    }
    
    public static VertexFactory<DirectedVertex, DirectedEdge> getFactory() {
        return factory;
    }
    
    public void addIncomingEdge( DirectedEdge e ) {
        incomingEdges.add( e );
    }
    
    public void addOutgoingEdge( DirectedEdge e ) {
        super.addEdge( e );
    }
    
    //this vertex is head
    public Set<DirectedEdge> getIncomingEdges() {
        return incomingEdges;
    }
    
    //this vertex is tail
    public Set<DirectedEdge> getOutgoingEdges() {
        return super.getEdges();
    }
    
    @Override
    public Set<DirectedEdge> getEdges() {
        return getOutgoingEdges();
    }

    /**
     * @return the visited
     */
    public boolean isVisited() {
        return visited;
    }

    /**
     * @param visited the visited to set
     */
    public void setVisited( boolean visited ) {
        this.visited = visited;
    }
    
    @Override
    public void reset() {
        setVisited( false );
    }
    
    public void setF( int f ) {
        this.f = f;
    }
    
    public int getF() {
        return f;
    }
}

class DirectedEdge extends AbstractEdge<DirectedVertex> {
    
    public DirectedEdge( DirectedVertex tail, DirectedVertex head ) {
        super( tail, head );
    }
    
    public DirectedVertex getTail() {
        return getFirst();
    }
    
    public DirectedVertex getHead() {
        return getSecond();
    }
}

/* ٩(͡๏̯͡๏)۶ */

KosarajuSCC.java

package org.coursera.algo;

import java.io.*;
import java.util.*;
import java.util.zip.*;

import org.coursera.algo.DirectedGraph.EdgeTraversalPolicy;

/**
 * https://class.coursera.org/algo/quiz/attempt?quiz_id=57
 * 
 * Reads the graph directly from the zip file
 */
public class KosarajuSCC {
    
    private static int t;
    private static ArrayList<Integer> scc = new ArrayList<Integer>();
    private static int pass = 0;
    
    private static void dfsLoop( DirectedGraph gr, EdgeTraversalPolicy tp ) {
        t = 0;
        
        Collection<DirectedVertex> vs; 
        if( pass == 0 ) 
            vs = gr.getVerticesInReversedOrder().values();
        else {
            vs = new TreeSet<DirectedVertex>(new Comparator<DirectedVertex>() {
                @Override
                public int compare( DirectedVertex v1, DirectedVertex v2 ) {
                    return new Integer( v2.getF() ).compareTo( v1.getF() );
                }
            });
            vs.addAll( gr.getVertices().values() );
        }
        
        for ( DirectedVertex v : vs ) {
            if( !v.isVisited() ) {
                
                dfs( tp, v );
                
                if( pass == 1 ) {
                    scc.add( t );
                    t = 0;
                }
            }
        }
        
        pass++;
    }
    
    private static void dfs( EdgeTraversalPolicy tp, DirectedVertex v ) {
        
        v.setVisited( true );
        
        for ( DirectedEdge edge : tp.edges( v ) ) {
            DirectedVertex next = tp.vertex( edge );
            if( !next.isVisited() )
                dfs( tp, next );
        }
        t++;
        if( pass == 0 ) {
            v.setF( t );
        }
    }
    
    private static DirectedGraph readGraph( InputStream is ) throws FileNotFoundException {
        Scanner sc = new Scanner( is );
        DirectedGraph gr = new DirectedGraph();
        while( sc.hasNext() ) {
            addEdge( gr, sc.nextInt(), sc.nextInt() );
        }
        sc.close();
        
        return gr;
    }
    
    private static void addEdge( DirectedGraph gr, int tailId, int headId ) {
        DirectedVertex tail = gr.getVertex( tailId );
        DirectedVertex head = gr.getVertex( headId );
        DirectedEdge edge = new DirectedEdge( tail, head );
        gr.addEdge( edge );
        tail.addOutgoingEdge( edge );
        head.addIncomingEdge( edge );
    }

    private static void test( DirectedGraph gr ) {
        System.out.println("First pass:");
        dfsLoop( gr, DirectedGraph.BACKWARD_TRAVERSAL );
        
        gr.reset();
        System.out.println("Second pass:");
        dfsLoop( gr, DirectedGraph.FORWARD_TRAVERSAL );
        
        int count = 0;
        Collections.sort( scc );
        for( int i = scc.size()-1; i >= 0; i-- ) {
            if( count >= 5 ) break;
            System.out.println("ssc:" + scc.get( i ));
            count++;
        }
        
        cleanup();
    }

    private static void cleanup() {
        t = 0;
        pass = 0;
        scc.clear();
    }
    
    private static DirectedGraph example1() {
        DirectedGraph gr = new DirectedGraph();
        addEdge( gr, 1, 2 );
        addEdge( gr, 1, 3 );
        addEdge( gr, 3, 4 );
        addEdge( gr, 2, 4 );
        return gr;
    }

    private static DirectedGraph example2() {
        DirectedGraph gr = new DirectedGraph();
        addEdge( gr, 1, 4 );
        addEdge( gr, 2, 8 );
        addEdge( gr, 3, 6 );
        addEdge( gr, 4, 7 );
        addEdge( gr, 5, 2 );
        addEdge( gr, 6, 9 );
        addEdge( gr, 7, 1 );
        addEdge( gr, 8, 5 );
        addEdge( gr, 8, 6 );
        addEdge( gr, 9, 3 );
        addEdge( gr, 9, 7 );
        return gr;
    }

    private static DirectedGraph example3()
            throws Exception {
        
        long start = System.currentTimeMillis();
        ZipFile zf = new ZipFile( "src/org/coursera/algo/SCC.zip" );
        DirectedGraph g = readGraph( zf.getInputStream( zf.getEntry( "SCC.txt" ) ) );
        
        System.out.println( "Read from ZIP: " + ( System.currentTimeMillis() - start ) );
        System.out.println( "Graph: " + g.getVertices().size() + " vertices, "
                + g.getEdges().size() + " edges." );
        return g;
    }
    
    /**
     * @param args
     * @throws IOException 
     */
    public static void main( String[] args ) throws Exception {
        
         test(example1());
         test(example2());
         test(example3());
    }

}

If you have no time to refactor the code, then these VM's options will do the trick:
-Xmx2g -Xss2g -Xms2g -XX:-UseGCOverheadLimit

Could anyone please post the output of this code. Its not getting executed in my IDE.