net.walend.measured
Class DijkstraShortestCEPaths

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

All Implemented Interfaces:

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

Direct Known Subclasses:

JITShortestCEPaths, JohnsonShortestCEPaths

public abstract class DijkstraShortestCEPaths

extends AbstractShortestCEPaths

implements ShortestCEPaths, java.io.Serializable

DijkstraShortestCEPaths is an abstract class that contains Dijkstra's algorithm for shortest paths, plus supporting code for solutions with nodes must go inside a hash table.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

private class

DijkstraShortestCEPaths.HeapNode

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

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

DijkstraShortestCEPaths(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

DijkstraShortestCEPaths(IndexedCEDigraph ceDigraph, IndexedMutableCEDigraph delegate, CEPathMeter pathMeter)

Method Summary

protected DijkstraShortestCEPaths.HeapNode	createNode(java.lang.Object wrappedNode, int index)
protected void	dijkstra(int endIndex) Find all of the shortest paths to the node at endIndex.
protected void	initWithNodesFrom(IndexedCEDigraph digraph) Initialize this with the nodes from digraph at the same index values as in digraph.

Methods inherited from class net.walend.measured.AbstractShortestCEPaths

bfTest, getEdge, getLength, getLength, getPath, getPath, getPathMeter, getPrincipleInterface, getShortestPath, getShortestPath, initializeSolution, recalculate, 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, 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, getLength, getPathMeter, recalculate

Constructor Detail

DijkstraShortestCEPaths

public DijkstraShortestCEPaths(IndexedCEDigraph ceDigraph,
                               CEPathMeter pathMeter)
                        throws CENegativeWeightCycleException

DijkstraShortestCEPaths

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

Method Detail

initWithNodesFrom

protected void initWithNodesFrom(IndexedCEDigraph digraph)

Description copied from class: AbstractDelegateDigraphOfCEPaths

Initialize this with the nodes from digraph at the same index values as in digraph.

Overrides:

initWithNodesFrom in class AbstractDelegateDigraphOfCEPaths

createNode

protected DijkstraShortestCEPaths.HeapNode createNode(java.lang.Object wrappedNode,
                                                      int index)

dijkstra

protected void dijkstra(int endIndex)

Find all of the shortest paths to the node at endIndex.

Parameters:

endIndex -