goldman.graph
Class ShortestPathMatrix<V,E extends WeightedEdge<V>>

java.lang.Object
  extended by goldman.collection.tagged.TaggedCollectionWrapper<K,V>
      extended by goldman.collection.tagged.set.OpenAddressingMapping<V,InTree<V,E>>
          extended by 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.


Field Summary
 
Fields inherited from class goldman.collection.tagged.TaggedCollectionWrapper
pairs, target
 
Method Summary
 InTree<V,E> getInTreeForSource(V source)
           
 PositionalCollection<E> getNegativeWeightCycle()
           
 PositionalCollection<E> getPath(V source, V dest)
           
 double getPathDistance(V source, V dest)
           
 boolean hasNegativeWeightCycle()
           
 
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 class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
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
 

Method Detail

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 vertex
dest - 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 vertex
dest - 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