boostorg / graph Goto Github PK

View Code? Open in Web Editor NEW

307.0 15.0 205.0 28.23 MB

Boost.org graph module

Home Page: http://boost.org/libs/graph

C 1.69% C++ 97.92% HTML 0.02% Shell 0.04% CMake 0.05% Starlark 0.30%

graph's Introduction

Boost Graph Library

===================

A generic interface for traversing graphs, using C++ templates.

The full documentation is available on boost.org.

Support, bugs and feature requests

Bugs and feature requests can be reported through the Github issue page.

Development

	Master	Develop
Github Actions
Drone

Clone the whole boost project, which includes the individual Boost projects as submodules (see boost+git doc):

git clone https://github.com/boostorg/boost
cd boost
git submodule update --init

The Boost Graph Library is located in libs/graph/.

Boost Graph Library is mostly made of headers but also contains some compiled components. Here are the build commands:

./bootstrap.sh            <- compile b2
./b2 headers              <- just installs headers
./b2                      <- build compiled components

Note: The Boost Graph Library cannot currently be built outside of Boost itself.

Running tests

First, make sure you are in libs/graph/test. You can either run all the 300+ tests listed in Jamfile.v2 or run a single test:

../../../b2                        <- run all tests
../../../b2 cycle_canceling_test   <- single test

You can also check the regression tests reports.

graph's People

Contributors

Stargazers

Watchers

Forkers

jbohren-forks giogadi belcourt j-4 atombrella sanderbog cirosantilli benpope javidcf marcelraad gatlex wygos lastique gomani danieljames ymarkovitch mikael-s-persson josefcibulka jakobandersen lorenzb faithandbrave jzmaddock xuhdev mbradle antmd jaredgrubb nusus maelvls fsun2p10 limbolily annlei1 arafatkatze aschnell jviiret crossbuild daniel-j-h coderakki skramm felix-salfelder sgayda2 arneboe sehe awulkiew murraycu kundor autodesk-forks mfuchs danielae xltools akumta mdb256 ychelanguagestudio dicky98 hustdc njlr omshinde hsnks100 bergfi asomers saiganesh10 scottgw yi-ji jwakely bazelboost db12138 myestro smeenai davydden johncoconut tlming16 raahlb andrewmw94 mike-devel jeremy-murphy kenkangxgwe mkatliar zamazan4ik cromwellenage hookk harshavardhank mr-nightskycoder aleden deinst buckaroo-pm approx-uw akag98 jacobhartzellou ahhz chenmeng0508 kojoley tinko92 jeking3 anadon cartney mosjin tntljc jasjuang tingyingwu2010 tapaswenipathak przemb

graph's Issues

Enhancement proposal: verices() and edges() returning boost::iterator_range

Currently the vertices() and edges() functions in BGL return an std::pair of iterators. To iterate over vertices, a code like following is usually written:

typename graph_traits<Graph>::vertices_size_type b = 0;
typename graph_traits<Graph>::vertex_iterator i, end;
for (boost::tie(i, end) = vertices(g); i != end; ++i)
    do_something(*i);

If vertices() and edges() returned a boost::iterator_range, a cleaner code could be written:

for (auto v : vertices(g))
    do_something(v);

Typo in edge_coloring docs

It appears that the basic template of the docs of edge_coloring was taken from the docs of king_ordering and modified accordingly. However, some parts of the docs still contain words from king_ordering documentation, which must also be modified.

The following changes must be done:

In the Example section of the docs, the line See example/king_ordering.cpp shall be changed to See example/edge_coloring.cpp. The hypertext reference of the link is correct, though.

Also, there is the following comment in the HTML file of the docs:

which is also copied from king_ordering. It should be replaced with the following comment:

The reference of this can be found here.

Add support for ephemeral vertexes

I'm looking at GraphQL, and they have a legitimate use case where vertices aren't local but are dynamically generated. It would be really powerful to support that use case, though it may need to wait for a whole new implementation. Anyways, an eye should be kept to supporting their use case.

Request: add degree_sequence_game in BGL

igraph has this degree_sequence_game src/games.c method to randomly create a graph with a set of degrees.

I wonder if you know if there is any implementation of that stochastic algorithm using BGL. And if not, if there is any road map on implementing it. Thanks!

topo-sort1.cpp fails to compile if included header file order is changed

I found the error when my editor uses clang-format to format the code.

Example directory has a file topo-sort1.cpp. It includes two header files from bgl library.

/* ommited */
#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/topological_sort.hpp>

If I change the order to

/* ommited */
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/vector_as_graph.hpp>

gcc-8.2 compiler shows a error message shown below.

(The error message is also saved as a text file errorlog.txt, if you wish to read on your terminal.)

In file included from /usr/include/boost/graph/topological_sort.hpp:16,
                 from topo-sort1.cpp:12:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]’:
/usr/include/boost/graph/depth_first_search.hpp:335:36:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
/usr/include/boost/graph/topological_sort.hpp:65:23:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]’
topo-sort1.cpp:42:61:   required from here
/usr/include/boost/graph/depth_first_search.hpp:232:43: error: no matching function for call to ‘vertices(const std::vector<std::__cxx11::list<int> >&)’
     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
                                   ~~~~~~~~^~~
In file included from /usr/include/boost/graph/depth_first_search.hpp:18,
                 from /usr/include/boost/graph/topological_sort.hpp:16,
                 from topo-sort1.cpp:12:
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: candidate: ‘template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&)’
 typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
                                                ^~~~~~~~
/usr/include/boost/graph/graph_concepts.hpp:47:48: note:   template argument deduction/substitution failed:
/usr/include/boost/graph/graph_concepts.hpp: In substitution of ‘template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&) [with T = std::vector<std::__cxx11::list<int> >]’:
/usr/include/boost/graph/depth_first_search.hpp:232:43:   required from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]’
/usr/include/boost/graph/depth_first_search.hpp:335:36:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
/usr/include/boost/graph/topological_sort.hpp:65:23:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]’
topo-sort1.cpp:42:61:   required from here
/usr/include/boost/graph/graph_concepts.hpp:47:48: error: no type named ‘ThereReallyIsNoMemberByThisNameInT’ in ‘class std::vector<std::__cxx11::list<int> >’
In file included from /usr/include/boost/graph/topological_sort.hpp:16,
                 from topo-sort1.cpp:12:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]’:
