BGL: Wie speichere ich edge_descriptors und vertex_descriptors effizient?

Question

Nachdem mein zirkuläres Abhängigkeitsproblem mit der BGL gelöst war, bin ich zu einem anderen Hindernis gekommen.

Ich verwende derzeit eine Adjazenz-Liste, um mein Diagramm zu modellieren. Gebündelte Eigenschaften für beide Knoten und Kanten werden angewendet, um einige Informationen im Diagramm zu speichern. So habe ich so etwas wie diese:

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

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

Das Problem entsteht, wenn ich Verknüpfungen zu bestimmten Knoten und Kanten in meinem Code woanders gespeichert werden soll (zum Beispiel für eine Straße, die mehrere Fahrspuren hat). Mein erster Ansatz bestand darin, edge_descriptors und vertex_descriptors dort zu speichern, wo ich sie benötigte. Aber ich frage mich, wie groß (in Bytes) solche Deskriptoren wären. Vielleicht gibt es eine bessere Lösung, um nur einen Bruchteil an Informationen zu speichern, um die gleichen Ergebnisse zu erhalten.

Weiß jemand, wie viel Speicher, die für einen Vektor dieses Typs verwendet wird:

std::vector<edge_descriptor> ? 

Ich dachte schon über nur Zeiger auf edge_descriptors speichern, aber ich weiß nicht, ob und wie das funktionieren würde.

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

EDIT: Nun, da meine erste Frage gründlich beantwortet wurde, frage ich mich immer noch eine Sache. Ich möchte eine Art Schnittstelle für meine Graphklasse erstellen. Diese Schnittstelle soll die Graphenklassendetails von anderen Klassen trennen, die sich der Details des Graphen nicht bewusst sein müssen. Daher sollten andere Klassen Knoten und Kanten vorzugsweise als Zahlen erkennen. So kam ich mit zwei Ideen:

1. I std::tr1::unordered_map<int, edge_descriptor> eine hash_map verwenden zu können, um die Zahlen zu Deskriptoren übersetzen, die dann wieder als Indizes zu meinem Graph-Objekt verwendet werden. Dies könnte ein Schritt zu viel sein - vielleicht wird die Berechnung der Hash-Werte zu lange dauern, wenn genug Knoten und Kanten berechnet werden müssen. Deshalb hatte ich eine zweite Idee.
2. Der Graph selbst soll diese Zahlen intern in Kanten und Knoten umwandeln. Ich weiß, dass interne Eigenschaften zusammen mit Eigenschaftskarten verwendet werden können, um meine Idee zu verwirklichen. Anschließend können Sie einen Knoten zugreifen, indem Sie einfach etwas eingeben wie:
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

Aber ist es eine Möglichkeit, eine solche Eigenschaft Karten mit meinem gebündelten Eigenschaften zu kombinieren?

Oder hast du eine andere Idee, die ich noch nicht getroffen habe?

Answer 1

Scheitelpunkt- und Kantenbeschreiber nehmen eine sehr kleine Größe an.

Vertex-Deskriptoren sind Zahlen. Edgedeskriptoren sind eine kleine Struktur, die Quell- und Zielscheitelpunktdeskriptoren sowie einen Zeiger auf interne Daten enthält, die an Kantenbeschreiber angehängt sind.

Daher die Antwort auf Ihre Frage ist, dass Sie sie in Vektoren verwenden können. Es wird kein Speicherproblem verursachen.