fr.inria.opengve.bridge.algorithms.common.shortestPath
Class BellmanFord<V,E extends Link<V>,G extends Graph<V,E>>

java.lang.Object
  java.util.Observable
      fr.inria.opengve.bridge.algorithms.StepAlgo<V,E>
          fr.inria.opengve.bridge.algorithms.common.shortestPath.ShortestPathWithSingleOrigin<V,E,G>
              fr.inria.opengve.bridge.algorithms.common.shortestPath.BellmanFord<V,E,G>

All Implemented Interfaces:

java.lang.Runnable

public abstract class BellmanFord<V,E extends Link<V>,G extends Graph<V,E>>
extends ShortestPathWithSingleOrigin<V,E,G>

This class implement the Bellman-Ford algorithm. It's permit to compute all shortest path from a given vertex. This algorithms work also with negative weight on edges. You must verify after shortest path computation the presence of negative cycles (foundNegativeCycle()). Now we present shortly the use of this class.

After constructing the Bellman-Ford object, some steps are necessary to obtains shortest paths or distances.

Initialize Algorithm :

• Set the Map used to load edges distance : ShortestPathWithSingleOrigin.setDistanceMap(Map)
• Set the name of the distance value : ShortestPathWithSingleOrigin.setDistanceName(String)
• Set the context of distance value : ShortestPathWithSingleOrigin.setDistanceContext(Object)
• Set the AbstractScalar corresponding to infinity : ShortestPathWithSingleOrigin.setInfiniteDistance(AbstractScalar)

  After initialisation call ShortestPathWithSingleOrigin.valuateFromSource(Object) for shortest path computation.

  You can get result with two methods :

• Get a shortest path to a given vertex : ShortestPathWithSingleOrigin.getShortestPathTo(Object)
• Get the distance to a given vertex : ShortestPathWithSingleOrigin.getDistanceTo(Object)

  Author:

  fabrice.peix@sophia.inria.fr

  Nested Class Summary

  Nested classes/interfaces inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

  StepAlgo.StepAlgoMessage, StepAlgo.StepAlgoMessageType

  Field Summary

  Fields inherited from class fr.inria.opengve.bridge.algorithms.common.shortestPath.ShortestPathWithSingleOrigin

  g_, infiniteDistance, result, start_, VERTEX_DISTANCE

  Constructor Summary

  BellmanFord(G g)
  Constructor.

  BellmanFord(G g, boolean byStep)
  Constructor.

  Method Summary

  boolean	foundNegativeCycle() This method say if negative cycles are present in the graph.
  void	run() Run the algorithm.

  Methods inherited from class fr.inria.opengve.bridge.algorithms.common.shortestPath.ShortestPathWithSingleOrigin

  createMap, createPath, finalize, getDistanceContext, getDistanceMap, getDistanceName, getDistanceTo, getShortestPathTo, Initialize, setDistanceContext, setDistanceMap, setDistanceName, setInfiniteDistance, updateVerticesDistance, valuateFromSource

  Methods inherited from class fr.inria.opengve.bridge.algorithms.StepAlgo

  ends, getDemoMode, getStepMode, isEnded, nextStep, notifyGraphDisplayRequest, notifyGraphDisplayRequest, notifyLabelEdgesRequest, notifyLabelVerticesRequest, pause, setPauseMode, setTime, start

  Methods inherited from class java.util.Observable

  addObserver, clearChanged, countObservers, deleteObserver, deleteObservers, hasChanged, notifyObservers, notifyObservers, setChanged

  Methods inherited from class java.lang.Object

  clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  Constructor Detail

  BellmanFord

  public BellmanFord(G g,
                     boolean byStep)

  Constructor.

  Parameters:

  g - The graph on which is applied the algorithm.

  byStep - The step mode.

  BellmanFord

  public BellmanFord(G g)

  Constructor.

  Parameters:

  g - The graph on which is applied the algorithm.

  Method Detail

  run

  public void run()

  Description copied from class: StepAlgo

  Run the algorithm.

  Specified by:

  run in interface java.lang.Runnable

  Specified by:

  run in class StepAlgo<V,E extends Link<V>>

  foundNegativeCycle

  public boolean foundNegativeCycle()

  This method say if negative cycles are present in the graph. This method must be call after the call of ShortestPathWithSingleOrigin.valuateFromSource(Object).

  Returns:

  true if graph contain negative cycle and false otherwise.