Class DepthFirstSearch - SpartanRefactoring/Main GitHub Wiki

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

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