goldman.graph
Class InTree<V,E extends Edge<V>>
java.lang.Object
goldman.collection.tagged.TaggedCollectionWrapper<K,V>
goldman.collection.tagged.set.OpenAddressingMapping<V,goldman.graph.TreeData<V,E>>
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).
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 |
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.