0

我有一个 boost::filtered_graph< Graph_t, boost::keep_all, vertex_predicate >

假设FG是我的过滤图。v1是我想使用 out_edge_iterators 找出所有边的任何节点

edge_predicate 这里是“keep_all” 顶点谓词是一些用于修改图节点属性的谓词。

在文档中，给出了：

graph_traits<filtered_graph>::out_edge_iterator 
//The type for the iterators returned by out_edges(), which is:
filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>
The iterator is a model of MultiPassInputIterator.

现在，当我定义 out_edge_iterators 时：

out_edge_iterator begin, end;
boost::tie( begin, end) = out_edges ( v1, FG )

我期望的是以下内容： 1. 它应该考虑提供的 edge_predicate 并据此过滤边缘。基本上，开始和结束迭代器应该是基于边缘谓词的 filter_iterators。2. 我认为不应该在边的其他节点上调用 vertex_predicate。例如，假设v1有 3 个出边 (v1, v2), (v1, v4), (v1, v6)。

我的观察是：在查找 v1 的 out_edges 的过程中，在v1的第一个相对节点上调用了 vertex_predicate。在上述情况下，

suppose begin --> points to edge (v1, v2), then, 
out_edges(v1, G) ---> calls vertex_predicate on **v2**

为什么会这样？是因为执行 out_edges() 函数会涉及查找相邻节点并返回找到的第一个节点吗？

我在调用相邻顶点（）时观察到的情况相同。文档说它建模为 out_edge_iterator < edge_predicate , ... > 。

我得到了我的预期结果。但我想知道我的猜测是否正确？我没有为过滤图提供任何 edge_predicate 。

请建议。

4

1 回答 1

1

当过滤图排除了某个顶点时，它也排除了与其关联的所有边。这意味着即使您指定了一些边缘也会被过滤掉keep_all。

在内部，filtered_graph有一个特殊的边谓词（由边谓词和顶点谓词组合而成），用于过滤掉边。当您请求给定顶点的出边时，BGL 会返回一对过滤器迭代器。

“结束”迭代器通常基于out_edges底层图函数的“结束”。“开始”迭代器从函数的“开始”开始out_edges，检查边的“目标”是否是图的一部分。如果不是，迭代器会跳过它，直到找到一个好的顶点（或点击“结束”）。

因此迭代器不断检查“目标”顶点并调用顶点谓词。

于 2014-01-30T03:35:32.757 回答