Where Defined

<boost/graph/breadth_first_search.hpp>

Parameter Defaults

Все параметрыпоследовательного поиска по ширинеподдерживаются и имеют по существу одинаковое значение. Здесь документируются только различия.

IN: Graph& g

The graph type must be a model of Distributed Graph.

IN: vertex_descriptor s

The start vertex must be the same in every process.

IN: visitor(BFSVisitor vis)

The visitor must be a distributed BFS visitor. The suble differences between sequential and distributed BFS visitors are discussed in the section Visitor Event Points.

UTIL/OUT: color_map(ColorMap color)

The color map must be a Distributed Property Map with the same process group as the graph g whose colors must monotonically darken (white -> gray -> black). The default value is a distributed iterator_property_map created from a std::vector of default_color_type.

UTIL: buffer(Buffer& Q)

The queue must be a distributed queue that passes vertices to their owning process. If already-visited vertices should not be visited again (as is typical for BFS), the queue must filter duplicates itself. The queue controls synchronization within the algorithm: its empty() method must not return true until all local queues are empty.

Default: A distributed_queue of a filtered_queue over a

standard boost::queue. This queue filters out duplicate vertices and distributes vertices appropriately.

Complexity

Этот алгоритм выполняетO(V + E)работу вd + 1BSP-супершагах, гдеd— диаметр исследуемого подключенного компонента. На всех ступеняхО(Е)будут передаваться сообщения постоянного размера.

Visitor Event Points

КонцепцияBFS Visitorопределяет 9 точек событий, которые будут вызваныпоследовательным поиском по ширине. Распределенная BFS сохраняет эти девять точек событий, но последовательность событий и процесс, в котором происходит каждое событие, будут меняться в зависимости от распределения графика.

initialize_vertex(s, g)

This will be invoked by every process for each local vertex.

discover_vertex(u, g)

This will be invoked each time a process discovers a new vertex u. Due to incomplete information in distributed property maps, this event may be triggered many times for the same vertex u.

examine_vertex(u, g)

This will be invoked by the process owning the vertex u. If the distributed queue prevents duplicates, it will be invoked only once for a particular vertex u.

examine_edge(e, g)

This will be invoked by the process owning the source vertex of e. If the distributed queue prevents duplicates, it will be invoked only once for a particular edge e.

tree_edge(e, g)

Similar to examine_edge, this will be invoked by the process owning the source vertex and may be invoked only once. Unlike the sequential BFS, this event may be triggered even when the target has already been discovered (but by a different process). Thus, some non_tree_edge events in a sequential BFS may become tree_edge in a distributed BFS.

non_tree_edge(e, g)

Some non_tree_edge events in a sequential BFS may become tree_edge events in a distributed BFS. See the description of tree_edge for additional details.

gray_target(e, g)

As with tree_edge not knowing when another process has already discovered a vertex, gray_target events may occur in a distributed BFS when black_target events may occur in a sequential BFS, due to a lack of information on a given processor. The source of edge e will be local to the process executing this event.

black_target(e, g)

See documentation for gray_target

finish_vertex(e, g)

See documentation for examine_vertex.

template<typename DistanceMap>
struct bfs_discovery_visitor : bfs_visitor<>
{
  bfs_discovery_visitor(DistanceMap distance) : distance(distance) {}
  template<typename Edge, typename Graph>
  void tree_edge(Edge e, const Graph& g)
  {
    std::size_t new_distance = get(distance, source(e, g)) + 1;
    put(distance, target(e, g), new_distance);
  }
 private:
  DistanceMap distance;
};

template<typename DistanceMap>
struct bfs_discovery_visitor : bfs_visitor<>
{
  bfs_discovery_visitor(DistanceMap distance) : distance(distance)
  {
    set_property_map_role(vertex_distance, distance);
  }
  template<typename Edge, typename Graph>
  void tree_edge(Edge e, const Graph& g)
  {
    std::size_t new_distance = get(distance, source(e, g)) + 1;
    put(distance, target(e, g), new_distance);
  }
 private:
  DistanceMap distance;
};

Performance

Производительность Breadth-First Search иллюстрируется следующими диаграммами. Масштабирование и производительность являются разумными для всех графиков, которые мы пробовали.

Copyright (C) 2004 Попечители Университета Индианы.

Авторы: Дуглас Грегор и Эндрю Лумсдейн