net.sourceforge.combean.graph.alg.spath
Class BellmanFordAlg<NumType extends Comparable<NumType>>

Package class diagram package BellmanFordAlg
java.lang.Object
  extended by net.sourceforge.combean.graph.alg.AbstractGraphAlg
      extended by net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg<NumType>
          extended by net.sourceforge.combean.graph.alg.spath.BellmanFordAlg<NumType>
All Implemented Interfaces:
GraphAlgorithm, ShortestPathAlg<NumType>, SingleSourceShortestPathAlg<NumType>
Direct Known Subclasses:
BellmanFordWithNegCycleDetectionAlg

public class BellmanFordAlg<NumType extends Comparable<NumType>>
extends AbstractLabellingAlg<NumType>

Implements the classic Bellman-Ford algorithm (search shortest paths by a label correcting algorithm which visits the nodes in a FIFO order) Requires OutgoingEdgeNeighborhoodGraphProp.


Field Summary
 
Fields inherited from class net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg
algebra, distance, edgeWeights, neigh, pred, startNode
 
Constructor Summary
BellmanFordAlg()
          constructor
 
Method Summary
protected  void calcShortestPaths()
          A template method which contains the actual algorithm for calculating the shortest paths.
protected  boolean checkForNegativeCycleAtDequeue(Node v)
          Check whether a negative cycle has been identified.
protected  void init()
          Internal helper method which initializes the collaborators of the algorithm with sensible default values if they have not explicitly been set.
 void setNodeQueue(NodeQueue queue)
          Optional.
 
Methods inherited from class net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg
correctLabel, getCalcLengthOnly, getDistanceMap, getDistanceTo, getPredecessorMap, getShortestPathTo, run, setAlgebra, setCalcLengthOnly, setEdgeWeightMap, setSource
 
Methods inherited from class net.sourceforge.combean.graph.alg.AbstractGraphAlg
getGraph, setGraph
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm
getGraph, setGraph
 

Constructor Detail

BellmanFordAlg

public BellmanFordAlg()
constructor

Method Detail

calcShortestPaths

protected void calcShortestPaths()
Description copied from class: AbstractLabellingAlg
A template method which contains the actual algorithm for calculating the shortest paths.

Specified by:
calcShortestPaths in class AbstractLabellingAlg<NumType extends Comparable<NumType>>

setNodeQueue

public void setNodeQueue(NodeQueue queue)
Optional. Set a queue which shall be used by the algorithm to queue the nodes for which the labels shall be corrected.

Parameters:
queue - the queue to be used

init

protected void init()
Description copied from class: AbstractLabellingAlg
Internal helper method which initializes the collaborators of the algorithm with sensible default values if they have not explicitly been set.

Overrides:
init in class AbstractLabellingAlg<NumType extends Comparable<NumType>>

checkForNegativeCycleAtDequeue

protected boolean checkForNegativeCycleAtDequeue(Node v)
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.

Parameters:
v - the node which has just been dequeued.
Returns:
true if a negative cycle has been identified