/*

     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 24.03.2005

  *

  */

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

 import java.util.Iterator;

 import net.sourceforge.combean.graph.alg.traversal.DFSFinishedNodeOnStackVisitor;

 import net.sourceforge.combean.graph.alg.traversal.RecursiveDFSImpl;

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

 import net.sourceforge.combean.graph.decorators.OrderedNodesGraph;

 import net.sourceforge.combean.graph.iterators.IteratorAsNodeIterator;

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

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

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

 /**

  * This class implements the search for strongly connected components

  * using two DFS traversals, one in the original and one in the transposed graph.

  * 

  * @see "Introduction to Algorithms [CLR96], p. 488ff." 

  * 

  * @author schickin

  *

  */

 public class SCCByDoubleDFSImpl extends AbstractSCCImpl {

     // the graph to work with

     private NeighborhoodGraphProp graph = null;

     private GlobalNodesGraphProp globalNodes = null;

     // the DFS helper algorithm

     private DepthFirstSearch dfs = null;

     /**

      * constructor

      */

     public SCCByDoubleDFSImpl() {

         super();

         // access graph in order to satisfy the compiler

         assert this.globalNodes != null;

         assert this.graph != null;

     }

     /* (non-Javadoc)

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

      */

     public void run() {

         if (this.dfs == null) {

             this.dfs = new RecursiveDFSImpl();

         }

         this.dfs.setGraph(getGraph());

         StackAsNodeStack stack = new StackAsNodeStack();

         DFSFinishedNodeOnStackVisitor finishedNodeVis =

             new DFSFinishedNodeOnStackVisitor(stack);

         this.dfs.setDFSVisitor(finishedNodeVis);

         this.dfs.run();

         Iterator itStack = stack.getStack().iterator();

         OrderedNodesGraph orderedG =

             new OrderedNodesGraph(this.globalNodes,

                     new IteratorAsNodeIterator(itStack));

         this.dfs.setGraph(orderedG);

         this.dfs.setVisitor(new PartitionsTraversalVisitor(this.getVisitor()));

         this.dfs.run();

     }

     /**

      * @return Returns the dfs algorithm.

      */

     public final DepthFirstSearch getDfs() {

         return this.dfs;

     }

     /**

      * Set the DFS helper algorithm. If left unset RecursiveDFSImpl will be used

      * @see net.sourceforge.combean.graph.alg.traversal.RecursiveDFSImpl

      * 

      * @param dfs The dfs algorithm to set.

      */

     public final void setDfs(DepthFirstSearch dfs) {

         this.dfs = dfs;

     }

 }