正如我所预料的那样（根据我的回忆），边缘列表（无论是入边还是出边）已经按照它们的目标有序排列，因此它们是确定性的。
当选择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;
typedef OutEdgeIter InEdgeIter;
typedef typename OutEdgeList::iterator OutEdgeIter;
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))));
演示
这是一个完整的演示，包括所有内容，并对大型随机生成的图表进行了所有预期排序的断言：
在 Coliru 上实时查看
#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 << " --> ";
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))));
}
}
