Comment utiliser l'algorithme boost :: graph dijkstra si les propriétés de vertex sont des pointeurs?

Question

J'utilise le graphe boost pour gérer les graphes et j'ai besoin de faire un arbre maxmin.
Maintenant, j'essaie d'utiliser l'algorithme de boost dijkstra, mais j'utilise un pointeur vers ma classe en tant que propriété vertex au lieu d'utiliser typedef property<vertex_index_t, int> my_prop, et je ne peux pas le changer maintenant.
Alors, comment puis-je créer predecessor_map et distance_map pour mon graphe?

Mon code ressemble à ceci (et ces cartes prédécesseurs et de distance ne fonctionne pas):

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

post-scriptum
J'utilise un pointeur dans la définition de vertex parce que j'ai beaucoup de graphes avec le même noeud.
Peut-être qu'il existe un moyen de contourner sans modifier la propriété vertex dans la définition graphique?

Answer 1

Q.
Si j'understant ce droit, j'utilise make_iterator_property_map pour créer une carte de propriété externe, mais pour créer je besoin de passer le sommet ID carte de propriété. Mais je ne peux pas y accéder via boost :: get, car la propriété vertex est un pointeur. Quel type dois-je passer à boost :: get (some_type, m_graph) pour obtenir une telle carte d'identité?

Vous faites/n'importe quel type de propertymap qui satisfait à l'exigence /. Vous n'avez pas besoin de l'associer au graphique. Vous pouvez simplement le passer aux algorithmes quand vous en avez besoin (ce qui permet également de savoir à quel moment vous promettez d'avoir les données du graphique et le propertymap en synchronisation). Il m'est simplement venu à l'esprit que vous pourriez peut-être obtenir un laissez-passer sur ce dernier numéro - le fardeau de maintenir la carte de la propriété. Autrement dit, si votre index peut être dérivé de la valeur du pointeur (peut-être récupérée à partir de la structure vers laquelle il pointe).

Vous pouvez utiliser le

• transform_value_property_map
• function_property_map
• peut-être les deux combinés avec par exemple compose_property_map

Chacun de ces types a une méthode de fabrication correspondante déduisant make_transform_value_property_map, etc. make_function_property_map de sorte que vous n'avez pas épeler manuellement les types résultant.

Vous pouvez search mes réponses plus anciennes pour des exemples de ce qui peut être fait avec ceux-ci.

échantillons:

• Dijkstra graph with a table of weights on each edge
• Weight map as function in Boost Graph Dijkstra algorithm
• point général sur Immobilier Carte map set/get requests into C++ class/structure changes