将拓扑排序列表与原始列表进行比较

Question

我有一个来自 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} 并且我们有边 （甲、乙） (C,A)

所以在拓扑排序之后，我将在 v2

{C, A, B}

中得到。在某些情况下，我可能无法获得唯一的拓扑顺序，例如，如果我有 (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";
    }
  }
}

Answer 1

那么比较 v1 和 v2 来测试我的原始顶点向量 (v1) 是“按顺序”还是“无顺序”的最佳方法是什么。

不比较向量。该测试存在缺陷，如果成功（两个向量相同），您将知道它是按顺序排列的，但如果失败（向量不同），您将不知道它是否乱序或是否处于不同的顺序。命令。

考虑该图（想象边缘向下）：

  A
 / \
B   C
 \ /
  D

列表 { A, B, C, D } 和 { A, C, B, D } 均按拓扑顺序排列，因为 B 和 C 之间没有排序约束。如果您有其中一个选项，并且 boost::topological_sort 产生了另一种变体，您将不知道您是否有一个错误的顺序，或者更确切地说是一个不同的正确顺序。

最好编写一个简单的算法来检查顺序的正确性并在需要时重新排序。

Answer 2

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

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

• 令顶点列表为 v。现在构造一个列表r，其中r[i]给出顶点i在v中的索引，即v[r[i]] = i。
• 然后循环遍历所有有向边(i,j)并检查r[i] <= r[j]。
• 如果是这样，则列表 v 已经按拓扑顺序排列。

然而，这与对 v 进行完整的拓扑排序一样慢（两者在边数和顶点数上都是线性的）。因此，如果您的目标只是让 v 按拓扑顺序排列，只需进行排序即可。如果可能的话，如果您需要将 v 保持在当前顺序，这将很有用。

Answer 3

std::vector 有 operator== 所以你可以简单地 if(v1==v2)

编辑：这是一个充分但不是必要的条件。