/usr/include/boost/graph/depth_first_search.hpp:335:36:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
/usr/include/boost/graph/topological_sort.hpp:65:23:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]’
topo-sort1.cpp:42:61:   required from here
/usr/include/boost/graph/depth_first_search.hpp:242:43: error: no matching function for call to ‘vertices(const std::vector<std::__cxx11::list<int> >&)’
     for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
                                   ~~~~~~~~^~~
In file included from /usr/include/boost/graph/depth_first_search.hpp:18,
                 from /usr/include/boost/graph/topological_sort.hpp:16,
                 from topo-sort1.cpp:12:
/usr/include/boost/graph/graph_concepts.hpp:47:48: note: candidate: ‘template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&)’
 typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&);
                                                ^~~~~~~~
/usr/include/boost/graph/graph_concepts.hpp:47:48: note:   template argument deduction/substitution failed:
/usr/include/boost/graph/graph_concepts.hpp: In substitution of ‘template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&) [with T = std::vector<std::__cxx11::list<int> >]’:
/usr/include/boost/graph/depth_first_search.hpp:242:43:   required from ‘void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; DFSVisitor = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::graph_traits<Graph>::vertex_descriptor = int]’
/usr/include/boost/graph/depth_first_search.hpp:335:36:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
/usr/include/boost/graph/topological_sort.hpp:65:23:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]’
topo-sort1.cpp:42:61:   required from here
/usr/include/boost/graph/graph_concepts.hpp:47:48: error: no type named ‘ThereReallyIsNoMemberByThisNameInT’ in ‘class std::vector<std::__cxx11::list<int> >’
In file included from /usr/include/boost/graph/depth_first_search.hpp:21,
                 from /usr/include/boost/graph/topological_sort.hpp:16,
                 from topo-sort1.cpp:12:
/usr/include/boost/graph/named_function_params.hpp: In instantiation of ‘static boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::map_type boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::make_map(const Graph&, Value, const PM&, const ArgPack&) [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Value = boost::default_color_type; PM = int; boost::detail::map_maker_helper<false, Graph, ArgPack, Value, PM>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >; typename boost::remove_const<typename boost::detail::override_const_property_t<typename boost::parameter::value_type<ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, boost::vertex_index_t, Graph, boost::detail::parameter_exists<ArgPack, boost::graph::keywords::tag::vertex_index_map>::value>::result_type>::type = boost::typed_identity_property_map<long unsigned int>]’:
/usr/include/boost/graph/named_function_params.hpp:606:32:   required from ‘static boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(const Graph&, const ArgPack&, ValueType) [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type; boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >]’
/usr/include/boost/graph/named_function_params.hpp:621:70:   required from ‘typename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::make_property_map_from_arg_pack_gen<MapTag, ValueType>::operator()(const Graph&, const ArgPack&) const [with Graph = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type; typename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type = boost::shared_array_property_map<boost::default_color_type, boost::typed_identity_property_map<long unsigned int> >]’
/usr/include/boost/graph/depth_first_search.hpp:337:80:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; Graph = std::vector<std::__cxx11::list<int> >]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = std::vector<std::__cxx11::list<int> >; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::vertex_index_map, const boost::typed_identity_property_map<long unsigned int> >, boost::parameter::aux::empty_arg_list> >; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = std::vector<std::__cxx11::list<int> >; P = boost::topo_sort_visitor<std::front_insert_iterator<std::deque<int> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<boost::typed_identity_property_map<long unsigned int>, boost::vertex_index_t, boost::no_property>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
/usr/include/boost/graph/topological_sort.hpp:65:23:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = std::vector<std::__cxx11::list<int> >; OutputIterator = std::front_insert_iterator<std::deque<int> >; P = boost::typed_identity_property_map<long unsigned int>; T = boost::vertex_index_t; R = boost::no_property]’
topo-sort1.cpp:42:61:   required from here
/usr/include/boost/graph/named_function_params.hpp:580:30: error: ‘num_vertices’ was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
                  num_vertices(g),
                  ~~~~~~~~~~~~^~~
In file included from topo-sort1.cpp:13:
/usr/include/boost/graph/vector_as_graph.hpp:188:3: note: ‘template<class EdgeList, class Alloc> typename std::vector<_Tp, _Alloc>::size_type boost::num_vertices(const std::vector<_Tp, _Alloc>&)’ declared here, later in the translation unit
   num_vertices(const std::vector<EdgeList, Alloc>& v)
   ^~~~~~~~~~~~

9438-returns: call of overloaded ‘ignore_unused_variable_warning(...)’ is ambiguous

Hello dear team of Boostorg.

First, I am not sure wheter this is the right repository to post this issue, if not, I will grandly repost it somewhere else.

The error is pretty much the same as in the closed issue #9438 and I am not sure why it reappeared.

OS: Ubuntu 18.04 Bionic Beaver
clang: 6.0
lemon: 1.3.1
boost: happened under 1.63 and was reproduced with boost 1.68

#include <boost/geometry.hpp>
#include <lemon/list_graph.h>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

using Point = boost::geometry::model::point<double, 2, bg::cs::cartesian>;
using Graph = lemon::ListDigraph;
using Node = lemon::ListDigraph::Node;
typedef std::pair<Point, Node> Pair;
using BoostRTree = bgi::rtree<Pair, bgi::quadratic<16>>;
using BoostQueryResult = std::vector<Pair>;

int main()
{
	Point one = Point(10, 51);
	Point two = Point(10, 51);
	BoostRTree rtreePair = BoostRTree();
	Graph graph;
	Node dummy1 = graph.addNode();
	Node dummy2 = graph.addNode();

	rtreePair.insert(std::make_pair(one, dummy1));	
	return 0;
}

[Question] Why does BGL use exceptions to exit early?

The BGL documentation says to see boost email discussions for further details. (https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/faq.html)

Does anyone know where I can find these discussions?

Prim's minimum spanning tree algorithm can't use Dijkstra's shortest paths algorithm

