drasys.or.graph.sp
Class Iterate

java.lang.Object
  |
  +--drasys.or.graph.sp.Iterate

public class Iterate

extends java.lang.Object

implements AllPairsI

An implementation of an all pairs shortest path algorithm which iterates a single vertex shortest path algorithm.

References:

Introduction to Algorithms
    Thomas H. Cormen, et al / Hardcover / Published 1990
Graphs : Theory and Algorithms
    K. Thulasiraman, M.N.S. Swamy / Paperback / Published 1992

See Also:

SingleVertexI

Constructor Summary

Iterate(GraphI graph)           A constructor that sets the target graph.

Iterate(GraphI graph, SingleVertexI algorithm)           A constructor that sets the target graph and the underlying single vertex shortest path algorithm.

 

Method Summary
AddI	fillGraph(AddI graph)           This finds all the paths costs from each of the origin vertices and all of the paths to each of the destination vertices.
AddI	fillGraph(AddI graph, int maxPathsOut, int maxPathsIn)           This finds the 'maxPathsOut' lowest cost paths from each of the origin vertices and the 'maxPathsIn' lowest cost paths to each of the destination vertices.
void	fillMatrix(SizableMatrixI cost, SizableMatrixI time, SizableMatrixI distance)           This finds the shortest path costs from all the origin vertices to all of the connected destination vertices.
void	fillMatrix(SizableMatrixI cost, SizableMatrixI time, SizableMatrixI distance, int maxPathsOut, int maxPathsIn)           This finds 'maxPathsOut' lowest costs from each of the origin vertices and the 'maxPathsIn' lowest costs into each of the destination vertices.
VertexI[]	getDestinationVertices()           Returns an array containing all of the destination vertices.
VertexI[]	getOriginVertices()           Returns an array containing all the origin vertices.
void	setDestination(boolean isDestination)           Sets the destination flags for all vertices equal to the argument.
void	setDestination(java.lang.Object key, boolean isDestination)           Sets the destination flag for a vertex.
void	setOrigin(boolean isOrigin)           Sets the origin flags for all vertices equal to the argument.
void	setOrigin(java.lang.Object key, boolean isOrigin)           Sets the origin flag for a vertex.
void	setProperties(PropertiesI properties)           Sets the properties object in the underlying single vertex algorithm.

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

Iterate

public Iterate(GraphI graph)

A constructor that sets the target graph.

Iterate

public Iterate(GraphI graph,
               SingleVertexI algorithm)

A constructor that sets the target graph and the underlying single vertex shortest path algorithm.

setProperties

public void setProperties(PropertiesI properties)

Sets the properties object in the underlying single vertex algorithm.

Specified by:

setProperties in interface AllPairsI

setDestination

public void setDestination(boolean isDestination)

Sets the destination flags for all vertices equal to the argument.

Specified by:

setDestination in interface AllPairsI

setDestination

public void setDestination(java.lang.Object key,
                           boolean isDestination)
                    throws VertexNotFoundException

Sets the destination flag for a vertex.

Specified by:

setDestination in interface AllPairsI

Throws:

VertexNotFoundException - if the vertex is not found.

getDestinationVertices

public VertexI[] getDestinationVertices()

Returns an array containing all of the destination vertices. The index of a vertex in the array (not getIndex) matches its column index in the result matrix.

Specified by:

getDestinationVertices in interface AllPairsI

Returns:

null if there are no destination vertices.

setOrigin

public void setOrigin(boolean isOrigin)

Sets the origin flags for all vertices equal to the argument.

Specified by:

setOrigin in interface AllPairsI

setOrigin

public void setOrigin(java.lang.Object key,
                      boolean isOrigin)
               throws VertexNotFoundException

Sets the origin flag for a vertex. By default all vertices are marked as origins.

Specified by:

setOrigin in interface AllPairsI

Throws:

VertexNotFoundException - if the vertex is not found.

getOriginVertices

public VertexI[] getOriginVertices()

Returns an array containing all the origin vertices. The index of a vertex in the array (not getIndex) matches its row index in the result matrices.

Specified by:

getOriginVertices in interface AllPairsI

Returns:

null if there are no origin vertices.

fillMatrix

public void fillMatrix(SizableMatrixI cost,
                       SizableMatrixI time,
                       SizableMatrixI distance)
                throws InvalidPropertyException,
                       VertexNotFoundException

This finds the shortest path costs from all the origin vertices to all of the connected destination vertices. The row (first) index selects the origin vertex for the cost and the column (second) index selects the destination vertex. The row index for an origin vertex corresponds to its index in the array returned from getOriginVertices. The column index for a destination vertex corresponds to its index in the array returned from getDestinationVertices. An entry in the matrix for two disconnected vertices will be set to Double.POSITIVE_NFINITY. The cost for a vertex to itself is zero.

Specified by:

fillMatrix in interface AllPairsI

fillMatrix

public void fillMatrix(SizableMatrixI cost,
                       SizableMatrixI time,
                       SizableMatrixI distance,
                       int maxPathsOut,
                       int maxPathsIn)
                throws InvalidPropertyException,
                       VertexNotFoundException

This finds 'maxPathsOut' lowest costs from each of the origin vertices and the 'maxPathsIn' lowest costs into each of the destination vertices. The row (first) index selects the origin vertex for the cost and the column (second) index selects the destination vertex. The row index for an origin vertex corresponds to its index in the array returned from getOriginVertices. The column index for a destination vertex corresponds to its index in the array returned from getDestinationVertices. Elements in the matrix corresponding to disconnected vertices will not be changed. The cost for a vertex to itself will be set to zero.

Specified by:

fillMatrix in interface AllPairsI

fillGraph

public AddI fillGraph(AddI graph)
               throws InvalidPropertyException,
                      VertexNotFoundException,
                      DuplicateEdgeException,
                      DuplicateVertexException

This finds all the paths costs from each of the origin vertices and all of the paths to each of the destination vertices. The vertices in the returned graph have added the union of the origin and destination vertices. The returned graph will have a directed edge between every distinct pair of vertices whose path cost is less than Double.POSITIVE_INFINITY.

Specified by:

fillGraph in interface AllPairsI

fillGraph

public AddI fillGraph(AddI graph,
                      int maxPathsOut,
                      int maxPathsIn)
               throws InvalidPropertyException,
                      VertexNotFoundException,
                      DuplicateEdgeException,
                      DuplicateVertexException

This finds the 'maxPathsOut' lowest cost paths from each of the origin vertices and the 'maxPathsIn' lowest cost paths to each of the destination vertices. The vertices in the returned graph have added the union of the origin and destination vertices. The returned graph will have a directed edge between every distinct pair of vertices whose path cost is less than Double.POSITIVE_INFINITY.

Specified by:

fillGraph in interface AllPairsI