/** Generic depth first search traversal of a graph using the template method * pattern. A subclass should override various methods to add functionality. */ public abstract class DFS { protected Graph G; // The graph being traversed protected Object visitResult; // The result of the traversal protected static Object STATUS = new Object(); // The status attribute protected static Object VISITED = new Object(); // Visited value protected static Object UNVISITED = new Object(); // Unvisited value /** Execute a depth first search traversal on graph g, starting * from a vertex v, optionally passing in an information object (info) */ public abstract Object execute(Graph g, Vertex start, Object info); /** Initialize the graph g for a traversal. */ protected void init(Graph g) { G = g; for(Iterator vertices = g.vertices(); vertices.hasNext(); ) unVisit((DecorablePosition)vertices.next()); for(Iterator edges = g.edges(); edges.hasNext(); ) unVisit((DecorablePosition)edges.next()); }