com.net2plan.libraries

Class GraphUtils.SuurballeTarjanAlgorithm<V,E>

Object

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

Type Parameters:

V - Vertex type

E - Edge type

Enclosing class:

GraphUtils

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

Class to calculate the shortest link-disjoint path pair between two nodes using Suurballe-Tarjan's algorithm.

Reference: J.W. Suurballe, R.E. Tarjan, "A Quick Method for Finding Shortest Pairs of Disjoint Paths," <i>Networks</i>, vol. 14, no. 2, pp. 325-335, 1984

Since:

0.3.0

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo Zaragoza

Constructor Summary

Constructors

Constructor and Description
GraphUtils.SuurballeTarjanAlgorithm(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev) Default constructor.
GraphUtils.SuurballeTarjanAlgorithm(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, boolean cached) This constructor allows to configure if the shortest-path algorithm should cached previous computations.

Method Summary

Methods

Modifier and Type	Method and Description
List<List<E>>	getDisjointPaths(V startVertex, V endVertex) Returns the shortest link-disjoint path pair (in increasing order of weight).

Methods inherited from class Object

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

Constructor Detail

GraphUtils.SuurballeTarjanAlgorithm

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

Default constructor. Previous results from the shortest-path algorithm are cached.

Parameters:

graph - Graph on which shortest paths are searched

nev - The class responsible for returning weights for edges

Since:

0.3.0

GraphUtils.SuurballeTarjanAlgorithm

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

This constructor allows to configure if the shortest-path algorithm should cached previous computations.

Parameters:

graph - Graph on which shortest paths are searched

nev - The class responsible for returning weights for edges

cached - Indicates whether previous computations from the shortest-path algorithm should be cached

Since:

0.3.0

Method Detail

getDisjointPaths

public List<List<E>> getDisjointPaths(V startVertex,
                             V endVertex)

Returns the shortest link-disjoint path pair (in increasing order of weight).

Important: If only one path can be found, only such a path will be returned.

Parameters:

startVertex - Start vertex of the calculated paths

endVertex - Target vertex of the calculated paths

Returns:

List of paths in increasing order of weight

Since:

0.3.0