問題タブ [boost-graph]

ペア（int、int）エッジのセット（各intは頂点インデックスを表す）からの無向エッジでグラフを定義しようとしています。そのような各エッジには、独自のインデックスがあります。

キャッチは、グラフの内部頂点インデックスが元の頂点インデックスと一致することを望んでいることです。また、エッジ記述子から元のエッジインデックスを抽出できるようにしたいと思います。

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_property_maps.html（外部プロパティセクション）から、次のグラフタイプを使用する必要があることを理解しています。

残念ながら、edge_index_tプロパティの使用方法についての説明はありません。

map（pair（int、int）、int）を使用できることは明らかですが、よりエレガントなブースト指向のソリューションを探しています。

ありがとう、キリル

作成されたedge_arrayがボタンクリックハンドラーで使用されたときに未定義の識別子として表示される理由がよくわかりません。cli/c++に慣れていないので、VS2010を使用していることに注意してください。また、CLIマネージドのものを組み合わせてブーストアンマネージドコードを使用すると、どんな助けでも大歓迎です

私は現在、グラフ実装のパフォーマンスの問題に取り組んでいます。

使用技術

これはC++でプログラムされています。今のところ、グラフはBGLのおかげで実装されています。

グラフについて

管理されたグラフは動的で無向です。それは2種類の構造を持っています：多くの完全なサブグラフといくつかの単一のエッジです。必要な情報は、頂点のすぐ近くだけです。

問題文

当初、完全なサブグラフは小さく（約10頂点）、多数（約13k）でした。BGLの隣接リストの実装は完璧でした。しかし、今では、5000個の頂点のいくつかのサブグラフを管理するように求められています。つまり、5000x5000のエッジを意味します。時間と空間のパフォーマンスは、現在非常に劣っています。

拒否されたソリューション

私の最初の考えは、BGLによって提供される隣接行列の実装を使用することでした。ただし、動的グラフは使用できません。この制約を解決するには、2つの解決策があります。動的グラフの隣接行列の新しい実装を提供するか、静的グラフで使用可能な頂点のプールを使用します。振り返ってみると、それは良い考えではないと思います。スペースの複雑さはまだVxV/2です。

最終的な解決策と質問

したがって、ここでの最終的な解決策は、BGLを使用せず、頂点のバッグを実装して完全なサブグラフを表し（エッジは不要）、いくつかの単一エッジの頂点を直接接続します。そうすることで、最大のサブグラフのスペースの複雑さは、頂点の数である約5000に下がります。

1. この最後の解決策は良いものだと思いますか？
2. そうでない場合、どの実装を使用できますか？なぜ？

アップデート1

グラフの詳細：グラフには、約100kの頂点、約3つの頂点の約13kの完全なサブグラフ、およびサイズ範囲[10-5000]の約100の完全なサブグラフがあります。また、各エッジにはバンドルされたプロパティがあります。

アップデート2

私は最近、Salim Jouilliのおかげで、ノードのバッグがハイパーグラフの率直なアプローチであり、ハイパーエッジがノードのサブセットで構成されていることを学びました。

アップデート3

ソリューションの実装が完了しました。私はメモリ消費と実行時間を効果的に増やしました：6GBから24MBと50分から2分30。

私はツリー（グラフの意味で）ツリー（物理的な意味で）の表現を持っています。ツリーは、各頂点に半径と位置のプロパティが含まれる BGL 隣接リストとして表されます。つまり、グラフは次の形式で定義されます。

ブランチのリストを作成するために、ツリーで DFS を実行したいと考えています。追加の要件は、頂点に複数の未探索の隣接頂点がある場合は常に、最大の半径を持つ頂点を選択することです。このルールにより、グラフの走査順序が物理的なツリー ブランチを表すようになります。

DFS ビジターはプライオリティ キューをサポートしていないようです。そのため、おそらく A* 経由でこの情報を取得する別の検索方式があるかどうか疑問に思っていました。

別の方法として、頂点をソートして独自の DFS アルゴリズムを実装することもできますが、可能であれば BGL フレームワークを活用したいと考えています。

ありがとう

-ジョン

BGL の depth_first_search アルゴリズムは、グラフに循環がない場合でも、訪問者に対して back_edge() を呼び出すことがあります。バック エッジの定義により、また Boost のDFS Visitor Documentationによると、これは発生しないはずです。これは、listS が頂点とエッジの両方の表現として使用されている場合にのみ再現可能であることに注意してください。

以下のコード例 (そのままコンパイルする必要があります) は、2 つのノードと 1 つのエッジを持つグラフを作成します。「後端」が正しく印刷されません。私はここで何か悪いことをしていますか? それともこれはバグですか？

Mac OS 10.7 で i686-apple-darwin11-llvm-g++-4.2 を使用して Boost 1.46.1 でテスト済み。
Debian 2.6.32-34squeeze1 で gcc 4.4.5 を使用して Boost 1.42.0 でテスト済み。

