org.apache.openjpa.lib.graph
Class BreadthFirstWalk

java.lang.Object
  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, 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, 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,
                       NodeInfo info)

Push the given node onto the queue to be processed. Notify visitors.

visit

protected void visit(Object node,
                     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.