What is required for a custom BGL graph to work with topological sort?

Question

I've created a custom BGL graph model, like in this answer: What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?.

It adapts a custom data structure for use with some Boost.Graph algorithms.

The linked answer was enough to get depth-first search working (Coliru) but I run into a problem when using boost::topological_sort:

std::list<V> rev_topo;
boost::topological_sort(g, back_inserter(rev_topo));

Gives: Coliru

In file included from /usr/include/boost/iterator/iterator_categories.hpp:15,
                 from /usr/include/boost/unordered/detail/implementation.hpp:18,
                 from /usr/include/boost/unordered/detail/set.hpp:6,
                 from /usr/include/boost/unordered/unordered_set.hpp:20,
                 from /usr/include/boost/unordered_set.hpp:17,
                 from /usr/include/boost/graph/adjacency_list.hpp:21,
                 from /home/sehe/Projects/stackoverflow/test.cpp:3:
/usr/include/boost/mpl/eval_if.hpp: In instantiation of ‘struct boost::mpl::eval_if<boost::detail::has_vertex_property_type<Glue::MyGraph, mpl_::bool_<false> >, boost::detail::get_vertex_property_type<Glue::MyGraph>, boost::no_property>’:
/usr/include/boost/graph/graph_traits.hpp:276:12:   required from ‘struct boost::vertex_property_type<Glue::MyGraph>’
/usr/include/boost/graph/properties.hpp:201:12:   required from ‘struct boost::detail::vertex_property_map<Glue::MyGraph, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:212:10:   required from ‘struct boost::property_map<Glue::MyGraph, boost::vertex_index_t, void>’
/usr/include/boost/graph/named_function_params.hpp:415:69:   required from ‘struct boost::detail::override_const_property_t<int, boost::vertex_index_t, Glue::MyGraph, false>’
/usr/include/boost/graph/named_function_params.hpp:571:31:   required from ‘struct boost::detail::map_maker_helper<false, Glue::MyGraph, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >, boost::default_color_type, int>’
/usr/include/boost/graph/named_function_params.hpp:604:41:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
/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::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >; Graph = Glue::MyGraph]’
/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 = Glue::MyGraph; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const 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 = Glue::MyGraph; P = boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<int, boost::buffer_param_t>; 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 = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >; P = int; T = boost::buffer_param_t; R = boost::no_property]’
/usr/include/boost/graph/topological_sort.hpp:71:21:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator) [with VertexListGraph = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >]’
/home/sehe/Projects/stackoverflow/test.cpp:139:55:   required from here
/usr/include/boost/mpl/eval_if.hpp:38:31: error: no type named ‘type’ in ‘boost::mpl::eval_if<boost::detail::has_vertex_property_type<Glue::MyGraph, mpl_::bool_<false> >, boost::detail::get_vertex_property_type<Glue::MyGraph>, boost::no_property>::f_’ {aka ‘struct boost::no_property’}
   38 |     typedef typename f_::type type;
      |                               ^~~~
In file included from /usr/include/boost/graph/breadth_first_search.hpp:23,
                 from /home/sehe/Projects/stackoverflow/test.cpp:4:
/usr/include/boost/graph/named_function_params.hpp: In instantiation of ‘struct boost::detail::override_const_property_t<int, boost::vertex_index_t, Glue::MyGraph, false>’:
/usr/include/boost/graph/named_function_params.hpp:571:31:   required from ‘struct boost::detail::map_maker_helper<false, Glue::MyGraph, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >, boost::default_color_type, int>’
/usr/include/boost/graph/named_function_params.hpp:604:41:   required from ‘struct boost::detail::map_maker<Glue::MyGraph, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >, boost::graph::keywords::tag::color_map, boost::default_color_type>’
/usr/include/boost/graph/named_function_params.hpp:620:7:   required by substitution of ‘template<class Graph, class ArgPack> typename boost::detail::map_maker<Graph, ArgPack, boost::graph::keywords::tag::color_map, boost::default_color_type>::map_type boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>::operator()<Graph, ArgPack>(const Graph&, const ArgPack&) const [with Graph = Glue::MyGraph; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >]’
/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::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >; Graph = Glue::MyGraph]’
/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 = Glue::MyGraph; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const 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 = Glue::MyGraph; P = boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<int, boost::buffer_param_t>; 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 = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >; P = int; T = boost::buffer_param_t; R = boost::no_property]’
/usr/include/boost/graph/topological_sort.hpp:71:21:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator) [with VertexListGraph = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >]’
/home/sehe/Projects/stackoverflow/test.cpp:139:55:   required from here
/usr/include/boost/graph/named_function_params.hpp:415:69: error: no type named ‘const_type’ in ‘struct boost::property_map<Glue::MyGraph, boost::vertex_index_t, void>’
  415 |       typedef typename boost::property_map<Graph, Prop>::const_type result_type;
      |                                                                     ^~~~~~~~~~~
