Class StrongComponentProcessor - SpartanRefactoring/Main GitHub Wiki

public class StrongComponentProcessor<Data> extends EmptyProcessor<Data, Graph<Component<Data>>> { 
    /*
     * Forge (1)
     */
        StrongComponentProcessor(); 
    /*
     * Type (6)
     */
        void before(Graph<Data> g); 
        void before(Vertex<Data> v); 
        void after(Vertex<Data> from, Vertex<Data> to); 
        void revisit(Vertex<Data> from, Vertex<Data> to); 
        void after(Vertex<Data> v); 
        Graph<Component<Data>> after(Graph<Data> _); 
} 

// SSDLPedia
package il.ac.technion.cs.cs236700.graph;

import static java.lang.Math.min;
import il.ac.technion.cs.cs236700.graph.Graph.Vertex;

import java.util.Stack;

/**
 * Implementation of a strong components algorithm.
 * 
 * <Data> the type of information stored in a graph node
 * Author: Yossi Gil 
 * See:  28/06/2007
 */
public class StrongComponentProcessor<Data extends Comparable<Data>> extends EmptyProcessor<Data, Graph<Component<Data>>> {
    private int max_dfs = 0;
    private final Stack<Vertex<Data>> stack = new Stack<Vertex<Data>>();
    private Component<Data>[] vertex2Component;
    private int[] dfs;
    private int[] lowlink;
    private boolean[] stacked;
    
    @Override public void before(final Graph<Data> g) {
        final int n = g.vertices.length;
        dfs = new int[n];
        lowlink = new int[n];
        stacked = new boolean[n];
        @SuppressWarnings("unchecked") final Component<Data>[] v2c = new Component[n];
        vertex2Component = v2c;
    }
    
    @Override public void before(final Vertex<Data> v) {
        dfs[v.i] = lowlink[v.i] = max_dfs++;
        stacked[v.i] = true;
        stack.push(v);
    }
    
    @Override public void after(final Vertex<Data> from, final Vertex<Data> to) {
        lowlink[from.i] = min(lowlink[from.i], lowlink[to.i]);
    }
    
    @Override public void revisit(final Vertex<Data> from, final Vertex<Data> to) {
        if (stacked[to.i])
            lowlink[from.i] = min(lowlink[from.i], dfs[to.i]);
    }
    
    @Override public void after(final Vertex<Data> v) {
        if (lowlink[v.i] != dfs[v.i])
            return;
        final Component.Builder<Data> b = new Component.Builder<Data>();
        while (true) {
            final Graph.Vertex<Data> u = stack.pop();
            stacked[u.i] = false;
            b.add(u);
            if (u == v)
                break;
        }
        final Component<Data> c = b.build();
        for (final Graph.Vertex<Data> u : c.vertices)
            vertex2Component[u.i] = c;
    }
    
    /**
     * Create the strongly connected components graph by adding all edges
     * between between the strong components. There is an arc from a strong
     * component to another if there is at least one edge from a vertex of one
     * component to a vertex the other.
     */
    @Override public Graph<Component<Data>> after(@SuppressWarnings("unused") final Graph<Data> _) {
        final Graph.Builder<Component<Data>> $ = new Graph.Builder<Component<Data>>();
        for (final Component<Data> c : vertex2Component) {
            $.newVertex(c);
            for (final Graph.Vertex<Data> v : c.vertices)
                for (final Graph.Vertex<Data> u : v.to)
                    if (vertex2Component[u.i] != c)
                        $.newEdge(c, vertex2Component[u.i]);
        }
        return $.build();
    }
}