title: compare topologically sorted list with the original list
body: <p>i have a vector of vertices from mygraph, and i topologically sort the vertices.</p>
  
  <pre><code>typedef typename boost::adjacency_list&lt;boost::listS, boost::vecS, 
         boost::directedS,Vertex_t*&gt; Graph_t;
  
  typedef typename boost::graph_traits&lt;Graph_t&gt;::vertex_descriptor Vd_t;
  Graph_t mygraph;
  std::vector&lt;Vd_t&gt; v1; 
  //initialize the vertices and get a copy of vertices in vector v1
  //...
  //and then i use
  
  std::vector&lt;Vd_t&gt; v2;
  boost::topological_sort(mygraph,std::back_inserter(v2));
  </code></pre>
  
  <p>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'.</p>
  
  <p>EDIT:
  For example:
  if vector v1 has vertices {A,  B,  C} and we have edges
  (A,B)
  (C,A)</p>
  
  <p>so after topological sort I'll have in v2 </p>
  
  <p>{C, A, B}</p>
  
  <p>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}</p>
  
  <p>Now i need to look into v1 and v2 to find out if both v1 and v2 represent the same order or not. </p>
  
  <p>SECOND EDIT:
  I tried an approach and it works for now, please tell me if this is a good approach or not.</p>
  
  <pre><code>template &lt;typename Vertex_t&gt;
  void DepAnalyzer&lt;Vertex_t&gt;::CheckTotalOrder()
  {
    //Vd_t is the vertex descriptor type
    typename std::vector&lt;Vd_t&gt; topo_order;
    typename std::vector&lt;Vd_t&gt;::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&lt;Graph_t&gt;::vertex_iterator vi, vi_end;
    std::unordered_map&lt;Vertex_t*,int,std::hash&lt;Vertex_t*&gt;,
                        VertexEqual&gt; 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&lt;&lt;depGraph[*vi]-&gt;get_identifier_str()&lt;&lt;"\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&lt;&lt;depGraph[*ordered_vertices_iter]-&gt;get_identifier_str()&lt;&lt;"\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]] &gt;
        topo_order_map[depGraph[*ordered_vertices_iter]]) {
        std::cerr &lt;&lt; depGraph[*ordered_vertices_iter]-&gt;get_identifier_str() 
                  &lt;&lt; ": out of order\n";
      }
    }
  }
  </code></pre>