net.walend.measured
Class JITShortestGEPaths

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

All Implemented Interfaces:

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

public class JITShortestGEPaths

extends DijkstraShortestGEPaths

implements ShortestGEPaths, java.io.Serializable

JITShortestGEPaths is an implementation of ShortestGEPaths 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.DijkstraShortestGEPaths

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

AbstractShortestGEPaths.MeasuredEdge

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

AbstractDelegateDigraphOfGEPaths.ADDOCEPIndexedEdgeIterator, AbstractDelegateDigraphOfGEPaths.DigraphGEPath, AbstractDelegateDigraphOfGEPaths.Edge

Field Summary

private boolean[]

measuredNodes

Fields inherited from class net.walend.measured.AbstractShortestGEPaths

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

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

JITShortestGEPaths(IndexedGEDigraph ceDigraph, GEPathMeter pathMeter)

JITShortestGEPaths(IndexedGEDigraph ceDigraph, IndexedMutableCEDigraph delegate, GEPathMeter pathMeter)

Method Summary

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

Methods inherited from class net.walend.measured.DijkstraShortestGEPaths

createNode, dijkstra, initWithNodesFrom

Methods inherited from class net.walend.measured.AbstractShortestGEPaths

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

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, 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.ShortestGEPaths

getLength, getPathMeter, getShortestPath, validLengths

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

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

Field Detail

measuredNodes

private boolean[] measuredNodes

Constructor Detail

JITShortestGEPaths

public JITShortestGEPaths(IndexedGEDigraph ceDigraph,
                          GEPathMeter pathMeter)
                   throws GENegativeWeightCycleException

JITShortestGEPaths

public JITShortestGEPaths(IndexedGEDigraph ceDigraph,
                          IndexedMutableCEDigraph delegate,
                          GEPathMeter pathMeter)
                   throws GENegativeWeightCycleException

Method Detail

recalculate

public void recalculate()
                 throws GENegativeWeightCycleException

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

Specified by:

recalculate in interface ShortestGEPaths

Specified by:

recalculate in class AbstractShortestGEPaths

GENegativeWeightCycleException

getLength

public int getLength(int from,
                     int to)

Specified by:

getLength in interface ShortestGEPaths

Overrides:

getLength in class AbstractShortestGEPaths

getShortestPath

public MeasuredGEPath getShortestPath(int fromIndex,
                                      int toIndex)

Specified by:

getShortestPath in interface ShortestGEPaths

Overrides:

getShortestPath in class AbstractShortestGEPaths