自定义BGL图与拓扑排序一起工作需要什么? [英] What is required for a custom BGL graph to work with topological sort?

问题描述

我已经创建了一个自定义BGL图形模型，如下所示:

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 *>)?.

它调整了自定义数据结构，以用于某些Boost.Graph算法.

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

链接的答案足以使深度优先搜索有效( Coliru )，但使用

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));

赠予: Coliru

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

胶水"必须满足哪些附加要求.层见面以便使用 boost :: topological_sort ?在内部，拓扑排序使用 depth_first_search ，但是看来它可能需要顶点索引图.

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.

推荐答案

您正确地猜到了，错误小说告诉您没有索引映射.那就是

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颜色)该算法用于通过图表跟踪其进度.类型 ColorMap 必须是读/写属性映射的模型，并且其键类型必须是图形的顶点描述符类型和颜色图的值类型必须为 ColorValue 建模.

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.

默认 :从以下位置创建的 iterator_property_map 大小为 num_vertices(g)和的 default_color_type 的 std :: vector 索引图的 i_map .

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))
    );

更多缪斯:教导BGL顶点指数

现在，当您的图形模型具有顶点索引图时，许多算法都需要索引映射，就像上面一样，许多算法都变得更加方便.

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.

顶点索引应将顶点描述符映射到整数 [0，n)(其中 n 是顶点总数).在示例图模型的情况下，平凡索引将是顶点向量中的元素索引.

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);
});

现在，您可以根据其默认颜色映射来调用算法: Coliru

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)
    );

这不是一个大的胜利，因为现在我们仍然需要可选的命名参数，甚至还需要 idmap 的配置，这似乎比以前的 vertex_colors 映射要复杂得多?

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?

我们可以通过教BGL如何从Glue :: MyGraph模型获取属性映射来使它更好.

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

物业地图将由BGL使用

Property Maps will be found by BGL using

• 类型特征 boost :: property_map< Graph，Tag> 告诉BGL属性映射的类型.

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

在这里， Tag 例如顶点索引图的 boost :: vertex_index_t .

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

访问器功能

• 获取(标签，图形)

返回该类型的属性映射的副本

Returning a copy of the property-map of that type

get(标签类型，图形，描述符)

对于可写属性映射，还有相应的 put 访问器，但为了简洁起见，我将其保留.请参阅 Boost PropertyMap库的文档.有关该库功能的更多信息.

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.

让我们这样做.我们首先将 idmap 生成器移动到我们的 MyGraph 模型中，所以我们不再需要了解实现细节了:

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);
        });
    }

这意味着您只需调用 g.idmap()即可获得相同的属性图.但是，我们希望该库神奇地"存储在数据库中.知道.因此，首先我们要研究特质:

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());
    };
}

我们可以推断出所有这些类型，这是C ++ 14的一种乐趣.剩下的唯一步骤:访问器函数，它们又是启用ADL的自定义点，因此我们将它们放入了我们的Glue命名空间:

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);

并使用 idmap [v] 来获取值.

在Coliru上直播

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";
}

打印

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

这篇关于自定义BGL图与拓扑排序一起工作需要什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！