問題タブ [boost-graph]

私は後押しするのが初めてで、erdos アルゴリズムによって生成された分散ランダム グラフを構築しようとしています。ドキュメントで提案されているように、internal_vertex_name テンプレートを名前付き頂点で動作するように特化しているため、すべてうまくいきます。

コードはこちらにあります。

次のような多くのコンパイル エラーが発生します。

なにか提案を？

したがって、BGL の循環依存の問題が解決された後、別の障害に直面しました。

現在、隣接リストを使用してグラフをモデル化しています。ノードとエッジの両方にバンドルされたプロパティが適用され、グラフに一部の情報が格納されます。だから私はこのようなものを持っています:

特定のノードとエッジへのショートカットをコード内の別の場所に保存したい場合に問題が発生します (たとえば、複数の車線がある道路など)。私の最初のアプローチは、edge_descriptors と vertex_descriptors を必要な場所に保存することでした。しかし、そのような記述子が (バイト単位で) どれくらいの大きさになるのか疑問に思っています。同じ結果を得るために情報の一部だけを保存するなど、より良い解決策があるかもしれません。

このタイプのベクトルに使用されるメモリの量を知っている人はいますか:

edge_descriptors へのポインターを格納することについてはすでに考えましたが、それが機能するかどうか、またどのように機能するかはわかりません。

/////////////////////////////////////////////// /////////////////////////////////////////////// /////////////////////////////////////////////// ///////////////

編集：私の最初の質問が徹底的に答えられた今、私はまだ一つのことを疑問に思っています. グラフ クラス用にある種のインターフェイスを構築したいと考えています。このインターフェイスは、グラフ クラスの詳細を、グラフの詳細を認識してはならない他のクラスから分離します。したがって、他のクラスはノードとエッジを数値として認識できることが望ましいです。そこで、次の 2 つのアイデアを思いつきました。

1. hash_map を使用してstd::tr1::unordered_map<int, edge_descriptor>、数値を記述子に変換できるようにします。記述子は、再びグラフ オブジェクトのインデックスとして使用されます。これは、1 つのステップから多くのステップになる可能性があります。計算するノードとエッジが十分にある場合、ハッシュ値の計算に時間がかかりすぎる可能性があります。だからこそ、私は第二の考えを思いつきました。
2. グラフ自体は、これらの数値をエッジとノードに内部的に変換します。内部プロパティとプロパティ マップを併用すると、私のアイデアを実現できることを知っています。次に、次のように入力するだけでノードにアクセスできます。
   boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

しかし、そのようなプロパティ マップをバンドルされたプロパティと組み合わせる方法はありますか?

それとも、私がまだ思いつかなかった別のアイデアがありますか?

Boost Graphic Library に関して別の問題があり、Google で検索したりドキュメントを読んだりしても答えられませんでした。他の質問とは直接関係ないので、新しいスレッドを立てたほうがいいと思います。

隣接レイアウトのグラフがあり、バンドルされたプロパティを使用してノードとエッジのデータにアクセスします。便宜上、Graph に typedef を使用します。したがって、次のように入力することで、たとえば vertex_descriptor 用に保存されているデータにアクセスできます。

ここで、データ格納オブジェクトへの参照を定義して、そのようなものを入力できるようにしたいと思います。

これまたは同様のアプローチにより[]operator、マップの と特定の記述子オブジェクトを使用してアクセスされるマップされた値の不要な再計算を回避しようとします。私の頂点とエッジには多くのデータが含まれているため、特定の状況では、現在のコードはこのデータを処理するために同じ値の多くの再計算を生成します。これは醜いようです。

私がやろうとしていることを達成する可能性があるかどうか、誰かが知っていますか?

ブースト グラフ ライブラリの使用を開始しています。astar_search を使用してゼロ コストで実装できるベスト ファースト検索が必要です。(間違っていたら訂正してください。)

しかし、これを行う別の可能性があるのだろうか？コストが考慮されていない場合、アルゴリズムはわずかに効率的になります。

編集: 説明がわかりにくくてすみません。私は実際に潜在的なフィールド検索を実装しているので、エッジに関連するコスト/重みはありませんが、最急降下検索を行う必要があります (局所最小値を克服できます)。

ヒントをありがとう！

タイトルが示すように、私はboost::depth_first_searchVisitor (から継承boost::default_dfs_visitor) を使用していくつかのアルゴリズムを実装しています。

ただし、アルゴリズムの実行中に、後で照会できるように、いくつかの情報をビジターに保存したいと考えています。ただし、DFSが完了すると情報が消去されるため、コピーを使用していると思います。すべてのプライベート変数にポインターを使用する以外に、これを防ぎ、ブーストに私のコピーを使用させる方法はありますか?

DAGの保存にBGLを使用しています。頂点には状態があります。頂点の1つで状態が変化した場合、依存する頂点を更新したいと思います。これは、boost::depth_first_searchとカスタムビジターを使用して実行できます。

ここでの論理は、検索された頂点と、頂点が特定の状態にある場合にその依存する頂点を更新したくないということです。基本的に、dfsまたはbfsのいずれかで頂点のエンキューを制御したいと思います。BGLでこれを達成するための最良の方法は何ですか。

ありがとう。

私は使用boost::graphしていますが、2つありvertex_descriptorます。すべてのエッジを反復処理せずに、それらの間のエッジを取得する最も簡単な方法は何ですか？

構造体を作成し、それをadjacency_listのテンプレートパラメーターとして使用しました。ただし、add_edge（vertex1、vertex2、property、graph）を実行しようとすると、コンパイラーは「一致する関数呼び出しがありません」と文句を言います。誰かが私がここで間違っているところを見ることができますか？

ありがとう、

デビッド

グラフのエッジを反復処理して、エッジの重みを出力しようとしています。私は混乱しています。「エッジ」を出力する方法は知っていますが、これは実際にはエッジを定義する単なる（頂点、頂点）です。では、* edgePair.firstをEdgeWeightMapにインデックス付けして、頂点* edgePair.firstから始まるエッジの重みを取得しますか？これはコンパイルされません："演算子<<に一致しません"。

何かご意見は？

ありがとう、デビッド

Boostグラフライブラリを使用して、エッジのポート識別子を取得することは可能ですか？

例：を呼び出した後read_graphviz、このグラフの端を反復処理して、それらを出力node_idできます-「A-> B、A->B」を取得します。「A：p0-> B：p1、A：p0-> B：p2」のようなものを印刷するにはどうすればよいですか？