Prim's algorithm can NOT use Dijkstra' shortest paths algorithm to return the map of the predecessor, because Dijkstra's shortest path allows to create a shortest paths tree, that is a spanning tree (if all the nodes are connected) but not always a minimum spanning tree.
I suggest to do a new implementation of the algorithm.
In general, the two algorithms are different: Dijkstra minimizes the weights of the paths from the root to the other nodes, Prim minimizes the sum of the weights of the tree.
Here follow a simple example:
Consider a complete graph with 3 vertices: a, b, c
Now,
{a, b} = 2
{a, c} = 1
{b, c} = 1
A correct spanning tree, using Dijkstra, is:

a
- b
- c

The sum of the weights is {a, b} + {a, c} = 2 + 1 = 3.
However, Prim's algorthim (starting with a) would find this spanning tree, instead:

a
- c
  - b

The sum of the weights this time is {a, c} + {b, c} = 1 + 1 = 2
The problem can be found in include/boost/graph/prim_minimum_spanning_tree.hpp.

Edit: there was a typo in the sum of the weights for Prim (wrong edge)

revising BGL code (isomorphism.hpp) that uses abort()

graph/include/boost/graph/isomorphism.hpp

Line 321 in 887e63d

abort();

is an abort() call. This is a problem for interoperation with R as the static checker warns about such calls, and warnings preclude inclusion of packages in certain ecosystems.

There don't seem to be many instances of abort() in BGL code. Should it be replaced by a boost::throw_exception?

HTML and other errors in doc/graph_theory_review.html

Due to unclosed HTML tag the page reads: This graph is the undirected version(b,y))

I already fixed this and other errors on this page in #191

breadth_first_visit substitues null BFS visitor

breadth_first_visit ignores the visitor object passed in and uses a null one instead. To recreate:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
using namespace std;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, uint>, boost::property<boost::edge_index_t, uint>> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor                       vertex_t;
typedef boost::graph_traits<Graph>::edge_descriptor                         edge_t;
typedef boost::graph_traits<Graph>::vertex_descriptor                       vertex_t;


struct CollectBFSVisitor : public boost::default_bfs_visitor
{
        virtual void initialize_vertex(vertex_t v, Graph const& g) {cout << "init vertex\n";};
        virtual void discover_vertex(vertex_t v, Graph const& g) {};
        virtual void examine_vertex(vertex_t v, Graph const& g) {};
        virtual void finish_vertex(vertex_t v, Graph const& g) {};
        virtual void black_target(edge_t, Graph const& g) {};
        virtual void gray_target(edge_t, Graph const& g) {};
        virtual void tree_target(edge_t, Graph const& g) {};
        virtual void tree_edge(edge_t, Graph const& g) {};
        virtual void non_tree_edge(edge_t, Graph const& g) {};
};

struct VertBuffer : boost::queue<vertex_t>
{
};

int main()
{
        Graph g;
        vertex_t x = add_vertex(g);
        auto indexmap = boost::get(boost::vertex_index, g);
        auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

        VertBuffer q;

        CollectBFSVisitor v;
        breadth_first_visit(g, x, q, v, colormap); // the cout doesn't run, but if you change it to breadth_first_search it does
}

Problem line in boost/graph/breadth_first_search.hpp

breadth_first_visit
  (ng, s,
   choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(),
   choose_param(get_param(params, graph_visitor),
                make_bfs_visitor(null_visitor())),
   choose_pmap(get_param(params, vertex_color), ng, vertex_color)
   );

Dijkstra's shortest paths ignores color_map named parameter

Dijsktra's shortest paths takes as parameter UTIL/OUT a color_map. Which should be passed to and used by breadth first search.
However, the current implementation ignores the color_map, if provided, and always creates a default one.

https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html
https://github.com/boostorg/graph/blob/develop/include/boost/graph/dijkstra_shortest_paths.hpp

Store properties without indirection

stored_edge_property contains a std::unique_ptr<Property> instead of the raw Property. In my application, this doubles the memory use of the graph and more than doubles the running time. It comes with this explanation

// Holding the property by-value causes edge-descriptor
// invalidation for add_edge() with EdgeList=vecS. Instead we
// hold a pointer to the property. std::auto_ptr is not
// a perfect fit for the job, but it is darn close.

I tried to understand and couldn't make sense of what this is supposed to mean. In any case, my property is a (wrapper for a) double, and I strongly doubt that storing a double will invalidate anything. Or do people keep pointers/references to internal properties, do some insertions/removals, then expect the properties are still there? If so, I'd like this expensive feature to be optional please... The comment seems to indicate that this is only needed for vecS but it doesn't seem restricted to vecS (and even for vecS I want to be able to avoid it).

Function mcgregor_common_subgraphs cannot correctly find subgraph

Here is my code. My code is trying to find common subgraph between graph1 and graph2 with specific number of vertices.

#include <iostream>
#include <unordered_map>
#include <string>
#include <boost/algorithm/string.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/property_map.hpp>

using EdgeProperty = boost::property<boost::edge_name_t, unsigned int>;
using VertexProperty = boost::property<boost::vertex_name_t, unsigned int, boost::property<boost::vertex_index_t, int> >;
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperty, EdgeProperty>;

