Java: spanning tree minimum avec JGraphT?

Question

J'ai un problème qui peut essentiellement être considéré comme un graphique. J'envisage d'utiliser JGraphT pour la mettre en œuvre au lieu de rouler mon propre. Quelle serait la meilleure façon d'obtenir un arbre couvrant minimal d'un graphique à l'aide JGraphT?

Answer 1

Malheureusement, je ne connais pas assez la théorie des graphes pour vous donner une réponse complète, directe, mais je l'ai utilisé JGraphT dans quelques projets, alors peut-être cela vous aidera.

La liste des algorithmes inclus JGraphT est ici: http : //www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html, et vous pouvez également trouver traversals graphique mis en œuvre itérateurs (si cela est une aide) ici: http://www.jgrapht.org/javadoc/org/jgrapht/traverse/ package-summary.html

Je suis sûr qu'aucun de ces algorithmes vous voulez obtenir que vous voulez sortir de la boîte, de sorte que vous auriez à ce code vous-même, mais je peux vous dire par expérience que le codage sur le dessus de JGraphT au lieu de commencer à partir de zéro est beaucoup plus facile. Il y a aussi un classe qui tas de fibonacci serait probablement aider à la mise en œuvre l'algorithme de Prim.

Si vous avez besoin d'aide avec l'algorithme lui-même, il y a un certain nombre d'algorithmes avec des entrées Wikipedia, avec des descriptions détaillées et pseudocode. Les minimum couvrant liens article arbre pour eux.

Answer 2

Jung a une mise en œuvre de cela.

Answer 3

ClosestFirstIterator peut vous aider. Il construit un arbre couvrant l'utilisation itérer sur tout tas de fibonacci les sommets.

ClosestFirstIterator fournit les méthodes getShortestPathLength () et getSpanningTreeEdge () pour obtenir des parties de l'arbre couvrant minimal.

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

Dernières versions de la bibliothèque JGraphT ont différents choix pour un algorithme MST, pas besoin de mettre en œuvre un à partir de zéro.

Le code suivant fonctionne avec Java 8 et la version JGraphT 1.3.0. Il calcule l'arbre minimum d'un petit graphique en utilisant les algorithmes de (a) Prim, (b) Kruskal et (c) Borůvka. Des détails sur les différents algorithmes peuvent être trouvés dans l'article wikipedia sur le problème mst .

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

    }

}