Boost C++ 库

...世界上最受推崇和专业设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ Coding Standards

BFS Visitor 概念

此概念定义了 breadth_first_search() 的访问者接口。用户可以定义一个具有 BFS Visitor 接口的类，并将该类的对象传递给breadth_first_search()，从而增强图搜索期间执行的操作。

改进自

Copy Constructible (复制访问者应该是一个轻量级操作)。

符号

`V`	作为 BFS Visitor 模型的类型。
`vis`	类型为的对象`V`.
`G`	作为 Graph 模型的类型。
`g`	类型为的对象`G`.
`e`	类型为的对象`boost::graph_traits<G>::edge_descriptor`.
`s,u`	类型为的对象`boost::graph_traits<G>::vertex_descriptor`.

关联类型

无

有效表达式

名称	表达式	返回类型	描述
初始化顶点	`vis.initialize_vertex(s, g)`	`void`	这在图搜索开始之前，在图的每个顶点上调用。
发现顶点	`vis.discover_vertex(u, g)`	`void`	当首次遇到顶点时调用此方法。
检查顶点	`vis.examine_vertex(u, g)`	`void`	当顶点从队列中弹出时，将调用此方法。这发生在`examine_edge()`在顶点`u`.
检查边	`vis.examine_edge(e, g)`	`void`	在发现每个顶点后，在其每个出边上调用此方法。
树边	`vis.tree_edge(e, g)`	`void`	当每条边成为构成搜索树的边的一部分时，将调用此方法。
非树边	`vis.non_tree_edge(e, g)`	`void`	对于有向图，在后向边或交叉边上调用此方法；对于无向图，在交叉边上调用此方法。
灰色目标	`vis.gray_target(e, g)`	`void`	对于在检查时目标顶点颜色为灰色的非树边的子集，将调用此方法。颜色灰色表示顶点当前在队列中。
黑色目标	`vis.black_target(e, g)`	`void`	对于在检查时目标顶点颜色为黑色的非树边的子集，将调用此方法。颜色黑色表示顶点已从队列中移除。
完成顶点	`vis.finish_vertex(u, g)`	`void`	在顶点的所有出边都已添加到搜索树并且所有相邻顶点都已被发现之后（但在检查相邻顶点的出边之前），在顶点上调用此方法。

模型

bfs_visitor

Python

要实现BFSVisitor在 Python 中的概念模型，创建一个从以下类派生的新类BFSVisitor图的类型，将被命名为GraphType.BFSVisitor。事件和语法与 C++ 中的访问者相同。这是 Python 的一个示例bgl.Graph图类型

class count_tree_edges_bfs_visitor(bgl.Graph.BFSVisitor):
  def __init__(self, name_map):
    bgl.Graph.BFSVisitor.__init__(self)
    self.name_map = name_map

  def tree_edge(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Tree edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]

另请参阅

访问者概念

Jeremy Siek，印第安纳大学 (jsiek@osl.iu.edu)
Lie-Quan Lee，印第安纳大学 (llee@cs.indiana.edu)
Andrew Lumsdaine，印第安纳大学 (lums@osl.iu.edu)