Minimum Spanning Tree mit Boost-

Question

Ich habe den folgenden Code, der einen ungerichteten Graphen erzeugt:

// --- Header File --- 
class Node { ... }; 
struct Edge { float weight; }; 
typedef adjacency_list<vecS, vecS, undirectedS, Node, Edge> Grafo; 

class MST 
{ 
    public: 
     MST(std::vector<Node> nodes); 
     Grafo g; 
     vector<edge_t> build(); 
}; 

// --- cpp File --- 
MST::MST(std::vector<Node> nodes) { // build the graph by setting vertices and edges... } 

vector<edge_t> MST::build() 
{ 
    vector<edge_t> mst; 
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst)); 
    return mst; 
} 

Das Problem ist in der Zeile, die ich Kruskal nennen: kruskal_minimum_spanning_tree(). Wenn ich diese Zeile Kommentar wird es in Ordnung kompilieren, und ich kann die Grafik mit graphviz exportieren (können Sie die Grafik bei webgraphviz.com sehen):

graph G { 
0[label="a"]; 
1[label="b"]; 
2[label="c"]; 
3[label="d"]; 
4[label="e"]; 
0--1 [label=80.4487381]; 
0--2 [label=406.060333]; 
0--3 [label=405.738831]; 
0--4 [label=434.203857]; 
1--2 [label=25.9422436]; 
1--3 [label=210.344955]; 
1--4 [label=246.965591]; 
2--3 [label=35.805027]; 
2--4 [label=35.1283379]; 
3--4 [label=167.5858]; 
} 

Aber wenn ich versuche, mit dieser Linie zu kompilieren bekomme ich eine Menge von Fehlern von Boost (ich benutze g ++ 4.9.2). Der erste Fehler ist: error: forming reference to void typedef value_type& reference;, dieser Fehler wird mehrmals wiederholt. Andere Fehler, die angezeigt wird:

error: no matching function for call to 'get(boost::edge_weight_t, const boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Symbol, Edge>&)' 
     get(edge_weight, g)); 

Also habe ich versucht, get(edge_weight, g); vor Aufruf der Kruskal Methode hinzufügen, aber ich habe Notizen sagen:

note: types 'boost::subgraph<Graph>' and 'const boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Symbol, Edge>' have incompatible cv-qualifiers 
     get(edge_weight, g)); 

und

note: mismatched types 'const boost::two_bit_color_map<IndexMap>' and 'boost::edge_weight_t' 
     get(edge_weight, g)); 

I don‘ Ich weiß was zu tun ist. Dies ist das erste Mal, dass ich Boost Graph Library verwende. Es ist sehr mächtig, aber nicht leicht zu verstehen.

Answer 1

TLDR:

Das Problem Sie konfrontiert sind, ist, dass der Algorithmus eine grafische Darstellung der Gewichts Karte zugreifen muss und Ihnen muss man nicht standardmäßig über:

kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
         weight_map(get(&Edge::weight, g)); 

Ursprüngliche Antwort verwenden . Wenn Sie in the documentation bei der Unterzeichnung des Algorithmus können Sie sehen, dass es ist:

template <class Graph, class OutputIterator, class P, class T, class R> 
OutputIterator kruskal_minimum_spanning_tree(Graph& g, OutputIterator tree_edges, 
            const bgl_named_params<P, T, R>& params = all defaults); 

Es hat zwei „normalen“ Parameter (die, die Sie verwendet werden) und dann seltsam ein bgl_named_params<P, T, R>& params suchen. Mit diesem letzten Parameter können Sie die vier Parameter verwenden, die später auf dieser Seite aufgeführt sind: weight_map, rank_map, predecessor_map und vertex_index_map. Wenn Sie keinen dieser Parameter verwenden, wird der Standardwert verwendet. Bei weight_map ist dieser Standardwert get(edge_weight,g). Das funktioniert nur, wenn Sie eine innere edge_weight Eigenschaft in Ihrem Diagramm haben, was bedeutet, Ihr Diagramm wie folgt definiert ist:

typedef adjacency_list<vecS, vecS, undirectedS, 
        property<vertex_name_t,char>,//Could also be `Node` unless you use another algorithm with requirements on the vertices 
        property<edge_weight_t,float> 
        > InternalPropGraph; 

Aber wenn diese Definition erforderlich war kruskal_minimum_spanning_tree (oder einen anderen Algorithmus) zu verwenden, dann würde bundled properties nicht sein überhaupt nützlich. Sie müssen nur die Standardeinstellung außer Kraft setzen weight_map die genannten Parameter:

//typedef adjacency_list<vecS, vecS, undirectedS, Node, Edge> Grafo; 
... 
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
         weight_map(get(&Edge::weight, g)); 

Um eine Eigenschaft Karte zuzugreifen, die eine Ecke/Kante Beschreiber mit einem Mitglied Ihrer structs bezieht man einfach get(&Struct::member, g) verwenden können.

Eine letzte Bemerkung über benannte Parameter, wenn in Ihrem Aufruf des Algorithmus müssen Sie mehr als einen dieser Parameter verwenden, müssen Sie sie mit . statt der üblichen , da in der Signatur params trotz seines Namens ist verketten ein einzelner Parameter.

//the order of the named params is irrelevant 
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
           weight_map(my_weights) 
           .vertex_index_map(my_indices) 
           .predecessor_map(my_predecessors)); 

Here ist ein Beispiel, das auf etwas ähnliches zeigt, was Sie wollen beide inneren Eigenschaften und gebündelt Eigenschaften verwenden. Es verwendet absichtlich verschiedene Möglichkeiten zum Festlegen/Zugreifen auf Eigenschaften, um zu zeigen, was Sie tun können.