C++ Boost Prim-Algorithmus mit benutzerdefinierten Gewichten?

Question

Ich versuche, boots prims Algorithmus zu verwenden, um den minimalen Spannbaum mit Kantengewicht und einer ID-Nummer statt nur Kantengewicht zu finden.

Zum Beispiel, wenn beide Kantengewichte 1 wären, würde die ID verglichen werden, je nachdem was weniger war, würde die Krawatte brechen.

Ich habe eine EdgeWeight-Klasse erstellt und die Operatoren < und + überladen, um dies zu tun, und dann die Eigenschaft edge_weight_t von int in EdgeWeight geändert, in der Hoffnung, dass es funktioniert.

// TestPrim.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 

#include <boost/config.hpp> 
#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/prim_minimum_spanning_tree.hpp> 

using namespace std; 

class EdgeWeight{ 
    public: 
    EdgeWeight(){} 
    EdgeWeight(int weightIn, int destinationIdIn){ 
     weight = weightIn; 
     destinationId = destinationIdIn; 
    } 

     bool operator<(const EdgeWeight& rhs) const { 
     if (weight < rhs.weight) 
      return true; 
     else if(weight == rhs.weight){ 
      if (destinationId < rhs.destinationId) 
       return true; 
      else 
       return false; 
     } 
     else 
      return false; 
     } 

    EdgeWeight operator+(const EdgeWeight& rhs) const { 
     EdgeWeight temp; 
     temp.weight = weight + rhs.weight; 
     temp.destinationId = destinationId + rhs.destinationId; 
     return temp; 
     } 

    int weight; 
    int destinationId; 
}; 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    using namespace boost; 
    typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, EdgeWeight>,  property < edge_weight_t, EdgeWeight > > Graph; 
    typedef std::pair < int, int >E; 
    const int num_nodes = 5; 
    E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3), 
    E(3, 4), E(4, 0) 
    }; 
    EdgeWeight weights[] = { EdgeWeight(1, 2), EdgeWeight(1, 3), EdgeWeight(2, 4), 
     EdgeWeight(7, 1), EdgeWeight(3, 3), EdgeWeight(1, 4), EdgeWeight(1, 0) }; 
    Graph g(edges, edges + sizeof(edges)/sizeof(E), weights, num_nodes); 
    property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g); 
    std::vector < graph_traits <Graph>::vertex_descriptor > p(num_vertices(g)); 
    prim_minimum_spanning_tree(g, &p[0]); 

    for (std::size_t i = 0; i != p.size(); ++i) 
    if (p[i] != i) 
     std::cout << "parent[" << i << "] = " << p[i] << std::endl; 
    else 
     std::cout << "parent[" << i << "] = no parent" << std::endl; 

    return EXIT_SUCCESS; 
} 

ich einen Fehler habe, „c: \ Programme (x86) \ Microsoft Visual Studio 10.0 \ vc \ include \ Grenzen (92): Fehler C2440: '': Konvertierung von 'int' zu ' D ' 1> Kein Konstruktor könnte den Quelltyp verwenden, oder Konstruktor Überladung Auflösung war mehrdeutig "

Mache ich das den richtigen Weg? Gibt es einen besseren Weg, dies zu tun?

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

edit: ok so implementiert ich die Gewichte für jetzt cjm die gestörte Methode verwendet, aber in die Zukunft, die ich glaube, ich werde das obige Verfahren irgendwie verwenden haben, immer noch fragen, wie es

edit2 tun: basierend auf Jeremias reponse änderte ich den vertex_distance_t von int nach EdgeWeight bekam aber den gleichen Fehler

Answer 1

Boosts Implementierung des "Prim's" -Algorithmus (Jarník entdeckte den Algorithmus fast dreißig Jahre vor Prim) verwendet eine generische Implementierung des Dijkstra-Algorithmus als Subroutine. Ich bin sicher, dass jemand dachte, dass dies wirklich clever war.

Dijkstra-Algorithmus benötigt nichtnegative Gewichte, die Addition mit Identität und Vergleich unterstützen, und diese Operationen müssen kompatibel sein (für alle x, y, z, wenn x < = y, dann x + z < = y + z). In der Praxis ist der einzige nützliche Weg, diese Operationen zu instanziieren, der übliche (ich nehme das zurück; es ist möglich, den Algorithmus von Dijkstra auf die gleiche Weise zu brechen), so nimmt Boosts Implementierung des Dijkstra-Algorithmus vernünftigerweise die Existenz von "unendlich" an (std::numeric_limits<vertex_distance_t>::max()). Es behauptet auch, dass alle Gewichte nicht negativ sind.

Im Gegensatz dazu benötigt der Algorithmus von Prim Gewichtungen, die nur Vergleiche unterstützen. Sie mögen sich fragen, was das "Minimum" im "minimalen Spannbaum" ohne Addition bedeutet, aber eine alternative Charakterisierung eines minimalen Spannbaums ist, dass für jeden Weg P von einem Eckpunkt zu einem Eckpunkt v die längste Kante in P ist mindestens so lange wie die längste Kante im Baumpfad von u nach v.

Das Ergebnis ist, dass Boosts Implementierung des Prim-Algorithmus einige ungerechtfertigte Annahmen trifft. Sie können wie folgt um sie herum codieren, aber Boost scheint nicht vertraglich verpflichtet zu sein, diesen Hack in Zukunft nicht zu brechen.

• Entfernen Sie den Additionsoperator; Es wird nicht benutzt.

• Da Boost behaupten wird, dass all Ihre Gewichte nicht kleiner als der standardmäßig konstruierte Wert sind, nehmen wir den Standard "negative Unendlichkeit".

  #include <limits> 
  ... 
  EdgeWeight() : weight(numeric_limits<int>::min()), 
         destinationId(numeric_limits<int>::min()) {} 
  

• -Boost benötigt "positive Unendlichkeit", so brauchen wir std::numeric_limits zu spezialisieren.

  namespace std { 
  template<> 
  struct numeric_limits<EdgeWeight> { 
      static EdgeWeight max() { return EdgeWeight(numeric_limits<int>::max(), 
                 numeric_limits<int>::max()); } 
  }; 
  } 
  

• Sie können den Vergleich vereinfachen.

  bool operator<(const EdgeWeight& rhs) const { 
      return (weight < rhs.weight || 
        (weight == rhs.weight && destinationId < rhs.destinationId)); 
  } 
  

Answer 2

der Scheitelabstand Karte value_type muss die gleiche wie t sein er Kantengewichtstyp für den Algorithmus zu arbeiten. Die Dokumentation impliziert, dass (im ersten Teil der Beschreibung von distance_map) aber nicht explizit darauf hingewiesen wird. Ich habe (seit Beantwortung dieser Frage) die Dokumentation im Boost-Koffer geklärt und korrigiert.