template<typename GraphFirst, typename GraphSecond>
struct generate_subgraph_callback {
  generate_subgraph_callback(const GraphFirst &graph1, const GraphSecond &graph2,
                             std::vector <Graph> *result, int size) :
    m_graph1(graph1), m_graph2(graph2), m_result(result), m_subgraph_size(size) {}
  template<typename CorrespondenceMapFirstToSecond, typename CorrespondenceMapSecondToFirst>
  bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                  CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                  typename boost::graph_traits<GraphFirst>::vertices_size_type subgraph_size) {
    // only when size equals input
    if (subgraph_size != m_subgraph_size) {
      return (true);
    }
    Graph subgraph;
    std::vector<int> vertex_set; // vertex_set contains old graph id
    std::unordered_map<int, int> map;

    BGL_FORALL_VERTICES_T(vertex1, m_graph1, GraphFirst){
      // skip unmapped vertices
      if (boost::get(correspondence_map_1_to_2, vertex1) != boost::graph_traits<GraphSecond>::null_vertex()) {
        vertex_set.push_back(vertex1);
      }
    }

    // reconstruct vertices
    int index = 0;
    for (auto it = vertex_set.begin(); it != vertex_set.end(); it++) {
      boost::add_vertex(VertexProperty(boost::get(boost::vertex_name_t(), m_graph1, *it)), subgraph);
      std::cout << *it << " " << get(boost::vertex_name_t(), m_graph1, *it) << " " << index << std::endl;
      map[*it] = index;
      index++;
    }
    // reconstruct edges
    for (auto it = vertex_set.begin(); it != vertex_set.end(); it++) {
      int index1 = map[*it];
      for (auto _it = std::next(it); _it != vertex_set.end(); _it++) {
        int index2 = map[*_it];
        // check edge exists
        if (boost::edge(*it, *_it, m_graph1).second) {
          boost::add_edge(index1, index2, 
            boost::get(boost::edge_name_t(), m_graph1, boost::edge(*it, *_it, m_graph1).first), subgraph);
        } else if(boost::edge(*_it, *it, m_graph1).second) {
          boost::add_edge(index2, index1, 
            boost::get(boost::edge_name_t(), m_graph1, boost::edge(*_it, *it, m_graph1).first), subgraph);
        }
      }
    }

    (*m_result).push_back(subgraph);
    return (true);
  }

private:
  const GraphFirst &m_graph1;
  const GraphSecond &m_graph2;
  std::vector <Graph> *m_result;
  int m_subgraph_size;
};

std::vector <Graph> find_maximal_common_subgraphs_n_vertices(const Graph& g1, const Graph& g2, int n) {
  // use boost::mcgregor_common_subgraphs
  auto vertex_comp = boost::make_property_map_equivalent(boost::get(boost::vertex_name, g1), boost::get(boost::vertex_name, g2));
  auto edge_comp = boost::make_property_map_equivalent(boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));

  std::vector <Graph> result;
  // store each common subgraph into result
  generate_subgraph_callback<Graph, Graph> callback(g1, g2, &result, n);
  boost::mcgregor_common_subgraphs_maximum_unique(g1, g2, true, callback, boost::edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));

  return result;
}

int main(){
  Graph graph1;
  boost::add_vertex(VertexProperty(11), graph1);
  boost::add_vertex(VertexProperty(12), graph1);
  boost::add_vertex(VertexProperty(13), graph1);
  boost::add_vertex(VertexProperty(10), graph1);
  boost::add_edge(0, 1, EdgeProperty(1), graph1);
  boost::add_edge(1, 2, EdgeProperty(1), graph1);
  boost::add_edge(2, 3, EdgeProperty(1), graph1);
  boost::add_edge(3, 1, EdgeProperty(1), graph1);
 
  Graph graph2;
  boost::add_vertex(VertexProperty(11), graph2);
  boost::add_vertex(VertexProperty(12), graph2);
  boost::add_vertex(VertexProperty(13), graph2);
  boost::add_vertex(VertexProperty(10), graph2);
  boost::add_edge(0, 1, EdgeProperty(1), graph2);
  boost::add_edge(1, 2, EdgeProperty(1), graph2);
  boost::add_edge(2, 3, EdgeProperty(1), graph2);
  boost::add_edge(3, 0, EdgeProperty(1), graph2);

  std::vector <Graph> result = find_maximal_common_subgraphs_n_vertices(graph1, graph2, 4);
  std::cout << result.size() << std::endl;

  return 0;
}

It is clear that 11->12->13->10 should be a common subgraph with 4 vertices while result size is 0. I looked at source code of function mcgregor_common_subgraphs and I believe the reason is in below code segment.

if (!is_undirected2)
                {

                    // Search for edge from new to existing vertex (graph2)
                    BGL_FORALL_OUTEDGES_T(
                        new_vertex2, edge2, graph2, GraphSecond)
                    {
                        if (target(edge2, graph2) == existing_vertex2)
                        {
                            edge_from_new2 = edge2;
                            edge_from_new_exists2 = true;
                            break;
                        }
                    }
                }

                // Make sure edges from new to existing vertices are equivalent
                if ((edge_from_new_exists1 != edge_from_new_exists2)
                    || ((edge_from_new_exists1 && edge_from_new_exists2)
                        && !edges_equivalent(edge_from_new1, edge_from_new2)))
                {

                    return (false);
                }

                if ((edge_from_new_exists1 && edge_from_new_exists2)
                    || (edge_to_new_exists1 && edge_to_new_exists2))
                {
                    has_one_edge = true;
                }

Here when subgraph is a graph containing nodes 11,12,13 and we want to extend node 10, mcgregor_common_subgraphs finds out there is an edge between 10 and 11 in subgraph2 while ther e is no edge between 10 and 11 in subgraph1. Hence can_extend_graph will return false. I believe the implementation of mcgregor_common_subgraphs now can only find subgraphs that appears "fully" in both graphs, which will miss many common subgraphs.

Add file save/load support

One thing which would be useful to add would be general support for reading from and writing to a number of graph file formats. antlr4 should be of help here. It looks like there shouldn't be any licensing conflicts. I'd like to coordinate with cwl and NetworkX about some of these to add or improve support for their use cases.

Here's a little reading:
https://github.com/antlr/antlr4/blob/master/doc/cpp-target.md
http://graphml.graphdrawing.org/
https://github.com/antlr/grammars-v4/tree/master/xml
https://github.com/antlr/grammars-v4/tree/master/gml
https://github.com/antlr/grammars-v4/tree/master/dot
https://github.com/common-workflow-language/common-workflow-language

The `m_eproperty` are not same in subgraph.

Imagine we have a root graph g, and two sons of it g1 and g2.
If we use edges(g1) to get two iterators and cycle from one to the other to find an edge with index i,
we name its corresponding descriptor as ed_1 = *e1_i.
We use the same method in g, find an edge with index i, and convert it to g1's local edge descriptor, we name it ed_2 = g1.global_to_local(*e_i).
And I found that their m_eproperty are not the same. Shouldn't these two be the same descriptor?

bidir_vec_remove_edge.cpp not tested

bidir_vec_remove_edge.cpp is currently not tested, and triggers a static assert if you try and build it. Any ideas anyone?

ordered_out_edges.cpp dereferences a null iterator

