javautils.graph.templates
Class BfsTemplate

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

public abstract class BfsTemplate

extends java.lang.Object

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

Note:

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

Example: Shortest path in an unweighted graph

This example shows how the BFS template could be used to compute a shortest path between two nodes. The following algorithm is asymptotically optimal in the worst case.

 // First we need a method to compute an inverted BFS-tree representation.
 public static Map mapOfInvertedBfsTree(final Graph graph, List roots) {
   // Here we define a map that holds the inverted BFS-tree.
   final Map nodeToParentMap = new HashMap();

   // Here we specialize an algorithm from the BFS template...
   new BfsTemplate() {
     // For each tree edge, we update the inverted BFS-tree.
     protected void treeEdge(Object edge) {
       nodeToParentMap.put(graph.targetOf(edge), graph.sourceOf(edge));
     }
   }.search(graph, roots);
   // ...and above we invoke the specialized template, searching
   // only the specified roots.

   return nodeToParentMap;
 }

 // The actual shortest path finding method.
 public static List shortestUnweightedPath(Graph graph,
                                           Object source,
                                           final Object target) {
   final Map nodeToParentMap =
     mapOfInvertedBfsTree(graph, Collections.singletonList(source));

   // Is there a path?
   return nodeToParentMap.containsKey(target)
     ? new Unfold() {
         // Here we traverse the inverted BFS-tree starting at the
         // target node towards the source node and construct the path.

         Object work = target;

         protected boolean more() {return null != work;}
         protected Object value() {return work;}
         protected void advance() {work = nodeToParentMap.get(work);}
       }.unfoldRight()
     : null;
 }
 

Constructor Summary

BfsTemplate()

Method Summary

protected void	discoverNode(java.lang.Object node) Called once for each discovered node either after the node has been discovered as a root or after all edges in the previous level of the search tree have been examined, but before any edges in the current level are examined.
protected void	discoverRoot(java.lang.Object node) Called once for each node that is first encountered from the root list.
protected void	finishNode(java.lang.Object node) Called once for each node in the searh tree after all edges from the node have been examined but before any nodes on the next level of the search tree are examined.
protected void	finishRoot(java.lang.Object node) Called once for each discovered root node after the entire search tree rooted at the node has been examined.
protected void	initNode(java.lang.Object node) Called once for each node before the search.
protected void	nonTreeEdge(java.lang.Object edge) Called for each edge that is not part of the search tree after discovering all the nodes in the current level of the search tree, but before any nodes in the next level are discovered.
void	search(Graph graph) Performs breadth-first search on the given graph and calls the event point methods.
void	search(Graph graph, java.util.Collection rootOrder)
void	search(Graph graph, java.util.Iterator roots) Performs breadth-first search on the given 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 for each search tree edge after discovering all the nodes in the current level of the search tree, but before any nodes in the next level are discovered.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BfsTemplate

public BfsTemplate()

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 root list.

finishRoot

protected void finishRoot(java.lang.Object node)

Called once for each discovered root node after the entire search tree rooted at the node has been examined.

discoverNode

protected void discoverNode(java.lang.Object node)

Called once for each discovered node either after the node has been discovered as a root or after all edges in the previous level of the search tree have been examined, but before any edges in the current level are examined.

finishNode

protected void finishNode(java.lang.Object node)

Called once for each node in the searh tree after all edges from the node have been examined but before any nodes on the next level of the search tree are examined.

treeEdge

protected void treeEdge(java.lang.Object edge)

Called for each search tree edge after discovering all the nodes in the current level of the search tree, but before any nodes in the next level are discovered.

nonTreeEdge

protected void nonTreeEdge(java.lang.Object edge)

Called for each edge that is not part of the search tree after discovering all the nodes in the current level of the search tree, but before any nodes in the next level are discovered.

search

public final void search(Graph graph)

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

search

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

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

search

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

search

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