mascoptLib.algos.abstractalgos
Class DijkstraAdvanced

java.lang.Object
  |
  +--mascoptLib.algos.abstractalgos.StepAlgo
        |
        +--mascoptLib.algos.abstractalgos.DijkstraAdvanced

All Implemented Interfaces:

Runnable

public class DijkstraAdvanced

extends StepAlgo

Provides a advanced algorithm to find distance from a node and the paths corresponding to this node.

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

Nota 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 getDoubleValue 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 Double.

Version:

23/05/2002

Author:

jflaland@sophia.inria.fr

See Also:

valuateFromSource

Field Summary

static String

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

Constructor Summary

DijkstraAdvanced(mascoptLib.abstractGraph.AbstractGraph g, String nameOfValue)
Default constructor.

Method Summary

Double	getDistanceTo(mascoptLib.abstractGraph.AbstractVertex v) Returns the distance from source of a node.
mascoptLib.abstractGraph.AbstractPath	getShortestPathTo(mascoptLib.abstractGraph.AbstractVertex v) Returns the chain form source to node v.
mascoptLib.abstractGraph.AbstractVertex	getStartNode() Returns the current starting node.
void	run() Computes the shortest distances and paths from node u.
void	slowAlgorithm(boolean slow)
void	valuateFromSource(mascoptLib.abstractGraph.AbstractVertex u) Computes the shortest distances and paths from node u.

Methods inherited from class mascoptLib.algos.abstractalgos.StepAlgo

byStep, ends, isDemo, isEnded, nextStep, setTime, start, waitB

Methods inherited from class java.lang.Object

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

Field Detail

DIJKSTRADISTANCE

public static final String DIJKSTRADISTANCE

The string which identify the value to consider as the distance on edges. You can't change it.

See Also:

Constant Field Values

Constructor Detail

DijkstraAdvanced

public DijkstraAdvanced(mascoptLib.abstractGraph.AbstractGraph g,
                        String nameOfValue)

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

nameOfValue - the string name of the value to consider as distances on arcs

Method Detail

valuateFromSource

public void valuateFromSource(mascoptLib.abstractGraph.AbstractVertex u)

Computes the shortest distances and paths from node u.

Parameters:

u - the abstractnode source from where computing distances

slowAlgorithm

public void slowAlgorithm(boolean slow)

run

public void run()

Computes the shortest distances and paths from node u.

Specified by:

run in interface Runnable

Specified by:

run in class StepAlgo

getDistanceTo

public Double getDistanceTo(mascoptLib.abstractGraph.AbstractVertex 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 mascoptLib.abstractGraph.AbstractPath getShortestPathTo(mascoptLib.abstractGraph.AbstractVertex v)

Returns the chain form source to node v.

Parameters:

v - the node ending the shortest chain starting at source node.

Returns:

the chain form source to node v.

getStartNode

public mascoptLib.abstractGraph.AbstractVertex getStartNode()

Returns the current starting node.

Returns:

the current starting node from where to compute..