net.walend.measured
Class FloydWarshallShortestGEPaths

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

All Implemented Interfaces:

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

public class FloydWarshallShortestGEPaths

extends AbstractShortestGEPaths

implements ShortestGEPaths, java.io.Serializable

FloydWarshallShortestGEPaths 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.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.AbstractShortestGEPaths

Fields inherited from class net.walend.digraph.path.AbstractDelegateDigraphOfGEPaths

Fields inherited from interface net.walend.digraph.CEDigraph

EMPTY

Constructor Summary

FloydWarshallShortestGEPaths(IndexedGEDigraph ceDigraph, GEPathMeter pathMeter)

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

FloydWarshallShortestGEPaths

public FloydWarshallShortestGEPaths(IndexedGEDigraph ceDigraph,
                                    GEPathMeter pathMeter)
                             throws GENegativeWeightCycleException

FloydWarshallShortestGEPaths

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

Method Detail

floydWarshall

private void floydWarshall()

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