6

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

typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

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

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

4

3 に答える 3

3

エッジはstd::vectorに保存されます。N個の頂点がある場合、すべての頂点に0からNまでの番号が付けられます。1つを削除すると、頂点の番号がoからN-1に変更されます。そのため、記述子は無効になります。

ただし、回避策がある可能性があります：– Nから0まで繰り返します–ノードをテストし、必要に応じて削除します

これは、削除したばかりの頂点の後にのみ頂点の番号が付け直されることを前提としています（そして、私にはわかりませんが、かなり自信があります）。

この操作を頻繁に行うと、グラフのサイズによってはかなり遅くなる可能性があります。

そのアプローチが機能しない場合は、古いグラフから新しいグラフを作成する必要があります（頂点とエッジの数を事前に計算することにより、実際にはかなり高速になる可能性があります）。

それで、申し訳ありませんが、本当の答えはありませんが、あなたがそれから何かをなんとか得ることができることを願っています。

于 2011-02-15T12:50:56.450 に答える
3

反復前に特別な「ゴミ箱」頂点を作成し、反復中に削除用のすべてのノードをそのゴミ箱頂点に接続し、反復後にすべての「ゴミ箱接続」頂点を削除できますか?

于 2011-02-15T12:34:19.110 に答える
1

vecSテンプレートパラメータとしては（妥当な時間内に）可能ではないと思います。Boostのドキュメントに書かれていることを見てください。

のVertexListテンプレートパラメータがadjacency_listだった場合vecS、グラフのすべての頂点記述子、エッジ記述子、およびイテレータは、この操作によって無効になります。remove_vertex()<...>関数を頻繁に使用する必要がある場合は、テンプレートパラメーターlistSとしてセレクターを選択することをお勧めします。VertexList

イテレータが削除された実際の頂点を指していない限り、イテレータがlistS呼び出しによって無効化されない場合。remove_vertex

于 2010-07-06T04:32:07.050 に答える