Class StrongComponentProcessor

Synopsis of Class StrongComponentProcessor

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

Input types: Comparable<Data>, Graph<Data>, Vertex<Data>.

Output types: Comparable<Data>, Component<Data>, Graph<Component<Data>>.

Code

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

Metrics

Metric	Value	Acronym	Explanation
LOC	82	Lines Of Code	Total number of lines in the code
SCC	33	SemiColons Count	Total number of semicolon tokens found in the code.
NOT	601	Number Of Tokens	Comments, whitespace and text which cannot be made into a token not included.
VCC	2147	Visible Characters Count	The total number of non-white (i.e., not space, tab, newline, carriage return, form feed) characters.
CCC	1733	Code Characters Count	Total number of non-white characters in tokens. White space characters in string and character literals are not counted.
UIC	49	Unique Identifiers Count	The number of different identifiers found in the code
WHC	4	Weighted Horizontal Complexity	A heuritistic on horizontal complexity
y

Statistics

Statistic	Value
Average token length	2.9
Tokens/line	7.3
Visible characters/line	26
Code characters/line	21
Semicolons/tokens	5%
Comment text percentage	19%

Tokens by kind

Token Kind	Occurrences
KEYWORD	75
OPERATOR	81
LITERAL	3
ID	220
PUNCTUATION	222
COMMENT	3
OTHER	224