問題タブ [boost-graph]

次のように定義された boost::graph のエッジ リストを並べ替えたいと思います。

頂点とエッジを追加した後、エッジ リストを並べ替える方法。最初に最大の重みで優位に立ちますか?

私は1つが使用できることを知っています

ベクトルの場合、std::list では機能しません。

バンドルされたプロパティと adjacency_list を使用しており、サブグラフ クラスを使用したいと考えています。

サブグラフは2つのエッジを比較するproperty<edge_index_t,int,Edge>必要があるため、この部分が必要です。edge_index_t

今私の質問は、サブグラフにバンドルされたプロパティを使用してエッジを追加するにはどうすればよいですか? 通常のグラフでproperty<edge_index_t,int,Edge>は、次のようにエッジを追加します。

しかし、これはサブグラフでは機能しません。

誰かがこれに対する解決策を知っていることを願っています。

ありがとう

ベン

私が使用boost::graphしているのは、その Dijkstra 実装です。

一連の頂点から別の一連の頂点までの最短経路を計算したいと考えています。これらのセット間のすべての可能なパスを計算したくありません。

アイデアは次のとおりです。さまざまな通りに入り口がある建物にいます。そのため、どの通りからでも旅を始めることができます。しかし、私は最短のものにしか興味がありません。

ダイクストラのアルゴリズムの独自の実装を使用した場合、次のようにします。

• 開始ノードごとに、距離は 0 にマップされます
• 開始ノードを優先キューに追加します。

を使用して距離マップを 0 に設定するのは簡単boost::dijkstra_shortest_paths_no_initですが、ノードをプライオリティ キューに追加する方法がわかりません。ソースコードを調べたところ、ほとんど不可能のようです。そこで、開始ノードの 1 つに到達した場合に 0 の距離を返す独自の結合ファンクターを定義することを考えていますが、かなり醜いようです。

仮想ノードを作成し、仮想ノードから開始ノードにエッジを追加できます。ただし、これにより、回避したい同時アクセスの問題がいくつか発生します。

ブーストライブラリの可能性を見逃したのですか、それとも誰かが巧妙な回避策を知っていますか? また、プライオリティ キューのカスタム初期化を可能にするために、boost にパッチを適用することも考えています。

私は現在 C++ を使用して、boost::graph を使用してグラフ関連の計算を行っています。boost::graph はそのグラフをドット ファイルとして出力でき、std::stringstream を使用して出力ドット ファイルをキャプチャします。したがって、ドットファイルの内容はメモリに常駐します。

ドット ファイルを使用して、グラフを視覚化したいと考えています (できるだけ速く)。したがって、ドットファイルを生成し、svg ファイルを生成して、キャンバスに印刷したいと考えています。グラフは小さく、とにかくメモリが利用可能であるため、これに一時ファイルを使用することは避けたいと思います。

ただし、graphviz libgraph には機能しかありません。これを機能させる唯一の方法は、実際には移植できないextern Agraph_t *agread(FILE *);ファイルハンドルをハックすることです。struct __FILE

Unix/Linux でライブラリにメモリの内容をファイルとして読み込ませるにはどうすればよいですか?

GraphViz の libcgraph では、ここでオーバーロードされたバージョンを入力できることがわかりましたが、これまでのところ、ドキュメントは有用な場所を示していません。

boostlibのbrandes_betweenness_centralityを使用してbetweenessを計算する簡単なプログラムを作成しようとしています。出力（CentralityMap）を取得するのに行き詰まりました。私はドキュメントを読んでいますが、すべてをまとめる方法がわかりません。

これが私の簡単なコードです：

私の理解から、結果が書き込まれる中心性マップを定義する必要があります。読み取り/書き込みプロパティマップに関連していますが、定義方法がわかりません。

最終的には、中間性を出力する必要があります。

いくつかのフィールドを含む2つの構造体があります：structMyNodeDataとstructMyEdgeDataです。VertexListをvecSとしてグラフを作成する場合、頂点などの記述子にアクセスするのに問題はありません。次に例を示します。

しかし、私は通常、グラフからエッジと頂点を追加/削除する必要があります。したがって、vecSでは、vecSの代わりにsetSまたはlistSをVertexListとして使用したいと思います。これは、vecSでは、インデックスの1つを削除すると、インデックスが無効になるためです。問題は、VertexListをsetSまたはlistSとして定義すると、以前のように頂点/エッジのリストを参照してそこの記述子にアクセスできないことです。

