Package org.apache.openjpa.lib.graph

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