Wie boost :: graph dijkstra Algorithmus verwenden, wenn Vertex-Eigenschaften Zeiger sind?

Question

Ich verwende Boost-Graphen, um Graphen zu verwalten, und ich muss einen Maxmin-Baum erstellen.
Jetzt versuche ich Boost Dijkstra-Algorithmus zu verwenden, aber ich verwende einen Zeiger auf meine Klasse als Vertex-Eigenschaft anstelle von typedef property<vertex_index_t, int> my_prop, und ich kann es jetzt nicht ändern.
Also, wie kann ich Vorgänger-Map und Distanz-Map für mein Diagramm erstellen?

Mein Code sieht wie folgt aus (und diese Vorgänger und Abstandskarten funktionieren nicht):

struct LinkStruct {...}; 
class Node {...}; 
typedef Node* NodePtr; 

typedef adjacency_list<listS, listS, bidirectionalS, NodePtr, LinkStruct> MyGraph; 
typedef MyGraph::vertex_descriptor vertex_descriptor; 

MyGraph m_graph; 
// Fill the graph 
{...} 

// Dijkstra parameters 
std::vector<vertex_descriptor> result_tree(some_struct.size(), MyGraph::null_vertex()); 
std::vector<uint32_t> result_distances(some_struct.size(), 0); 

// Compute maxmin tree 
dijkstra_shortest_paths_no_color_map(
    m_graph, // Graph 
    root_vertex, // Start vertex 
    weight_map(boost::get(&LinkStruct::weight, m_graph)). // Link property map 
    distance_compare([](uint32_t first, uint32_t second) -> bool { 
            return first > second; }). // Compare maxmin path lengths (if maxmin > maxmin) 
    distance_combine([](uint32_t first, uint32_t second) -> uint32_t { 
         return (first > second) ? second : first; }). // Get min weight of the path 
    predecessor_map(make_iterator_property_map(result_tree.begin(), 
               boost::get(vertex_index, m_graph))). // Result tree 
    distance_map(make_iterator_property_map(result_distances.begin(), 
              boost::get(vertex_index, m_graph))) // Result distances 
); 

P. S.
Ich benutze Zeiger in Vertex-Definition, weil ich viele Graphen mit dem gleichen Knoten haben.
Vielleicht gibt es einen Weg herum, ohne Vertex-Eigenschaft in der Grafikdefinition zu ändern?

Answer 1

Q.
Wenn ich es richtig understant, verwende ich make_iterator_property_map eine externe Eigenschaft Karte zu schaffen, sondern um es zu schaffen Ich brauche die Vertex-ID-Eigenschaft Karte zu übergeben. Aber ich kann nicht auf boost :: get zugreifen, weil die Vertex-Eigenschaft ein Zeiger ist. Welchen Typ sollte ich an boost :: get (some_type, m_graph) weitergeben, um eine solche ID-Map zu erhalten?

Sie machen/jede Art von PropertyMap, die die Anforderung erfüllt /. Sie müssen es nicht mit dem Diagramm verknüpfen. Sie können es bei Bedarf einfach an die Algorithmen übergeben (wodurch auch klar wird, an welcher Stelle Sie versprechen, die Diagrammdaten und die Propertymap synchron zu halten).

Es ist mir gerade in den Sinn gekommen, dass Sie tatsächlich in der Lage sein könnten, das letzte Problem zu lösen - die Last, die Property Map zu verwalten. Das heißt, wenn Ihr Index aus dem Zeigerwert abgeleitet werden kann (vielleicht von der Struktur abgerufen, auf die er zeigt).

können Sie verwenden die

• transform_value_property_map
• function_property_map
• vielleicht kombiniert beide mit z.B. compose_property_map

Jeder dieser Typen hat eine entsprechende herzuleiten Factory-Methode make_transform_value_property_map, make_function_property_map usw., so dass Sie manuell die resultierenden Typen nicht buchstabieren müssen.

Sie können search meine älteren Antworten für Beispiele, was mit diesen getan werden kann.

Proben:

• Dijkstra graph with a table of weights on each edge
• Weight map as function in Boost Graph Dijkstra algorithm
• Allgemeine Punkt über Immobilien Karte map set/get requests into C++ class/structure changes