BGL: ¿Cómo almaceno edge_descriptors y vertex_descriptors eficiente?

Question

Así que después se resolvió mi problema dependencia circular con el BGL he llegado a otro obstáculo.

Actualmente estoy usando una adyacencia lista para modelar mi gráfica. propiedades liados para ambos nodos y los bordes se aplican a almacenar alguna información en el gráfico. Así que tengo algo como esto:

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

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

El problema surge cuando quiero almacenar accesos directos a determinados nodos y bordes en otra parte de mi código (por ejemplo, para una calle que tiene varios carriles). Mi primer acercamiento fue salvar edge_descriptors y vertex_descriptors donde los necesitaba. Pero me pregunto qué tan grande (en términos de bytes) serían dichos descriptores. Tal vez hay una mejor solución tal que tienda sólo una fracción de la información para obtener los mismos resultados.

¿Alguien sabe la cantidad de memoria que se utiliza para un vector de este tipo:

std::vector<edge_descriptor> ?

Ya pensó en simplemente almacenar punteros a edge_descriptors pero yo no sé si y cómo funcionaría.

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

EDIT: Ahora que mi primera pregunta ha sido contestada thorougly todavía estoy preguntando una cosa. Quiero construir algún tipo de interfaz para mi clase de gráfico. Esta interfaz debe separar los detalles de categoría gráfica de otras clases que no deben estar al tanto de los detalles de la gráfica. Por lo tanto otras clases deberían reconocer preferentemente nodos y bordes como números. Así me ocurrió con dos ideas:

1. Uso un std::tr1::unordered_map<int, edge_descriptor> hash_map ser capaz de traducir los números a los descriptores que a su vez luego se utilizan como índices a mi gráfico de objetos. Esto podría ser un paso a mucho - tal vez el cálculo de los valores hash tomará demasiado tiempo si hay suficientes nodos y bordes que ser calculados. Es por eso que tenía una segunda idea.
2. El gráfico en sí convertirá internamente estos números a los bordes y nodos. Yo sé que las propiedades internas, junto con los mapas de propiedad se pueden utilizar para realizar mi idea. A continuación, puede acceder a un nodo con solo escribir algo como:
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

Pero, ¿existe una manera de combinar estos mapas de propiedad con mis propiedades paquetes?

o tiene otra idea que no me golpeó en, todavía?

Answer 1

Vertex y descriptores de borde tienen un tamaño muy pequeño.

descriptores Vertex son números. descriptores de borde son una pequeña estructura que contiene la fuente y vértice destino descriptores, y un puntero a los datos internos unidos a descriptores de borde.

Por lo tanto la respuesta a su pregunta es que se puede utilizar en vectores. No va a constitué un problema de memoria.