Title says it all, msvc runtime checks catch this.

Consume boostorg/disjoint_sets

The repository disjoint_sets contains one non-detail header and it is in boost/pending. A search of boost shows that only Boost.Graph and Boost.GraphParallel use disjoint_sets. I would like to eliminate disjoint_sets as a separate repository to ease the burden on the CMT. The maintainer of Boost.Container did not feel that disjoint_sets belonged there. As such I would like to move this module into Boost.Graph and update Graph and GraphParallel appropriately.

breadth_first_search segfaults on graphs with no edges

breath_first_search appears to not be robust against degenerate graphs, such as a single vertex with no edges. Adding an edge connecting this single vertex to itself seems to be a workaround.

To reproduce:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/breadth_first_search.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, uint>, boost::property<boost::edge_index_t, uint>> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor                       vertex_t;


struct BFSVisitor : boost::default_bfs_visitor
{
};

int main()
{
        Graph g;
        vertex_t x;

        add_vertex(x, g);

        //add_edge(x, x, g); // uncomment this line for workaround

        BFSVisitor v;
        breadth_first_search(g, x, boost::visitor(v));
}

On Fedora this crashes with:

boostbug: /usr/local/boost/boost/graph/two_bit_color_map.hpp:87: void boost::put(const boost::two_bit_color_map&, typename boost::property_traits::key_type, boost::two_bit_color_type) [with IndexMap = boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_index_t, unsigned int>, long unsigned int>; typename boost::property_traits::key_type = long unsigned int]: Assertion `(std::size_t)i < pm.n' failed.
[1] 14139 abort (core dumped) ./boostbug

Add timing information to tests

In order to keep track of which tests are taking how long, it'd be useful to see how long each one takes.

csr-example.cpp does not compile

I see:

1>csr-example.cpp
1>d:\data\boost\boost\boost\graph\graphviz.hpp(265): error C2064: term does not evaluate to a function taking 1 arguments
1>d:\data\boost\boost\boost\graph\graphviz.hpp(291): note: see reference to function template instantiation 'void boost::write_graphviz<Graph,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,boost::typed_identity_property_map<size_t>>(std::ostream &,const Graph &,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,VertexID,boost::graph::detail::no_parameter)' being compiled
1>        with
1>        [
1>            Graph=WebGraph,
1>            VertexPropertiesWriter=boost::dynamic_properties,
1>            EdgePropertiesWriter=std::string,
1>            GraphPropertiesWriter=boost::typed_identity_property_map<size_t>,
1>            VertexID=boost::typed_identity_property_map<size_t>
1>        ]
1>d:\data\boost\boost\libs\graph\example\csr-example.cpp(58): note: see reference to function template instantiation 'void boost::write_graphviz<WebGraph,boost::dynamic_properties,std::string,boost::typed_identity_property_map<size_t>>(std::ostream &,const Graph &,VertexPropertiesWriter,EdgePropertiesWriter,GraphPropertiesWriter,boost::graph::detail::no_parameter)' being compiled
1>        with
1>        [
1>            Graph=WebGraph,
1>            VertexPropertiesWriter=boost::dynamic_properties,
1>            EdgePropertiesWriter=std::string,
1>            GraphPropertiesWriter=boost::typed_identity_property_map<size_t>
1>        ]
1>d:\data\boost\boost\boost\graph\graphviz.hpp(271): error C2064: term does not evaluate to a function taking 2 arguments
1>d:\data\boost\boost\boost\graph\graphviz.hpp(277): error C2064: term does not evaluate to a function taking 2 arguments

regression: "no matching function for call to 'isomorphism_with_named_params'" since 1.71.0

My code using boost::graph::isomorphism(g1, g2) works with boost 1.70.0 but fails to compile with boost 1.71.0. I'm using clang 9.

For a reproducer, see https://godbolt.org/z/bysaYi

Where is PBGL?

Boost documentation mentions Parallel Boost Graph Library but I cannot find the code anywhere here.
Does anyone know where i can find it?

Thanks.

std::max_element requires forward iterator

std::max_element contract required forward iterator. Graph library's uses this interface in betweenness_centrality_clustering on edge iterators, which according to boost iterator library are deduced as input iterators. This fails to build with libc++, which validates the category at compile time.

The easiest solution is to handcraft the for loop:

auto it = edges_iters.first;
auto it_max = it;
while (++it != edges_iters.second) {
  if (cmp(*it_max, *it)) it_max = it;
}
// Here we assume graph is not empty and contains at least one edge.
edge_descriptor e = *it_max;

tiernan_all_cycles doesn't work out of the box with adjacency_list

there might be a bug in
boost/graph/tiernan_all_cycles.hpp
which comes from tiernan_all_cycles.hpp, line 161:
BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> ));
and then in graph_concepts.hpp on line 469/70

// This is relaxed
renumber_vertex_indices(g);

One way to make it compile is to just provide the renumber_vertex_indices the concept checks for, but since tiernan_all_cycles doesn't directly or indirectly call renumber_vertex_indices the check on line 161 in tiernan_all_cycles.hpp can also be commented out.
I don't understand why this concept check is used. Maybe it's fine and the "workaround" is the right way to deal with it?

Here's a godbolt.

min_max_paths.cpp example terminally broken

The example starts with:

#error "This example appears to be incorrect; it uses edge weights that are smaller than 0 using the comparison operator passed to Dijkstra's algorithm, which is not allowed."

std:fill call in two_bit_color_map.hpp causes warning for downstream project in Visual Studio

This line in two_bit_color_map.hpp I believe should be changed to

std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, (unsigned char)0);

If my downstream project happens to include two_bit_color_map.hpp I will have warning messages similar to the below, and it's because data is unsigned char yet it is being filled with 0, which is int.

1>mycpp.cpp
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2903): error C2220: warning treated as error - no 'object' file generated
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2917): note: see reference to function template instantiation 'void std::_Fill_unchecked1<_FwdIt,_Ty>(_FwdIt,_FwdIt,const _Ty &,std::false_type)' being compiled
1>        with
1>        [
1>            _FwdIt=unsigned char *,
1>            _Ty=int
1>        ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2925): note: see reference to function template instantiation 'void std::_Fill_unchecked<_Ty*,int>(_FwdIt,_FwdIt,const int &)' being compiled
1>        with
1>        [
1>            _Ty=unsigned char,
1>            _FwdIt=unsigned char *
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(61): note: see reference to function template instantiation 'void std::fill<T*,int>(_FwdIt,_FwdIt,const _Ty &)' being compiled
1>        with
1>        [
1>            T=unsigned char,
1>            _FwdIt=unsigned char *,
1>            _Ty=int
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(57): note: while compiling class template member function 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>::two_bit_color_map(size_t,const IndexMap &)'
1>        with
1>        [
1>            Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,
1>            IndexMap=boost::vec_adj_list_vertex_id_map<CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,unsigned __int64>
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/two_bit_color_map.hpp(100): note: see reference to function template instantiation 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>::two_bit_color_map(size_t,const IndexMap &)' being compiled
1>        with
1>        [
1>            Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,
1>            IndexMap=boost::vec_adj_list_vertex_id_map<CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>,unsigned __int64>
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/breadth_first_search.hpp(317): note: see reference to class template instantiation 'boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<Property,unsigned __int64>>' being compiled
1>        with
1>        [
1>            Property=CGAL::internal::MST_graph_vertex_properties<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<PointVectorPair>>>>
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\boost/graph/breadth_first_search.hpp(345): note: see reference to function template instantiation 'void boost::detail::bfs_dispatch<boost::param_not_found>::apply<VertexListGraph,boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property>(VertexListGraph &,unsigned __int64,const boost::bgl_named_params<boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property> &,boost::param_not_found)' being compiled
1>        with
1>        [
1>            VertexListGraph=MST_graph,
1>            _Ty=PointVectorPair
1>        ]
1>C:\dev\vcpkg\installed\x64-windows-dev\include\CGAL/mst_orient_normals.h(706): note: see reference to function template instantiation 'void boost::breadth_first_search<MST_graph,boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property>(const VertexListGraph &,unsigned __int64,const boost::bgl_named_params<boost::bfs_visitor<CGAL::internal::Propagate_normal_orientation<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,NormalMap,Kernel>>,boost::graph_visitor_t,boost::no_property> &)' being compiled
1>        with
1>        [
1>            _Ty=PointVectorPair,
1>            VertexListGraph=MST_graph
1>        ]
1>C:\Users\jasju\Desktop\test\mycpp.cpp(22): note: see reference to function template instantiation 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>> CGAL::mst_orient_normals<std::vector<_Ty,std::allocator<_Ty>>,CGAL::cgal_bgl_named_params<CGAL::Second_of_pair_property_map<PointVectorPair>,CGAL::internal_np::normal_t,CGAL::cgal_bgl_named_params<CGAL::First_of_pair_property_map<PointVectorPair>,CGAL::internal_np::point_t,boost::no_property>>>(PointRange &,unsigned int,const NamedParameters &)' being compiled
1>        with
1>        [
1>            _Ty=PointVectorPair,
1>            PointRange=std::vector<PointVectorPair,std::allocator<PointVectorPair>>,
1>            NamedParameters=CGAL::cgal_bgl_named_params<CGAL::Second_of_pair_property_map<PointVectorPair>,CGAL::internal_np::normal_t,CGAL::cgal_bgl_named_params<CGAL::First_of_pair_property_map<PointVectorPair>,CGAL::internal_np::point_t,boost::no_property>>
1>        ]
1>C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Tools\MSVC\14.16.27023\include\xutility(2903): warning C4244: '=': conversion from 'const _Ty' to '_Ty', possible loss of data
1>        with
1>        [
1>            _Ty=int
1>        ]
1>        and
1>        [
1>            _Ty=unsigned char
1>        ]
1>Done building project "Example.vcxproj" -- FAILED.

For more details on how to recreate this see here

Merge to master?

If you merge Graph to master, please let me know, as the changes include moving a header and so GraphParallel needs to be merged in tandem.

labeled_graph::remove_vertex does not remove label

When calling remove_vertex on a labeled_graph the vertex is removed but the label is not.
A dangling reference to the vertex is left behind. Accessing it causes segfaults.

Minimal example:

#include <iostream>
#include <string>

#include <boost/graph/directed_graph.hpp>
#include <boost/graph/labeled_graph.hpp>

using namespace boost;
using namespace std;

int main() {

    using namespace boost::graph_detail;
    typedef directed_graph<> Digraph;
    typedef labeled_graph<Digraph, string> Graph;
    
    Graph g;
    g.add_vertex("foo");
    
    auto v = g.vertex("foo");
    if(v != nullptr)
        cout << "foo exists\n";
    
    g.remove_vertex("foo");
    
    auto v2 = g.vertex("foo");
    if(v2 != nullptr)
        std::cout << " BUG! vertex label still exists.\n";


    return 0;
}

Isomorphism improvements

I want to improve the isomorphism documentation and discuss some improvements to the algorithm.

Null vertices can appear in the isomorphism map if single-vertex components exist. This should either be explicitly documented or the algorithm adapted to map them, too.
Vertex invariant functors actually require the AdaptableUnaryFunction concept, not UnaryFunction as stated (argument_type and result_type typedefs)
In a named parameter call to isomorphism, the second vertex invariant functor additionally requires a max() member function as an alternative if vertex_max_invariant is not passed. ~~This is undocumented.~~ I think both vertex_max_invariant and max() here are misnomers, as it is demanded that they are upper exclusive bounds on the vertex invariant values (i.e. number of different values, not maximum values). Any added documentation of max() should have this information too, though.
Both vertex_max_invariant and vertex_invariant2::max() are unnecessary: test_isomorphism immediately evaluates all invariants for all vertices of both graphs, sorts them, and lexicographically compares. The upper exclusive bound on the invariant values is then the maximum of the back of both invariant lists plus one. Yes, it is then less clear why invariants must be in a contiguous range with a reasonable upper bound - which, I assume, is purely for the efficiency and memory-compactness of the invariant multiplicity calculation here:
```
// isomorphism.hpp, line 156 onwards
std::vector<vertex1_t> V_mult;
BGL_FORALL_VERTICES_T(v, G1, Graph1)
  V_mult.push_back(v);
{
  std::vector<size_type> multiplicity(max_invariant, 0);
  BGL_FORALL_VERTICES_T(v, G1, Graph1)
    ++multiplicity.at(invariant1(v));
  sort(V_mult, compare_multiplicity(invariant1, &multiplicity[0]));
}
```
But I think that can be fixed with documentation, too. In principle, we could ignore the named parameter, even if supplied, and remove the ~~undocumented~~ requirement on vertex_invariant2, without breaking existing code.
We could even go further and remove the range requirement on vertex invariants entirely. The multiplicity of invariants can be calculated efficiently by counting in the sorted list of invariants for one graph from the previous step. If the range requirement is removed, then it will need to be replaced by an unordered_map to avoid wasting memory.
Something small: The first step of test_isomorphism, where all invariants are calculated for all vertices, does not reserve.

Thoughts?

Typo in name adjacenct_vertices()

I think it should be adjacent_vertices(), not adjacenct_vertices().

In file https://github.com/boostorg/graph/blob/develop/include/boost/graph/labeled_graph.hpp.

/** @name Adjacency Graph */
//@{
template < LABELED_GRAPH_PARAMS >
inline std::pair< typename LABELED_GRAPH::adjacency_iterator,
    typename LABELED_GRAPH::adjacency_iterator >
adjacenct_vertices(
    typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
{
    return adjacent_vertices(v, g.graph());
}
//@}

Expected outputs of subgraph is incorrect

Expected outputs of graph/example/subgraph.expected and graph/example/subgraph.cpp is incorrect.

No add_edge in labeled_graph

while trying to build the example labeled_graph.cpp I see:

1>d:\data\boost\boost\libs\graph\example\labeled_graph.cpp(61): error C2039: 'add_edge': is not a member of 'boost::labeled_graph<G,size_t,boost::defaultS>'
1>d:\data\boost\boost\libs\graph\example\labeled_graph.cpp(57): note: see declaration of 'boost::labeled_graph<G,size_t,boost::defaultS>'

[boykov-kolmogorov] mismatch between doc/figure on colors

In the lib documentation,
https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/boykov_kolmogorov_max_flow.html
the figure shows a white Source node and a black Sink node, whether it is previously written that:

the source and the sink are colored (source==black, sink==white)

This is confusing. Either change the picture or the code/doc.

IMO the source should be white and not black (i.e change the code and doc), but it would be too complicated to keep backward compatibility...

cycle_ratio_example.cpp is non-deterministic and sometime fails

We're running cycle_ratio_example.cpp in the tests, but it uses a non-deterministic random number generator which very occasionally results in the assertions failing. It's not clear if this is inevitable, or is showing up a deeper bug of some sort.

Observed failure is:

Vertices number: 1000
Edges number: 30000
Maximum cycle ratio is 9.32637
Minimum cycle ratio is -0.45058
Critical cycle:
(354,386) (386,354) 
cycle_ratio_example: libs/graph/example/cycle_ratio_example.cpp:83: int main(int, char**): Assertion `std::abs(cr.first / cr.second - min_cr) < epsilon * 2' failed.
Aborted (core dumped)

