java - Java: Minimum spanning tree with JGraphT?

Question

I have a problem that can essentially be viewed as a graph. I'm considering using JGraphT to implement it instead of rolling my own. What would be the best way to get a minimum spanning tree out of a graph using JGraphT?

Answer 1

Unfortunately, I don't know enough graph theory to give you a complete, direct answer, but I have used jgrapht in a few projects, so maybe this will help.

The list of algorithms included with jgrapht is here: http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html, and you can also find graph traversals implemented as iterators (if that is any help) here: http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html

I'm pretty sure none of those algorithms will get you want you want out of the box, so you'd have to code it yourself, but I can tell you from experience that coding on top of jgrapht as opposed to starting from scratch is A LOT easier. There is also a FibonacciHeap class that would presumably help with implementing Prim's algorithm.

If you need help with the algorithm itself, there are a number of algorithms with Wikipedia entries, with detailed descriptions and pseudocode. The Minimum spanning tree article links to them.

Answer 2

Jung has an implementation of this.

Answer 3

ClosestFirstIterator may help you out. It builds a spanning tree using FibonacciHeap while iterating over the vertices.

ClosestFirstIterator provides the methods getShortestPathLength() and getSpanningTreeEdge() to get parts of the minimum spanning tree.

// instantiate the iterator
ClosestFirstIterator<V,E> it = new ClosestFirstIterator<V,E>(graph, start_vertex);

// iterate to build the tree
while(it.hasNext())
  it.next();

// query
double distance = getShortestPathLength(vertex);
E next_edge = getSpanningTreeEdge(vertex);

Answer 4

Latest versions of the JGraphT library have various choices for an MST algorithm, no need to implement one from scratch.

The following code works with Java 8 and JGraphT version 1.3.0. It computes the minimum spanning tree of a small graph using the algorithms by (a) Prim, (b) Kruskal and (c) Borůvka. Details about the different algorithms can be found in the wikipedia article about the mst problem.

package org.myorg.mstdemo;

import org.jgrapht.Graph;
import org.jgrapht.alg.spanning.BoruvkaMinimumSpanningTree;
import org.jgrapht.alg.spanning.KruskalMinimumSpanningTree;
import org.jgrapht.alg.spanning.PrimMinimumSpanningTree;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.builder.GraphTypeBuilder;
import org.jgrapht.util.SupplierUtil;

/**
 * MST demo
 */
public class App {

    public static void main(String[] args) {

        Graph<String, DefaultWeightedEdge> graph = GraphTypeBuilder
                .undirected()
                .weighted(true)
                .allowingMultipleEdges(false)
                .allowingSelfLoops(false)
                .vertexSupplier(SupplierUtil.createStringSupplier())
                .edgeSupplier(SupplierUtil.createDefaultWeightedEdgeSupplier())
                .buildGraph();

        String v0 = graph.addVertex();
        String v1 = graph.addVertex();
        String v2 = graph.addVertex();

        DefaultWeightedEdge e1 = graph.addEdge(v0, v1);
        DefaultWeightedEdge e2 = graph.addEdge(v1, v2);
        DefaultWeightedEdge e3 = graph.addEdge(v0, v2);

        graph.setEdgeWeight(e1, 100d);
        graph.setEdgeWeight(e2, 5d);
        graph.setEdgeWeight(e3, 1d);

        System.out.println("Prim:");
        for(DefaultWeightedEdge e: new PrimMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

        System.out.println("Kruskal:");
        for(DefaultWeightedEdge e: new KruskalMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

        System.out.println("Borůvka:");
        for(DefaultWeightedEdge e: new BoruvkaMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

    }

}