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

java.lang.Object
  net.sourceforge.combean.graph.alg.AbstractGraphAlg
      net.sourceforge.combean.graph.alg.spath.AbstractLabellingAlg<NumType>

All Implemented Interfaces:

GraphAlgorithm, ShortestPathAlg<NumType>, SingleSourceShortestPathAlg<NumType>

Direct Known Subclasses:

BellmanFordAlg

public abstract class AbstractLabellingAlg<NumType extends Comparable<NumType>>
extends AbstractGraphAlg
implements SingleSourceShortestPathAlg<NumType>

Abstract base path for label setting or label correcting shortest path algorithms.

Field Summary

protected PathAlgebra<NumType>	algebra
protected NodeMap<NumType>	distance
protected FixedEdgeMap<NumType>	edgeWeights
protected OutgoingEdgeNeighborhoodGraphProp	neigh
protected NodeMap<Edge>	pred
protected Node	startNode

Constructor Summary

AbstractLabellingAlg()
constructor

Method Summary

protected abstract void	calcShortestPaths() A template method which contains the actual algorithm for calculating the shortest paths.
protected boolean	correctLabel(Node v, Edge e) Elementary correction of one label.
boolean	getCalcLengthOnly() Return the value of the flag which enables/disables the calculation of the actual paths.
NodeMap<NumType>	getDistanceMap() Return a NodeMap which contains the shortest distance to the source for every node (or infinity if the node is not reachable from the source).
NumType	getDistanceTo(Node t) Return the shortest path distance to a given node (may only be called after the algorithm has been run).
NodeMap<Edge>	getPredecessorMap() Return a NodeMap which maps every node in the graph to its predecessor (or null if no precedessor exists, e.g. for the source or because the node has not been reached by the shortest path algorithm).
FixedPath	getShortestPathTo(Node t) Return the shortest path to a given node (may only be called after the algorithm has been run)
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	run() Execute the algorithm.
void	setAlgebra(PathAlgebra<NumType> algebra) Define the operations which are used to calculate the distance of a node to the source.
void	setCalcLengthOnly(boolean calcLengthOnly) Enable/disable the calculation of the actual paths.
void	setEdgeWeightMap(FixedEdgeMap<NumType> edgeWeights) Set the weights of the edges of the graph.
void	setSource(Node s) Define the source of the shortest paths.

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

Field Detail

neigh

protected OutgoingEdgeNeighborhoodGraphProp neigh

algebra

protected PathAlgebra<NumType extends Comparable<NumType>> algebra

startNode

protected Node startNode

edgeWeights

protected FixedEdgeMap<NumType extends Comparable<NumType>> edgeWeights

distance

protected NodeMap<NumType extends Comparable<NumType>> distance

pred

protected NodeMap<Edge> pred

Constructor Detail

AbstractLabellingAlg

public AbstractLabellingAlg()

constructor

Method Detail

setSource

public final void setSource(Node s)

Description copied from interface: SingleSourceShortestPathAlg

Define the source of the shortest paths.

Specified by:

setSource in interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

getCalcLengthOnly

public final boolean getCalcLengthOnly()

Description copied from interface: ShortestPathAlg

Return the value of the flag which enables/disables the calculation of the actual paths.

Specified by:

getCalcLengthOnly in interface ShortestPathAlg<NumType extends Comparable<NumType>>

Returns:

true if only the length but not the actual paths shall be calculated.

setAlgebra

public final void setAlgebra(PathAlgebra<NumType> algebra)

Description copied from interface: ShortestPathAlg

Define the operations which are used to calculate the distance of a node to the source. If this parameter is not set, the 'standard' algebra with numeric values and the addition of doubles and the minimization as operations for combining paths shall be taken.

Specified by:

setAlgebra in interface ShortestPathAlg<NumType extends Comparable<NumType>>

Parameters:

algebra - the path algebra containing the required operations

setCalcLengthOnly

public final void setCalcLengthOnly(boolean calcLengthOnly)

Description copied from interface: ShortestPathAlg

Enable/disable the calculation of the actual paths. If set to true, only the length of the shortest path but not the path itself shall be calculated. Default value for this parameter shall be false. Setting it to true may speed up the calculation a bit.

Specified by:

setCalcLengthOnly in interface ShortestPathAlg<NumType extends Comparable<NumType>>

Parameters:

calcLengthOnly - the new value of the calcLengthOnly flag.

setEdgeWeightMap

public final void setEdgeWeightMap(FixedEdgeMap<NumType> edgeWeights)

Description copied from interface: ShortestPathAlg

Set the weights of the edges of the graph.

Specified by:

setEdgeWeightMap in interface ShortestPathAlg<NumType extends Comparable<NumType>>

Parameters:

edgeWeights - the map of the weights of the edges in the graph.

getDistanceMap

public final NodeMap<NumType> getDistanceMap()

Description copied from interface: SingleSourceShortestPathAlg

Return a NodeMap which contains the shortest distance to the source for every node (or infinity if the node is not reachable from the source). The elements must be of type Comparable. The exact type depends on the subclass of Comparable which is used by the PathAlgebra.

Specified by:

getDistanceMap in interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

Returns:

the map of shortest distances to the source.

getPredecessorMap

public final NodeMap<Edge> getPredecessorMap()

Description copied from interface: SingleSourceShortestPathAlg

Return a NodeMap which maps every node in the graph to its predecessor (or null if no precedessor exists, e.g. for the source or because the node has not been reached by the shortest path algorithm).

Specified by:

getPredecessorMap in interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

Returns:

the predecessor map

getDistanceTo

public final NumType getDistanceTo(Node t)

Description copied from interface: SingleSourceShortestPathAlg

Return the shortest path distance to a given node (may only be called after the algorithm has been run).

Specified by:

getDistanceTo in interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

Parameters:

t - the node to which the shortest path distance shall be given.

Returns:

the length of the shortest path to t.

getShortestPathTo

public final FixedPath getShortestPathTo(Node t)

Description copied from interface: SingleSourceShortestPathAlg

Return the shortest path to a given node (may only be called after the algorithm has been run)

Specified by:

getShortestPathTo in interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

Parameters:

t - the node to which the shortest path shall be given

Returns:

the shortest path to t

calcShortestPaths

protected abstract void calcShortestPaths()

A template method which contains the actual algorithm for calculating the shortest paths.

run

public final void run()

Description copied from interface: GraphAlgorithm

Execute the algorithm.

Specified by:

run in interface GraphAlgorithm

init

protected void init()

Internal helper method which initializes the collaborators of the algorithm with sensible default values if they have not explicitly been set.

correctLabel

protected boolean correctLabel(Node v,
                               Edge e)

Elementary correction of one label. Checks if the label of neighbor w of v reachable through edge e has to be corrected because the path to w through v and e is shorter than the shortest distance previously recorded for w.

Parameters:

v - the source node of e

e - the edge from v to the node where the label shall be corrected

Returns:

true if the label has been corrected