Boost Graph Library: Dijkstra 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

Dijkstra Visitor Concept

This concept defines the visitor interface for dijkstra_shortest_paths() and related algorithms. The user can create a class that matches this interface, and then pass objects of the class into dijkstra_shortest_paths() to augment the actions taken during the search.

Refinement of

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

Notation

`V`	Тип, который является моделью Dijkstra Visitor.
`Вис`	Объект типа`В`.
`G`	Тип, который является моделью графа.
`г`	Объект типа`G`.
`е`	Объект типа`boost::graph_traits::edge_descriptor`.
`s,u,v`	Объект типа`boost::graph_traits::vertex_descriptor`.
`Дистанционная карта`	Тип, который является модельюКарта свойств чтения / записи.
`d`	Дистанционная карта.
`Карта веса`	Тип, который является модельюReadable Property Map.
`w`	Вещественная карта.

Associated Types

none

Valid Expressions

Name	Expression	Return Type	Description
Инициировать Vertex	`vis.initialize_vertex(u, g)`	`пустота`	Это вызывается по одной вершине графа при его инициализации.
Проверить Vertex	`vis.examine_vertex(u, g)`	`пустота`	Это вызывается на вершине, когда она выскакивает из очереди. Это происходит непосредственно перед тем, как`проверить_edge()`вызывается на каждом из краев вершины`у`.
Проверить Edge	`vis.examine_edge(e, g)`	`пустота`	Это делается на каждом краю каждой вершины после ее обнаружения.
Откройте для себя Vertex	`vis.discover_vertex(u, g)`	`пустота`	Это вызывается, когда вершина встречается впервые.
Edge расслабился	`vis.edge_relaxed(e, g)`	`пустота`	При осмотре, если следующее условие удерживает, то край расслаблен (его расстояние уменьшено), и этот метод вызывается. `tie(u,v) = incident(e, g); D d_u = get(d, u), d_v = get(d, v); W w_e = get(w, e); assert(compare(combine(d_u, w_e), d_v));`
Edge не расслабляется	`vis.edge_not_relaxed(e, g)`	`пустота`	При осмотре, если край не расслаблен (см. выше), то этот метод вызывается.
Завершить Vertex	`vis.finish_vertex(u, g)`	`пустота`	Это вызвано на вершине после того, как все ее внешние края были добавлены к дереву поиска, и все соседние вершины были обнаружены (но до того, как их края были исследованы).

Models

dijkstra_visitor

Python

To implement a model of the DijkstraVisitor concept in Python, create a new class that derives from the DijkstraVisitor type of the graph, which will be named GraphType.DijkstraVisitor. 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_dijkstra_visitor(bgl.Graph.DijkstraVisitor):
  def __init__(self, name_map):
    bgl.Graph.DijkstraVisitor.__init__(self)
    self.name_map = name_map
  def edge_relaxed(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Relaxed edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]

Джереми Сик, Университет Индианыjsiek@osl.iu.edu]
Ли-Куан Ли, Университет Индианыllee@cs.indiana.edu
Эндрю Лумсдейн, Университет Индианыlums@osl.iu.edu

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

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

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

Время компиляции файла: 2024-08-30 08:47:00
2025-10-31 06:01:03/0.010064840316772/0