net.walend.measured
Class GEBellmanFordTest

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

All Implemented Interfaces:

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

public class GEBellmanFordTest

extends AbstractShortestGEPaths

implements ShortestGEPaths

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	GEBellmanFordTest.BFGEDigraph This is simply a wrapper of a GEDigraph that has a BFNode and BFEdges from that node to all nodes.
private static class	GEBellmanFordTest.BFNode A marker object used in the bellman-ford algorithm.
private static class	GEBellmanFordTest.BFPathMeter A special path meter for the Bellman Ford algorithm that wraps another path meter.

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

private

GEBellmanFordTest(IndexedGEDigraph ceDigraph, GEPathMeter 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(IndexedGEDigraph ceDigraph, GEPathMeter pathMeter)

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

GEBellmanFordTest

private GEBellmanFordTest(IndexedGEDigraph ceDigraph,
                          GEPathMeter pathMeter)
                   throws GENegativeWeightCycleException

Method Detail

test

public static void test(IndexedGEDigraph ceDigraph,
                        GEPathMeter pathMeter)
                 throws GENegativeWeightCycleException

GENegativeWeightCycleException

bellmanFordTest

private void bellmanFordTest()
                      throws GENegativeWeightCycleException

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

Throws:

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

GENegativeWeightCycleException

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