net.walend.measured
Class CEBellmanFordTest

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

All Implemented Interfaces:

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

public class CEBellmanFordTest

extends AbstractShortestCEPaths

implements ShortestCEPaths

Performs the Bellman-Ford test for a given digraph and pathmeter.

Author:

David Walend dfw1@cornell.edu

See Also:

Serialized Form

Nested Class Summary

private static class	CEBellmanFordTest.BFCEDigraph This is simply a wrapper of a CEDigraph that has a BFNode and BFEdges from that node to all nodes.
private static class	CEBellmanFordTest.BFEdge A marker object used in the bellman-ford algorithm.
private static class	CEBellmanFordTest.BFNode A marker object used in the bellman-ford algorithm.
private static class	CEBellmanFordTest.BFPathMeter A special path meter for the Bellman Ford algorithm that wraps another path meter.

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

private

CEBellmanFordTest(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

Method Summary

private void	bellmanFordTest() Uses the Bellman Ford algorithm to get some initial values in the delegate digraph.
void	recalculate() If the digraph is not valid, rediscover the shortest paths.
static void	test(IndexedCEDigraph ceDigraph, CEPathMeter pathMeter)

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

CEBellmanFordTest

private CEBellmanFordTest(IndexedCEDigraph ceDigraph,
                          CEPathMeter pathMeter)
                   throws CENegativeWeightCycleException

Method Detail

test

public static void test(IndexedCEDigraph ceDigraph,
                        CEPathMeter pathMeter)
                 throws CENegativeWeightCycleException

CENegativeWeightCycleException

bellmanFordTest

private void bellmanFordTest()
                      throws CENegativeWeightCycleException

Uses the Bellman Ford algorithm to get some initial values in the delegate digraph.

Throws:

CENegativeWeightCycleException - if Bellman-Ford detects a negative weight cycle.

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