net.walend.measured
Class DijkstraShortestGEPaths

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

All Implemented Interfaces:

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

Direct Known Subclasses:

JITShortestGEPaths, JohnsonShortestGEPaths

public abstract class DijkstraShortestGEPaths

extends AbstractShortestGEPaths

implements ShortestGEPaths, java.io.Serializable

DijkstraShortestGEPaths 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

DijkstraShortestGEPaths.HeapNode

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

DijkstraShortestGEPaths(IndexedGEDigraph ceDigraph, GEPathMeter pathMeter)

DijkstraShortestGEPaths(IndexedGEDigraph ceDigraph, IndexedMutableCEDigraph delegate, GEPathMeter pathMeter)

Method Summary

protected DijkstraShortestGEPaths.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(IndexedGEDigraph digraph) Initialize this with the nodes from digraph at the same index values as in digraph.

Methods inherited from class net.walend.measured.AbstractShortestGEPaths

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.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, getLength, getPathMeter, getShortestPath, getShortestPath, recalculate, 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

DijkstraShortestGEPaths

public DijkstraShortestGEPaths(IndexedGEDigraph ceDigraph,
                               GEPathMeter pathMeter)
                        throws GENegativeWeightCycleException

DijkstraShortestGEPaths

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

Method Detail

initWithNodesFrom

protected void initWithNodesFrom(IndexedGEDigraph digraph)

Description copied from class: AbstractDelegateDigraphOfGEPaths

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

Overrides:

initWithNodesFrom in class AbstractDelegateDigraphOfGEPaths

createNode

protected DijkstraShortestGEPaths.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 -