自定义 BGL 图需要什么才能使用拓扑排序？
What is required for a custom BGL graph to work with topological sort?
我已经创建了一个自定义的 BGL 图模型，就像这个答案一样：。
它采用自定义数据结构以用于某些 Boost.Graph 算法。
链接的答案足以让深度优先搜索工作（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
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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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，但它似乎可能需要顶点索引映射。
如你所料，错误小说告诉你没有索引图。即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.
事实上，如果您自己满足色图要求，甚至不需要索引图：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 顶点索引
现在，许多算法都需要一个索引图，并且很多算法变得更加方便，就像上面一样，当您的图模型确实有一个顶点索引图时。
顶点索引应将顶点描述符映射到整数 [0, n)（其中 n 是顶点总数）。在示例图模型的情况下，一个简单的索引将是顶点向量中的元素索引。
因此，您也可以将索引图表示为：
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
boost::topological_sort(
g,
back_inserter(rev_topo),
boost::vertex_index_map(idmap)
);
这不是一个很大的胜利，因为现在我们仍然需要可选的命名参数，甚至需要 idmap 看起来比之前的 vertex_colors 映射更复杂的装置？
简化/集成到模型中
我们可以通过教 BGL 如何从 Glue::MyGraph 模型中获取我们的 属性 地图来使其变得更好。
属性 BGL 将使用
找到地图
类型特征 boost::property_map<Graph, Tag> 告诉 BGL 属性map 的类型。
在这里，Tag 例如boost::vertex_index_t 用于顶点索引图。
存取函数
get(tag, graph)
正在返回该类型的 属性-map 的副本
get(tag_type, graph, descriptor)
对于可写 属性 映射，还有相应的 put 访问器，但为了简洁起见，我将保留它。有关该库功能的更多信息，请参阅 Boost PropertyMap Library 的文档。
让我们开始吧。我们首先将 idmap 生成器移动到我们的 MyGraph 模型，因此我们不再需要了解实现细节：
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() 即可获得相同的 属性 地图。但是，我们希望图书馆“神奇地”知道。所以，首先我们专门化特征：
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 命名空间中：
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
布丁的证明
现在，由于库“只理解”我们模型的顶点索引，我们可以在没有任何额外帮助的情况下享受需要一个的算法：
std::list<V> order;
boost::topological_sort(g, back_inserter(order));
我们可以练习另一个访问器来获得乐趣：
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";
在您自己的（非通用、库）代码中，您可能会编写
auto idmap = g.idmap(); // or
auto idmap = get(boost::vertex_index, g, v);
并使用 idmap[v] 来获取值。
现场演示
#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 图模型，就像这个答案一样：
它采用自定义数据结构以用于某些 Boost.Graph 算法。
链接的答案足以让深度优先搜索工作（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
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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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/Whosebug/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，但它似乎可能需要顶点索引映射。
如你所料，错误小说告诉你没有索引图。即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 typeColorMapmust 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 modelColorValue.Default: an
iterator_property_mapcreated from astd::vectorofdefault_color_typeof sizenum_vertices(g)and using thei_mapfor the index map.
事实上，如果您自己满足色图要求，甚至不需要索引图：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 顶点索引
现在，许多算法都需要一个索引图，并且很多算法变得更加方便，就像上面一样，当您的图模型确实有一个顶点索引图时。
顶点索引应将顶点描述符映射到整数 [0, n)（其中 n 是顶点总数）。在示例图模型的情况下，一个简单的索引将是顶点向量中的元素索引。
因此，您也可以将索引图表示为：
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
boost::topological_sort(
g,
back_inserter(rev_topo),
boost::vertex_index_map(idmap)
);
这不是一个很大的胜利，因为现在我们仍然需要可选的命名参数，甚至需要 idmap 看起来比之前的 vertex_colors 映射更复杂的装置？
简化/集成到模型中
我们可以通过教 BGL 如何从 Glue::MyGraph 模型中获取我们的 属性 地图来使其变得更好。
属性 BGL 将使用
找到地图类型特征
boost::property_map<Graph, Tag>告诉 BGL 属性map 的类型。在这里，
Tag例如boost::vertex_index_t用于顶点索引图。存取函数
get(tag, graph)正在返回该类型的 属性-map 的副本
get(tag_type, graph, descriptor)
对于可写 属性 映射，还有相应的
put访问器，但为了简洁起见，我将保留它。有关该库功能的更多信息，请参阅 Boost PropertyMap Library 的文档。
让我们开始吧。我们首先将 idmap 生成器移动到我们的 MyGraph 模型，因此我们不再需要了解实现细节：
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() 即可获得相同的 属性 地图。但是，我们希望图书馆“神奇地”知道。所以，首先我们专门化特征：
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 命名空间中：
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
布丁的证明
现在，由于库“只理解”我们模型的顶点索引，我们可以在没有任何额外帮助的情况下享受需要一个的算法：
std::list<V> order;
boost::topological_sort(g, back_inserter(order));
我们可以练习另一个访问器来获得乐趣：
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";
在您自己的（非通用、库）代码中，您可能会编写
auto idmap = g.idmap(); // or
auto idmap = get(boost::vertex_index, g, v);
并使用 idmap[v] 来获取值。
现场演示
#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