/*
* (C) Copyright 2013-2017, by Alexey Kudinkin 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.*;
/**
* An implementation of Prim's
* algorithm that finds a minimum spanning tree/forest subject to connectivity of the supplied
* weighted undirected graph. The algorithm was developed by Czech mathematician V. JarnÃk and later
* independently by computer scientist Robert C. Prim and rediscovered by E. Dijkstra.
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Alexey Kudinkin
* @since Mar 5, 2013
*/
public class PrimMinimumSpanningTree
implements SpanningTreeAlgorithm
{
private final Graph g;
/**
* Construct a new instance of the algorithm.
*
* @param graph the input graph
*/
public PrimMinimumSpanningTree(Graph graph)
{
this.g = Objects.requireNonNull(graph, "Graph cannot be null");
}
/**
* {@inheritDoc}
*/
@Override
public SpanningTree getSpanningTree()
{
Set minimumSpanningTreeEdgeSet = new HashSet<>(g.vertexSet().size());
double spanningTreeWeight = 0d;
Set unspanned = new HashSet<>(g.vertexSet());
while (!unspanned.isEmpty()) {
Iterator ri = unspanned.iterator();
V root = ri.next();
ri.remove();
// Edges crossing the cut C = (S, V \ S), where S is set of
// already spanned vertices
PriorityQueue dangling = new PriorityQueue<>(
g.edgeSet().size(),
(lop, rop) -> Double.valueOf(g.getEdgeWeight(lop)).compareTo(g.getEdgeWeight(rop)));
dangling.addAll(g.edgesOf(root));
for (E next; (next = dangling.poll()) != null;) {
V s, t = unspanned.contains(s = g.getEdgeSource(next)) ? s : g.getEdgeTarget(next);
// Decayed edges aren't removed from priority-queue so that
// having them just ignored being encountered through min-max
// traversal
if (!unspanned.contains(t)) {
continue;
}
minimumSpanningTreeEdgeSet.add(next);
spanningTreeWeight += g.getEdgeWeight(next);
unspanned.remove(t);
for (E e : g.edgesOf(t)) {
if (unspanned.contains(
g.getEdgeSource(e).equals(t) ? g.getEdgeTarget(e) : g.getEdgeSource(e)))
{
dangling.add(e);
}
}
}
}
return new SpanningTreeImpl<>(minimumSpanningTreeEdgeSet, spanningTreeWeight);
}
}
// End PrimMinimumSpanningTree.java
Ads help maintain this website.