問題タブ [boost-graph]

私はグラフを作成する必要があるソフトウェアに取り組んでいます(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の仕様/例を読むのは難しいです。たぶん私はテンプレートの一般的な情報源を探す必要がありますか？

プロジェクトで Boost Graph Library を使用しており、次のように宣言されています。

グラフで connected_components を呼び出さなければならないまでは、うまくいっています。

VertexList=listS の場合、頂点のプロパティとして vertex_index がないことが問題のようです。これにより、connected_components で次のようなエラーが発生します。

/usr/local/include/boost-1_39/boost/property_map.hpp: メンバー関数内 'R boost::iterator_property_map::operator[](typename boost::property_traits::key_type) const [with RandomAccessIterator = __gnu_cxx::__normal_iterator 、IndexMap = boost::adj_list_vertex_property_map、boost::detail::error_property_not_found、const boost::detail::error_property_not_found&、boost::vertex_index_t>、T = boost::default_color_type、R = boost::default_color_type&]':

問題は、頂点のプロパティとして vertex_index を追加するにはどうすればよいかということです。

追加すると、add_vertex、remove_vertex などを呼び出すたびに、頂点ごとにこの情報を更新する必要があるということですか?

VertexList=vecSのブーストグラフがあります。

次に、頂点を反復処理して、特定のプロパティを持つ頂点を削除します。これどうやってするの？

問題は、remove_vertexを呼び出すたびに、頂点記述子とともにグラフ内の頂点へのイテレータが無効になることです。

非平面グラフの平面化のための一般的なアルゴリズムはありますか?

現在、無向グラフ用の直交平面レイアウト アルゴリズムを Boost ( Boost Graph Library ) に実装することを計画しています。BGL には、無向グラフ (Boyer-Myrvold Planarity Testing) の平面性をチェックする実装があり、このメソッドによって返される平面埋め込みを使用して直交レイアウトを行う予定です。

しかし、入力グラフが非平面の場合、どうすればよいかわかりません。このようなシナリオで返された Kuratowski サブグラフを使用して、グラフを平面にする必要があります。

「非平面グラフの平面化」を Google 検索すると、複数の研究論文が返されます。どこから始めればよいかわかりません。

おそらくこれはばかげた質問ですが、BGL を使用しようとしていますdijkstra_shortest_paths。特に、Edge バンドル プロパティのフィールドをウェイトマップとして使用しようとしています。私の試みは現在、数十ページのコンパイラエラーにつながっているので、誰かが私を助ける方法を知っていることを願っています. これは基本的に私のコードがどのように見えるかです:

問題なくグラフを作成できますが、 を呼び出すと問題dijkstra_shortest_pathsが発生します。lengthフィールドを利用したい。具体的には、次のような通話に適合するために必要なブードゥー教のブーストが何であるかを知りたいです。

lengthそのような重みマップは、グラフの特定のエッジをプロパティの対応するフィールドに何らかの方法で関連付けます。これを行う簡単な方法があると確信していますが、BGL のドキュメントは非常にわかりにくいものです。この例がドキュメントのどこに記載されているか教えていただければ、私も大変嬉しく思います。

前もって感謝します！

いくつかのスレッドからBGLadjacency_listの頂点とエッジを反復処理する必要があります。グラフが大きい（mutex ..）場合、これを行うのに効率的な方法はどれですか？

BGLメソッドはリエントラント呼び出しをサポートしていませんか？