（タイトルをお詫びします。140文字より短い良いものを思い付くことができませんでした...）

boost::graphライブラリのグラフアルゴリズムを書いています。私のアルゴリズム内では、ノードに関する変数、重み、およびカウンターを保持する必要があります。これを行う一般的な方法は、ドキュメントや他の人のコードからわかる限り、これらのプロパティをグラフに直接添付し、プロパティマップを使用してアクセスすることです。

ただし、ライブラリ関数では、特定の読み取り/書き込みマップをグラフにバンドルする必要がないため、独自の外部プロパティマップを作成します。しかし、これらにはstd::map（または同等の）が必要なので、astd::mapとaの両方を作成することになりboost::associative_property_map<std::map>ます。これの良いところは、アルゴリズムのプロパティとユーザーのプロパティ（boost::get）の両方を取得する方法が統一されていることですが、欠点として、2つの冗長なマップがあるようです。言及された均一性以外にこれを行うことに意味はありますか？どういうわけか、プロパティマップに独自の内部マップを維持させることはできますか（メモリなどにゲインがないことはわかりますが、プロパティごとに追跡するメンバー変数が1つ少なくなります）。

私が現在実装しているアルゴリズムには、次の線があります（ここuで、はグラフの頂点であり、Pred(u)すべての頂点はエッジが指しているu）：

Pred(u)私がboost::graphコードに変換する部分は次のようになります。

今のところ、私は明示的にDo stuffループの外側で作業を行っていますuが、ループ内で実行したいと思いforます。uから返されたかのようにイテレータを作成するためのトリックはありますboost::in_edgesか？

boost::graph次のように定義すると、すべてのエッジのエッジインデックスがゼロになります。なんで？私は何が間違っているのですか？

ドキュメントと例からわかる限り、これは機能するはずです。

グラフからエッジのセットがあり、任意のエッジと頂点を共有するすべてのエッジで展開したいと考えています。sでこれを効率的に行うにはどうすればよいboost::graphですか?

私が思いついた唯一の方法は、すべてのソース頂点とターゲット頂点を抽出し、 を使用boost::adjacent_verticesしてすべての隣接関係を取得し、 を使用してすべての新しいエッジを作成する単純なソリューションですboost::edge。これを行うより良い方法はありますか？

コンテキスト: グラフの頂点は、地形の三角形分割の重心です。エッジは、対応する三角形が隣接している頂点を接続します (双対グラフのようなものです)。拡大しようとしているエッジのセットは、ブロックされている三角形間のパスに対応しており、ブロックされた領域が拡大しています。この領域は一種の円形であるため、上記の単純なアプローチを使用して表示されるエッジのほとんどは、すでにセットの一部になっています。

MutableGraphブースト グラフ ライブラリを使用して、グリッドとしての生活を開始するために a を初期化しようとしています。エッジは後で追加および削除されるためadjacency_list<vecS,listS,undirectedS>、正しい選択だと思います。

BGL について読んだところ、これらのエッジで BGL を初期化する賢明な方法は、すべての初期エッジを無料で作成できるa からコピーすることboost::grid_graphを利用 することであることがわかりました。のモデルから のモデルへのコピーは、まさに私が持っているものです。boost::copy_graphboost::grid_graphcopy_graphVertexListGraphMutableGraph

私は最初、 の 2 引数バージョンを使用してみcopy_graphましたが、残りのデフォルトで何か賢明なことが起こるという漠然とした希望を持っていました。そうではないことが判明しましたgrid_graph(理由がよくわかりませんでした) には、エッジまたは頂点のいずれかで s を使用する機能がないようPropertyMapです。プロパティ。vertex_copyedge_copy

引数が 2 つのバージョンは明らかに適切ではないように思われたので、次に進み、頂点とエッジをコピーするための独自の 2 項演算子を実装しようとしました。'no-op' コピーを使用しても、期待どおりに動作しません (つまり、コンパイルされません)。

問題を説明する最小限の実例をまとめました。

この例はコンパイルされません:

grid_graphそのエラーの私の分析は、私にはひどく明確ではない何らかの理由で、デフォルトで構築できないの内部の一部をデフォルトで構築しようとしているように見えるということです。(clang は、ここで g++ から見えないことは何も教えてくれません)。

質問:

1. これは、可変グラフを初期化して通常のグリッドとして開始する正しい方法ですか? 私は当初、自分で関数を書くよりもはるかに簡単だと思っていましたが、今ではよくわかりません!
2. orig_to_copyここでand/orのデフォルト値がvertex_index適切でないのはなぜですか? この2つがエラーの原因だと思います。(もしあれば、実際に問題を引き起こしているのはどれですか?現在のエラーの根本的な原因が何であるかを解読することはできません)。
3. これを修正する「正しい」方法は何ですか？