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

java.lang.Object
  fr.inria.opengve.bridge.algorithms.common.shortestPath.FloydWarshall<V,E,G>

public abstract class FloydWarshall<V,E extends Link<V>,G extends Graph<V,E>>
extends java.lang.Object

This class is the implementation of the Floyd-Warshall algorithms. After construction some initialization are need before computation.

Initialize Algorithm :

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

  After initialisation call computeShortestPath() for shortests paths computation.

  You can get result with two methods :

• Get a shortest path between two vertices : getShortestPath(Object, Object)
• Get the distance between two vertices : getDistance(Object, Object)

  Author:

  fabrice.peix@sophia.inria.fr

  Constructor Summary

  FloydWarshall(G graph)
  Algorithm constructor.

  Method Summary

  boolean	computeShortestPath() Compute shortest path for any cuple of vertices and say if cycle of negative distance was found.
  protected abstract Path<V,E>	createPath() Create a new empty path of the same type(directed or undirected) than the graph on which is applied this algorithms.
  AbstractScalar	getDistance(V source, V destination) Give the distance of shortest path beetween two vertices.
  Path<V,E>	getShortestPath(V source, V destination) Give a shortest path between two vertices.
  void	setDistanceContext(java.lang.Object distanceContext) Set context used to load distance of edges.
  void	setDistanceMap(Map distance) Set the map used to load distance of edges.
  void	setDistanceName(java.lang.String distanceName) Set the name used to load distance of edges in the map.
  void	setInfiniteDistance(AbstractScalar infiniteDistance) Set the value used as infinite distance.

  Methods inherited from class java.lang.Object

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

  Constructor Detail

  FloydWarshall

  public FloydWarshall(G graph)

  Algorithm constructor.

  Parameters:

  graph - The graph on which we want compute shortest path for any cuple of vertices.

  Method Detail

  createPath

  protected abstract Path<V,E> createPath()

  Create a new empty path of the same type(directed or undirected) than the graph on which is applied this algorithms.

  Returns:

  A new empty path.

  computeShortestPath

  public boolean computeShortestPath()

  Compute shortest path for any cuple of vertices and say if cycle of negative distance was found.

  Returns:

  false if the graph doesn't contains cycles of negative distance and true otherwise.

  getDistance

  public AbstractScalar getDistance(V source,
                                    V destination)

  Give the distance of shortest path beetween two vertices.

  Parameters:

  source - The source.

  destination - The destination.

  Returns:

  The distance of the shortest path between v1 and v2.

  getShortestPath

  public Path<V,E> getShortestPath(V source,
                                   V destination)

  Give a shortest path between two vertices.

  Parameters:

  source - The source.

  destination - The destination.

  Returns:

  A shortest path between v1 and v2 or null if no path exist between v1 and v2.

  setDistanceMap

  public void setDistanceMap(Map distance)

  Set the map used to load distance of edges.

  Parameters:

  distance - The map used to load distance of edges.

  setDistanceContext

  public void setDistanceContext(java.lang.Object distanceContext)

  Set context used to load distance of edges.

  Parameters:

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

  setDistanceName

  public void setDistanceName(java.lang.String distanceName)

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

  Parameters:

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

  setInfiniteDistance

  public void setInfiniteDistance(AbstractScalar infiniteDistance)

  Set the value used as infinite distance.

  Parameters:

  infiniteDistance - The new infinite distance.