com.net2plan.libraries

Class GraphUtils.YenAlgorithm<V,E>

Object

com.net2plan.libraries.GraphUtils.YenAlgorithm<V,E>

Type Parameters:

V - Vertex type

E - Edge type

Enclosing class:

GraphUtils

public static class GraphUtils.YenAlgorithm<V,E>
extends Object

Class to calculate the (loopless) k-shortest paths between a node pair using Yen's algorithm.

Reference: J.Y. Yen, "Finding the K Shortest Loopless Paths in a Network," <i>Management Science</i>, vol. 17, no. 11, pp. 712-716, Jul. 1971

Since:

0.3.0

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo Zaragoza

Constructor Summary

Constructors

Constructor and Description
GraphUtils.YenAlgorithm(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev) Default constructor.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	acceptPath(GraphUtils.GraphPath<E> candidate) Indicates whether a path is valid.
boolean	compareCandidateToShortestPath(GraphUtils.GraphPath<E> candidate, GraphUtils.GraphPath<E> shortestPath) Indicates whether a path is valid when compared to the shortest path.
List<List<E>>	getPaths(V startVertex, V endVertex, int k) Returns the (loopless) k-shortest simple paths in increasing order of weight.

Methods inherited from class Object

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

Constructor Detail

GraphUtils.YenAlgorithm

public GraphUtils.YenAlgorithm(edu.uci.ics.jung.graph.Graph<V,E> graph,
                       org.apache.commons.collections15.Transformer<E,Double> nev)

Default constructor.

Parameters:

graph - Graph on which shortest paths are searched

nev - The class responsible for returning weights for edges

Since:

0.3.0

Method Detail

acceptPath

public boolean acceptPath(GraphUtils.GraphPath<E> candidate)

Indicates whether a path is valid. It can be override to implement checks like maximum path length. In contrast, compareCandidateToShortestPath() method. method can be used to compare current candidate path with the shortest path.

Parameters:

candidate - Candidate path

Returns:

true must be accepted. Otherwise, false

Since:

0.3.0

compareCandidateToShortestPath

public boolean compareCandidateToShortestPath(GraphUtils.GraphPath<E> candidate,
                                     GraphUtils.GraphPath<E> shortestPath)

Indicates whether a path is valid when compared to the shortest path. It can be override to implement checks like maximum distance from the shortest path.

Parameters:

candidate - Candidate path

shortestPath -

Returns:

true must be accepted. Otherwise, false

Since:

0.3.0

getPaths

public List<List<E>> getPaths(V startVertex,
                     V endVertex,
                     int k)

Returns the (loopless) k-shortest simple paths in increasing order of weight.

Important: If only n < k paths can be found, only such n paths will be returned.

Parameters:

startVertex - Start vertex of the calculated paths

endVertex - Target vertex of the calculated paths

k - Number of paths to be computed

Returns:

List of paths in increasing order of weight

Since:

0.2.0