問題タブ [boost-graph]

C ++ Boostの無向グラフを作成し、深さ優先探索（DFS）の順序でトラバースするにはどうすればよいですか？

大規模な実稼働サーバーに BGL を使用している人はいますか?

• ネットワークはいくつのノードで構成されていますか?
• コミュニティの検出をどのように処理しますか
• BGL には、コミュニティを検出するクールな方法がありますか?
• 2 つのコミュニティが 1 つまたは 2 つのエッジでリンクされている場合もありますが、これらのエッジは信頼性が低く、消えていく可能性があります。エッジがまったくない場合もあります。

誰かがこの問題を解決する方法について簡単に話すことができますか. 私の心を開いて、私にインスピレーションを与えてください。

これまでのところ、2 つのノードが 1 つの島 (コミュニティ内) にあるかどうかを最も安価な方法で解決することができましたが、別の島にあるどの 2 つのノードが互いに最も近いかを判断する必要があります。信頼できない地理データは最小限しか使用できません。

それを比喩的に本土と島と比較し、社会的距離の文脈から外すと. 私は、水域を横切って最も接近している 2 つの土地を特定したいと考えています。

boost::graph を使用して情報を保存する方法を理解しようとしています。ただし、各頂点に関連付けたい情報があります。ライブラリのドキュメントをじっと見ると、(a)ドキュメントの書き方が悪いか、(b)思ったほど C++ が得意ではないことがわかります。2つ選んでください。

簡単な使用例を探しています。

Dataコードの実行時に何千ものインスタンス (オブジェクト)を持つクラス (C++) を呼び出します。DataWidgetオブジェクトの属性を表示するウィジェット(Qt)があります。ウィジェットを迅速に作成するために、オブジェクト属性をファイルに書き込んで、ウィジェットにそのファイルの属性を解析させました。このアプローチは機能しますが、スケーラブルでもきれいでもありません。

より明確にするために、私の要件は次のとおりです
。1 -DataWidget複数の異なるDataオブジェクトの属性を一度に表示できる必要があります
2 - 1 秒あたりDataWidget数千のDataオブジェクトを表示できる必要があります
3 -新しいオブジェクトDataWidgetを生成するコードと一緒に実行する必要があります4 - 各オブジェクトは、ファイル/データベースに永続的に保存する必要がありますData
Data

現在、GUI が作成され、DataWidgetが作成された後、実験が実行され、何千ものDataオブジェクトが生成されます (それらの一部を定期的にファイルに書き込みます)。実験の実行後、DataWidget最後Dataにファイルに書き込まれたオブジェクトが表示されます (それらは XML ファイルに書き込まれます)。

現在のファイル アプローチでは、実験の実行後に複数のファイルを取得することで(1)を満たすことができます。実験は に関連付けられていないため、同時実行性がないため、新しいファイルが存在することを に通知するシグナルを追加するまで(3)DataWidgetは実行できません。DataWidget

私は 2 つの理由でこのアプローチを進めていません。まず、ファイルがすぐにディスクに書き込まれなくても、キャッシュ システムを実装しない限り、この方法がスケーラブルであるとは想像できません。車輪の再発明ですか？次に、Dataグラフ データ構造のラッパーであり、Graphml を使用して (Boost グラフ ライブラリ、つまりwrite_graphml()を介して) 構造を XML ファイルに書き込み、Boost のread_graphml()で構造を読み戻す必要があります。ファイルをオブジェクトに読み込みDataます...つまり、プログラムの実験部分がオブジェクトを XML にエンコードし、XML をファイルに書き込みます (ただし、できればディスクではなくメモリに書き込みます)。DataWidgetファイルから XML を読み取り、それをオブジェクトにデコードします。

すべてのキャッシングなどを処理するデータベースを使用する必要があるように思えます。さらに、ファイル/データベースのステップをスキップして、プログラム内の に渡すことができるように思われますData(DataWidgetおそらくへの参照を渡します)。のリストData)。それでも、Dataファイル/データベースへの保存手順は完全に無意味ではありません。間違ったタイミングで間違った方法で使用しているだけです。

私の要件を考えると、より良いアプローチは何ですか?

このようなデータを処理および表示するための一般的なリソースやガイドラインはありますか?

私は債券グラフを操作するためのライブラリを作成しており、Boost Graph Library を使用してデータを保存しています。残念ながら、頂点をサブクラス化できないため、それを使用して適切なビジター パターンを実装する方法を理解できないようです。代わりに「プロパティ」に依存する必要があります。ライブラリで提供されているビジター フレームワークは、頂点がすべて同じタイプであるが、異なる情報を格納する特定のアルゴリズムを操作することに重点を置いているようです。私の問題では、頂点はさまざまなタイプであり、さまざまなタイプの情報を格納しています.いくつかの頂点は抵抗器であり、いくつかの頂点はコンデンサなどです。頂点そのもの？

これまでの私の唯一の考えは、グラフ情報を取得するために必要な元の頂点を指すオブジェクトの型を表す小さなクラスを作成することでした。ただし、これは非常に厄介で、操作するのが悪いようです。

私は 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に到達したくありません。