Java: minimo spanning tree con JGraphT?

Question

Ho un problema che può essere essenzialmente visto come un grafico. Sto pensando di utilizzare JGraphT per la sua attuazione, invece di rotolare mio. Quale sarebbe il modo migliore per ottenere un albero di copertura minimo di un grafico utilizzando JGraphT?

Answer 1

Purtroppo, io non ne so abbastanza teoria dei grafi per darvi una risposta completa, diretta, ma ho usato JGraphT in alcuni progetti, così forse questo sarà di aiuto.

La lista degli algoritmi incluso con JGraphT è qui: http : //www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html , e si possono anche trovare attraversamenti grafico implementato come iteratori (se questo è di aiuto) qui: http://www.jgrapht.org/javadoc/org/jgrapht/traverse/ pacchetto-summary.html

Sono abbastanza sicuro che nessuno di questi algoritmi l'otterrà vuole si vuole fuori dalla scatola, in modo da dovreste codice da soli, ma si può dire per esperienza che codifica in cima JGraphT al contrario di partenza da zero è molto più facile. C'è anche un FibonacciHeap classe che presumibilmente aiutare con l'attuazione algoritmo di Prim.

Se hai bisogno di aiuto con l'algoritmo in sé, ci sono una serie di algoritmi con voci di Wikipedia, con descrizioni dettagliate e pseudocodice. I minimo spanning link articolo albero a loro.

Answer 2

Jung ha un'implementazione di questo.

Answer 3

ClosestFirstIterator può aiutarti. Si costruisce un albero di copertura utilizzando FibonacciHeap mentre l'iterazione di vertici.

ClosestFirstIterator fornisce i metodi getShortestPathLength () e getSpanningTreeEdge () per ottenere parti dell'albero di copertura minimo.

// 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

Ultime versioni della libreria JGraphT hanno varie scelte per un algoritmo MST, non c'è bisogno di implementare uno da zero.

Il seguente codice funziona con Java 8 e JGraphT versione 1.3.0. Calcola l'albero di copertura minimo di un piccolo grafico utilizzando gli algoritmi di (a) Prim, (b) Kruskal e (c) Borůvka. Dettagli sui diversi algoritmi si possono trovare in questo articolo Wikipedia sulla mst problema .

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);
        }

    }

}