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

java.lang.Object
  net.sourceforge.combean.graph.alg.AbstractGraphAlg
      net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg<NumType>
          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