J'ai un graphe de boost avec VertexList = VECS.
typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;
3 Réponses :
Je ne pense pas que ce soit possible (dans un délai raisonnable) avec Si le paramètre VertexList du modèle adjacency_list était dans le cas de VECS comme paramètre de modèle. Regardez ce que Boost Documentation dit:
Vecs , puis tous les descripteurs de vertex, des descripteurs de bord et des itérateurs du graphique sont invalidés par cette opération. <...> Si vous avez besoin de faire une utilisation fréquente de la Supprimer_vertex () Fonction Les listes Le sélecteur est un choix bien meilleur pour la verticale Paramètre de modèle.
listes Les itérateurs ne sont pas invalidés en appelant supprimer_vertex sauf si l'itérateur pointe sur le sommet réel qui a été supprimé.
Le problème avec les listes est que je ne peux pas obtenir connecté_components de travailler avec elle. Stackoverflow .com / questions / 3183186 / ...
Peut être, avant son itération, vous pouvez créer une "corbeille" spéciale, lors de l'itération, vous connectez tous les nœuds-supprits à cette corbetex et, après itération, supprimer toutes les sommets "Trash-connectés"?
Cela vaut bien la peine d'enquêter.
Mais comment garder une trace de la corbetex lors de la suppression de ses voisins invalide le descripteur Vertex?
Vos bords sont stockés dans un std :: vecteur. Si vous avez n sommets, tous les sommets sont numérotés de 0 à N. Si vous en supprimez un, vos sommets seront renumérotés de O à N-1. Par conséquent, votre descripteur sera invalidé.
Cependant, il pourrait y avoir un travail de travail: - itérer de n à 0 - Testez votre nœud et supprimez-le si nécessaire
Ce suppose (et je ne suis pas sûr, mais plutôt confiant) qu'il ne renumérotera que les sommets Si vous faites cette manipulation beaucoup, cela pourrait être assez lent en fonction de la taille de votre graphique.
Si cette approche ne fonctionne pas, vous devrez construire un nouveau graphique de l'ancien (en pré-calculant combien de sommets et d'arêtes que vous aurez, cela pourrait réellement être de manière réaménable).
Alors, désolé, pas de réponse réelle, mais j'espère que vous allez réussir à en tirer quelque chose.
Ce serait bien si vous venez de fonctionner sur le vecteur. Mais adjacency_list le gère et doit réindex les bords de toute façon. Il peut choisir de réaffecter le vecteur après n (à nouveau invalider tous itérateurs). Enfin, inverse itération sommets (graphique) n'est pas garanti d'être équivalent à l'inverse itération du vecteur interne des sommets