- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
TL;DR:我非常希望 in_edges
的迭代顺序在我的图表上(adjacency_list
和 edge_list of setS
)是确定性的,但据我所知,迭代的顺序是由只是指针的比较运算符确定比较---因此迭代顺序由变幻莫测的 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
中定义( boost 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 }
如果有一种方法可以引起比较,我真的很喜欢(以及迭代顺序)基于某些确定性的东西(即 不是 由 malloc 确定的指针地址;例如我写的自定义运算符查看 VertexCargo::Id
对于源和边缘的目标),但看起来这在这里可能行不通因为 void*
Actor 。
从上面的代码来看,注入(inject) property
也是可能的(?)给出所需的顺序。但这让我觉得很骇人听闻。
谁有智慧可以分享?
@sehe 的回答是正确的——底层容器实际上是一个std::set<StoredEdge>
。 ,它定义了一个 operator<
在边缘目标上进行比较;当顶点容器选择器为 vecS
时,这 是确定性的但不是一般情况(因为其他情况下的顶点标识符基本上是从 malloc 获得的指针)。
最佳答案
正如我所料(根据我的记忆),边缘列表(包括输入/输出)已经按其目标排序,因此它们是确定性的。
当 VertexContainer 选择器为 vecS
时,这一点尤其明确。因为,那里有 vertex_descriptor
是一个简单的整数类型,兼作你的 vertex_index_t
无论如何属性(property)。
因为我不是 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
, 它将是 std::set
的 StoredEdge
, 这是
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))));
}
}
关于c++ - boost 图形库 : deterministic order of iteration of in_edges?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30968690/
我正在寻找通过 sql 查询对我的 sql 结果进行排序,大概在 order by 子句中使用某种嵌套的 order by/order by 我有以下数据: TERM USER I
我有一个表格,其中包含如下所示的部分数据。我已经在 edition_id 上完成了订购。现在还需要订购 laungauge_id,这取决于 edition_id 的值。 Edition_id 是指报纸
所以我有两个表,Questions 和 Answers,由多对多关系表 QuestionsAnswers 连接。 Questions 有一个排序列,允许我控制它们如何显示给用户,而 Questions
当我们说“高阶”函数时,我怀疑“阶”的真正含义是什么?例如,我有一个嵌入式函数调用: f.g.h 那么它叫“三阶”函数吗? “高阶”函数是静态函数累加的概念吗?然后当我有一个递归函数 f 时,在运行时
在具有多个 order by 子句的 SQL 查询中,它们是否真的在执行期间全部运行? 例子: select * from my_table order by field5, field3, fiel
我跟进 query其中 schema.org 数据库用于查找类的子级数量 - 作为比我的应用程序更简单的数据库。我想按字母顺序连接 child 的名字。查询: prefix schema: pre
正如 nazdrovje 所指出的(参见 here ) Ordering@Ordering 可用于获取列表中每个元素的排名。即使列表包含重复元素,结果也是 n 排列(作为整数 1 到 n 的有序列表,
我有两张 table 。 它们都有日期和 item_id 列。 我正在通过 item_id 加入他们。 结果应按两个日期列一起排序 下面的代码有效,生成正确的结果集... 但是它们仅按第一个表的日期排
尝试掌握 SQL 我想按日期订购,然后在其中按标题订购。 示例: SELECT * FROM tblboek ORDER BY jr_van_uitgave DESC 如何在按年龄的订单中按头衔排序?
我想使用 FIELD 参数对我的 SQL 输出进行排序,但是当我这样做时,它首先吐出我不想要的结果,然后它首先吐出我想要的结果。在结果之上,它首先吐出。如果这有意义的话 ;) 如何先吐出已定义的值,然
我有一个无法破解的排序问题。我这样从我的表中选择: SELECT * FROM 'sidemodules' WHERE name = 'module1' OR name = 'module2' OR
我对 Django oscar 的覆盖模型有疑问。我想为模型添加一个新字段,但是当我这样做时,我遇到了 RuntimeError: Conflicting 'order' models in appl
我有两个表,电影和类别,我想先按CategoryID获得一个排序列表,然后按名称排序。。电影表格有三个列ID、NAME和CategoryID。CATEGORY表有两列ID和NAME。。我尝试了下面这样
In a MySQL query, when using the DISTINCT option, does ORDER BY apply after the duplicates are re
我想创建一个 sql 查询,为 2 个不同的查询一起返回结果。例如,我想要以下形式的结果:产品名称, avg(price), min(price), max(price), avg(order), m
我正在使用行号从存储过程中获取分页结果。 我发现使用动态 case 语句列名称进行排序会减慢速度 - 但如果我对所有内容进行硬编码就可以了。 有没有办法通过不使整个 sql 查询一个字符串并使用 SP
如何在范围搜索中使用Morton Order? 在wiki中,在“使用一维数据结构进行范围搜索”段落中, 它说 "the range being queried (x = 2, ..., 3, y =
我正在使用 sequelize.js,我在使用 order 语句时遇到问题,我想先通过 if id 排序(如果我的 id 在该别名表中),然后再排序.... order = [['alias', 'i
我有一个 php 脚本,它从数据库中提取内容并以某种方式打印它们。数据库有一个名为“order”的列标题,它的 INT 大小为 11。当我从数据库中获取数据时,我试图按数据库中的值“order”对内容
我有一个带有 ORDER BY 子句的 UPDATE 查询。我已将相同的查询复制到具有相同 ORDER BY 子句的 SELECT 中,但得到了不同的结果。 更新查询: UPDATE t_locks
我是一名优秀的程序员,十分优秀!