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

}

Thanks for the code, but I was having trouble with it (StackOverflow), so I made some changes on it to use interative mode. Try it! =)

Thanks you,
Montolide please could you tell me how you get out to StackOverflow problem? Thank you

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.