goldman.graph
Class ShortestPathMatrix<V,E extends WeightedEdge<V>>
java.lang.Object
goldman.collection.tagged.TaggedCollectionWrapper<K,V>
goldman.collection.tagged.set.OpenAddressingMapping<V,InTree<V,E>>
goldman.graph.ShortestPathMatrix<V,E>
- All Implemented Interfaces:
- Mapping<V,InTree<V,E>>, TaggedCollection<V,InTree<V,E>>, Iterable<TaggedElement<V,InTree<V,E>>>
public class ShortestPathMatrix<V,E extends WeightedEdge<V>>
- extends OpenAddressingMapping<V,InTree<V,E>>
The ShortestPathMatrix class is used
to store the result from an all-pairs
shortest path algorithm.
Methods inherited from class goldman.collection.tagged.TaggedCollectionWrapper |
accept, clear, contains, elements, ensureCapacity, get, getCapacity, getLocator, getSize, isEmpty, iterator, put, putAll, remove, tags, toString, trimToSize, values |
Methods inherited from interface goldman.collection.tagged.TaggedCollection |
accept, clear, contains, elements, ensureCapacity, get, getCapacity, getLocator, getSize, isEmpty, iterator, put, putAll, remove, tags, toString, trimToSize, values |
hasNegativeWeightCycle
public boolean hasNegativeWeightCycle()
- Returns:
- true if and only
if the graph has a negative weight cycle.
getNegativeWeightCycle
public PositionalCollection<E> getNegativeWeightCycle()
- Returns:
- a positional collection
that holds the edges in a negative weight cycle, or null if there is
no negative weight cycle
getInTreeForSource
public InTree<V,E> getInTreeForSource(V source)
- Parameters:
source
- the desired
source vertex
- Returns:
- a shortest path tree for the given source vertex
getPath
public PositionalCollection<E> getPath(V source,
V dest)
- Parameters:
source
- the source vertexdest
- the destination vertex
- Returns:
- a positional collection
that holds the edges, in order, in a shortest path from
source
to dest
. If there is no path from source
to dest
then null\
is returned.
getPathDistance
public double getPathDistance(V source,
V dest)
- Parameters:
source
- the source vertexdest
- the destination vertex
- Returns:
- the length of the shortest
path from
source
to dest
, or INF
(infinity) if there is no path
from source
to dest