net.walend.measured
Class FloydWarshallShortestCEPaths

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

All Implemented Interfaces:

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

public class FloydWarshallShortestCEPaths

extends AbstractShortestCEPaths

implements ShortestCEPaths, java.io.Serializable

FloydWarshallShortestCEPaths uses the very simple Floyd-Warshall algorithm to find the shortest paths.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

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

FloydWarshallShortestCEPaths(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

FloydWarshallShortestCEPaths(IndexedCEDigraph ceDigraph, IndexedMutableCEDigraph delegate, CEPathMeter pathMeter)

Method Summary

private void	floydWarshall()
void	recalculate() If the digraph is not valid, rediscover the shortest paths.

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

FloydWarshallShortestCEPaths

public FloydWarshallShortestCEPaths(IndexedCEDigraph ceDigraph,
                                    CEPathMeter pathMeter)
                             throws CENegativeWeightCycleException

FloydWarshallShortestCEPaths

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

Method Detail

floydWarshall

private void floydWarshall()

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