/*
 * (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.