/*

     This file is part of Combean.

     Combean is free software; you can redistribute it and/or modify

     it under the terms of the GNU General Public License as published by

     the Free Software Foundation; either version 2 of the License, or

     (at your option) any later version.

     Combean is distributed in the hope that it will be useful,

     but WITHOUT ANY WARRANTY; without even the implied warranty of

     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License

     along with Combean; if not, write to the Free Software

     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

 */

 /*

  * Created on 20.08.2005

  *

  */

 package net.sourceforge.combean.graph.alg.traversal;

 import java.util.BitSet;

 import net.sourceforge.combean.graph.alg.AbstractGraphAlg;

 import net.sourceforge.combean.graph.containers.NodeSetAdvisor;

 import net.sourceforge.combean.interfaces.graph.EdgeIterator;

 import net.sourceforge.combean.interfaces.graph.Node;

 import net.sourceforge.combean.interfaces.graph.NodeIterator;

 import net.sourceforge.combean.interfaces.graph.alg.traverse.GraphTraversalAlg;

 import net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor;

 import net.sourceforge.combean.interfaces.graph.containers.NodeSet;

 import net.sourceforge.combean.interfaces.graph.prop.GlobalNodesGraphProp;

 import net.sourceforge.combean.interfaces.graph.prop.NeighborhoodGraphProp;

 import net.sourceforge.combean.interfaces.graph.prop.OutgoingEdgeNeighborhoodGraphProp;

 /**

  * Abstract base class for DFS- and BFS-traversal. Holds common datastructures.

  * 

  * @author schickin

  *

  */

 public abstract class AbstractGraphTraversalAlg extends AbstractGraphAlg implements

         GraphTraversalAlg {

     private TraversalVisitor visitor = null;

     private Node startNode = null;

     private GlobalNodesGraphProp globalNodes = null;

     private NeighborhoodGraphProp graph = null;

     private OutgoingEdgeNeighborhoodGraphProp outgoingNeigh = null;

     private NodeSet visitedNodes = null;

     private boolean useOnlyOutgoingEdges = false;

     /**

      * constructor

      */

     public AbstractGraphTraversalAlg() {

         super();

     }

     /**

      * @see net.sourceforge.combean.interfaces.graph.alg.traverse.GraphTraversalAlg#setVisitor(net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor)

      */

     public void setVisitor(TraversalVisitor visitor) {

             this.visitor = visitor;

     }

     /**

      * @see net.sourceforge.combean.interfaces.graph.alg.traverse.GraphTraversalAlg#getVisitor()

      */

     public final TraversalVisitor getVisitor() {

             return this.visitor;

     }

     /**

      * @see net.sourceforge.combean.interfaces.graph.alg.traverse.GraphTraversalAlg#setLocalStartNode(net.sourceforge.combean.interfaces.graph.Node)

      */

     public final void setLocalStartNode(Node startNode) {

             this.startNode = startNode;

     }

     /**

      * @return Returns the startNode.

      */

     private final Node getStartNode() {

         return this.startNode;

     }

     /**

      * Set the NodeSet where the nodes are stored which have already been

      * visited during the traversal of the graph.

      * The NodeSetAdvisor will be consulted if left unset.

      * 

      * @param visitedNodes The visitedNodes to set.

      */

     public final void setVisitedNodes(NodeSet visitedNodes) {

             this.visitedNodes = visitedNodes;

     }

     /**

      * @return Returns the visitedNodes.

      */

     protected final NodeSet getVisitedNodes() {

         return this.visitedNodes;

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.interfaces.graph.alg.traverse.GraphTraversalAlg#setUseOnlyOutgoingEdges(boolean)

      */

     public void setUseOnlyOutgoingEdges(boolean useOnlyOutgoingEdges) {

         this.useOnlyOutgoingEdges = useOnlyOutgoingEdges;

     }

     /**

      * @return Returns the graph.

      */

     protected final NeighborhoodGraphProp getNeighborhood() {

         return this.graph;

     }

     /**

      * Helper method for setting up the internal data structures.

      */

     protected void init() {

         if (this.useOnlyOutgoingEdges) {

             this.outgoingNeigh = (OutgoingEdgeNeighborhoodGraphProp) getGraph();

         }

         if (this.visitedNodes == null) {

             this.visitedNodes = NodeSetAdvisor.getFastestNodeSet(getNeighborhood(),

                     new BitSet(NodeSetAdvisor.NUM_PROPS));

         }

         this.visitedNodes.clear();

     }

     /**

      * Template method. Override with the implementation of a traversal

      * of all nodes reachable from v

      * 

      * @param v the node where the traversal shall start

      */

     protected abstract void runTraversalWithSingleStartNode(Node v);

     protected final EdgeIterator getNeighborIterator(Node v) {

         if (this.useOnlyOutgoingEdges) {

             return this.outgoingNeigh.getOutgoingEdges(v);

         }

         return this.graph.getIncidentEdges(v);

     }

     /**

      * @see net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm#run()

      */

     public void run() {

         init();

             if (getStartNode() == null) {

                     getVisitor().init(getNeighborhood());

                     runTraversalForAllNodes();

             }

             else {

                     getVisitor().initLocal(getNeighborhood(), getStartNode());

                     getVisitor().visitComponent(getStartNode());

                     getVisitedNodes().add(getStartNode());

                     runTraversalWithSingleStartNode(getStartNode());

                     getVisitor().leaveComponent(getStartNode());

             }

     }

     /**

      * Execute the recursive DFS for all nodes in the graph.

      * 

      */

     private void runTraversalForAllNodes() {

         NodeIterator allNodesIt = this.globalNodes.getAllNodesIterator();

         while (allNodesIt.hasNext()) {

             Node v = allNodesIt.next();

             if (!getVisitedNodes().contains(v)) {

                 getVisitor().visitComponent(v);

                 getVisitedNodes().add(v);

                 runTraversalWithSingleStartNode(v);

                 getVisitor().leaveComponent(v);

             }

         }

     }

 }