...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

template<typename Graph, typename ComponentMap, typename OutputIterator, typename DiscoverTimeMap, typename LowPointMap> std::pair<std::size_t, OutputIterator> biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, DiscoverTimeMap discover_time, LowPointMap lowpt); template <typename Graph, typename ComponentMap, typename OutputIterator> std::pair<std::size_t, OutputIterator> biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out); template <typename Graph, typename ComponentMap> std::size_t biconnected_components(const Graph& g, ComponentMap comp); template<typename Graph, typename OutputIterator> OutputIterator articulation_points(const Graph& g, OutputIterator out);

A connected graph is *biconnected* if the removal of any single
vertex (and all edges incident on that vertex) can not disconnect the
graph. More generally, the biconnected components of a graph are the
maximal subsets of vertices such that the removal of a vertex from a
particular component will not disconnect the component. Unlike
connected components, vertices may belong to multiple biconnected
components: those vertices that belong to more than one biconnected
component are called *articulation points* or, equivalently,
*cut vertices*. Articulation points are vertices whose removal
would increase the number of connected components in the graph. Thus,
a graph without articulation points is biconnected. The following
figure illustrates the articulation points and biconnected components
of a small graph:

Vertices can be present in multiple biconnected components, but each
edge can only be contained in a single biconnected component. The
output of the `biconnected_components` algorithm records the
biconnected component number of each edge in the property map
`comp`. Articulation points will be emitted to the (optional)
output iterator argument to `biconnected_components`, or can be
computed without the use of a biconnected component number map via
`articulation_points`. These functions return the number of
biconnected components, the articulation point output iterator, or a
pair of these quantities, depending on what information was
recorded.

The algorithm implemented is due to Tarjan [41].

`boost/graph/biconnected_components.hpp`

An undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.OUT:

Python: The parameter is namedgraph.

The algorithm computes how many biconnected components are in the graph, and assigning each component an integer label. The algorithm then records which component each edge in the graph belongs to by recording the component number in the component property map. TheOUT:ComponentMaptype must be a model of Writable Property Map. The value type shouch be an integer type, preferably the same as theedges_size_typeof the graph. The key type must be the graph's edge descriptor type.

Default:dummy_property_map.

Python: Must be anedge_int_mapfor the graph.

Python default:graph.get_edge_int_map("bicomponent")

The algorithm writes articulation points via this output iterator and returns the resulting iterator.UTIL/OUT:

Default: a dummy iterator that ignores values written to it.

Python: this parameter is not used in Python. Instead, both algorithms return a Pythonlistcontaining the articulation points.

The discovery time of each vertex in the depth-first search. The typeUTIL/OUT:DiscoverTimeMapmust be a model of Read/Write Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default: an iterator_property_map created from astd::vectorofvertices_size_typeof sizenum_vertices(g)and usingget(vertex_index, g)for the index map.

Python: Unsupported parameter.

The low point of each vertex in the depth-first search, which is the smallest vertex reachable from a given vertex with at most one back edge. The typeLowPointMapmust be a model of Read/Write Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default: an iterator_property_map created from astd::vectorofvertices_size_typeof sizenum_vertices(g)and usingget(vertex_index, g)for the index map.

Python: Unsupported parameter.

The time complexity for the biconnected components and articulation
points algorithms
*O(V + E)*.

The file `examples/biconnected_components.cpp`
contains an example of calculating the biconnected components and
articulation points of an undirected graph.

Copyright © 2000-2004 |
Jeremy Siek, Indiana
University (jsiek@osl.iu.edu) Doug Gregor, Indiana University |