問題タブ [boost-graph]

私は adjacency_list< vecS, vecS, bidirectionalS ... > を広範囲に使用しています。一度に多数のグラフをロードすると、メモリが問題になります。私は静的プログラム分析を行っており、逆アセンブルされたバイナリのコールグラフとフローグラフをブースト グラフに格納しています。したがって、数万の functions==flowgraphs と 1 つの巨大な callgraph を持つことができます。BGL を使用しながら、グラフのメモリ使用量を削減したいと考えています。

私のグラフはロード後に静的であり、エッジと頂点の数が事前にわかっているため、最適化の大きな可能性が見えます。たとえば、1 つのグラフのすべての頂点/エッジに 1 つのバッファーを割り当て、グラフがそのバッファーにインデックスを格納するだけにしたいと考えています。

その他の質問:
1) 頂点とエッジのプロパティを使用する場合のメモリ オーバーヘッドはどれくらいですか? 私はそれらのかなりの数を持っています。
2）イディオムに合わせて縮小を使用するようにBGLを説得することは可能ですか？私が理解しているように、隣接リストは push_back を使用してエッジを追加します。結果のベクトルをそれ自体のコピーと交換することでメモリ使用量を減らすことは可能ですか? 多分グラフ全体をコピーすることによって？
3) BGL でブースト プール アロケータを使用することは可能ですか? 私が知る限り、BGL は現在多くの小さな割り当てを実行しています。スペースと実行効率の理由から、これは避けたいと思っています。

メモリ使用量に最適化された BGL バージョンを既に構築した人はいますか? 既存のグラフ構造を使用して、カスタム アロケータなどで拡張する必要がありますか?それとも、独自の実装を記述して、BGL とのインターフェイス互換性を維持して、そのアルゴリズムを引き続き使用できるようにする方が実り多いですか?

よろしくお願いします、

事前に作成されたグラフ/ノード ネットワーク ライブラリを使用するか、自分で作成するかを決定しようとしています。

ノードやエッジのクラス構造に大幅なカスタマイズが必要になる可能性のあるグラフ検索アルゴリズムをいくつか実装しています。

何をすればよいかわからない理由は、既製のものをカスタマイズする方が、そもそも自分で作るよりも費用や手間がかかる可能性があるかどうかわからないからです。パフォーマンスのトレードオフについても興味がありますが、それほど興味はありません。

ライブラリの 1 つを直接使用した経験があり、成功または失敗の話に基づいてアドバイスを持っている人はいますか? 最悪の事態を聞きたいので、何を選んでも、自分が何に夢中になっているのかがわかります。

これまでの検索で見つかったのは、Boost Graph Library (BGL)とGOBLINの 2 つだけです。これらのいずれかに関する具体的なアドバイス、または他の人への提案も大歓迎です。BGLはかなり難解なようです。苦労する価値はありますか？

基準を満たすノードが見つかったので、検索を停止する必要があるとします。

ビジター内から頂点のバンドルされたプロパティを変更するにはどうすればよいですか?

グラフに添え字を付ける単純な方法を使用したいのですが、ビジターに渡されるグラフ パラメーターが const であるため、コンパイラーは変更を許可しません。

グラフへの参照をビジターに保存できますが、これは奇妙に思えます。

DAGグラフを検索する必要がありますが、ノードを指すリンクを向けている他のすべてのノードを確認する前に、ノードを通過したくありません。

この特定の状況を処理するための既存のアルゴリズムはありますか？深さ優先探索と幅優先探索は、このトラバーサルの順序では機能しません。

すなわち：

BとCの両方を見る前にDに到達したくありません。

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

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

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

頂点参照自体の代わりにキーを使用して頂点プロパティにアクセスする方法を探しています。たとえば、私が持っている場合

使用する代わりに

私はを頂きたい

すぐに使用できるメカニズムは存在しますか？

私が考えているさまざまなネットワークの問題にブースト グラフ ライブラリを適用するために、ブースト グラフ ライブラリの使用を調査しています。

私が見てきた例では、グラフ エッジの値 (「重み」) は常に整数として初期化されます。これらのBellman-FordおよびKruskalアルゴリズムでは、次のようになります。

私の問題は、重みを2倍に変更しようとすると、変換などに関する警告メッセージが大量に表示されることです。これまでのところ、克服する方法を理解できていません。

誰かがこれを回避する方法を見ていますか?

型付けされたエッジ (型プロパティを持つエッジ) を持つ巨大なグラフがあります。言う

エッジの「タイプ」は edge_prop のメンバーであり、{A,B,C,D} の値を持ちます
。タイプ A または B のエッジのみを考慮して、幅優先探索アルゴリズムを実行したいと思い
ます。それを行う？

私はC++テンプレートに錆びていて、ブーストグラフライブラリ（致命的な組み合わせ）を使用しています。Webを検索しましたが、カスタムグラフ構造を取得して、ブーストグラフトラバースアルゴリズムを使用できるBGL（ブーストグラフライブラリ）に十分に適合させる方法についての直接的な指示が見つかりません。私を助けるのに十分な図書館に精通している人はいますか？

編集：それで、私が抱えている主な問題は、任意のグラフをBGLグラフにマップするための合計要件があるソースをどこで見つけるかです。私はテンプレートに本当に慣れていないので、BGLの仕様/例を読むのは難しいです。たぶん私はテンプレートの一般的な情報源を探す必要がありますか？