net.walend.measured
Class AbstractShortestCEPaths

java.lang.Object
  |
  +--net.walend.digraph.path.AbstractDelegateDigraphOfCEPaths
        |
        +--net.walend.measured.AbstractShortestCEPaths

All Implemented Interfaces:

CEDigraph, Digraph, DigraphOfCEPaths, HasState, IndexedCEDigraph, IndexedDigraph, java.io.Serializable, ShortestCEDistances, ShortestCEPaths

Direct Known Subclasses:

CEBellmanFordTest, DijkstraShortestCEPaths, FloydWarshallShortestCEPaths

public abstract class AbstractShortestCEPaths

extends AbstractDelegateDigraphOfCEPaths

implements ShortestCEPaths, java.io.Serializable

AbstractShortestCEPaths 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	AbstractShortestCEPaths.DigraphMeasuredCEPath
protected class	AbstractShortestCEPaths.MeasuredEdge

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

AbstractDelegateDigraphOfCEPaths.ADDOCEPIndexedEdgeIterator

Field Summary

private CEPathMeter

pathMeter

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

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

protected

AbstractShortestCEPaths(IndexedCEDigraph ceDigraph, IndexedMutableCEDigraph delegate, CEPathMeter 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)
CEPath	getPath(int fromIndex, int toIndex)
CEPath	getPath(java.lang.Object fromNode, java.lang.Object toNode)
CEPathMeter	getPathMeter() Return the path meter used to evaluate these shortest paths.
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
MeasuredCEPath	getShortestPath(int fromIndex, int toIndex)
MeasuredCEPath	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.AbstractDelegateDigraphOfCEPaths

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.DigraphOfCEPaths

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

Methods inherited from interface net.walend.measured.ShortestCEDistances

getBase

Field Detail

pathMeter

private CEPathMeter pathMeter

Constructor Detail

AbstractShortestCEPaths

protected AbstractShortestCEPaths(IndexedCEDigraph ceDigraph,
                                  IndexedMutableCEDigraph delegate,
                                  CEPathMeter pathMeter)
                           throws CENegativeWeightCycleException

Method Detail

bfTest

protected void bfTest()
               throws CENegativeWeightCycleException

CENegativeWeightCycleException

getEdge

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

Specified by:

getEdge in interface IndexedCEDigraph

Overrides:

getEdge in class AbstractDelegateDigraphOfCEPaths

getPath

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

Specified by:

getPath in interface DigraphOfCEPaths

Overrides:

getPath in class AbstractDelegateDigraphOfCEPaths

NodeMissingException

getPath

public CEPath getPath(int fromIndex,
                      int toIndex)

Specified by:

getPath in interface DigraphOfCEPaths

Overrides:

getPath in class AbstractDelegateDigraphOfCEPaths

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 DigraphOfCEPaths

Overrides:

valid in class AbstractDelegateDigraphOfCEPaths

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 ShortestCEPaths

recalculate

public abstract void recalculate()
                          throws CENegativeWeightCycleException

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

Specified by:

recalculate in interface ShortestCEDistances

CENegativeWeightCycleException

getPathMeter

public CEPathMeter getPathMeter()

Return the path meter used to evaluate these shortest paths.

Specified by:

getPathMeter in interface ShortestCEDistances

getShortestPath

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

Specified by:

getShortestPath in interface ShortestCEPaths

NodeMissingException

getShortestPath

public MeasuredCEPath getShortestPath(int fromIndex,
                                      int toIndex)

Specified by:

getShortestPath in interface ShortestCEPaths

getLength

public int getLength(int from,
                     int to)

Specified by:

getLength in interface ShortestCEDistances

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 ShortestCEDistances

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 AbstractDelegateDigraphOfCEPaths

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 AbstractDelegateDigraphOfCEPaths

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object