boostorg / boostorg/graph

reverse_graph.hpp breaks ADL get

Open
#116 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

Including `reverse_graph.hpp` defines a `get` overload inside the `boost::detail` namespace:

```
namespace detail {
template
struct underlying_edge_desc_map_type {
E operator[](const reverse_graph_edge_descriptor& k) const {
return k.underlying_descx;
}
};

template
E
get(underlying_edge_desc_map_type m,
const reverse_graph_edge_descriptor& k)
{
return m[k];
}
}

```

If included before other algorithms it can mess up the ADL on `get` calls from within that detail namespace. E.g. in `strong_components.hpp` the Tarjan visitor does

if (get(comp, w) == (std::numeric_limits::max)())

This call fails to compile if `reverse_graph.hpp` had been included before. In fact, the developers probably found this out when they decided to only include the `transpose_graph.hpp` header /after/ the Tarjan implementation (and before the Kosaraju version that requires it).

The exact mechanics of the bug are not completely clear to me. But I guess it sits on the intersection of ADL and partial ordering. In fact using

using ::boost::get;
if (get(comp, w) == (std::numeric_limits::max)()) // ...

does enable ADL at instantiation time. But I suspect the **structural** fix would be to avoid declaring a `get` overload inside the detail namespace.

----

found from https://stackoverflow.com/questions/52239778/bgl-call-to-strong-components-fails-to-compile-when-random-spanning-tree-hpp-is

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.