net.walend.measured
Class JohnsonShortestCEPaths

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

All Implemented Interfaces:

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

public class JohnsonShortestCEPaths

extends DijkstraShortestCEPaths

implements ShortestCEPaths, java.io.Serializable

JohnsonShortestCEPaths uses Johnson's algorithm to find the shortest paths during construction.

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

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

JohnsonShortestCEPaths(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

JohnsonShortestCEPaths(IndexedCEDigraph ceDigraph, IndexedMutableCEDigraph delegate, CEPathMeter pathMeter)

Method Summary

private void	johnson()
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, getLength, getPath, getPath, getPathMeter, getPrincipleInterface, getShortestPath, 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, 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

Constructor Detail

JohnsonShortestCEPaths

public JohnsonShortestCEPaths(IndexedCEDigraph ceDigraph,
                              CEPathMeter pathMeter)
                       throws CENegativeWeightCycleException

JohnsonShortestCEPaths

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

Method Detail

johnson

private void johnson()

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