net.sourceforge.combean.interfaces.graph.alg.spath
Interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>

Package class diagram package SingleSourceShortestPathAlg
All Superinterfaces:
GraphAlgorithm, ShortestPathAlg<NumType>
All Known Subinterfaces:
SingleSourceShortestPathWithNegCycleDetectionAlg<NumType>
All Known Implementing Classes:
AbstractLabellingAlg, BellmanFordAlg, BellmanFordWithNegCycleDetectionAlg

public interface SingleSourceShortestPathAlg<NumType extends Comparable<NumType>>
extends ShortestPathAlg<NumType>

Interface for single source shortest path algorithms.


Method Summary
 NodeMap 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)
 void setSource(Node s)
          Define the source of the shortest paths.
 
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
 

Method Detail

setSource

void setSource(Node s)
Define the source of the shortest paths.

Parameters:
s -

getShortestPathTo

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

Parameters:
t - the node to which the shortest path shall be given
Returns:
the shortest path to t

getDistanceTo

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

Parameters:
t - the node to which the shortest path distance shall be given.
Returns:
the length of the shortest path to t.

getPredecessorMap

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

Returns:
the predecessor map

getDistanceMap

NodeMap 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). The elements must be of type Comparable. The exact type depends on the subclass of Comparable which is used by the PathAlgebra.

Returns:
the map of shortest distances to the source.