/*

     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 10.02.2005

  *

  */

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

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

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

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

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

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

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

 import net.sourceforge.combean.interfaces.graph.alg.partition.NodePartitionVisitor;

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

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

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

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

 import net.sourceforge.combean.util.except.UnsupportedMethodException;

 /**

  * Find strongly connected components by DFS (Tarjan's algorithm for SCCs).

  * 

  * @author schickin

  *

  */

 public final class SCCByDFSImpl extends AbstractSCCImpl {

     // the graph to work with

     private NeighborhoodGraphProp graph = null;

     private GlobalNodesGraphProp globalNodes = null;

     // the DFS helper algorithm

     private DepthFirstSearch dfs = null;

     private SCCVisitor sccVis = null;

     // helper data structures for the DFS

     // store lowest dfs number of a node reachable via at least one tree edge

     private NodeNumbering lowNum = null;

     private class SCCVisitor extends DFSNodeStackVisitor {

         private SCCByDFSImpl sccAlg = null;

         private NeighborhoodGraphProp g = null;

         private boolean sccOpened = false;

         /**

          * @param sccAlg the algorithm for which the visitor works

          */

         SCCVisitor(SCCByDFSImpl sccAlg) {

             super();

             this.sccAlg = sccAlg;

         }

         /**

          * Update the low numbering of v, assuming that w is a neighbor of w

          * that w already has its correct low numbering

          * 

          * @param v

          * @param w

          */

         private void adjustLowNum(Node v, Node w) {

             int lowV = this.sccAlg.getLowNumbering().getNumber(v);

             int lowW = this.sccAlg.getLowNumbering().getNumber(w);

             if (lowW < lowV) {

                 this.sccAlg.getLowNumbering().setNumber(v, lowW);

             }

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.DFSVisitor#leaveNode(net.sourceforge.combean.interfaces.graph.Node)

          */

         public final void leaveNode(Node v) {

             super.leaveNode(v);

             NodePartitionVisitor vis = this.sccAlg.getVisitor();

             if (!this.sccOpened) {

                 vis.startPartition();

                 this.sccOpened = true;

             }

             vis.addNode(v);

             int dfsV = getDfsNum(v);

             int lowV = this.sccAlg.getLowNumbering().getNumber(v);

             if (dfsV == lowV) {

                 vis.endPartition();

                 this.sccOpened = false;

             }

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.DFSVisitor#leaveNeighbor(net.sourceforge.combean.interfaces.graph.Node, net.sourceforge.combean.interfaces.graph.Edge)

          */

         public final void leaveNeighbor(Edge e, Node from) {

             super.leaveNeighbor(e,from);

             Node w = this.g.getOtherNode(e, from);

             adjustLowNum(from, w);

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor#init(net.sourceforge.combean.interfaces.graph.Graph)

          */

         public void init(Graph g) {

             super.init(g);

             this.g = (NeighborhoodGraphProp) g;

             this.sccAlg.getLowNumbering().init(g);

             this.sccOpened = false;

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor#initLocal(net.sourceforge.combean.interfaces.graph.Graph, net.sourceforge.combean.interfaces.graph.Node)

          */

         public void initLocal(Graph g, Node startNode) {

             /*

              we only look for SCCs globally

             */

             throw new UnsupportedMethodException();

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor#visitNode(net.sourceforge.combean.interfaces.graph.Node)

          */

         public void visitNode(Node v) {

              super.visitNode(v);

              this.sccAlg.getLowNumbering().setNumber(v, getDfsNum(v));

         }

         /* (non-Javadoc)

          * @see net.sourceforge.combean.interfaces.graph.alg.traverse.TraversalVisitor#reopenNeighbor(net.sourceforge.combean.interfaces.graph.Edge, net.sourceforge.combean.interfaces.graph.Node)

          */

         public final void reopenNeighbor(Edge e, Node from) {

             super.reopenNeighbor(e,from);

             Node w = this.g.getOtherNode(e, from);

             int dfsW = this.sccAlg.getDfsNumbering().getNumber(w);

             if (dfsW < 0) {

                 adjustLowNum(from, w);

             }

         }

     }

     /**

      * constructor

      */

     public SCCByDFSImpl() {

         super();

         // access graph in order to satisfy the compiler

         assert this.globalNodes != null;

         assert this.graph != null;

     }

     /**

      * @return Returns the dfs numbering.

      */

     public final NodeNumbering getDfsNumbering() {

         return this.sccVis.getDfsNumbering();

     }

     /**

      * Set the dfs numbering. If left unset, the NodeNumberingAdvisor will

      * be consulted.

      * 

      * @param dfsNum The dfs numbering to set.

      */

     public final void setDfsNumbering(NodeNumbering dfsNum) {

         this.sccVis.setDfsNumbering(dfsNum);

     }

     /**

      * @return Returns the low numbering.

      */

     public final NodeNumbering getLowNumbering() {

         return this.lowNum;

     }

     /**

      * Set the low numbering. If left unset, the NodeNumberingAdvisor will

      * be consulted.

      * 

      * @param lowNum The low numbering to set.

      */

     public final void setLowNumbering(NodeNumbering lowNum) {

         this.lowNum = lowNum;

     }

     /**

      * @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;

     }

     /* (non-Javadoc)

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

      */

     public void run() {

         getVisitor().init(getGraph());

         initDFS();

         this.dfs.run();

         getVisitor().finish();

     }

     private final void initDFS() {

         if (this.lowNum == null) {

             this.lowNum = NodeNumberingAdvisor.getFastestNodeNumbering(getGraph());

         }

         if (this.dfs == null) {

             this.dfs = new RecursiveDFSImpl();

         }

         this.sccVis = new SCCVisitor(this);

         this.dfs.setGraph(getGraph());

         this.dfs.setDFSVisitor(this.sccVis);

     }

 }