org.jgrapht.alg

Class GreedyMultiplicativeSpanner<V,E>

java.lang.Object

org.jgrapht.alg.GreedyMultiplicativeSpanner<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public class GreedyMultiplicativeSpanner<V,E>
extends Object

Greedy algorithm for (2k-1)-multiplicative spanner construction (for any integer k >= 1).

The spanner is guaranteed to contain O(n^{1+1/k}) edges and the shortest path distance between any two vertices in the spanner is at most 2k-1 times the corresponding shortest path distance in the original graph. Here n denotes the number of vertices of the graph.

The algorithm is described in: Althoefer, Das, Dobkin, Joseph, Soares. On Sparse Spanners of Weighted Graphs. Discrete Computational Geometry 9(1):81-100, 1993.

If the graph is unweighted the algorithm runs in O(m n^{1+1/k}) time. Setting k to infinity will result in a slow version of Kruskal's algorithm where cycle detection is performed by a BFS computation. In such a case use the implementation of Kruskal with union-find. Here n and m are the number of vertices and edges of the graph respectively.

If the graph is weighted the algorithm runs in O(m (n^{1+1/k} + nlogn)) time by using Dijkstra's algorithm. Edge weights must be non-negative.

Since:

July 15, 2016

Author:

Dimitrios Michail

Constructor Summary

Constructors

Constructor and Description
GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph, int k) Constructs instance to compute a (2k-1)-spanner of a graph.

Method Summary

Modifier and Type	Method and Description
Set<E>	getSpannerEdgeSet() Get the edge set of the spanner.

Methods inherited from class java.lang.Object

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

Constructor Detail

GreedyMultiplicativeSpanner

public GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph,
                                   int k)

Constructs instance to compute a (2k-1)-spanner of a graph.

Parameters:

graph - the input graph

k - positive integer.

Method Detail

getSpannerEdgeSet

public Set<E> getSpannerEdgeSet()

Get the edge set of the spanner.

Returns:

the set of edges of the spanner