In file included from /home/sehe/Projects/stackoverflow/test.cpp:5:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of ‘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::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >; Graph = Glue::MyGraph]’:
/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 = Glue::MyGraph; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const 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 = Glue::MyGraph; P = boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > >; T = boost::graph_visitor_t; R = boost::bgl_named_params<int, boost::buffer_param_t>; 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 = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >; P = int; T = boost::buffer_param_t; R = boost::no_property]’
/usr/include/boost/graph/topological_sort.hpp:71:21:   required from ‘void boost::topological_sort(VertexListGraph&, OutputIterator) [with VertexListGraph = Glue::MyGraph; OutputIterator = std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> >]’
/home/sehe/Projects/stackoverflow/test.cpp:139:55:   required from here
/usr/include/boost/graph/depth_first_search.hpp:337:80: error: no match for call to ‘(const boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>) (const Glue::MyGraph&, const boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const boost::topo_sort_visitor<std::back_insert_iterator<std::__cxx11::list<YourLibrary::myVertex*> > > >, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::buffer, const int>, boost::parameter::aux::empty_arg_list> >&)’
  337 |                                     boost::detail::make_color_map_from_arg_pack(g, arg_pack),
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/boost/graph/breadth_first_search.hpp:23,
                 from /home/sehe/Projects/stackoverflow/test.cpp:4:
/usr/include/boost/graph/named_function_params.hpp:620:7: note: candidate: ‘template<class Graph, class ArgPack> 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 = Graph; ArgPack = ArgPack; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type]’
  620 |       operator()(const Graph& g, const ArgPack& ap) const {
      |       ^~~~~~~~
/usr/include/boost/graph/named_function_params.hpp:620:7: note:   substitution of deduced template arguments resulted in errors seen above

What additional requirements must the "glue" layer meet in order to use boost::topological_sort? Internally, topological sort uses depth_first_search, but it appears it may require a vertex index map.

Foresee

Answer 1

As you correctly surmised, the error novel is telling you that there is no index map. That is required for the default color map:

UTIL/OUT: color_map(ColorMap color) This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.

Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.

Indeed, the index map isn't even required if you fulfill the color map requirement yourself: Live On Coliru

std::map<V, boost::default_color_type> vertex_colors;
boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::color_map(boost::make_assoc_property_map(vertex_colors))
    );

More Musings: Teaching BGL Vertex Indices

Now, many algorithms require an index-map, and many get much more convenient, just like above, when your graph model does have a vertex index map.

A vertex index should map the vertex descriptors to integral numbers [0, n) (where n is the total number of vertices). In the case of the example graph model, a trivial index would be the element index into the vector of vertices.

So, you could also express the index map as:

auto idmap = boost::make_function_property_map<V>([&](V v) {
    auto match = std::find(begin(vv), end(vv), v);
    assert(match != end(vv));
    return std::distance(begin(vv), match);
});

Now you can call the algorithm relying on their default color map: Coliru

boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::vertex_index_map(idmap)
    );

That's not a big win, since now we still need optional named params, and even need the idmap contraption which seems more complicated than the vertex_colors map before?

Simplifying / Integrating Into The Model

We can make it better by teaching the BGL how to get our property maps from the Glue::MyGraph model.

Property Maps will be found by BGL using

