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

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::const_iterator vertex_iterator; typedef typename std::vector::size_type vertices_size_type; // ... std::vector m_vertices; }; std::pair vertices(const my_graph& g) { return std::make_pair(g.m_vertices.begin(), g.m_vertices.end()); } // ... Doug