Java: A quoi ressemble mon Prim?

Question

J'essaye d'implémenter l'algorithme de spanning tree minimum de Prim avec JGraphT. De quoi ça a l'air?

Un problème que j'ai rencontré était la gestion par JGraphT de tout ce qui est dirigé. Donc, parfois, il est nécessaire de faire des appels gênants pour inverser g.getEdgeSource(e) et g.getEdgeTarget(e) si elles ne se sont pas avérées justes.

J'ai essayé de l'implémenter à l'origine avec le tas de Fibonacci de JGraphT mais c'était trop dur donc j'ai juste fait un PQ régulier. Au lieu de définir des poids de bords inexistants à l'infini, je ne l'ai simplement pas ajouté à la file d'attente.

Conseil? Problèmes stylistiques? Des inefficacités flagrantes? Code que je devrais utiliser au lieu de rouler le mien?

public static Graph<String, DefaultWeightedEdge> primPQ(final WeightedGraph<String, DefaultWeightedEdge> g, String root) { 
    Graph<String, DefaultWeightedEdge> mst = new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 
    Queue<DefaultWeightedEdge> pq = new PriorityQueue<DefaultWeightedEdge>(g.vertexSet().size(), new Comparator<DefaultWeightedEdge>() { 
    @Override 
    public int compare(DefaultWeightedEdge o1, DefaultWeightedEdge o2) { 
     if (g.getEdgeWeight(o1) < g.getEdgeWeight(o2)) { 
     return -1; 
     } 
     if (g.getEdgeWeight(o1) > g.getEdgeWeight(o2)) { 
     return 1; 
     } 
     return 0; 
    } 
    }); 

    mst.addVertex(root); 
    DefaultWeightedEdge link; 

    for (String v : g.vertexSet()) { 
    link = g.getEdge(root, v); 
    if (link != null) { 
     pq.add(link); 
    } 
    } 

    //this is made difficult by JGraphT's assumption that everything is directed 
    DefaultWeightedEdge minEdge = pq.poll(); 
    String toAdd; 
    String alreadyFound; 
    String tmp; 

    while (minEdge != null) { 
    // guessing at which is in the MST 
    toAdd = g.getEdgeTarget(minEdge); 
    alreadyFound = g.getEdgeSource(minEdge); 

    if (!(mst.containsVertex(toAdd) && mst.containsVertex(alreadyFound))) { 
     // swap if backwards 
     if (mst.containsVertex(toAdd)) { 
     tmp = toAdd; 
     toAdd = alreadyFound; 
     alreadyFound = tmp; 
     } 
     mst.addVertex(toAdd); 
     mst.addEdge(alreadyFound, toAdd, minEdge); 
     System.out.format("%s --> %s\n", g.getEdgeSource(minEdge), toAdd); 

     for (String v : g.vertexSet()) { 
     if (! mst.containsVertex(v)) { 
      link = g.getEdge(toAdd, v); 
      if (pq.contains(link)) { 
      g.setEdgeWeight(minEdge, Math.min(g.getEdgeWeight(minEdge), g.getEdgeWeight(link))); 
      } 
      if (link != null && ! pq.contains(link)) { 
      pq.add(link); 
      } 
     } 
     } 
    } 
    minEdge = pq.poll(); 
    } 
    return mst; 
} 

Answer 1

J'ai comparé le résultat de votre algorithme pour une mine qui était un devoir et à la fois donne le même poids total minimum, continuez!

Answer 2

deux tout en augmentant le nombre d'arêtes et le nombre de sommets, je reçois des résultats différents, je serai de retour ...

Answer 3

OKAY, il semble bien maintenant. A propos, mon exercice était un peu compliqué: je devais écrire un algorithme qui trouve effectivement l'arbre couvrant minimum, mais mon algorithme devait procéder par élimination sur les bords. J'ai écrit quelque chose qui utilise un peu de profondeur en premier pour trouver des cycles et ensuite élimine le bord le plus pondéré en le "colorant" en rouge.

Votre alg PRIM donne le même poids total minimum que mon alg pour 4 graphiques générés aléatoirement N = 200 nœuds et diverses valeurs M = (N * (N-1)/k) pour k = 2,3,4,8 pour le nombre d'arêtes. A première vue, j'aurais pensé que ce genre de test était trop lourd, mais ce n'était pas le cas!