1

mygraph から頂点のベクトルがあり、頂点をトポロジカルに並べ替えます。

typedef typename boost::adjacency_list<boost::listS, boost::vecS, 
       boost::directedS,Vertex_t*> Graph_t;

typedef typename boost::graph_traits<Graph_t>::vertex_descriptor Vd_t;
Graph_t mygraph;
std::vector<Vd_t> v1; 
//initialize the vertices and get a copy of vertices in vector v1
//...
//and then i use

std::vector<Vd_t> v2;
boost::topological_sort(mygraph,std::back_inserter(v2));

頂点を「順番に」位相的にソートします。v1 と v2 を比較して、元の頂点のベクトル (v1) が「順序どおり」または「順序どおり」であるかどうかをテストする最良の方法は何ですか。

編集: 例: ベクトル v1 に頂点 {A, B, C} があり、エッジ (A,B) (C,A) がある場合

したがって、トポロジカルソートの後、v2 になります

{タクシー}

一意のトポロジー順序が得られない場合があります。たとえば、(A,C) が唯一のエッジである場合、v2 は {A , B , C} または {B , A , C} になる可能性があります。

ここで、v1 と v2 を調べて、v1 と v2 の両方が同じ順序を表しているかどうかを確認する必要があります。

2番目の編集：私はアプローチを試みましたが、今のところうまくいきます。これが良いアプローチかどうか教えてください。

template <typename Vertex_t>
void DepAnalyzer<Vertex_t>::CheckTotalOrder()
{
  //Vd_t is the vertex descriptor type
  typename std::vector<Vd_t> topo_order;
  typename std::vector<Vd_t>::iterator ordered_vertices_iter;

  //puts the topologically sorted vertices into topo_order
  DoTopologicalSort(topo_order);

  //will point to the vertices in the order they were inserted
  typename boost::graph_traits<Graph_t>::vertex_iterator vi, vi_end;
  std::unordered_map<Vertex_t*,int,std::hash<Vertex_t*>,
                      VertexEqual> orig_order_map, topo_order_map;  

  int i = 0;
  for(std::tie(vi, vi_end) = boost::vertices(depGraph); vi != vi_end; ++vi) {
    orig_order_map[depGraph[*vi]] = ++i;
    //std::cout<<depGraph[*vi]->get_identifier_str()<<"\n";
  }
  i = 0;
  //will point to the vertices in the topological order
  ordered_vertices_iter = topo_order.begin();
  for(;ordered_vertices_iter != topo_order.end(); ordered_vertices_iter++) {
    topo_order_map[depGraph[*ordered_vertices_iter]] = ++i;
    //std::cout<<depGraph[*ordered_vertices_iter]->get_identifier_str()<<"\n";
  }
  //checking the order now
  ordered_vertices_iter = topo_order.begin();
  for(;ordered_vertices_iter != topo_order.end(); ordered_vertices_iter++) {
    //if the vertex in topologically sorted list occurs before(w.r.t. position)
    //the macro in the original list of vertices, then it's okay
    if(orig_order_map[depGraph[*ordered_vertices_iter]] >
      topo_order_map[depGraph[*ordered_vertices_iter]]) {
      std::cerr << depGraph[*ordered_vertices_iter]->get_identifier_str() 
                << ": out of order\n";
    }
  }
}
4

3 に答える 3

4

v1 と v2 を比較して、元の頂点のベクトル (v1) が「順序どおり」または「順序どおり」であるかどうかをテストする最良の方法は何ですか。

ベクトルを比較しない。このテストには欠陥があり、成功した場合 (両方のベクトルが同じ) は順序どおりであることがわかりますが、失敗した場合 (ベクトルが異なる) は順序が間違っていたのか、それとも異なる順序だったのかがわからないという点です。注文。

グラフを考えてみましょう (エッジが下がっていると想像してください):

  A
 / \
B   C
 \ /
  D

と の間には順序の制約がないため、{ A, B, C, D }とのリストは両方ともトポロジカルな順序になっています。オプションの 1 つがあり、他のバリアントが生成された場合、注文が間違っていたのか、別の正しい注文だったのかわかりません。{ A, C, B, D }BCboost::topological_sort

順序が正しいかどうかをチェックし、必要に応じて順序を変更する単純なアルゴリズムを作成することをお勧めします。

于 2011-07-13T08:01:42.120 に答える
2

頂点のリストがすでにトポロジカル順序になっているかどうかをテストしたいというあなたの質問を正しく理解していますか？

もしそうなら、あなたは次のことをするかもしれません：

  • 頂点のリストを。としますv。次に、の頂点のインデックスを与えるリストrを作成します。r[i]ivv[r[i]] = i
  • 次に、すべての有向エッジをループして、それ(i,j)を確認しr[i] <= r[j]ます。
  • もしそうなら、リストvはすでにトポロジカル順序になっています。

ただし、これは完全なトポロジカルソートを実行するのと同じくらい遅くなりますv（どちらもエッジの数と頂点の数が線形です）。したがってv、トポロジカルソートだけを目的としている場合は、ソートを実行してください。可能であれば現在の順序を維持する必要がある場合はv、これが役立ちます。

于 2011-07-13T08:46:14.447 に答える
0

std::vector持っているoperator==ので、簡単にできますif(v1==v2)

編集:これは十分な条件ですが、必須条件ではありません。

于 2011-07-13T07:46:25.973 に答える