goldman.graph
Class InTree<V,E extends Edge<V>>

java.lang.Object
  extended by goldman.collection.tagged.TaggedCollectionWrapper<K,V>
      extended by goldman.collection.tagged.set.OpenAddressingMapping<V,goldman.graph.TreeData<V,E>>
          extended by goldman.graph.InTree<V,E>
All Implemented Interfaces:
Mapping<V,goldman.graph.TreeData<V,E>>, TaggedCollection<V,goldman.graph.TreeData<V,E>>, Iterable<TaggedElement<V,goldman.graph.TreeData<V,E>>>

public class InTree<V,E extends Edge<V>>
extends OpenAddressingMapping<V,goldman.graph.TreeData<V,E>>

The InTree class provides an implementation of an in-tree that stores a parent edge associated with each vertex of the graph (possibly null).


Field Summary
 
Fields inherited from class goldman.collection.tagged.TaggedCollectionWrapper
pairs, target
 
Method Summary
 PositionalCollection<E> getCycleReachableFromSource()
           
 double getPathDistanceFromSource(V dest)
           
 PositionalCollection<E> getPathFromSource(V dest)
           
 V getSource()
           
 boolean hasNegativeWeightCycleReachableFromSource()
           
 boolean isReachableFromSource(V dest)
           
 
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

getSource

public V getSource()
Returns:
the source vertex for this in-tree

isReachableFromSource

public boolean isReachableFromSource(V dest)
Parameters:
dest - the destination vertex
Returns:
true if and only if there is a path in this tree from the source to dest in this graph.

getPathDistanceFromSource

public double getPathDistanceFromSource(V dest)
Parameters:
dest - the destination vertex
Returns:
the cost of the path represented in the in-tree from the source to dest. By definition, an unreachable vertex has infinite cost. When dest is not reachable from the source, infinity is returned.

getPathFromSource

public PositionalCollection<E> getPathFromSource(V dest)
Parameters:
dest - the destination vertex
Returns:
a positional collection containing the edges along the path from the root to dest, in order. If dest is not reachable from s, null is returned.

hasNegativeWeightCycleReachableFromSource

public boolean hasNegativeWeightCycleReachableFromSource()
Returns:
true if and only if there is a negative weight cycle reachable from s

getCycleReachableFromSource

public PositionalCollection<E> getCycleReachableFromSource()
Returns:
a positional collection containing the edges of a cycle in the graph reachable from the source vertex, or null if there is no cycle in the graph reachable from the source.