4

私はグラフを作成する必要があるソフトウェアに取り組んでいます(boost::adjacency_listを使用)。頂点の増分挿入には非常に長い時間がかかります。STLport を使用することでこの問題が解消されたため、今までこの問題に取り組んでいませんでした。現在、自分の作業を Visual Studio 2008 に移行しましたが、STLport を使用する時間がありません (STLport を使用してブースト ライブラリのコンパイルを維持するのが困難です)。

頂点識別子を整数のように使用することが多いため、グラフの頂点をリストに格納したくありません。

この問題を解決するには、他にどのようなオプションが必要ですか (デバッグ モードとリリース モードで)。

4

4 に答える 4

2

ノードがいくつあるかを事前に知っていますか？はいの場合、これによりグラフの作成時間が大幅に短縮されます。

たとえば、10000ノードのグラフの場合：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, > Graph_t;
Graph_t g(10000);
于 2010-01-26T13:42:19.113 に答える
1 
template<class OutEdgeListS = vecS, class VertexListS = vecS,.....> adjacency_list;

OutEdgeListS と VertexListS の選択は、boost adjacency_list によって実装されるグラフ アルゴリズムの時間の複雑さに大きな影響を与えます。

  • add_vertex() は、vecS と listS (push_back() で実装) の両方で一定時間償却されます。ただし、VertexListS タイプが vecS の場合、ベクトルが再割り当てされ、グラフ全体がコピーされるため、この操作に時間がかかることがあります。
  • remove_vertex() は、listS では一定時間、vecS では O(V + E) です。

上記でわかるように、両方のデフォルトは vecS です。そのため、VertexListS に listS を使用すると (スペースのオーバーヘッドが高くなります)、時間の短縮が期待できます。

于 2010-01-26T14:32:39.710 に答える
1

実行に時間がかかるコードを実際にプロファイリングしてみましたか? 驚くかもしれませんが、予想外のもの (暗黙の変換/変換コンストラクター、予想よりも多くの比較、データのコピーなど) に気付くかもしれません。さらに、プロファイリングにより、挿入アルゴリズムのどの部分に時間がかかっているか、およびそれを修正する可能性 (例: adjacency_list コンストラクターの引数を変更する) についてのアイデアが得られる場合があります。

于 2010-02-11T21:52:13.153 に答える
0

頂点識別子を整数のように使用することが多いため、グラフの頂点をリストに格納したくありません。

結局、 listS を使用できるかもしれません。頂点インデックスをプロパティとして宣言するだけです ( http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/using_adjacency_list.html#sec:adjacency-list-propertiesを確認してください)。ただし、頂点を削除すると、頂点の番号を付け直さなければならない場合があります。また、頂点を追加する場合は、その頂点インデックス値を割り当てる必要があります。

于 2011-03-06T06:25:53.617 に答える