Make boost graph contain only two vertices when adding one edge

Question

I'm using Boost library to work with graphs in C++.

boost::adjacency_list <boost::vecS, boost::vecS, boost::bidirectionalS> DiGraph;
DiGraph graph;
boost::add_edge(10000, 20000, graph);

The graph contains 20001 vertices and one edge. Yet, I need to have only two vertices 10000 and 20000.

One possible way is to associate data with nodes (e.g. from this example); however, maybe there is a simpler way to do this. How can I have a graph with 2 vertices and one edge, if the vertices are not (0,1)?

In python networkx I would use simply graph.add_edge(10000, 20000) and would get desired behavior. Any clues how to do this in C++?

Answer 1

You should use a node-based container selector for the vertex collection.

E.g. using listS:

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

int main() {
    typedef boost::adjacency_list <boost::vecS, boost::listS, boost::bidirectionalS, int> DiGraph;
    DiGraph graph;

    DiGraph::vertex_descriptor 
        v1 = add_vertex(100000, graph),
        v2 = add_vertex(200000, graph);

    boost::add_edge(v1, v2, graph);
    boost::print_graph(graph, boost::get(boost::vertex_bundle, graph));
}

Note that vertex_index doesn't come for free now (you have to pass/maintain it manually for all algorithms).

On the up-side, iterators and descriptors are stable (unless deleted).