Typedef set with custom comparator and extra parameters

I have a wrapper around a boost directed graph. Each vertex has an integer id field and I want to write at typedef for a set of vertex descriptors ordered by id. In essence I have:

struct VertexData {
  int id;
};
typedef adjacency_list<vecS, vecS, bidirectionalS, VertexData> DirGraph;

typedef graph_traits<DirGraph>::vertex_descriptor GraphVd;

class GraphWrapper {
public:
  DirGraph g;
}

And I want to add:

typedef std::set<GraphVd> VdSet;

And have it be sorted by g[vd].id, i.e. the id at that vertex. I know that there are custom comparators for STL sets where you pass in a struct but I'm struggling to get access to the DirGraph g variable in the wrapper and also typedef-ing it.

When I do try to do something like

struct VdCmp {
  VdCmp(GraphWrapper &g) : g(g){};
  bool operator()(const GraphVd &vd1, const GraphVd&vd2) { return g[vd1].id > g[vd2].id }
private:
DirGraph g;
}

Then how do I typedef it for use in a header file? I'd have to create a VdCmp instance which requires a GraphWrapper for its constructor and I don't want to create classes in my header file.

Adjacency Lists allow a good deal of customization (e.g. Customizing Adjacency List Storage). However your expected customization is not a part of it.

The actual vertex storage (which determines enumeration order for global vertices) is actually an opaque collection which stores internal nodes - that happen to include the property bundle that you want to sort by. If you used setS as the container selector if would always use std::set<StoredEdge, ComparatorByTargetVertexDescriptor>, no way to override that.

You could approximate your desired behaviour by using the trick I described recently: How to use boost graph to traverse a planar graph ( representing a tree ) to simulate walking around the edge of the graph

If you don't mind going into undocumented implementation details you can even sort m_vertices using your own predicate:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <ranges>
namespace R = std::ranges;

struct VertexData {
    int id;

    constexpr bool operator<(VertexData const& other) const { return id < other.id; }
};

using DirGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexData>;
using GraphVd  = DirGraph::vertex_descriptor;

int main() {
    DirGraph g;

    GraphVd v1 = add_vertex(VertexData{100}, g);
    GraphVd v2 = add_vertex(VertexData{90}, g);
    GraphVd v3 = add_vertex(VertexData{80}, g);
    GraphVd v4 = add_vertex(VertexData{180}, g);
    /*GraphVd v5 =*/ add_vertex(VertexData{-42}, g);

    add_edge(v1, v2, g);
    add_edge(v1, v3, g);
    add_edge(v2, v4, g);
    add_edge(v2, v1, g);

    print_graph(g, get(&VertexData::id, g), std::cout << " === Before:\n");

    g.m_vertices.sort([&g](GraphVd a, GraphVd b) { return g[a].id < g[b].id; });

    print_graph(g, get(&VertexData::id, g), std::cout << "\n === Sorted vertices:\n");

    for (auto v : boost::make_iterator_range(vertices(g)))
        R::sort(g.out_edge_list(v), std::less{},
                [&g](auto const& out) { return g[out.get_iter()->m_target].id; });

    print_graph(g, get(&VertexData::id, g), std::cout << "\n === Sorted adjacencies:\n");
}

Printing

 === Before:
100 --> 90 80 
90 --> 180 100 
80 --> 
180 --> 
-42 --> 

 === Sorted vertices:
-42 --> 
80 --> 
90 --> 180 100 
100 --> 90 80 
180 --> 

 === Sorted adjacencies:
-42 --> 
80 --> 
90 --> 100 180 
100 --> 80 90 
180 --> 

Caveat

The above assume you know what you're doing. E.g. if you'd be using this approach with vecS as vertex container selector, you'd be changing the graph topology if edges already existed before sorting. listS was chosen to ensure reference stability of the vertices across the sort.

Also, the behavior may silently break in the future since this is using undocumented interface.

It might be worth "just" sorting the vertices before building your graph to avoid these pitfalls/restrictions.