Boost Graph Library: BFSVisitor

Boost , ,

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

BFS Visitor Concept

This concept defines the visitor interface for breadth_first_search(). Users can define a class with the BFS Visitor interface and pass and object of the class to breadth_first_search(), thereby augmenting the actions taken during the graph search.

Refinement of

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

`V`	Тип, который является моделью BFS Visitor.
`Вис`	Объект типа`В`.
`G`	Тип, который является моделью графа.
`г`	Объект типа`G`.
`е`	Объект типа`boost::graph_traits::edge_descriptor`.
`s,u`	Объект типа`boost::graph_traits::vertex_descriptor`.

Associated Types

none

Valid Expressions

Name	Expression	Return Type	Description
Инициировать Vertex	`vis.initialize_vertex(s, g)`	`пустота`	Это вызывается на каждой вершине графа до начала поиска графа.
Откройте для себя Vertex	`vis.discover_vertex(u, g)`	`пустота`	Это вызывается, когда вершина встречается впервые.
Проверить Vertex	`vis.examine_vertex(u, g)`	`пустота`	Это вызывается на вершине, когда она выскакивает из очереди. Это происходит непосредственно перед`проверкой_edge()`на каждом из краев вершины`у`.
Проверить Edge	`vis.examine_edge(e, g)`	`пустота`	Это делается на каждом краю каждой вершины после ее обнаружения.
Край дерева	`vis.tree_edge(e, g)`	`пустота`	Это вызывается на каждом краю, поскольку он становится членом краев, которые образуют дерево поиска.
Нетронутый край	`vis.non_tree_edge(e, g)`	`пустота`	Это вызывается на задних или поперечных краях для направленных графов и поперечных краях для ненаправленных графов.
Серая цель	`vis.gray_target(e, g)`	`пустота`	Это вызывается на подмножестве недеревянных краев, чья целевая вершина окрашена в серый цвет во время исследования. Серый цвет указывает на то, что вершина в настоящее время находится в очереди.
Черная цель	`vis.black_target(e, g)`	`пустота`	Это вызывается на подмножестве недеревянных краев, чья целевая вершина окрашена в черный цвет во время исследования. Черный цвет указывает на то, что вершина была удалена из очереди.
Завершить Vertex	`vis.finish_vertex(u, g)`	`пустота`	Это вызвано на вершине после того, как все ее внешние края были добавлены к поисковому дереву, и все смежные вершины были обнаружены (но до того, как были исследованы крайние точки смежных вершин).

Models

bfs_visitor

Python

To implement a model of the BFSVisitor concept in Python, create a new class that derives from the BFSVisitor type of the graph, which will be named GraphType.BFSVisitor. The events and syntax are the same as with visitors in C++. Here is an example for the Python bgl.Graph graph type:

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]

Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.

:: Главная :: ::

Время компиляции файла: 2024-08-30 11:47:00
2025-05-20 14:55:23/0.0035200119018555/0