DFS Visitor

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

DFS Visitor Concept

This concept defines the visitor interface for depth_first_search(). Users can define a class with the DFS Visitor interface and pass an object of the class to depth_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`	Тип, который является моделью DFS Visitor.
`vis`	Объект типа `V`.
`G`	Тип, который является моделью Графа.
`g`	Объект типа `G`.
`e`	Объект типа `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)`	`void`	Это делается на каждой вершине графа до начала поиска графа.
Начало Vertex	`vis.start_vertex(s, g)`	`void`	На это ссылаются на исходную вершину один раз перед началом поиска.
Откройте для себя Vertex	`vis.discover_vertex(u, g)`	`void`	На это ссылаются, когда вершина встречается впервые.
Исследуйте край	`vis.examine_edge(e, g)`	`void`	На это ссылаются на каждую переднюю часть каждой вершины после ее обнаружения.
Деревянный край	`vis.tree_edge(e, g)`	`void`	Это делается на каждом краю, поскольку оно становится членом краев, образующих дерево поиска.
Назад	`vis.back_edge(e, g)`	`void`	Это делается на задних краях графа. Для ненаправленного графа существует некоторая двусмысленность между ребрами деревьев и обратными краями, поскольку край (u,v) и (v,u) являются одним и тем же краем, но будут использоваться как `tree_edge()`, так и `back_edge()` функции. Один из способов решить эту двусмысленность состоит в том, чтобы зафиксировать края деревьев, а затем игнорировать задние конечности, которые уже обозначены как края деревьев. Простой способ записать ребра деревьев - записать предшественников на `tree_edge` точка события.
Вперед или крест край	`vis.forward_or_cross_edge(e, g)`	`void`	Это делается на передних или поперечных краях графа. В ненаправленном графе этот метод никогда не называется.
Финиш Эдж	`vis.finish_edge(e, g)`	`void`	На это ссылаются на каждый недревесный край, а также на каждый край дерева после того, как `finish_vertex` был назван на его целевой вершине.
Финиш Vertex	`vis.finish_vertex(u, g)`	`void`	На это ссылаются на вершину `u` после того, как `finish_vertex` был назван для всех вершин в DFS-деревье, корневом на вершине `u`. Если вершина `u` является листом в DFS-деревье, то функция `finish_vertex` называется на `u` после того, как были изучены все выдержки `u`.

Models

dfs_visitor

Python

To implement a model of the DFSVisitor concept in Python, create a new class that derives from the DFSVisitor type of the graph, which will be named GraphType.DFSVisitor. 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_dfs_visitor(bgl.Graph.DFSVisitor):
  def __init__(self, name_map):
    bgl.Graph.DFSVisitor.__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, Indiana University (jsiek@osl.iu.edu)
Lie-Quan Lee, Indiana University (llee@cs.indiana.edu)
Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)

Статья DFS Visitor раздела может быть полезна для разработчиков на c++ и boost.

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

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

Время компиляции файла: 2024-08-30 11:47:00
2025-05-19 19:51:06/0.008526086807251/1