net.sourceforge.combean.graph.alg.spath
Class BellmanFordWithNegCycleDetectionAlg<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>
              net.sourceforge.combean.graph.alg.spath.BellmanFordWithNegCycleDetectionAlg<NumType>

All Implemented Interfaces:

GraphAlgorithm, NegativeCycleDetectionAlg<NumType>, ShortestPathAlg<NumType>, SingleSourceShortestPathAlg<NumType>, SingleSourceShortestPathWithNegCycleDetectionAlg<NumType>

public class BellmanFordWithNegCycleDetectionAlg<NumType extends Comparable<NumType>>
extends BellmanFordAlg<NumType>
implements SingleSourceShortestPathWithNegCycleDetectionAlg<NumType>

An enhancement of the Bellman-Ford algorithm which is able to detect negative cycles. Requires also GlobalNodesGraphProp.

Field Summary

Fields inherited from class net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg

algebra, distance, edgeWeights, neigh, pred, startNode

Constructor Summary

BellmanFordWithNegCycleDetectionAlg()
constructor

Method Summary

protected boolean	checkForNegativeCycleAtDequeue(Node v) Check whether a negative cycle has been identified.
FixedPath	getNegativeCycle()
boolean	hasNegativeCycle() Check whether a negative cycle has been found
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	setCycleDetector(CycleInPredMapDetectionAlg cycleDetector) Optional.
void	setNodeVisitCount(NodeNumbering nodeVisitCount) Optional.

Methods inherited from class net.sourceforge.combean.graph.alg.spath.BellmanFordAlg

calcShortestPaths, setNodeQueue

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.spath.SingleSourceShortestPathAlg

getDistanceMap, getDistanceTo, getPredecessorMap, getShortestPathTo, setSource

Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.spath.ShortestPathAlg

getCalcLengthOnly, setAlgebra, setCalcLengthOnly, setEdgeWeightMap

Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm

getGraph, run, setGraph

Constructor Detail

BellmanFordWithNegCycleDetectionAlg

public BellmanFordWithNegCycleDetectionAlg()

constructor

Method Detail

hasNegativeCycle

public boolean hasNegativeCycle()

Description copied from interface: NegativeCycleDetectionAlg

Check whether a negative cycle has been found

Specified by:

hasNegativeCycle in interface NegativeCycleDetectionAlg<NumType extends Comparable<NumType>>

Returns:

true if a negative cycle has been found

getNegativeCycle

public FixedPath getNegativeCycle()

Specified by:

getNegativeCycle in interface NegativeCycleDetectionAlg<NumType extends Comparable<NumType>>

setNodeVisitCount

public void setNodeVisitCount(NodeNumbering nodeVisitCount)

Optional. Set the object where the number of visits to each node shall be counted.

Parameters:

nodeVisitCount - the node numbering which shall be used to count the number of visits at each node

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 BellmanFordAlg<NumType extends Comparable<NumType>>

checkForNegativeCycleAtDequeue

protected boolean checkForNegativeCycleAtDequeue(Node v)

Description copied from class: BellmanFordAlg

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.

Overrides:

checkForNegativeCycleAtDequeue in class BellmanFordAlg<NumType extends Comparable<NumType>>

Parameters:

v - the node which has just been dequeued.

Returns:

true if a negative cycle has been identified

setCycleDetector

public final void setCycleDetector(CycleInPredMapDetectionAlg cycleDetector)

Optional. Set algorithm for detection of negative cycles.

Parameters:

cycleDetector - the algorithm which shall be used to find cycles in the predecessor graph.