net.walend.measured
Class AbstractShortestGEPaths

java.lang.Object
  |
  +--net.walend.digraph.path.AbstractDelegateDigraphOfGEPaths
        |
        +--net.walend.measured.AbstractShortestGEPaths

All Implemented Interfaces:

CEDigraph, Digraph, DigraphOfGEPaths, HasState, IndexedCEDigraph, IndexedDigraph, java.io.Serializable, ShortestGEPaths

Direct Known Subclasses:

DijkstraShortestGEPaths, FloydWarshallShortestGEPaths, GEBellmanFordTest

public abstract class AbstractShortestGEPaths

extends AbstractDelegateDigraphOfGEPaths

implements ShortestGEPaths, java.io.Serializable

AbstractShortestGEPaths is a CEDigraph containing the nodes from the base digraph and edges that are the shortest paths between some pairs of nodes. This class holds a lot of common workhorse methods used by other classes.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

private class	AbstractShortestGEPaths.DigraphMeasuredGEPath
protected class	AbstractShortestGEPaths.MeasuredEdge

Nested classes inherited from class net.walend.digraph.path.AbstractDelegateDigraphOfGEPaths

AbstractDelegateDigraphOfGEPaths.ADDOCEPIndexedEdgeIterator

Field Summary

private GEPathMeter

pathMeter

Fields inherited from class net.walend.digraph.path.AbstractDelegateDigraphOfGEPaths

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

protected

AbstractShortestGEPaths(IndexedGEDigraph ceDigraph, IndexedMutableCEDigraph delegate, GEPathMeter pathMeter)

Method Summary

protected void	bfTest()
java.lang.Object	getEdge(int fromIndex, int toIndex)
int	getLength(int from, int to)
int	getLength(java.lang.Object fromNode, java.lang.Object toNode)
GEPath	getPath(int fromIndex, int toIndex)
GEPath	getPath(java.lang.Object fromNode, java.lang.Object toNode)
GEPathMeter	getPathMeter() Return the path meter used to evaluate these shortest paths.
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
MeasuredGEPath	getShortestPath(int fromIndex, int toIndex)
MeasuredGEPath	getShortestPath(java.lang.Object fromNode, java.lang.Object toNode)
protected void	initializeSolution()
abstract void	recalculate() If the digraph is not valid, rediscover the shortest paths.
protected void	relax(java.lang.Object fromNode, int fromIndex, java.lang.Object throughNode, int throughIndex, java.lang.Object toNode, int toIndex)
protected int	safeLength(int from, int to)
boolean	sameStateAs(HasState victim) If two HasStates have the same internal state, return true.
java.lang.String	toString()
boolean	valid() Checks to make sure all the nodes and edges in the path still exist in the base digraph, and that none of the edge lengths have changed.
boolean	validLengths() Checks to make sure all the two node paths have lengths equal to or less than the lengths predicted by the path meter.

Methods inherited from class net.walend.digraph.path.AbstractDelegateDigraphOfGEPaths

addEdge, clearEdges, containsCEDigraph, containsEdge, containsEdge, containsEdge, containsEdge, containsNode, containsNode, containsNodes, countInboundEdges, countInboundEdges, countOutboundEdges, countOutboundEdges, edgeCount, edgeIterator, edgeNodeIterator, getBase, getDelegate, getEdge, getEdges, getFromIndices, getFromNodes, getFromNodes, getInboundEdges, getInboundEdges, getNode, getNodeIndex, getNodes, getOutboundEdges, getOutboundEdges, getToIndices, getToNodes, getToNodes, indexedEdgeIterator, indexedEdgeNodeIterator, indexedNodeIterator, initWithNodesFrom, intersectWithCEDigraph, isEdgeFree, isEmpty, nodeCapacity, nodeCount, nodeIndices, nodeIterator, sameCEDigraphAs, unionCEDigraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface net.walend.digraph.path.DigraphOfGEPaths

getBase

Methods inherited from interface net.walend.digraph.IndexedCEDigraph

containsEdge, getInboundEdges, getOutboundEdges, indexedEdgeIterator

Methods inherited from interface net.walend.digraph.IndexedDigraph

containsEdge, containsNode, countInboundEdges, countOutboundEdges, getFromIndices, getFromNodes, getNode, getNodeIndex, getToIndices, getToNodes, indexedEdgeNodeIterator, indexedNodeIterator, nodeCapacity, nodeIndices

Methods inherited from interface net.walend.digraph.Digraph

