org.apache.openjpa.lib.graph
Class BreadthFirstWalk

java.lang.Object
  extended by org.apache.openjpa.lib.graph.BreadthFirstWalk

public class BreadthFirstWalk
extends Object

Performs a breadth-first walk of a given Graph, notifying visitors as it sees each node. See the BFS algorithm in the book 'Introduction to Algorithms' by Cormen, Leiserson, and Rivest.

Each GraphVisitor will be notified when a node is colored black (nodeVisited), edge seen (edgeVisited), and a node is seen for the first time, i.e. colored gray (nodeSeen).

Since:
1.0.0
Author:
Steve Kim

Constructor Summary
BreadthFirstWalk(Graph graph)
           
 
Method Summary
 void addGraphVisitor(GraphVisitor visitor)
          add a GraphVisitor to be notified during breadth first search.
protected  void edgeVisited(Edge edge)
          An edge is seen.
protected  void enqueue(Object node, org.apache.openjpa.lib.graph.NodeInfo info)
          Push the given node onto the queue to be processed.
 void removeGraphVisitor(GraphVisitor visitor)
          remove a given GraphVisitor from the listener set.
protected  void visit(Object node, org.apache.openjpa.lib.graph.NodeInfo info)
          Visit the node.
 void walk()
          Begins the breadth first traversal.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BreadthFirstWalk

public BreadthFirstWalk(Graph graph)
Method Detail

walk

public void walk()
Begins the breadth first traversal.


enqueue

protected void enqueue(Object node,
                       org.apache.openjpa.lib.graph.NodeInfo info)
Push the given node onto the queue to be processed. Notify visitors.


visit

protected void visit(Object node,
                     org.apache.openjpa.lib.graph.NodeInfo info)
Visit the node. Mark the node black and notify visitors.


edgeVisited

protected void edgeVisited(Edge edge)
An edge is seen. Notify visitors.


addGraphVisitor

public void addGraphVisitor(GraphVisitor visitor)
add a GraphVisitor to be notified during breadth first search.


removeGraphVisitor

public void removeGraphVisitor(GraphVisitor visitor)
remove a given GraphVisitor from the listener set.



Copyright © 2006-2010 Apache Software Foundation. All Rights Reserved.