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 是否代表相同的订单。

第二次编辑：我尝试了一种方法，它现在有效，请告诉我这是否是一个好方法。

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 }和{ A, C, B, D }都按拓扑顺序排列，因为B和之间没有排序约束C。如果您有一个选项并boost::topological_sort产生了另一个变体，您将不知道您的订单是否不正确，或者更确切地说是不同的正确订单。

编写一个简单的算法可能会更好，该算法将检查顺序的正确性并在需要时重新排序。

于 2011-07-13T08:01:42.120 回答
2

我是否正确理解了您想要测试顶点列表是否已按拓扑顺序排列的问题？

如果是这样，您可以执行以下操作：

  • 设顶点列表为v。现在构造一个列表r，其中r[i]给出 中的顶点索引i，v即v[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 回答