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

All Implemented Interfaces:

java.lang.Runnable

public abstract class Dijkstra<V,E extends Link<V>,G extends Graph<V,E>>
extends StepAlgo<V,E>

Provides a simple algorithm to find distance from a vertex and the paths corresponding to this vertex.

After constructing the dijkstra object, two steps are necessary to obtains shortest paths or distances. Choose a vertex from where you want to compute distances and launch valuateFromSource(Object). Then, you can access the values via other access methods.

Note that DISTANCE_MAX is a constant representing the maximum distance beetween two nodes (modelize the infinite value). It can be a serious limitation for the use of algorithm.

The distance on edges are read with getValue with the parameter DIJKSTRADISTANCE. You can change this string to another string to read another value.

Note that all values on edges must be stored as string.

Version:

23/05/2002

Author:

jflaland@sophia.inria.fr

Nested Class Summary

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

StepAlgo.StepAlgoMessage, StepAlgo.StepAlgoMessageType

Field Summary

java.lang.String

DIJKSTRADISTANCE The string which identify the value to consider as the distance on edges.

Constructor Summary

Dijkstra(G g, Map result)
Default constructor.

Dijkstra(G g, Map result, boolean stepMode)
Default constructor.

Method Summary

protected abstract Path<V,E>	createPath() Method to create Path.
protected abstract AbstractScalar	createScalar(int value) Create a new AbstractScalar of a given value.
protected abstract HierarchicalSet<V>	createVertexSet(HierarchicalSet<V> vertexSet) Method to create intermediate vertexSet.
java.util.Hashtable<V,AbstractScalar>	getDistances() Returns the hashtable giving distances.
int	getDistanceTo(java.lang.Object v) Returns the distance from source of a node.
Path<V,E>	getShortestPathTo(V v) Returns the path from source to vertex v.
V	getStartNode() Returns the current starting node.
void	run() Computes the shortest distances and paths from vertex u.
void	valuateFromSource(V u) Computes the shortest distances and paths from node u.

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, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DIJKSTRADISTANCE

public java.lang.String DIJKSTRADISTANCE

The string which identify the value to consider as the distance on edges. You can easily change it to compute shortests paths with another distance.

Constructor Detail

Dijkstra

public Dijkstra(G g,
                Map result)

Default constructor. When constructed, execute the valuateFromSource function to compute the distances and path and then, get these results via other access method of the class.

Parameters:

g - the graph used by Dijkstra algorithm

result - The map where result are stored.

Dijkstra

public Dijkstra(G g,
                Map result,
                boolean stepMode)

Default constructor. When constructed, execute the valuateFromSource function to compute the distances and path and then, get these results via other access method of the class.

Parameters:

g - the graph used by Dijkstra algorithm

result - The map where result are stored.

Method Detail

createVertexSet

protected abstract HierarchicalSet<V> createVertexSet(HierarchicalSet<V> vertexSet)

Method to create intermediate vertexSet.

Parameters:

vertexSet - The super set of the create set

Returns:

The new empty subset.

createPath

protected abstract Path<V,E> createPath()

Method to create Path.

Returns:

The new empty Path.

createScalar

protected abstract AbstractScalar createScalar(int value)

Create a new AbstractScalar of a given value.

Parameters:

value - The value of the new AbstractScalar.

Returns:

The new AbstractScalar.

valuateFromSource

public void valuateFromSource(V u)

Computes the shortest distances and paths from node u.

Parameters:

u - the abstractnode source from where computing distances

run

public void run()

Computes the shortest distances and paths from vertex u.

Specified by:

run in interface java.lang.Runnable

Specified by:

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

getDistances

public java.util.Hashtable<V,AbstractScalar> getDistances()

Returns the hashtable giving distances. The key of hashtable is the node. Giving a node returns an integer representing distance from source.

Returns:

the hashtable which keys are nodes and containing all distances from source node.

getDistanceTo

public int getDistanceTo(java.lang.Object v)

Returns the distance from source of a node.

Parameters:

v - the node wanted to know the distance.

Returns:

the distance in an integer value.

getShortestPathTo

public Path<V,E> getShortestPathTo(V v)

Returns the path from source to vertex v.

Parameters:

v - the vertex ending the shortest path starting at source node.

Returns:

the path form source to vertex v.

getStartNode

public V getStartNode()

Returns the current starting node.

Returns:

the current starting node from where to compute..