compare topologically sorted list with the original list

i have a vector of vertices from mygraph, and i topologically sort the vertices.

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

typedef typename boost开发者_C百科::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));

to topologically sort the vertices 'in order'. So what is the best way to compare v1 and v2 to test if my original vector of vertices(v1) was 'in order' or 'out of order'.

EDIT: For example: if vector v1 has vertices {A, B, C} and we have edges (A,B) (C,A)

so after topological sort I'll have in v2

{C, A, B}

There will be cases where i may not get a unique topological order, for example if i have (A,C) as the only edge, then v2 might end up with {A , B , C} or {B , A , C}

Now i need to look into v1 and v2 to find out if both v1 and v2 represent the same order or not.

SECOND EDIT: I tried an approach and it works for now, please tell me if this is a good approach or not.

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";
    }
  }
}

So what is the best way to compare v1 and v2 to test if my original vector of vertices(v1) was 'in order' or 'out of order'.

Not comparing the vectors. The test is flawed in that if it succeeds (both vectors are the same) you will know that it was in order, but if it fails (vectors differ) you will not know whether it was out of order or if it was in a different order.

Consider the graph (imagine edges going down):

  A
 / \
B   C
 \ /
  D

The lists { A, B, C, D } and { A, C, B, D } are both in topological order, because there is no ordering constraint between B and C. If you had one of the options and the boost::topological_sort yielded the other variant you will not know whether you had an incorrect order or rather a different correct one.

It is probably better to write a simple algorithm that will check the order for correctness and reorder if needed.

Do I understand your question correctly that you want to test if a list of vertices is already in topological order?

If so, you might do the following:

• Let the list of vertices be v. Now construct a list r where r[i] gives the index of vertex i in v, i.e. v[r[i]] = i.
• Then loop over all directed edges (i,j) and check that r[i] <= r[j].
• If so, the list v is already in topological order.

However, this will be just as slow as doing a full topological sort of v (both are linear in the number of edges plus number of vertices). So if your aim is just to have v in topological order, just do the sorting. If you need to keep v in the current order if possible, this will be useful.

std::vector has operator== so you can simply if(v1==v2)

Edit: this is a sufficient but not neccesary condition.