containsEdge, containsNode, containsNodes, countInboundEdges, countOutboundEdges, edgeCount, edgeNodeIterator, getFromNodes, getNodes, getToNodes, isEdgeFree, isEmpty, nodeCount, nodeIterator

Methods inherited from interface net.walend.digraph.CEDigraph

containsCEDigraph, containsEdge, edgeIterator, getEdge, getEdges, getInboundEdges, getOutboundEdges, intersectWithCEDigraph, sameCEDigraphAs, unionCEDigraph

Field Detail

pathMeter

private GEPathMeter pathMeter

Constructor Detail

AbstractShortestGEPaths

protected AbstractShortestGEPaths(IndexedGEDigraph ceDigraph,
                                  IndexedMutableCEDigraph delegate,
                                  GEPathMeter pathMeter)
                           throws GENegativeWeightCycleException

Method Detail

bfTest

protected void bfTest()
               throws GENegativeWeightCycleException

GENegativeWeightCycleException

getEdge

public java.lang.Object getEdge(int fromIndex,
                                int toIndex)

Specified by:

getEdge in interface IndexedCEDigraph

Overrides:

getEdge in class AbstractDelegateDigraphOfGEPaths

getPath

public GEPath getPath(java.lang.Object fromNode,
                      java.lang.Object toNode)
               throws NodeMissingException

Specified by:

getPath in interface DigraphOfGEPaths

Overrides:

getPath in class AbstractDelegateDigraphOfGEPaths

NodeMissingException

getPath

public GEPath getPath(int fromIndex,
                      int toIndex)

Specified by:

getPath in interface DigraphOfGEPaths

Overrides:

getPath in class AbstractDelegateDigraphOfGEPaths

initializeSolution

protected void initializeSolution()

relax

protected void relax(java.lang.Object fromNode,
                     int fromIndex,
                     java.lang.Object throughNode,
                     int throughIndex,
                     java.lang.Object toNode,
                     int toIndex)

valid

public boolean valid()

Checks to make sure all the nodes and edges in the path still exist in the base digraph, and that none of the edge lengths have changed.

Specified by:

valid in interface DigraphOfGEPaths

Overrides:

valid in class AbstractDelegateDigraphOfGEPaths

validLengths

public boolean validLengths()

Checks to make sure all the two node paths have lengths equal to or less than the lengths predicted by the path meter. If a length is less than the path meter's prediction, makes sure that the path has more than two nodes.

Specified by:

validLengths in interface ShortestGEPaths

recalculate

public abstract void recalculate()
                          throws GENegativeWeightCycleException

If the digraph is not valid, rediscover the shortest paths.

Specified by:

recalculate in interface ShortestGEPaths

GENegativeWeightCycleException

getPathMeter

public GEPathMeter getPathMeter()

Return the path meter used to evaluate these shortest paths.

Specified by:

getPathMeter in interface ShortestGEPaths

getShortestPath

public MeasuredGEPath getShortestPath(java.lang.Object fromNode,
                                      java.lang.Object toNode)
                               throws NodeMissingException

Specified by:

getShortestPath in interface ShortestGEPaths

NodeMissingException

getShortestPath

public MeasuredGEPath getShortestPath(int fromIndex,
                                      int toIndex)

Specified by:

getShortestPath in interface ShortestGEPaths

getLength

public int getLength(int from,
                     int to)

Specified by:

getLength in interface ShortestGEPaths

safeLength

protected final int safeLength(int from,
                               int to)

getLength

public int getLength(java.lang.Object fromNode,
                     java.lang.Object toNode)
              throws NodeMissingException

Specified by:

getLength in interface ShortestGEPaths

NodeMissingException

getPrincipleInterface

public java.lang.Class getPrincipleInterface()

Description copied from interface: HasState

Returns the class's principle interface for state comparisons. If two objects have different principle interfaces, they never have the same state.

Specified by:

getPrincipleInterface in interface HasState

Overrides:

getPrincipleInterface in class AbstractDelegateDigraphOfGEPaths

sameStateAs

public boolean sameStateAs(HasState victim)

Description copied from interface: HasState

If two HasStates have the same internal state, return true.

For objects with subobjects, Generally this method should only return true if the internal objects are equal. Implement a contentsHaveSameState() method to determine if the contents have the same state.

Specified by:

sameStateAs in interface HasState

Overrides:

sameStateAs in class AbstractDelegateDigraphOfGEPaths

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object