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:

• Be careful to override the correct event-point methods.
• Remember to explicitly call the desired search-method.

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)