Class GreedyMultiplicativeSpanner<V,E>
- java.lang.Object
-
- org.jgrapht.alg.spanning.GreedyMultiplicativeSpanner<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
SpannerAlgorithm<E>
public class GreedyMultiplicativeSpanner<V,E> extends java.lang.Object implements SpannerAlgorithm<E>
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} + n \log n))$ time by using Dijkstra's algorithm. Edge weights must be non-negative.
- Author:
- Dimitrios Michail
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpannerAlgorithm
SpannerAlgorithm.Spanner<E>, SpannerAlgorithm.SpannerImpl<E>
-
-
Constructor Summary
Constructors Constructor Description GreedyMultiplicativeSpanner(Graph<V,E> graph, int k)
Constructs instance to compute a $(2k-1)$-spanner of an undirected graph.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description SpannerAlgorithm.Spanner<E>
getSpanner()
Computes a graph spanner.
-
-
-
Constructor Detail
-
GreedyMultiplicativeSpanner
public GreedyMultiplicativeSpanner(Graph<V,E> graph, int k)
Constructs instance to compute a $(2k-1)$-spanner of an undirected graph.- Parameters:
graph
- an undirected graphk
- positive integer.- Throws:
java.lang.IllegalArgumentException
- if the graph is not undirectedjava.lang.IllegalArgumentException
- if k is not positive
-
-
Method Detail
-
getSpanner
public SpannerAlgorithm.Spanner<E> getSpanner()
Description copied from interface:SpannerAlgorithm
Computes a graph spanner.- Specified by:
getSpanner
in interfaceSpannerAlgorithm<V>
- Returns:
- a graph spanner
-
-