/*

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

  *

  */

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

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

 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.containers.NodeQueue;

 /**

  * Implements the classic Bellman-Ford algorithm

  * (search shortest paths by a label correcting algorithm which visits the

  * nodes in a FIFO order)

  * 

  * Requires OutgoingEdgeNeighborhoodGraphProp.

  * 

  * @author schickin

  *

  */

 public class BellmanFordAlg

 <NumType extends Comparable<NumType>>

 extends AbstractLabellingAlg<NumType> {

     private NodeQueue queue = null;

     /**

      * constructor

      */

     public BellmanFordAlg() {

         super();

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg#calcShortestPaths()

      */

     protected void calcShortestPaths() {

         this.queue.enqueue(this.startNode);

         while (!this.queue.isEmpty()) {

             Node v = this.queue.dequeue();

             if (checkForNegativeCycleAtDequeue(v)) {

                 break;

             }

             EdgeIterator itOutgoing = this.neigh.getOutgoingEdges(v);

             while (itOutgoing.hasNext()) {

                 Edge e = itOutgoing.next();

                 boolean labelChanged = correctLabel(v, e);

                 if (labelChanged) {

                     this.queue.enqueue(this.neigh.getOtherNode(e, v));

                 }

             }

         }

     }

     /**

      * Optional. Set a queue which shall be used by the algorithm to queue

      * the nodes for which the labels shall be corrected.

      * 

      * @param queue the queue to be used

      */

     public void setNodeQueue(NodeQueue queue) {

         this.queue = queue;

     }

     /* (non-Javadoc)

      * @see net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg#init()

      */

     protected void init() {

          super.init();

          if (this.queue == null) {

              this.queue = new ListAsNodeQueue();

          }

     }

     /**

      * Check whether a negative cycle has been identified.

      * Default implementation does nothing, i.e., only more specialized

      * subclasses will be able to find negative cycles (this is not done

      * here because a direct implementation requires more specialised

      * graph properties).

      * The method is called immediately after a node has been dequeued.

      * 

      * @param v the node which has just been dequeued.

      * @return true if a negative cycle has been identified

      */

     protected boolean checkForNegativeCycleAtDequeue(Node v) {

         /* nothing to do here. intented to be overridden for detection of

          * negative cycles

          */

         if (v == null) {

             /* do nothing ... just to sooth the compiler because v is used */

         }

         return false;

     }

 }