Package 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 Details

    • BreadthFirstWalk

      public BreadthFirstWalk(Graph graph)

  • Method Details

    • 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.