сравнить топологически отсортированный список с исходным списком

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) «в порядке» или «не в порядке».

EDIT: Например: если вектор v1 имеет вершины {A, B, C} и у нас есть ребра (А, В) (С, А)

так что после топологической сортировки у меня будет 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)

Редактировать: это достаточное, но не обязательное условие.