提升图形库：in_edges 的确定性迭代顺序？
boost graph library: deterministic order of iteration of in_edges?
TL;DR: 我非常想要 in_edges 的迭代顺序
在我的图表上（adjacency_list 和 setS 的 edge_list）是
确定性的，但据我所知，迭代的顺序是
由只是指针的比较运算符确定
比较---因此迭代顺序由变幻莫测的
malloc。求助！
为了具体起见，我的图表和相关类型是：
struct VertexCargo { int Id; ... };
typedef adjacency_list<setS, vecS, bidirectionalS, property<vertex_info_t, VertexCargo> > Graph;
typedef graph_traits<Graph>::edge_descriptor ED;
typedef graph_traits<Graph>::vertex_descriptor VD;
我的逻辑，以防有人在任何地方发现谬论：
in_edges迭代直接由边列表容器的迭代决定
setS 的边列表意味着底层容器 std::set<edge_desc_impl>
注意：这个假设是不正确的；它实际上是一个 std::set<StoredEdge，它提供了一个在边缘目标上进行比较的比较器。
std::set<edge_desc_impl> 迭代顺序由
operator<(edge_desc_impl, edge_desc_impl)
operator<(edge_desc_impl, edge_desc_impl) 最终 只是一个
指针比较;
运算符<在boost/graph/detail/edge.hpp中定义（提升1.58）：
30 template <typename Directed, typename Vertex>
31 class edge_desc_impl : public edge_base<Directed,Vertex> {
...
35 typedef void property_type;
36
37 inline edge_desc_impl() : m_eproperty(0) {}
38
39 inline edge_desc_impl(Vertex s, Vertex d, const property_type* eplug)
40 : Base(s,d), m_eproperty(const_cast<property_type*>(eplug)) { }
41
42 property_type* get_property() { return m_eproperty; }
43 const property_type* get_property() const { return m_eproperty; }
44
45 // protected:
46 property_type* m_eproperty;
47 };
48
...
63
64 // Order edges according to the address of their property object
65 template <class D, class V>
66 inline bool
67 operator<(const detail::edge_desc_impl<D,V>& a,
68 const detail::edge_desc_impl<D,V>& b)
69 {
70 return a.get_property() < b.get_property();
71 }
如果有一种方法可以引起比较，我真的很喜欢
（以及迭代顺序）基于某些确定性的东西
（即 not 由 malalloc 确定的指针地址；例如
我写的自定义运算符查看 VertexCargo::Id 的来源和
边缘的目标），但看起来这在这里可能行不通
因为void*演员。
从上面的代码看来也可以 (?) 注入一个 property
给出所需的顺序。但这让我觉得很骇人听闻。
谁有智慧分享一下？
答案注释
@sehe的回答是正确答案---底层容器其实是一个std::set<StoredEdge>，它定义了一个operator<，在边缘目标上进行比较；这个 是 当顶点容器选择器是 vecS 但一般情况下不是 时是确定的（因为其他情况下的顶点标识符基本上是指针来自 malloc).
正如我所料（根据我的回忆）边缘列表（都是 in/out）已经按它们的目标排序，因此 它们是确定性的。
当 VertexContainer 选择器为 vecS 时，这一点尤其明确，因为在那里，vertex_descriptor 是一个简单的整数类型，无论如何都兼作 vertex_index_t 属性 .
掉进兔子洞
因为我不是 Boost Graph 开发人员，所以我不知道
BGL 类型的架构，如 adjacency_list，我天真地开始了我们的
顶级入口点：
template <class Config>
inline std::pair<typename Config::in_edge_iterator,
typename Config::in_edge_iterator>
in_edges(typename Config::vertex_descriptor u,
const bidirectional_graph_helper<Config>& g_)
{
typedef typename Config::graph_type graph_type;
const graph_type& cg = static_cast<const graph_type&>(g_);
graph_type& g = const_cast<graph_type&>(cg);
typedef typename Config::in_edge_iterator in_edge_iterator;
return
std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
in_edge_iterator(in_edge_list(g, u).end(), u));
}
实例化为：
std::pair<typename Config::in_edge_iterator, typename Config::in_edge_iterator>
boost::in_edges(typename Config::vertex_descriptor, const boost::bidirectional_graph_helper<C> &)
with
Config = boost::detail::adj_list_gen<
boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexCargo>, boost::vecS, boost::setS,
boost::bidirectionalS, VertexCargo, boost::no_property, boost::no_property, boost::listS>::config;
typename Config::in_edge_iterator = boost::detail::in_edge_iter<
std::_Rb_tree_const_iterator<boost::detail::stored_edge_iter<
long unsigned int, std::_List_iterator<boost::list_edge<long unsigned int, boost::no_property> >,
boost::no_property> >,
long unsigned int, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>, long int>;
typename Config::vertex_descriptor = long unsigned int
正在填写
using Config = boost::detail::adj_list_gen<
boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexCargo>, boost::vecS, boost::setS,
boost::bidirectionalS, VertexCargo, boost::no_property, boost::no_property, boost::listS>::config;
指向我们在 adj_list_gen<...>::config 处的实例化，迭代器被声明为
typedef in_edge_iter<
InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
> in_edge_iterator;
// leading to
typedef OutEdgeIter InEdgeIter;
// leading to
typedef typename OutEdgeList::iterator OutEdgeIter;
// leading to
typedef typename container_gen<OutEdgeListS, StoredEdge>::type OutEdgeList;
并且因为容器选择器是 setS，所以它将是 StoredEdge 的 std::set，即
typedef typename mpl::if_<on_edge_storage,
stored_edge_property<vertex_descriptor, EdgeProperty>,
typename mpl::if_<is_edge_ra,
stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
>::type
>::type StoredEdge;
计算结果为
boost::detail::stored_edge_iter<
long unsigned int,
std::_List_iterator<boost::list_edge<long unsigned int, boost::no_property> >,
boost::no_property>
现在这当然指向 EdgeList 的实现...
坚持住！踩刹车
但最重要的是强加的总弱排序 - 所以我们不去
进一步深入那个兔子洞，而是将我们的注意力转移到
stored_edge_iter<>::operator< 或类似的。
inline bool operator<(const stored_edge& x) const
{ return m_target < x.get_target(); }
啊哈！排序 已经确定地定义 。您可以使用例如 直接 访问它
for (auto v : make_iterator_range(vertices(g))) {
std::cout << v << " --> ";
auto const& iel = boost::in_edge_list(g, v);
for (auto e : iel) std::cout << e.get_target() << " ";
std::cout << "\n";
}
但你不需要。使用通用图形访问器几乎是一样的：
std::cout << v << " --> ";
for (auto e : make_iterator_range(in_edges(v, g))) std::cout << source(e, g) << " ";
std::cout << "\n";
并且您可以验证集合是否按预期正确排序，例如使用
assert(boost::is_sorted(make_iterator_range(in_edges(v,g)) | transformed(sourcer(g))));
assert(boost::is_sorted(make_iterator_range(out_edges(v,g)) | transformed(targeter(g))));
演示版
这是一个完整的演示，包括上述所有内容并在大型随机生成图上断言所有预期顺序：
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <random>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
using boost::adaptors::transformed;
using namespace boost;
struct VertexCargo { int Id = rand() % 1024; };
typedef adjacency_list<setS, vecS, bidirectionalS, VertexCargo> Graph;
typedef graph_traits<Graph>::edge_descriptor ED;
typedef graph_traits<Graph>::vertex_descriptor VD;
struct sourcer {
using result_type = VD;
Graph const* g;
sourcer(Graph const& g) : g(&g) {}
VD operator()(ED e) const { return boost::source(e, *g); }
};
struct targeter {
using result_type = VD;
Graph const* g;
targeter(Graph const& g) : g(&g) {}
VD operator()(ED e) const { return boost::target(e, *g); }
};
int main() {
std::mt19937 rng { std::random_device{}() };
Graph g;
generate_random_graph(g, 1ul<<10, 1ul<<13, rng);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << v << " --> ";
//auto const& iel = boost::in_edge_list(g, v);
//for (auto e : iel) std::cout << e.get_target() << " ";
for (auto e : make_iterator_range(in_edges(v, g))) std::cout << source(e, g) << " ";
//for (auto e : make_iterator_range(out_edges(v, g))) std::cout << target(e, g) << " ";
std::cout << "\n";
assert(boost::is_sorted(make_iterator_range(in_edges(v,g)) | transformed(sourcer(g))));
assert(boost::is_sorted(make_iterator_range(out_edges(v,g)) | transformed(targeter(g))));
}
}
TL;DR: 我非常想要 in_edges 的迭代顺序
在我的图表上（adjacency_list 和 setS 的 edge_list）是
确定性的，但据我所知，迭代的顺序是
由只是指针的比较运算符确定
比较---因此迭代顺序由变幻莫测的
malloc。求助！
为了具体起见，我的图表和相关类型是：
struct VertexCargo { int Id; ... };
typedef adjacency_list<setS, vecS, bidirectionalS, property<vertex_info_t, VertexCargo> > Graph;
typedef graph_traits<Graph>::edge_descriptor ED;
typedef graph_traits<Graph>::vertex_descriptor VD;
我的逻辑，以防有人在任何地方发现谬论：
in_edges迭代直接由边列表容器的迭代决定setS的边列表意味着底层容器std::set<edge_desc_impl>注意：这个假设是不正确的；它实际上是一个std::set<StoredEdge，它提供了一个在边缘目标上进行比较的比较器。std::set<edge_desc_impl>迭代顺序由operator<(edge_desc_impl, edge_desc_impl)operator<(edge_desc_impl, edge_desc_impl)最终 只是一个 指针比较;
运算符<在boost/graph/detail/edge.hpp中定义（提升1.58）：
30 template <typename Directed, typename Vertex>
31 class edge_desc_impl : public edge_base<Directed,Vertex> {
...
35 typedef void property_type;
36
37 inline edge_desc_impl() : m_eproperty(0) {}
38
39 inline edge_desc_impl(Vertex s, Vertex d, const property_type* eplug)
40 : Base(s,d), m_eproperty(const_cast<property_type*>(eplug)) { }
41
42 property_type* get_property() { return m_eproperty; }
43 const property_type* get_property() const { return m_eproperty; }
44
45 // protected:
46 property_type* m_eproperty;
47 };
48
...
63
64 // Order edges according to the address of their property object
65 template <class D, class V>
66 inline bool
67 operator<(const detail::edge_desc_impl<D,V>& a,
68 const detail::edge_desc_impl<D,V>& b)
69 {
70 return a.get_property() < b.get_property();
71 }
如果有一种方法可以引起比较，我真的很喜欢
（以及迭代顺序）基于某些确定性的东西
（即 not 由 malalloc 确定的指针地址；例如
我写的自定义运算符查看 VertexCargo::Id 的来源和
边缘的目标），但看起来这在这里可能行不通
因为void*演员。
从上面的代码看来也可以 (?) 注入一个 property
给出所需的顺序。但这让我觉得很骇人听闻。
谁有智慧分享一下？
答案注释
@sehe的回答是正确答案---底层容器其实是一个std::set<StoredEdge>，它定义了一个operator<，在边缘目标上进行比较；这个 是 当顶点容器选择器是 vecS 但一般情况下不是 时是确定的（因为其他情况下的顶点标识符基本上是指针来自 malloc).
正如我所料（根据我的回忆）边缘列表（都是 in/out）已经按它们的目标排序，因此 它们是确定性的。
当 VertexContainer 选择器为 vecS 时，这一点尤其明确，因为在那里，vertex_descriptor 是一个简单的整数类型，无论如何都兼作 vertex_index_t 属性 .
掉进兔子洞
因为我不是 Boost Graph 开发人员，所以我不知道
BGL 类型的架构，如 adjacency_list，我天真地开始了我们的
顶级入口点：
template <class Config>
inline std::pair<typename Config::in_edge_iterator,
typename Config::in_edge_iterator>
in_edges(typename Config::vertex_descriptor u,
const bidirectional_graph_helper<Config>& g_)
{
typedef typename Config::graph_type graph_type;
const graph_type& cg = static_cast<const graph_type&>(g_);
graph_type& g = const_cast<graph_type&>(cg);
typedef typename Config::in_edge_iterator in_edge_iterator;
return
std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
in_edge_iterator(in_edge_list(g, u).end(), u));
}
实例化为：
std::pair<typename Config::in_edge_iterator, typename Config::in_edge_iterator>
boost::in_edges(typename Config::vertex_descriptor, const boost::bidirectional_graph_helper<C> &)
with
Config = boost::detail::adj_list_gen< boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexCargo>, boost::vecS, boost::setS, boost::bidirectionalS, VertexCargo, boost::no_property, boost::no_property, boost::listS>::config; typename Config::in_edge_iterator = boost::detail::in_edge_iter< std::_Rb_tree_const_iterator<boost::detail::stored_edge_iter< long unsigned int, std::_List_iterator<boost::list_edge<long unsigned int, boost::no_property> >, boost::no_property> >, long unsigned int, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>, long int>; typename Config::vertex_descriptor = long unsigned int
正在填写
using Config = boost::detail::adj_list_gen<
boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexCargo>, boost::vecS, boost::setS,
boost::bidirectionalS, VertexCargo, boost::no_property, boost::no_property, boost::listS>::config;
指向我们在 adj_list_gen<...>::config 处的实例化，迭代器被声明为
typedef in_edge_iter<
InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
> in_edge_iterator;
// leading to
typedef OutEdgeIter InEdgeIter;
// leading to
typedef typename OutEdgeList::iterator OutEdgeIter;
// leading to
typedef typename container_gen<OutEdgeListS, StoredEdge>::type OutEdgeList;
并且因为容器选择器是 setS，所以它将是 StoredEdge 的 std::set，即
typedef typename mpl::if_<on_edge_storage,
stored_edge_property<vertex_descriptor, EdgeProperty>,
typename mpl::if_<is_edge_ra,
stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
>::type
>::type StoredEdge;
计算结果为
boost::detail::stored_edge_iter<
long unsigned int,
std::_List_iterator<boost::list_edge<long unsigned int, boost::no_property> >,
boost::no_property>
现在这当然指向 EdgeList 的实现...
坚持住！踩刹车
但最重要的是强加的总弱排序 - 所以我们不去
进一步深入那个兔子洞，而是将我们的注意力转移到
stored_edge_iter<>::operator< 或类似的。
inline bool operator<(const stored_edge& x) const
{ return m_target < x.get_target(); }
啊哈！排序 已经确定地定义 。您可以使用例如 直接 访问它
for (auto v : make_iterator_range(vertices(g))) {
std::cout << v << " --> ";
auto const& iel = boost::in_edge_list(g, v);
for (auto e : iel) std::cout << e.get_target() << " ";
std::cout << "\n";
}
但你不需要。使用通用图形访问器几乎是一样的：
std::cout << v << " --> ";
for (auto e : make_iterator_range(in_edges(v, g))) std::cout << source(e, g) << " ";
std::cout << "\n";
并且您可以验证集合是否按预期正确排序，例如使用
assert(boost::is_sorted(make_iterator_range(in_edges(v,g)) | transformed(sourcer(g))));
assert(boost::is_sorted(make_iterator_range(out_edges(v,g)) | transformed(targeter(g))));
演示版
这是一个完整的演示，包括上述所有内容并在大型随机生成图上断言所有预期顺序：
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <random>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext.hpp>
using boost::adaptors::transformed;
using namespace boost;
struct VertexCargo { int Id = rand() % 1024; };
typedef adjacency_list<setS, vecS, bidirectionalS, VertexCargo> Graph;
typedef graph_traits<Graph>::edge_descriptor ED;
typedef graph_traits<Graph>::vertex_descriptor VD;
struct sourcer {
using result_type = VD;
Graph const* g;
sourcer(Graph const& g) : g(&g) {}
VD operator()(ED e) const { return boost::source(e, *g); }
};
struct targeter {
using result_type = VD;
Graph const* g;
targeter(Graph const& g) : g(&g) {}
VD operator()(ED e) const { return boost::target(e, *g); }
};
int main() {
std::mt19937 rng { std::random_device{}() };
Graph g;
generate_random_graph(g, 1ul<<10, 1ul<<13, rng);
for (auto v : make_iterator_range(vertices(g))) {
std::cout << v << " --> ";
//auto const& iel = boost::in_edge_list(g, v);
//for (auto e : iel) std::cout << e.get_target() << " ";
for (auto e : make_iterator_range(in_edges(v, g))) std::cout << source(e, g) << " ";
//for (auto e : make_iterator_range(out_edges(v, g))) std::cout << target(e, g) << " ";
std::cout << "\n";
assert(boost::is_sorted(make_iterator_range(in_edges(v,g)) | transformed(sourcer(g))));
assert(boost::is_sorted(make_iterator_range(out_edges(v,g)) | transformed(targeter(g))));
}
}