Class DepthFirstSearch

Synopsis of Class DepthFirstSearch<Data, Result>

public abstract class DepthFirstSearch<Data, Result> implements TraversalActions<Data, Result> { 
    /*
     * Forge (1)
     */
        DepthFirstSearch(Graph<Data> graph); 
    /*
     * Type (1)
     */
        final Result go(); 
} 

Input types: Comparable, Graph.

Code

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

import il.ac.technion.cs.cs236700.graph.Graph.Vertex;

/**
 * Abstract class for all algorithms based on depth first search. This class is
 * designed in accordance with the Template Method pattern. The initial
 * algorithm (implemented in method #go ) reads:

   graph.reset();
   before(graph);
   for (Graph.Vertex<Data> v : graph.vertices)
    visit(v);
   return after(graph);

 * while in function #visit(Vertex) the actual visitation occurs, by the
 * following

   final void visit(Graph.Vertex<Data> v) {
    if (v.isVisited())
        return;
    v.visit();
    before(v);
    for (final Vertex<Data> u : v.to)
        if (u.isVisited())
            revisit(v, u);
        else {
            before(v, u);
            visit(u);
            after(v, u);
        }
    after(v);
   }

 * where the various after() and before() functions are to be implemented by the
 * subclass.
 * 
 * <Data> the type of information stored in a graph node
 * <Result> the type of the result of the traversal
 * Author: Yossi Gil
 * See:  20/06/2007
 */
public abstract class DepthFirstSearch<Data extends Comparable<Data>, Result> implements TraversalActions<Data, Result> {
    /**
     * The traversed graph
     */
    protected final Graph<Data> graph;
    
    /**
     * graph a graph to traverse
     */
    public DepthFirstSearch(final Graph<Data> graph) {
        this.graph = graph;
    }
    
    /**
     * Performs a traversal of the specified graph. Implemented with the
     * template method design pattern, the traversal shall call the hook
     * functions as appropriate:
     * 
     * 1. #before(Graph), prior to the traversal, and
     * #after(Graph), after its completion.
     * 2.
     * #before(Vertex) before visiting any vertex and
     * #after(Vertex) after visiting it.
     * 3.
     * {@link #before(Vertex, Vertex)} prior to traversing an edge for the
     * first time, and {@link #after(Vertex, Vertex)}
     * {@link #before(Vertex, Vertex)} after traversal through this edge has
     * completed
     * 4.
     * {@link #revisit(Vertex, Vertex)} whenever the traversal tries to
     * follow an edge and discovered that the vertex at the other end has been
     * visited already.
     * 
     * 
     * Return: The accumulated result of the traversal.
     */
    public final Result go() {
        graph.reset();
        before(graph);
        for (final Graph.Vertex<Data> v : graph.vertices)
            visit(v);
        return after(graph);
    }
    
    /**
     * Visit a specific node
     * 
     * v the node to visit
     */
    private final void visit(final Graph.Vertex<Data> v) {
        if (v.isVisited())
            return;
        v.visit();
        before(v);
        for (final Vertex<Data> u : v.to)
            if (!u.isVisited()) {
                before(v, u);
                visit(u);
                after(v, u);
            } else
                revisit(v, u);
        after(v);
    }
}

Metrics

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

Statistics

Statistic	Value
Average token length	2.9
Tokens/line	1.9
Visible characters/line	21
Code characters/line	5.5
Semicolons/tokens	7%
Comment text percentage	73%

Tokens by Kind

Token Kind	Occurrences
KEYWORD	27
OPERATOR	18
LITERAL	0
ID	78
PUNCTUATION	94
COMMENT	6
OTHER	83