3

したがって、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 を必要な場所に保存することでした。しかし、そのような記述子が (バイト単位で) どれくらいの大きさになるのか疑問に思っています。同じ結果を得るために情報の一部だけを保存するなど、より良い解決策があるかもしれません。

このタイプのベクトルに使用されるメモリの量を知っている人はいますか:

std::vector<edge_descriptor> ?

edge_descriptors へのポインターを格納することについてはすでに考えましたが、それが機能するかどうか、またどのように機能するかはわかりません。

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

編集：私の最初の質問が徹底的に答えられた今、私はまだ一つのことを疑問に思っています. グラフ クラス用にある種のインターフェイスを構築したいと考えています。このインターフェイスは、グラフ クラスの詳細を、グラフの詳細を認識してはならない他のクラスから分離します。したがって、他のクラスはノードとエッジを数値として認識できることが望ましいです。そこで、次の 2 つのアイデアを思いつきました。

  1. hash_map を使用してstd::tr1::unordered_map<int, edge_descriptor>、数値を記述子に変換できるようにします。記述子は、再びグラフ オブジェクトのインデックスとして使用されます。これは、1 つのステップから多くのステップになる可能性があります。計算するノードとエッジが十分にある場合、ハッシュ値の計算に時間がかかりすぎる可能性があります。だからこそ、私は第二の考えを思いつきました。
  2. グラフ自体は、これらの数値をエッジとノードに内部的に変換します。内部プロパティとプロパティ マップを併用すると、私のアイデアを実現できることを知っています。次に、次のように入力するだけでノードにアクセスできます。
    boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

しかし、そのようなプロパティ マップをバンドルされたプロパティと組み合わせる方法はありますか?

それとも、私がまだ思いつかなかった別のアイデアがありますか?

4

1 に答える 1

1

頂点とエッジの記述子は、非常に小さいサイズを取ります。

頂点記述子は数値です。エッジ記述子は、ソース頂点記述子とターゲット頂点記述子、およびエッジ記述子に添付された内部データへのポインターを含む小さな構造です。

したがって、あなたの質問に対する答えは、それらをベクターで使用できるということです。メモリの問題にはなりません。

于 2010-11-25T11:49:06.807 に答える