Access vertex via vertex_index property?

Question

Is there a built-in way in BGL to access a vertex via its vertex_index property?

using VertexProperties = boost::property<boost::vertex_index_t, int>;
using DirectedGraph = boost::adjacency_list<
   boost::listS, 
   boost::vecS, 
   boost::directedS, 
   VertexProperties,
   boost::no_property>;
using VertexDescriptor = boost::graph_traits<DirectedGraph>::vertex_descriptor;
using EdgeDescriptor = boost::graph_traits<DirectedGraph>::edge_descriptor;

int main()
{
    DirectedGraph g;
    auto indices = boost::get(boost::vertex_index, g);

    boost::add_vertex(DirectedGraph::vertex_property_type{123123}, g); // unique index
    boost::add_vertex(DirectedGraph::vertex_property_type{451345}, g); // unique index

    // how do I access the vertex with my unique index?

    // I only see the way from vertex->vertex_index via the property map
    indices[x];

}

The usual suggestion for this sort of thing is to use the bundled properties feature. https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/bundles.html. This is easier and far more flexible. — ravenspoint, Oct 29 '22 at 14:09
With bundled properties the same issue applies though, doesnt it? — Yamahari, Oct 29 '22 at 14:12
The flexibility of bundled properties allows you to design for your particular requirements ( which you have not described ). Perhaps something like this: when you add a vertex and its bundled class, store a pointer to the bundled class in a map keyed by your index number. — ravenspoint, Oct 29 '22 at 14:25

score 2 · Accepted Answer · answered Oct 30 '22 at 17:11

By far the most user-friendly solution in this realm is to use internal name properties. This is a mixin-feature for boost::adjacency_list (implemented in maybe_named_graph).

Moreover, your approach "repurposing" vertex_index_t for this is probably misguided: vertex indices are a library "contract" which assumes that it maps all vertices vertices(g) to a contiguous integral domain [0, num_vertices(g)). Your ID doesn't satisfy those properties so it will lead to unspecified, and most likely Undefined Behaviour when you invoke BGL algorithms on your graph.

All in all, I'd redefine the properties as your own bundle:

struct VertexProps {
    int my_id;
    VertexProps(int id) : my_id(std::move(id)) {}
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, VertexProps,
                                    boost::no_property>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

Now you need to specialize some traits to tell maybe_named_graph that some part of VertexProps is your vertex name:

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = int;
        int const& operator()(VertexProps const& vp) const { return vp.my_id; }
    };
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    struct type {
        auto operator()(int const& value) const { return VertexProps{value}; }
    };
};

Now you can add vertices by name:

V a = add_vertex(123123, g); // unique index
V b = add_vertex(451345, g); // unique index

But instead of using a or b you can keep using the name for subsequent operations:

add_edge(123123, 451345, g);

You can get vertex descriptors from the property explicitly:

V va = *g.vertex_by_property(123123);
V vb = *g.vertex_by_property(451345);

As a surprise bit of user-friendliness, you don't even need to create vertices ahead of time:

add_edge(234234, 562456, g);

will magically add the two new, named, vertices.

Live Demo

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

struct VertexProps {
    int my_id;
    VertexProps(int id) : my_id(std::move(id)) {}
};

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = int;
        int const& operator()(VertexProps const& vp) const { return vp.my_id; }
    };
};

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    struct type {
        auto operator()(int const& value) const { return VertexProps{value}; }
    };
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::directedS, VertexProps,
                                    boost::no_property>;
using V     = Graph::vertex_descriptor;
using E     = Graph::edge_descriptor;

int main() {
    Graph g;
    print_graph(g, get(&VertexProps::my_id, g), std::cout << "\n --- Empty:\n");
    auto my_id = get(&VertexProps::my_id, g);

    V a = add_vertex(123123, g); // unique index
    V b = add_vertex(451345, g); // unique index
    print_graph(g, my_id, std::cout << "\n --- Vertices:\n");

    std::cout << g[a].my_id << std::endl;
    std::cout << g[b].my_id << std::endl;

    add_edge(123123, 451345, g);
    print_graph(g, my_id, std::cout << "\n --- Edge:\n");

    V va = *g.vertex_by_property(123123);
    V vb = *g.vertex_by_property(451345);
    add_edge(vb, va, g);
    print_graph(g, my_id, std::cout << "\n --- Edges:\n");

    add_edge(234234, 562456, g);
    print_graph(g, my_id, std::cout << "\n --- Magically added:\n");
}

Prints

 --- Empty:

 --- Vertices:
123123 --> 
451345 --> 
123123
451345

 --- Edge:
123123 --> 451345 
451345 --> 

 --- Edges:
123123 --> 451345 
451345 --> 123123 

 --- Magically added:
123123 --> 451345 
451345 --> 123123 
562456 --> 
234234 --> 562456

More and Caveats

There are a number of interesting edge cases around this. You can read more about them here:

How to use boost graph algorithm on a named graph?

Access vertex via vertex_index property?

1 Answers1

Live Demo

More and Caveats