Spanning

Algorithms

jgrapht.algorithms.spanning.boruvka(graph)

Compute the minimum spanning tree using Borůvka’s algorithm.

This implementation uses a union-find data structure (with union by rank and path compression heuristic) in order to track components. In graphs where edges have identical weights, edges with equal weights are ordered lexicographically. The running time is \(\mathcal{O}((m+n) \log n)\) under the assumption that the union-find uses path-compression. Here \(n\) is the number of vertices and \(m\) the number of edges of the graph.

Parameters

graph – The input graph

Returns

A tuple (weight, mst)

jgrapht.algorithms.spanning.kruskal(graph)

Compute the minimum spanning tree using Kruskal’s algorithm.

If the given graph is connected it computes the minimum spanning tree, otherwise it computes the minimum spanning forest. The algorithm runs in time \(\mathcal{O}(m \log m)\) or \(\mathcal{O}(m \log n)\) in case multiple edges are not allowed and thus \(m \le n^2\). Here \(n\) is the number of vertices and \(m\) the number of edges of the graph.

Parameters

graph – The input graph

Returns

A tuple (weight, mst)

jgrapht.algorithms.spanning.multiplicative_greedy(graph, k)

Greedy algorithm for \((2k-1)\)-multiplicative spanner construction (for any integer \(k \ge 1\).

The spanner is guaranteed to contain \(\mathcal{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 \(\mathcal{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 \(\mathcal{O}(m (n^{1+1/k} + n \log n))\) time by using Dijkstra’s algorithm. Edge weights must be non-negative.

Parameters

• graph – The input graph

• k – integer

Returns

tuple of the form (weight, spanner_edges)

jgrapht.algorithms.spanning.prim(graph)

Compute the minimum spanning tree using Prim’s algorithm.

The algorithm was developed by Czech mathematician V. Jarník and later independently by computer scientist Robert C. Prim and rediscovered by E. Dijkstra. This implementation uses a Fibonacci Heap in order to achieve a running time of \(\mathcal{O}(m+n\log n)\) where \(n\) is the number of vertices and \(m\) the number of edges of the graph.

Parameters

graph – The input graph

Returns

A tuple (weight, mst)