Package org.apache.openjpa.lib.graph

Class BreadthFirstWalk

  • public class BreadthFirstWalk
extends java.lang.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

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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​(java.lang.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​(java.lang.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​(java.lang.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​(java.lang.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.