fr.inria.opengve.bridge.algorithms.common.shortestPath
Class ShortestPathWithSingleOrigin<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>

All Implemented Interfaces:

java.lang.Runnable

Direct Known Subclasses:

BellmanFord, DijkstraAdvanced

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

This class define common datas and methods between DijkstraAdvanced and BellmanFord.

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

protected G	g_ The graph on which is the algorithms is applied.
protected AbstractScalar	infiniteDistance The infinite distance value.
protected Map	result The map where result are stored.
protected V	start_ The vertex from which shortest paths are computed.
static java.lang.String	VERTEX_DISTANCE The string which identify the value to consider as the distance on vertex.

Constructor Summary

ShortestPathWithSingleOrigin(G g, boolean byStep)
Initialize data structures.

Method Summary

protected abstract Map	createMap() This method is used to create a new Map
protected abstract Path<V,E>	createPath() This method is used to create Path
protected void	finalize()
protected java.lang.Object	getDistanceContext() Give the context used to load distance of edges in the map.
protected Map	getDistanceMap() Return the map where distance are stored.
protected java.lang.String	getDistanceName() Give the name used to load distance of edges in the map.
AbstractScalar	getDistanceTo(java.lang.Object v) Give the distance of the shortest path to a given vertex.
Path<V,E>	getShortestPathTo(V v) Returns a shortest path form source to vertex v.
protected void	Initialize(AbstractScalar zero) This methods initialise data structure.
void	setDistanceContext(java.lang.Object context) Set the context used to load distance of edges.
void	setDistanceMap(Map m) Set the map used to load distance of edges.
void	setDistanceName(java.lang.String name) Set the name used to load distance of edges in the map.
void	setInfiniteDistance(AbstractScalar max) Set the value used as infinite distance.
protected boolean	updateVerticesDistance(V v1, V v2, E edge) Update the distance of a given vertice v2 with the distance of vertex v1 plus the distance of the Link edge if and only if this value is lesser that the initial one.
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, run, 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

Field Detail

VERTEX_DISTANCE

public static final java.lang.String VERTEX_DISTANCE

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

See Also:

Constant Field Values

g_

protected G extends Graph<V,E> g_

The graph on which is the algorithms is applied.

start_

protected V start_

The vertex from which shortest paths are computed.

result

protected Map result

The map where result are stored.

infiniteDistance

protected AbstractScalar infiniteDistance

The infinite distance value.

Constructor Detail

ShortestPathWithSingleOrigin

public ShortestPathWithSingleOrigin(G g,
                                    boolean byStep)

Initialize data structures.

Parameters:

g - The graph on which is apply the algorithm.

byStep - The stepMode of the algorithm.

Method Detail

createPath

protected abstract Path<V,E> createPath()

This method is used to create Path

Returns:

A new create Path.

createMap

protected abstract Map createMap()

This method is used to create a new Map

Returns:

A new empty map.

valuateFromSource

public void valuateFromSource(V u)

Computes the shortest distances and paths from node u.

Parameters:

u - the vertex source from where computing distances

Initialize

protected void Initialize(AbstractScalar zero)

This methods initialise data structure. Set the distance of each node to infiniteDistance and 0 for the source.

Parameters:

zero - An AbstractScalar representing 0.

updateVerticesDistance

protected boolean updateVerticesDistance(V v1,
                                         V v2,
                                         E edge)

Update the distance of a given vertice v2 with the distance of vertex v1 plus the distance of the Link edge if and only if this value is lesser that the initial one.

Parameters:

v1 - The first vertex.

v2 - The second vertex.

edge - The edge.

Returns:

true if the update is done and false otherwise.

getShortestPathTo

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

Returns a shortest path form source to vertex v.

Parameters:

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

Returns:

A shortest path form source to vertex v.

getDistanceTo

public AbstractScalar getDistanceTo(java.lang.Object v)

Give the distance of the shortest path to a given vertex.

Parameters:

v - The destination vertex.

Returns:

The distance of the shortest path to v.

setDistanceMap

public void setDistanceMap(Map m)

Set the map used to load distance of edges.

Parameters:

m - The map used to load distance of edges.

getDistanceMap

protected Map getDistanceMap()

Return the map where distance are stored.

Returns:

The map storing distance of edges.

setDistanceContext

public void setDistanceContext(java.lang.Object context)

Set the context used to load distance of edges. If null is given then default context is used.

Parameters:

context - The context used to load distance of edges in the map.

getDistanceContext

protected java.lang.Object getDistanceContext()

Give the context used to load distance of edges in the map.

Returns:

The context used to load distance of edges in the map or null if default context is used.

setDistanceName

public void setDistanceName(java.lang.String name)

Set the name used to load distance of edges in the map. By default this name is "distance".

Parameters:

name - The new name used to load distance of edges in the map.

getDistanceName

protected java.lang.String getDistanceName()

Give the name used to load distance of edges in the map.

Returns:

The name used to load edges distance on the map.

setInfiniteDistance

public void setInfiniteDistance(AbstractScalar max)

Set the value used as infinite distance.

Parameters:

max - The new infinite distance.

finalize

protected void finalize()
                 throws java.lang.Throwable

Overrides:

finalize in class java.lang.Object

Throws:

java.lang.Throwable