Re: [Boost-users] What is the way to sort graph vertices?

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-11-08 17:59:16

Slava wrote:

>Hi, 
>
>I need to find Maxumum Common Subgraph (between two graphs).
>For that task i need to get all the vertices of the 2 graphs sorted with some 
>property (like vertex label or id).
>
>regular std::sort seems not working with vertex iterators (vertices(graph)).
>
>What is the way to accomplish this?
>  
>
I can't think of any good way to do this with adjacency_list: there are 
no operations that allow one to arbitrarily reorder the vertices. This 
isn't the first time someone has asked for this feature; we'll try to 
get it into adjacency_list in a future version. For now, your best bet 
would probably be to inherit from the adjacency_list but keep your own, 
separate list of vertex_descriptors in that class, e.g.,

class my_graph : public adjacency_list<...>
{
  typedef adjacency_list<...> inherited;

public:
  typedef typename graph_traits<inherited>::vertex_descriptor 
vertex_descriptor;
  typedef typename std::vector<vertex_descriptor>::const_iterator 
vertex_iterator;
  typedef typename std::vector<vertex_descriptor>::size_type 
vertices_size_type;

  // ...

  std::vector<vertex_descriptor> m_vertices;
};

std::pair<my_graph::vertex_iterator, my_graph::vertex_iterator> 
vertices(const my_graph& g)
{
  return std::make_pair(g.m_vertices.begin(), g.m_vertices.end());
}

// ...

    Doug