fr.inria.opengve.bridge.algorithms.common.shortestPath
Class DijkstraAdvanced<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.DijkstraAdvanced<V,E,G>

All Implemented Interfaces:

java.lang.Runnable

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

Provides a advanced algorithm to find all shortest paths from a vertex. You must note that this algorithm doesn't work with negative distance you must use BellmanFord.

After constructing the dijkstra 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)
  If you use the DijkstraAdvanced(Graph, boolean, Object) constructor the algorithm stop when the shortest path to the given vertice is found.

  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

  	DijkstraAdvanced(G g) Classic Dijkstra constructor.
  	DijkstraAdvanced(G g, boolean stepMode) This constructor permit to specify if algorithm must run in stepMode.
  protected	DijkstraAdvanced(G g, boolean stepMode, V destination) This constructor is used to do optimized computation when you want to compute shortest path between two vertices.

  Method Summary

  void	run() This method must not be call, use instead ShortestPathWithSingleOrigin.valuateFromSource(Object).

  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

  DijkstraAdvanced

  public DijkstraAdvanced(G g)

  Classic Dijkstra constructor.

  Parameters:

  g - the graph used by Dijkstra algorithm

  DijkstraAdvanced

  public DijkstraAdvanced(G g,
                          boolean stepMode)

  This constructor permit to specify if algorithm must run in stepMode.

  Parameters:

  g - the graph used by Dijkstra algorithm

  stepMode - The mode of the algorithms.

  DijkstraAdvanced

  protected DijkstraAdvanced(G g,
                             boolean stepMode,
                             V destination)

  This constructor is used to do optimized computation when you want to compute shortest path between two vertices.

  Parameters:

  g - The graph on which the algorithm is applied.

  stepMode - The mode of the algorithm.

  destination - The destination.

  Method Detail

  run

  public void run()

  This method must not be call, use instead ShortestPathWithSingleOrigin.valuateFromSource(Object).

  Specified by:

  run in interface java.lang.Runnable

  Specified by:

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