drasys.or.graph.sp
Interface AllPairsI

All Known Implementing Classes:

Iterate

public interface AllPairsI

The interface used by all algorithms to access all pairs shortest path algorithms.

See Also:

Iterate

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 used to access vertex and edge properties.

 

Method Detail

setProperties

public void setProperties(PropertiesI properties)

Sets the properties object used to access vertex and edge properties.

setDestination

public void setDestination(boolean isDestination)

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

setDestination

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

Sets the destination flag for a vertex.

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.

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.

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.

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.

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_INFINITY. The cost for a vertex to itself is zero.

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 cost for a vertex to itself is zero and all the remaining costs will be set to Double.POSITIVE_INFINITY. 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.

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.

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.