• the type trait boost::property_map<Graph, Tag> which tells BGL about the type of the propertymap.

  Here, Tag would be e.g. boost::vertex_index_t for the vertex index map.

• the accessor functions

  • get(tag, graph)

    Returning a copy of the property-map of that type

  • get(tag_type, graph, descriptor)

  For writable property maps there's also the corresponding put accessor, but I'll leave it for brevity. See the documentation for Boost PropertyMap Library for more information on the features of that library.

Let's do that. We start by moving the idmap generator to our MyGraph model, so we don't need to know about the implementation details anymore:

    auto idmap() const {
        using V = YourLibrary::myVertex const*;
        return boost::make_function_property_map<V>([this](V v) {
            auto match = std::find(begin(_vertices), end(_vertices), v);
            assert(match != end(_vertices));
            return std::distance(begin(_vertices), match);
        });
    }

That means you could simply call g.idmap() to get the same propery map. However, we wanted the library to "magically" know. So, first we specialize the trait:

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

It's a delight of c++14 that we can deduce all these types. Only remaining step: the accessor functions, which are again ADL-enabled customization points, so we put them into our Glue namespace:

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

Proof Of The Pudding

Now, since the library "just understands" vertex indices for our model, we can enjoy the algorithms that need one without any additional help:

std::list<V> order;
boost::topological_sort(g, back_inserter(order));

And we can exercise the other accessor for fun:

std::cout << "Topo order:\n";
order.reverse(); // output is reversed
for (auto v : order)
    std::cout << "Vertex index:" << get(boost::vertex_index, g, v)
              << " name:" << v->name << "\n";

In your own (non-generic, library) code you would probably write

auto idmap = g.idmap(); // or
auto idmap = get(boost::vertex_index, g, v);

And use idmap[v] to get values instead.

Live Demo

Live On Coliru

#include <algorithm>
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>
#include <utility>

namespace YourLibrary {
    struct myVertex {
        myVertex(std::string n) : name(std::move(n)) {}
        std::string name;
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        [[nodiscard]] myVertex* source() const { return _s; }
        [[nodiscard]] myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}  // namespace YourLibrary

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        auto idmap() const {
            using V = YourLibrary::myVertex const*;
            return boost::make_function_property_map<V>([this](V v) {
                auto match = std::find(begin(_vertices), end(_vertices), v);
                assert(match != end(_vertices));
                return std::distance(begin(_vertices), match);
            });
        }

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { 
            assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));
        }
    };
}  // namespace Glue

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}  // namespace boost

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>("a");
    auto b = std::make_unique<YourLibrary::myVertex>("b");
    auto c = std::make_unique<YourLibrary::myVertex>("c");
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto cb = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{c.get(), b.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), cb.get() };

    // this is the glue required to fulfill the BGL concepts:
    using boost::make_iterator_range;

    Glue::MyGraph g(vv, ee);
    for (auto v : make_iterator_range(vertices(g)))
        for (auto e : make_iterator_range(out_edges(v, g)))
            std::cout << "out edge ("
                      << source(e, g)->name << " -> "
                      << target(e, g)->name << ")\n";

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
        boost::visitor(boost::default_bfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data)));

    boost::depth_first_search(g, boost::default_dfs_visitor {},
        boost::make_assoc_property_map(color_data), start_vertex);

    // named params
    boost::depth_first_search(g,
        boost::visitor(boost::default_dfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data))
            .root_vertex(start_vertex));

    std::list<V> order;
    boost::topological_sort(g, back_inserter(order));

    std::cout << "Topo order:\n";
    order.reverse(); // output is reversed

    auto idmap = g.idmap();
    for (auto v : order)
        std::cout << "Vertex index:" << idmap[v] << " name:" << v->name << "\n";
}

Printing

out edge (a -> b)
out edge (c -> b)
Topo order:
Vertex index:2 name:c
Vertex index:0 name:a
Vertex index:1 name:b

Popliteal

I just realized I had completely forgotten about the edge ordering invariant in this graph model, so I added a constructor check in the final listing, just to avoid nasty surprises. – Popliteal