Re: [Boost][BGL] What are the correct vertex/edge index types?

From: Seth (bugs_at_[hidden])
Date: 2024-10-15 13:33:22

On Tue, Oct 15, 2024, at 10:04 AM, Hermann Stamm-Wilbrandt via Boost wrote:
> First I looked in graph/test.
> Most times int is used there, only once std::size_t:
>
> property< edge_index_t, int >
>
> Next I looked into graph/example, same picture there.
>
> Ok, I read that example and test might contain stuff that
> would not go into BGL code.
> So I looked into graph/include/boost/graph:

Vertex index doesn't have to be a "static" property of a graph. Many graph models don't naturally provide such an index.

Instead, it is often an auxiliary structure for a particular (set of) algorithms. The conceptual requirements are documented with the algorithms, e.g. [`copy_graph`](https://www.boost.org/doc/libs/1_86_0/libs/graph/doc/copy_graph.html) says

>> The vertex index map type must be a model of Readable Property Map and must map the vertex >> descriptors of G to the integers in the half-open range [0,num_vertices(G)).

Any type that satisfies this for your particular application domain will do. In some applications, `uint16_t` would be fine. Of course, in generic or library code, err on the safe side.

None of the library algorithms create a default index argument if the graph model doesn't supply it, as far as I can tell. So the user is always in control.