簡単に言うと、私の質問は次のとおりです。頂点コンテナとしてlistSまたはsetSを使用するadjacency_listは、このvertex_idプロパティを自動的に提供しないので、上記のコードに追加するにはどうすればよいですか？

Boost Graph Library について理解を深めようとしているところですが、いくつか質問があります。BGL グラフのラッパー クラスであるコードを書いています。アイデアは、必要に応じてグラフを操作し、ラッパー メソッドを呼び出してグラフを GEXF (XML) 形式で出力できるということです。

私のコードは次のようなものです：

ここに私の質問があります：

1. バンドルされたプロパティを使用すると、vertex_index にはアクセスできますが、edge_index にはアクセスできません。エッジ インデックスにアクセスするにはどうすればよいですか?

2. 上記のコードでは、GEXF クラスをジェネリックにしたかったのですが、宣言しようとしたときに問題が発生しましたGraph::edge_iterator e, e_end;。上記のコードは機能しますが、具象型を使用しています。edge_iterator を一般的に宣言するにはどうすればよいですか?

Boost :: Graphを使用して最初のステップを実行していますが、（私にとっては）予期しない動作が発生しました。

私が欲しいのは、一連のedge_weightプロパティ（数は実行時にのみ知られている）を持ち、特定の制約を満たすすべての重みの最小値を使用することです。まず、typedef宣言：

次のようにグラフを初期化します。

そして何度も出力INT_MAXします。（外部）weightMaps[j]はすべて同じで、内部プロパティと等しいようfastestLinkWeightです。しかし、なぜ？個別のマップを使用するようにするにはどうすればよいですか？

GoogleAIチャレンジ用のボットをPythonからC++に書き直しています。以前のPythonのように自分のグラフと検索コードをロールするのではなく、Boostのグラフライブラリを使用してパスファインディングを処理したいと考えています。

マップは、エッジを囲む単純な正方形のグリッドです。

私はこれまでブーストやC++を使用したことがなく（Cについてはよく知っています）、ブーストグラフのドキュメントを理解するのが非常に難しいので、少し助けが必要です。

私が問題を抱えている特定のドキュメント：

• http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/dijkstra_shortest_paths.html
• http://www.boost.org/doc/libs/1_47_0/libs/graph/example/dijkstra-example.cpp
• など、現時点では2つのリンクに制限されています:)

動作するPythonコードのスニペットは次のとおりです。

次に、shortest_path(self.graph, loc, dest)後で（マンハッタンヒューリスティックを使用した*検索）を使用して、別の場所への最短パスを含むリストを取得します。C ++では、似たようなもの（最短経路のベクトル）が欲しいです。これが私がこれまでに持っているコードです（私はそれを障害物なしで基本的なグリッド上で動作させるのに助けが必要です、私は残りをすることができます）：

インタラクティブな画像セグメンテーションに「インテリジェントなはさみ」を実装しようとしています。したがって、各頂点が 1 つのピクセルを表す画像から有向グラフを作成する必要があります。次に、各頂点は、2 つのエッジ (1 つの発信エッジと 1 つの着信エッジ) によって隣接する各頂点に接続されます。これは、エッジ (a,b) のコストが (b,a) のコストと異なる可能性があるためです。サイズが 512*512 ピクセルの画像を使用しているため、262144 個の頂点と 2091012 個のエッジを持つグラフを作成する必要があります。現在、次のグラフを使用しています。

グラフを処理する追加のクラスGraph (刺激を受けていない命名で申し訳ありません) を使用しています。

};

262144 個の頂点を持つ新しいグラフを作成するのは非常に高速ですが、エッジの挿入には最大 10 秒かかり、目的のアプリケーションには遅すぎます。現在、次の方法でエッジを挿入しています。

プログラムの速度を向上させるためにできることはありますか? Microsoft Visual C++ 2010 Express を最適化されたリリース モードで使用しています (Boost の推奨に従って)。頂点またはエッジにlistSコンテナーを使用できると考えましたが、頂点は問題ありません。エッジにlistSを使用すると、さらに遅くなります。