javautils.graph.templates
Class DfsTemplate

java.lang.Object
  |
  +--javautils.graph.templates.DfsTemplate

public abstract class DfsTemplate
extends java.lang.Object

An abstract Template Method [Gamma1995] for depth-first search [Cormen2001].

Note:

Example: DFS-tree

The following method computes the depth-first search tree.

  public static Graph dfsTree(final Graph graph) {
   // Here we define the map that will store the edges of the
   // depth-first search tree.
   final ObjectToListMap nodeToEdgesMap = new ObjectToListMap();

   // Here we specialize an algorithm from the DFS-template method...
   new DfsTemplate() {
     // For each tree edge, we add the edge to the list of the
     // corresponding source node.
     protected void treeEdge(Object edge) {
       nodeToEdgesMap.ensuredGet(graph.sourceOf(edge)).add(edge);
     }
   }.search(graph);
   // ...and above we call it on the graph.

   // Here we make the lists in the map unmodifiable in order to make
   // the returned graph unmodifiable.
   nodeToEdgesMap.transformListsToUnmodifiableLists();

   // Here we define a new graph that represents the computed
   // depth-first search tree.
   return new GraphDecorator(graph) {
       public List edgesFrom(Object node) {
         return nodeToEdgesMap.getOrEmptyUnmodifiableList(node);
       }};
 }
 


Constructor Summary
DfsTemplate()
           
 
Method Summary
protected  void backEdge(java.lang.Object edge)
          Called once for each back edge as it is examined by the search.
protected  void crossEdge(java.lang.Object edge)
          Called once for each cross edge as it is examined by the search.
protected  void discoverNode(java.lang.Object node)
          Called once for each node after the node is first discovered as a root or immediately after a tree edge is found whose target is the node.
protected  void discoverRoot(java.lang.Object node)
          Called once for each node that is first encountered from the search root list.
protected  void finishNode(java.lang.Object node)
          Called once for each node after the complete search tree starting at the node has been finished.
protected  void finishRoot(java.lang.Object node)
          Called once for each discovered search root after the complete search tree starting at the node has been finished.
protected  void forwardEdge(java.lang.Object edge)
          Called once for each forward edge as it is examined by the search.
protected  void initNode(java.lang.Object node)
          Called once for each node before the search.
 void search(Graph graph)
          Performs depth-first search on the graph and calls the event point methods.
 void search(Graph graph, java.util.Collection rootNodes)
           
 void search(Graph graph, java.util.Iterator rootNodes)
          Performs depth-first search on the graph, examines root nodes in the given sequence, and calls the event point methods.
 void search(Graph graph, java.lang.Object rootNode)
           
protected  void treeEdge(java.lang.Object edge)
          Called once for each tree edge as it is examined by the search.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DfsTemplate

public DfsTemplate()
Method Detail

initNode

protected void initNode(java.lang.Object node)

Called once for each node before the search.


discoverRoot

protected void discoverRoot(java.lang.Object node)

Called once for each node that is first encountered from the search root list.


finishRoot

protected void finishRoot(java.lang.Object node)

Called once for each discovered search root after the complete search tree starting at the node has been finished.


discoverNode

protected void discoverNode(java.lang.Object node)

Called once for each node after the node is first discovered as a root or immediately after a tree edge is found whose target is the node.


finishNode

protected void finishNode(java.lang.Object node)

Called once for each node after the complete search tree starting at the node has been finished.


treeEdge

protected void treeEdge(java.lang.Object edge)

Called once for each tree edge as it is examined by the search.


forwardEdge

protected void forwardEdge(java.lang.Object edge)

Called once for each forward edge as it is examined by the search.


crossEdge

protected void crossEdge(java.lang.Object edge)

Called once for each cross edge as it is examined by the search.


backEdge

protected void backEdge(java.lang.Object edge)

Called once for each back edge as it is examined by the search.


search

public final void search(Graph graph)

Performs depth-first search on the graph and calls the event point methods.


search

public final void search(Graph graph,
                         java.util.Iterator rootNodes)

Performs depth-first search on the graph, examines root nodes in the given sequence, and calls the event point methods.


search

public final void search(Graph graph,
                         java.util.Collection rootNodes)

search

public final void search(Graph graph,
                         java.lang.Object rootNode)