Je souhaite conserver les propriétés externes pour les sommets et les arêtes d'un graphe adjacency_list (et pour les groupes de sommets). Je dois pouvoir accéder aux vertices par leurs propriétés. Par exemple, je voudrais parcourir tous les sommets affectés d'un poids et obtenir leurs bords sortants.ids de sommets constants dans adjacency_list
Cependant, j'ai aussi besoin que mon conteneur vertex soit défini. Dans ce conteneur, ajouter \ supprimer un sommet peut invalider les descripteurs de sommet.
Le problème est que les propriétés externes peuvent maintenant être mappées à vertex_descriptors invalides.
class manage_data {
...
auto get_interesting(int weight) {
return ver_by_weight.equal_range(weight);
}
void do_stuff (...) {
auto for_later_use = get_interesting();
...
boost::remove_vertex(unrelated_vertex, graph_);
...
use_vec(for_later_use.front()); //bug
}
}
Une approche semble être d'ajouter une propriété vertex_index. Cela ne fonctionne pas, car il est un directionnel - vous pouvez obtenir le vertex_index via le vertex_descriptor, mais pas l'inverse. Cela signifie que je ne peux pas ajouter d'arête entre deux sommets dont je connais seulement l'index.
Une autre solution prometteuse était l'utilisation d'un graphe marqué. Ce graphique ne peut ajouter des arêtes que par des étiquettes. J'aurais pu aller assez loin en stockant des données externes avec un identifiant d'étiquette. Malheureusement, toute l'interface adjacency_list n'est pas réimplémentée en utilisant des étiquettes - par ex. out_edges. Cela signifie que je dois toujours être en mesure d'accéder au descripteur de vertex, et il est impossible (en un temps raisonnable) d'utiliser uniquement l'étiquette, comme on peut le voir here
Une solution encore meilleure serait de combiner les deux - avoir une propriété vertex_label. Cela semble trop complexe, et cela ne fonctionne pas (exemple ci-dessus).
Ne devrait-il pas être courant que les sommets se rapportent à des données externes? Comment peux-tu le faire?
"tous les sommets ont un poids" - vouliez-vous dire les bords? – sehe
non, comme dans l'exemple de code - ver_by_weight.equal_range (weight). – bravesirrobin