net.walend.measured
Class JohnsonShortestGEPaths

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

All Implemented Interfaces:

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

public class JohnsonShortestGEPaths

extends DijkstraShortestGEPaths

implements ShortestGEPaths, java.io.Serializable

JohnsonShortestGEPaths 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.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

Fields inherited from class net.walend.measured.DijkstraShortestGEPaths

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

JohnsonShortestGEPaths(IndexedGEDigraph ceDigraph, GEPathMeter pathMeter)

JohnsonShortestGEPaths(IndexedGEDigraph ceDigraph, IndexedMutableCEDigraph delegate, GEPathMeter 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.DijkstraShortestGEPaths

createNode, dijkstra, initWithNodesFrom

Methods inherited from class net.walend.measured.AbstractShortestGEPaths

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

Constructor Detail

JohnsonShortestGEPaths

public JohnsonShortestGEPaths(IndexedGEDigraph ceDigraph,
                              GEPathMeter pathMeter)
                       throws GENegativeWeightCycleException

JohnsonShortestGEPaths

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

Method Detail

johnson

private void johnson()

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