title: BGL adjacency_list: How to sort out_edges using vertex property, not descriptor
body: <p>Using BGL adjacency_list, I would like the out-edges from a vertex to be sorted by a property of the target vertex.</p>
  
  <p>In BGL, the out-edge list is already sorted by target vertex descriptor, but I happen to be using a <code>listS</code> as my vertex container, so my vertex descriptors are <code>void*</code> pointers. Unfortunately, I've found that sorting by these addresses makes the ordering of my graph traversal indeterministic. My vertices do have a custom property class which has an ID that could be used for sorting the out-edges, but I haven't been able to make it work. (See code below.)</p>
  
  <p>I've referred to this question, which was helpful in diagnosing the problem, but I didn't see a good solution in it: <a href="https://stackoverflow.com/questions/30968690/boost-graph-library-deterministic-order-of-iteration-of-in-edges">boost graph library: deterministic order of iteration of in_edges?</a></p>
  
  <h1>Unsorted MWE</h1>
  
  <p>This is a MWE without any attempt at sorting. Note that I create the vertices with <code>id</code> in the order 0, 5, 2, 8 to simulate the vertex addresses being in a different order than the <code>id</code>. In my real application, I can't guarantee that the addresses of these vertices will follow <code>id</code> ordering.</p>
  
  <p><strong><kbd><a href="http://coliru.stacked-crooked.com/a/ca02547ef42bc413" rel="nofollow noreferrer">Live On Coliru</a></kbd></strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/directed_graph.hpp&gt;
  
  class VertexInfo
  {
  public:
      VertexInfo(int i) : id(i) {}
      int id;
  };
  
  int main()
  {
      typedef boost::adjacency_list&lt; boost::setS,
                                     boost::listS,    
                                     boost::bidirectionalS,
                                     VertexInfo,
                                     boost::no_property,
                                     boost::no_property,
                                     boost::listS
                                   &gt; Graph;
  
      //typedef boost::graph_traits&lt;Graph&gt;::edge_descriptor Edge;
      typedef boost::graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
  
      Graph g;
  
      Vertex src  = boost::add_vertex(VertexInfo(0), g);
      Vertex tar1 = boost::add_vertex(VertexInfo(5), g);
      Vertex tar2 = boost::add_vertex(VertexInfo(2), g);
      Vertex tar3 = boost::add_vertex(VertexInfo(8), g);
  
      boost::add_edge(src, tar1, g);
      boost::add_edge(src, tar2, g);
      boost::add_edge(src, tar3, g);
  
      // If sorted by address, the order would probably be:
      // 0 --&gt; 5
      // 0 --&gt; 2
      // 0 --&gt; 8
      // If sorted by ID, the order should be:
      // 0 --&gt; 2
      // 0 --&gt; 5
      // 0 --&gt; 8
  
      typename boost::graph_traits&lt;Graph&gt;::out_edge_iterator ei, ei_end;
      for(boost::tie(ei, ei_end) = boost::out_edges(src, g); ei != ei_end; ++ei)
      {
          std::cout &lt;&lt; g[boost::source(*ei, g)].id 
                    &lt;&lt; " --&gt; " 
                    &lt;&lt; g[boost::target(*ei, g)].id 
                    &lt;&lt; std::endl;
      }
  
      return 0; 
  }
  </code></pre>
  
  <p>What this gives me currently is:</p>
  
  <pre><code>0 --&gt; 5
  0 --&gt; 2
  0 --&gt; 8
  </code></pre>
  
  <p>But I need it to give me this:</p>
  
  <pre><code>0 --&gt; 2
  0 --&gt; 5
  0 --&gt; 8
  </code></pre>
  
  <h1>Attempt at sorting, not working</h1>
  
  <p>I looked to the Boost documentation and found these two parts helpful.</p>
  
  <ol>
  <li><p>BGL provides an example on how to order the out-edges (<a href="http://www.boost.org/doc/libs/1_55_0/libs/graph/example/ordered_out_edges.cpp" rel="nofollow noreferrer">ordered_out_edges.cpp</a>) by creating a custom container selector and using a custom comparator for that container. Unfortunately, comparator in the example uses the target vertex descriptor and a default property of the edge in order to make the comparison. I would need a comparator that compares based on a custom property of the target vertices; without access to the graph object.</p></li>
  <li><p>BGL also shows how to add a <a href="http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/using_adjacency_list.html#sec:custom-vertex-properties" rel="nofollow noreferrer">custom vertex property tag</a> to the vertex; I had hoped that I could access a tagged vertex property from the vertex descriptor without having the graph object; but that doesn't seem to work either</p></li>
  </ol>
  
  <p><strong><kbd><a href="http://coliru.stacked-crooked.com/a/5c7dee0729278b87" rel="nofollow noreferrer">Live On Coliru</a></kbd></strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;functional&gt;
  #include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/directed_graph.hpp&gt;
  
  // http://www.boost.org/doc/libs/1_55_0/libs/graph/example/ordered_out_edges.cpp
  // http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/using_adjacency_list.html#sec:custom-vertex-properties
  // https://stackoverflow.com/questions/30968690/boost-graph-library-deterministic-order-of-iteration-of-in-edges
  // http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/adjacency_list.html
  
  // ??
  // https://stackoverflow.com/questions/9169276/bgl-edgeu-v-g-with-custom-associative-container-for-edge-lists
  
  #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  #error BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION not supported
  #endif
  
  // See custom-vetex-properties
  struct vertex_info_t
  {
      typedef boost::vertex_property_tag kind;
  };
  
  class VertexInfo
  {
  public:
      VertexInfo(int i) : id(i) {}
      int id;
  };
  
  ////////////////////////////////////////
  // See libs/graph/example/ordered_out_edges.cpp
  template &lt;class StoredEdge&gt;
  struct Comparator : public std::binary_function&lt;StoredEdge, StoredEdge, bool&gt;
  {
      bool operator()(const StoredEdge&amp; e1, const StoredEdge&amp; e2)
      {
          return boost::get(vertex_info_t(), e1.get_target()).id &lt; boost::get(vertex_info_t(), e2.get_target()).id;
          //return e2.get_target() &lt; e1.get_target(); // reverse order of insertion, an example to prove custom OrderedSetS but does not use vertex properties
      }
  };
  struct OrderedSetS {};
  namespace boost
  {
      template &lt;class ValueType&gt;
      struct container_gen&lt;OrderedSetS, ValueType&gt;
      {
          typedef std::set&lt;ValueType, Comparator&lt;ValueType&gt; &gt; type;
      };
      template &lt;&gt;
      struct parallel_edge_traits&lt;OrderedSetS&gt;
      { 
          typedef allow_parallel_edge_tag type;
      };
  }
  ////////////////////////////////////////
  
  int main()
  {
      typedef boost::adjacency_list&lt; OrderedSetS, //boost::setS,
                                     boost::listS,    
                                     boost::bidirectionalS,
                                     boost::property&lt;vertex_info_t, VertexInfo&gt;, //VertexInfo,
                                     boost::no_property,
                                     boost::no_property,
                                     boost::listS
                                   &gt; Graph;
  
      //typedef boost::graph_traits&lt;Graph&gt;::edge_descriptor Edge;
      typedef boost::graph_traits&lt;Graph&gt;::vertex_descriptor Vertex;
  
      Graph g;
  
      Vertex src  = boost::add_vertex(VertexInfo(0), g);
      Vertex tar1 = boost::add_vertex(VertexInfo(5), g);
      Vertex tar2 = boost::add_vertex(VertexInfo(2), g);
      Vertex tar3 = boost::add_vertex(VertexInfo(8), g);
  
      boost::add_edge(src, tar1, g);
      boost::add_edge(src, tar2, g);
      boost::add_edge(src, tar3, g);
  
      // If sorted by address, the order would probably be:
      // 0 --&gt; 5
      // 0 --&gt; 2
      // 0 --&gt; 8
      // If sorted by ID, the order should be:
      // 0 --&gt; 2
      // 0 --&gt; 5
      // 0 --&gt; 8
  
      typename boost::graph_traits&lt;Graph&gt;::out_edge_iterator ei, ei_end;
      for(boost::tie(ei, ei_end) = boost::out_edges(src, g); ei != ei_end; ++ei)
      {
          std::cout &lt;&lt; boost::get( boost::get(vertex_info_t(), g), boost::source(*ei, g) ).id 
                    &lt;&lt; " --&gt; " 
                    &lt;&lt; boost::get( boost::get(vertex_info_t(), g), boost::target(*ei, g) ).id 
                    &lt;&lt; std::endl;
      }
  
      return 0; 
  }
  </code></pre>
  
  <p>This results in a compilation error</p>
  
  <pre><code>main.cpp:38:26: error: no matching function for call to 'get(vertex_info_t, void*&amp;)'
           return boost::get(vertex_info_t(), e1.get_target()).id &lt; boost::get(vertex_info_t(), e2.get_target()).id;
  </code></pre>
  
  <p>It doesn't allow me to get the <code>VertexInfo</code> property class via <code>vertex_info_t</code> tag with only a vertex descriptor (<code>void*</code>) and without the graph.</p>
  
  <h1>Question</h1>
  
  <p>Can anyone think of a way to sort the out-edges by either external or internal-tagged properties of the target vertices?</p>