/*

     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 14.01.2005

  *

  */

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

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

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

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

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

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

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

 /**

  * A recursive implementation of the Depth First Search algorithm.

  * 

  * @author schickin

  *

  */

 public class RecursiveDFSImpl extends AbstractGraphTraversalAlg

 implements DepthFirstSearch {

         private DFSVisitor dfsVisitor = null;

         /**

          * constructor

          */

         public RecursiveDFSImpl() {

                 super();

         }

         /**

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.DepthFirstSearch#getDFSVisitor()

          */

         public DFSVisitor getDFSVisitor() {

                 return this.dfsVisitor;

         }

         /**

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.DepthFirstSearch#setDFSVisitor(net.sourceforge.combean.interfaces.graph.alg.traverse.DFSVisitor)

          */

         public void setDFSVisitor(DFSVisitor visitor) {

                 setVisitor(visitor);

                 this.dfsVisitor = visitor;

         }

         /**

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

          */

         public void setVisitor(TraversalVisitor visitor) {

                 super.setVisitor(visitor);

                 this.dfsVisitor = null;

         }

         /**

          * Explore the component of v with a recursive DFS.

          * 

          * @param v current node of the recursive DFS.

          */

         protected void runTraversalWithSingleStartNode(Node v) {

                 getVisitor().visitNode(v);

                 EdgeIterator it = getNeighborIterator(v);

                 while (it.hasNext()) {

                         Edge e = it.next();

                         Node w = getNeighborhood().getOtherNode(e, v);

                         boolean notYetVisited = getVisitedNodes().add(w);

                         if (notYetVisited) {

                                 getVisitor().openNeighbor(e, v);

                                 runTraversalWithSingleStartNode(w);

                                 if (this.dfsVisitor != null) {

                                         this.dfsVisitor.leaveNeighbor(e, v);

                                 }

                         }

                         else {

                                 getVisitor().reopenNeighbor(e, v);

                         }

                 }

                 if (this.dfsVisitor != null) {

                         this.dfsVisitor.leaveNode(v);

                 }

         }

 }