net.walend.measured
Class JITShortestCEPaths

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

All Implemented Interfaces:

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

public class JITShortestCEPaths

extends DijkstraShortestCEPaths

implements ShortestCEPaths, java.io.Serializable

JITShortestCEPaths is an implementation of ShortestCEPaths that uses Dijkstra's algorithm to find the shortest paths just in time. It caches previous results and uses those results to run future calls for new destinations faster. For repeated destinations, it simply returns an existing result.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

Nested classes inherited from class net.walend.measured.DijkstraShortestCEPaths

Nested classes inherited from class net.walend.measured.AbstractShortestCEPaths

AbstractShortestCEPaths.MeasuredEdge

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

AbstractDelegateDigraphOfCEPaths.ADDOCEPIndexedEdgeIterator, AbstractDelegateDigraphOfCEPaths.DigraphCEPath, AbstractDelegateDigraphOfCEPaths.Edge

Field Summary

private boolean[]

measuredNodes

Fields inherited from class net.walend.measured.AbstractShortestCEPaths

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

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

JITShortestCEPaths(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

JITShortestCEPaths(IndexedCEDigraph ceDigraph, IndexedMutableCEDigraph delegate, CEPathMeter pathMeter)

Method Summary

int	getLength(int from, int to)
MeasuredCEPath	getShortestPath(int fromIndex, int toIndex)
void	recalculate() If the digraph is not valid, rediscover the shortest paths.

Methods inherited from class net.walend.measured.DijkstraShortestCEPaths

createNode, dijkstra, initWithNodesFrom

Methods inherited from class net.walend.measured.AbstractShortestCEPaths

bfTest, getEdge, getLength, getPath, getPath, getPathMeter, getPrincipleInterface, getShortestPath, initializeSolution, relax, safeLength, sameStateAs, toString, valid, validLengths

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, 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.measured.ShortestCEPaths

getShortestPath, validLengths

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

getBase, getPath, getPath, valid

Methods inherited from interface net.walend.digraph.IndexedCEDigraph

containsEdge, getEdge, 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.collection.HasState

getPrincipleInterface, sameStateAs

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, getLength, getPathMeter

Field Detail

measuredNodes

private boolean[] measuredNodes

Constructor Detail

JITShortestCEPaths

public JITShortestCEPaths(IndexedCEDigraph ceDigraph,
                          CEPathMeter pathMeter)
                   throws CENegativeWeightCycleException

JITShortestCEPaths

public JITShortestCEPaths(IndexedCEDigraph ceDigraph,
                          IndexedMutableCEDigraph delegate,
                          CEPathMeter pathMeter)
                   throws CENegativeWeightCycleException

Method Detail

recalculate

public void recalculate()
                 throws CENegativeWeightCycleException

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

Specified by:

recalculate in interface ShortestCEDistances

Specified by:

recalculate in class AbstractShortestCEPaths

CENegativeWeightCycleException

getLength

public int getLength(int from,
                     int to)

Specified by:

getLength in interface ShortestCEDistances

Overrides:

getLength in class AbstractShortestCEPaths

getShortestPath

public MeasuredCEPath getShortestPath(int fromIndex,
                                      int toIndex)

Specified by:

getShortestPath in interface ShortestCEPaths

Overrides:

getShortestPath in class AbstractShortestCEPaths