BGL: Comment est-ce que je stocke efficacement des descripteurs de bord et des vertex_descriptors?

Question

Donc, après que mon problème de dépendance circulaire avec le BGL a été résolu, je suis venu à un autre obstacle. J'utilise actuellement une liste d'adjacence pour modéliser mon graphe. Les propriétés groupées pour les nœuds et les arêtes sont appliquées pour stocker certaines informations dans le graphique. J'ai donc quelque chose comme ceci:

class Node { 
    int x, int y // position 
}; 
class Edge { 
    float length; 
}; 

boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node, Edge> 

Le problème se pose quand je veux stocker des raccourcis vers des noeuds et des arêtes spécifiques à un autre endroit dans mon code (par exemple pour une rue qui a plusieurs voies). Ma première approche consistait à sauvegarder edge_descriptors et vertex_descriptors là où j'en avais besoin. Mais je me demande quelle serait la taille (en termes d'octets) de ces descripteurs. Peut-être y a-t-il une meilleure solution pour stocker juste une fraction d'information pour obtenir les mêmes résultats.

Est-ce que quelqu'un sait la quantité de mémoire qui est utilisée pour un vecteur de ce type:

std::vector<edge_descriptor> ? 

je l'ai déjà pensé à juste stocker des pointeurs vers edge_descriptors mais je ne sais pas si et comment cela pourrait fonctionner.

////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////// ///////////////////

EDIT: maintenant que ma première question a été répondu thorougly Je me demande encore une chose. Je veux construire une sorte d'interface pour ma classe graphique. Cette interface doit séparer les détails de classe de graphique d'autres classes qui ne doivent pas être au courant des détails du graphique. Ainsi, les autres classes devraient de préférence reconnaître les nœuds et les arêtes en tant que nombres. Alors je suis venu avec deux idées:

1. J'utilise un hash_map std::tr1::unordered_map<int, edge_descriptor> pour être en mesure de traduire les numéros de descripteurs qui encore une fois sont ensuite utilisés comme indices à mon graphique-objet. Cela peut être une étape de beaucoup - peut-être que le calcul des valeurs de hachage prendra trop de temps s'il y a suffisamment de nœuds et d'arêtes à calculer. C'est pourquoi j'ai eu une deuxième idée.
2. Le graphique lui-même doit convertir ces numéros en interne en arêtes et en nœuds. Je sais que les propriétés internes ainsi que les cartes de propriétés peuvent être utilisées pour réaliser mon idée. Vous pouvez alors accéder à un nœud en tapant quelque chose comme:
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

Mais est-il un moyen de combiner ces cartes de propriété avec mes propriétés empaquetés?

Ou avez-vous une autre idée sur laquelle je n'ai pas encore touché?

Answer 1

Les descripteurs de sommet et de bord prennent une très petite taille.

Les descripteurs de sommets sont des nombres. Les descripteurs de bord sont une petite structure contenant des descripteurs de sommet source et cible et un pointeur vers des données internes attachées à des descripteurs de bord.

Par conséquent, la réponse à votre question est que vous pouvez les utiliser dans des vecteurs. Cela ne constituera pas un problème de mémoire.