BGL：edge_descriptorsとvertex_descriptorsを効率的に保存するにはどうすればよいですか？

Question

BGLの私の循環依存性問題が解決された後、私は別の障害に遭遇しました。

私は現在、グラフをモデル化するために隣接リストを使用しています。グラフにいくつかの情報を格納するために、ノードとエッジの両方にバンドルされたプロパティが適用されます。だから私はこのようなものがあります：私は（例えば、複数のレーンを持ってストリート用）私のコードのどこか特定のノードとエッジへのショートカットを保存したいとき

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

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

を問題が発生します。私の最初のアプローチは、必要なところでedge_descriptorsとvertex_descriptorsを保存することでした。しかし、私はそのような記述子がどれほど大きく（バイトの点で）大きいのだろうと思っています。たぶん、同じ結果を得るためにほんの一部の情報を保存するなどの優れたソリューションがあります。私はすでにちょうどedge_descriptorsへのポインタを格納しますが、それがどのように動作するかどうかは知らないことについて考え

std::vector<edge_descriptor> ? 

：

誰もが、このタイプのベクトルのために使用されるメモリの量を知っています。

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

EDIT：私の最初の質問にはまだ答えがありました。私はまだ1つのことを疑問に思っています。私はグラフクラスのためのインターフェイスのいくつかの種類を構築したい。このインタフェースは、グラフの詳細を認識してはならない他のクラスからグラフクラスの詳細を分離しなければならない。したがって、他のクラスは、好ましくはノードおよびエッジを数字として認識すべきである。私は再び私のグラフオブジェクトへのインデックスとして使用されている記述子に番号を変換することができるようにhash_map std::tr1::unordered_map<int, edge_descriptor>を使用

1. ： だから私は2つのアイデアを思い付きました。これは1つのステップになるかもしれません。計算されるノードとエッジが十分にある場合、ハッシュ値の計算には多分時間がかかるでしょう。 だからこそ、私はもう一つのアイデアがありました。
2. グラフ自体は、これらの数値をエッジとノードに内部変換します。私は内部のプロパティとプロパティマップを使って自分のアイデアを実現できることを知っています。その後、ちょうどのようなものを入力して、ノードにアクセスすることができます。
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

しかし、私のバンドルされた特性を有するそのようなプロパティマップを結合する方法はありますか？

また、私はまだヒットしていない別のアイデアはありますか？

Answer 1

頂点およびエッジ記述子は非常に小さいサイズです。

頂点記述子は数字です。 エッジディスクリプタは、ソースおよびターゲットの頂点ディスクリプタを含む小さな構造体であり、エッジディスクリプタに接続された内部データへのポインタです。

したがって、あなたの質問に対する答えは、それらをベクトルで使用できることです。記憶上の問題はありません。