Actually looking at the result, I suspect we just need to up the error tolerance slightly - 2 epsilon might be a bit hopeful?

bucket_sorter.cpp does not compile

1>bucket_sorter.cpp
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(46): warning C4267: 'argument': conversion from 'size_t' to 'const int', possible loss of data
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(65): warning C4267: 'argument': conversion from 'size_t' to 'const int', possible loss of data
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(58): error C3861: 'get': identifier not found
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(58): note: 'get': function was not declared in the template definition context and can be found only via argument-dependent lookup in the instantiation context
1>d:\data\boost\boost\boost\pending\bucket_sorter.hpp(57): note: while compiling class template member function 'void boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>::push(const int &)'
1>        with
1>        [
1>            _Ty=size_t
1>        ]
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(46): note: see reference to function template instantiation 'void boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>::push(const int &)' being compiled
1>        with
1>        [
1>            _Ty=size_t
1>        ]
1>d:\data\boost\boost\libs\graph\example\bucket_sorter.cpp(43): note: see reference to class template instantiation 'boost::bucket_sorter<size_t,int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,ID>' being compiled
1>        with
1>        [
1>            _Ty=size_t
1>        ]

compress boost::property

(adapted from https://svn.boost.org/trac10/ticket/9826)

Looking at property_map, I noticed that boost::property is wasting space. property<tag,double> will typically have size 16 because of the no_property member. list_edge<Vertex,no_property> will also be too long for the same reason. A proper use of the empty base optimization (possibly through tuple or compressed_pair) should help with this. Partial specializations for no_property may be a simpler alternative. If you are lazy, [[no_unique_address]] would already be nice.

Graphs can grow large, and it seems quite important to avoid wasting memory.

This appears to be a regression caused by:

commit 616b9e7
Author: Jeremiah Willcock [email protected]
Date: Sat Jun 30 20:00:41 2012 +0000

Before that commit, property was implemented with derivation (which is still what the documentation shows...), and the empty base optimization avoided wasting so much space.

Large number of examples use interfaces that have been removed

The following files:

kruskal-telephone.cpp ;
loops_dfs.cpp ;
scc.cpp ;
reachable-loop-head.cpp ;
cc-internet.cpp ;
reachable-loop-tail.cpp ;
prim-telephone.cpp ;
dfs-parenthesis.cpp ;
edge_connectivity.cpp ;
edge-connectivity.cpp ;

All use GraphvizGraph and related interfaces which have been removed from the library - actually they are commented out with the note:

  // This interface has not worked for a long time

So either we need to remove these examples altogether, or better, figure out what interface they should be using.

In addition strong_components.cpp calls an old Graphviz API whose meaning has changed - as a result it chokes interpreting a filename as Graphviz data. Replacing the filename with a std::ifstream just moves the error elsewhere :(

Sample output of filtered_graph_edge_range.cpp is wrong

The sample output provided for the code in filtered_graph_edge_range.cpp is wrong.

bron_kerbosch_all_cliques unused variable

Using bron_kerbosch_all_cliques results in an unused variable warning

/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:227:41: error: unused variable 'j' [-Werror,-Wunused-variable]
        typename Container::iterator i, j;
                                        ^
/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:289:13: note: in instantiation of function template specialization 'boost::detail::extend_clique<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> >, std::__1::deque<unsigned long, std::__1::allocator<unsigned long> >, std::__1::vector<unsigned long, std::__1::allocator<unsigned long> >, octopus::MaxCliqueVisitor<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> > > >' requested here
    detail::extend_clique(g, clique, cands, nots, vis, min);
            ^
/usr/local/include/boost/graph/bron_kerbosch_all_cliques.hpp:297:3: note: in instantiation of function template specialization 'boost::bron_kerbosch_all_cliques<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> >, octopus::MaxCliqueVisitor<boost::adjacency_matrix<boost::undirectedS, unsigned long, octopus::Phred<double, void>, boost::no_property, std::__1::allocator<bool> > > >' requested here
{ bron_kerbosch_all_cliques(g, vis, 2); }

Looks like j can simply be removed?

List of non BOOST-prefixed macros

The following macros are missing a BOOST_ prefix, which is against Boost library guidelines:

./boost/graph/minimum_degree_ordering.hpp:#ifndef MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/minimum_degree_ordering.hpp:#define MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/minimum_degree_ordering.hpp:#endif // MINIMUM_DEGREE_ORDERING_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#ifndef EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#define EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/edmonds_karp_max_flow.hpp:#endif // EDMONDS_KARP_MAX_FLOW_HPP
./boost/graph/adj_list_serialize.hpp:#ifndef ADJ_LIST_SERIALIZE_HPP
./boost/graph/adj_list_serialize.hpp:#define ADJ_LIST_SERIALIZE_HPP
./boost/graph/adj_list_serialize.hpp:#endif // ADJ_LIST_SERIALIZE_HPP

examples crash when run

The following two examples crash at runtime:

astar_maze.cpp
kevin-bacon2.cpp

Sorry but I don't see what the issue is off hand.

Prevent switch fallthrough when assertions are not fatal

When BOOST_DISABLE_ASSERTS or BOOST_ENABLE_ASSERT_HANDLER is defined, the nested switch on str[1] can continue past the assert and will fallthrough to the default case below.

This can cause warnings with static analysis tools, and if a user-defined boost::assertion_failed function that doesn't terminate the process is being used, that function will be called twice because the first assertion falls through to the second.

Inserting a break avoids static analysis warnings and avoids potentially calling the assertion handler twice.

Different behavior labeled_graph::add_vertex()/labeled_graph::insert_vertex() with label as string and as integer.

If I try to use a string as a label, the result is expected. If an integer, then the result is different than expected.

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>

int main()
{
		using namespace std;
		cout << "add_vertex():\n";
		{
			using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, string>;
			LabeledGraph g;
			const auto vd1 = g.add_vertex("123");
			const auto vd2 = g.add_vertex("123");
			cout << " string:\n";
			cout << "  " << boolalpha << (vd1 == vd2) << endl;
		}
		{
			using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, size_t>;
			LabeledGraph g;
			const auto vd1 = g.add_vertex(123);
			const auto vd2 = g.add_vertex(123);
			cout << " size_t:\n";
			cout << "  " << boolalpha << (vd1 == vd2) << endl;
		}
		cout << "insert_vertex():\n";
		{
			using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, string>;
			LabeledGraph g;
			cout << " string:\n";
			cout << "  " << boolalpha << g.insert_vertex("123").second << endl;
			cout << "  " << boolalpha << g.insert_vertex("123").second << endl;
		}
		{
			using LabeledGraph = boost::labeled_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>, size_t>;
			LabeledGraph g;
			cout << " size_t:\n";
			cout << "  " << boolalpha << g.insert_vertex(123).second << endl;
			cout << "  " << boolalpha << g.insert_vertex(123).second << endl;
		}
}

If I compile this code using the following command line, I get this result.
g++ prog.cc -Wall -Wextra -I/opt/wandbox/boost-1.71.0/gcc-head/include -std=gnu++2a

add_vertex():
 string:
  true
 size_t:
  false
insert_vertex():
 string:
  true
  false
 size_t:
  true
  true

Tree class in BGL

Is there a class for trees in BGL?

maximum_weighted_matching() segfaults with constant weights

Some graphs cause maximum_weighted_matching() to segfault due to a stack overflow when unit weights are used.

Please see minimal example linked below which is a simple modification of the standard example from the library.

https://gist.github.com/count0/551867e10973d4b2dc047b8528908281

Protect <> in examples

https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/incremental_components.html
The first example, from examples/incremental_components.cpp, was copy-pasted raw, without protecting special characters from HTML, so in particular all templates are invisible.

reverse_graph.hpp breaks ADL get

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

namespace detail {                                                                                                                                                            
  template <class E>                                                                                                                                                          
  struct underlying_edge_desc_map_type {                                                                                                                                      
    E operator[](const reverse_graph_edge_descriptor<E>& k) const {                                                                                                           
      return k.underlying_descx;                                                                                                                                              
    }                                                                                                                                                                         
  };                                                                                                                                                                          
                                                                                                                                                                              
  template <class E>                                                                                                                                                          
  E                                                                                                                                                                           
  get(underlying_edge_desc_map_type<E> m,                                                                                                                                     
      const reverse_graph_edge_descriptor<E>& 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<comp_type>::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<comp_type>::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

Move headers out of boost/pending

Headers were likely never supposed to live in boost/pending for a long time. At this point boost/pending should be retired and the headers moved into their rightful and normal place. Here are the pending headers for this repository:

graph/include/boost/pending/bucket_sorter.hpp
graph/include/boost/pending/container_traits.hpp
graph/include/boost/pending/detail/property.hpp
graph/include/boost/pending/fenced_priority_queue.hpp
graph/include/boost/pending/fibonacci_heap.hpp
graph/include/boost/pending/indirect_cmp.hpp
graph/include/boost/pending/is_heap.hpp
graph/include/boost/pending/mutable_heap.hpp
graph/include/boost/pending/mutable_queue.hpp
graph/include/boost/pending/property.hpp
graph/include/boost/pending/queue.hpp
graph/include/boost/pending/relaxed_heap.hpp
graph/include/boost/pending/stringtok.hpp