/*
* (C) Copyright 2016-2017, by Dimitrios Michail and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.spanning;
import java.util.*;
import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.util.*;
/**
* Borůvka's algorithm for the computation of a minimum spanning tree.
*
*
* See the article on
* wikipedia for more
* information on the history of the 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 O((E+V) logV) under the
* assumption that the union-find uses path-compression.
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Dimitrios Michail
* @since November 2016
*/
public class BoruvkaMinimumSpanningTree
implements SpanningTreeAlgorithm
{
private final Graph graph;
private final Comparator comparator;
/**
* Construct a new instance of the algorithm.
*
* @param graph the input graph
*/
public BoruvkaMinimumSpanningTree(Graph graph)
{
this.graph = Objects.requireNonNull(graph, "Graph cannot be null");
this.comparator = new ToleranceDoubleComparator();
}
/**
* {@inheritDoc}
*/
@Override
public SpanningTree getSpanningTree()
{
// create result placeholder
Set mstEdges = new LinkedHashSet<>();
double mstWeight = 0d;
// fix edge order for unique comparison of edge weights
Map edgeOrder = new HashMap<>();
int i = 0;
for (E e : graph.edgeSet()) {
edgeOrder.put(e, i++);
}
// initialize forest
UnionFind forest = new UnionFind<>(graph.vertexSet());
Map bestEdge = new LinkedHashMap<>();
do {
// find safe edges
bestEdge.clear();
for (E e : graph.edgeSet()) {
V sTree = forest.find(graph.getEdgeSource(e));
V tTree = forest.find(graph.getEdgeTarget(e));
if (sTree.equals(tTree)) {
// same tree, skip
continue;
}
double eWeight = graph.getEdgeWeight(e);
// check if better edge
E sTreeEdge = bestEdge.get(sTree);
if (sTreeEdge == null) {
bestEdge.put(sTree, e);
} else {
double sTreeEdgeWeight = graph.getEdgeWeight(sTreeEdge);
int c = comparator.compare(eWeight, sTreeEdgeWeight);
if (c < 0 || (c == 0 && edgeOrder.get(e) < edgeOrder.get(sTreeEdge))) {
bestEdge.put(sTree, e);
}
}
// check if better edge
E tTreeEdge = bestEdge.get(tTree);
if (tTreeEdge == null) {
bestEdge.put(tTree, e);
} else {
double tTreeEdgeWeight = graph.getEdgeWeight(tTreeEdge);
int c = comparator.compare(eWeight, tTreeEdgeWeight);
if (c < 0 || (c == 0 && edgeOrder.get(e) < edgeOrder.get(tTreeEdge))) {
bestEdge.put(tTree, e);
}
}
}
// add safe edges to forest
for (V v : bestEdge.keySet()) {
E e = bestEdge.get(v);
V sTree = forest.find(graph.getEdgeSource(e));
V tTree = forest.find(graph.getEdgeTarget(e));
if (sTree.equals(tTree)) {
// same tree, skip
continue;
}
mstEdges.add(e);
mstWeight += graph.getEdgeWeight(e);
forest.union(sTree, tTree);
}
} while (!bestEdge.isEmpty());
// return mst
return new SpanningTreeImpl<>(mstEdges, mstWeight);
}
}
Ads help maintain this website.