mirror of
https://github.com/boostorg/graph.git
synced 2026-01-29 19:42:11 +00:00
94 lines
3.7 KiB
Plaintext
94 lines
3.7 KiB
Plaintext
[/
|
|
/ Copyright (c) 2007 Andrew Sutton
|
|
/
|
|
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
|
|
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
|
|
/]
|
|
|
|
[section Connected Components]
|
|
template <class Graph, class ComponentMap, class P, class T, class R>
|
|
typename property_traits<ComponentMap>::value_type
|
|
connected_components(const Graph &g, ComponentMap c,
|
|
const bgl_named_params<P,T,R>& params = ``/defaults/``);
|
|
|
|
|
|
The connected_components() functions compute the connected components of an undirected
|
|
graph using a DFS-based approach. A connected component of an undirected graph is a
|
|
set of vertices that are all reachable from each other. If the connected components
|
|
need to be maintained while a graph is growing the disjoint-set based approach of
|
|
function `incremental_components()` is faster. For "static" graphs this DFS-based
|
|
approach is faster \[8\].
|
|
|
|
The output of the algorithm is recorded in the component property map, which will
|
|
contain numbers giving the component number assigned to each vertex. This algorithm
|
|
returns the total number of connected components in the graph.
|
|
|
|
[heading Where Defined]
|
|
`boost/graph/connected_components.hpp`
|
|
|
|
[heading Parameters]
|
|
[table
|
|
[[Type] [Parameter] [Description]]
|
|
[
|
|
[in] [`const Graph& g`]
|
|
[
|
|
The /undirected/ graph for which connected components are being found.
|
|
This graph must be a model of VertexListGraph and Incidence Graph.
|
|
]
|
|
]
|
|
[
|
|
[out] [`ComponentMap c`]
|
|
[
|
|
The algorithm computes how many connected components are in the graph,
|
|
and assigning each component an integer label. The algorithm then records
|
|
which component each vertex in the graph belongs to by recording the
|
|
component number in the component property map. The ComponentMap type
|
|
must be a model of WritablePropertyMap. The value type shouch be an
|
|
integer type, preferably the same as the `vertices_size_type` of the
|
|
graph. The key type must be the graph's `vertex_descriptor` type.
|
|
]
|
|
]
|
|
]
|
|
|
|
[heading Named Parameters]
|
|
[table
|
|
[[Type] [Parameter] [Description]]
|
|
[
|
|
[util] [`color_map(ColorMap color)`]
|
|
[
|
|
This is used by the algorithm to keep track of its progress through the
|
|
graph. The type ColorMap must be a model of ReadWritePropertyMap and
|
|
its key type must be the graph's `vertex_descriptor` type and the value
|
|
type of the color map must model ColorValue.
|
|
|
|
*Default* An `iterator_property_map` create from a `std::vector` of
|
|
`default_color_type` of size `num_vertices(g)` and using `index_map` as
|
|
the index map (to access colors for a vertex).
|
|
]
|
|
]
|
|
[
|
|
[in] [`vertex_index_map(VertexIndexMap index_map)`]
|
|
[
|
|
This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
|
|
This parameter is only necessary when the default color property map is
|
|
used. The type VertexIndexMap must be a model of ReadablePropertyMap. 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* `get(vertex_index, g)`. Note if you use this default, make sure
|
|
that your graph has an interior `vertex_index` property. For example
|
|
`adjacency_list` with `VertexList=listS` does not have an interior
|
|
`vertex_index` property.
|
|
]
|
|
]
|
|
]
|
|
|
|
[heading Complexity]
|
|
This algorithm runs in /O(V + E)/.
|
|
|
|
[heading Notes]
|
|
This algorithm will not compile if passed a /directed/ graph.
|
|
|
|
[heading Examples]
|
|
|
|
[endsect] |