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

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

// named parameter versiontemplate <class Graph, class ComponentMap, class P, class T, class R> typename property_traits<ComponentMap>::value_type strong_components(Graph& g, ComponentMap comp, const bgl_named_params<P, T, R>& params =all defaults)// there is not a non-named parameter version of this function

The `strong_components()` functions compute the strongly
connected components of a directed graph using Tarjan's algorithm
based on DFS [41].

The output of the algorithm is recorded in the component property
map `comp`, which will contain numbers giving the component ID
assigned to each vertex. The number of components is the return value
of the function.

`boost/graph/strong_components.hpp`

A ** strongly connected
component** of a directed graph

A directed 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 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. TheComponentMaptype must be a model of Writable Property Map. The value type shouch be an integer type, preferably the same as thevertices_size_typeof the graph. The key type must be the graph's vertex descriptor type.

Python: Must be anvertex_int_mapfor the graph.

Python default:graph.get_vertex_int_map("component")

This is used by the algorithm to record the candidate root vertex for each vertex. By the end of the algorithm, there is a single root vertex for each component andUTIL:get(r_map, v)returns the root vertex for whichever component vertexvis a member. TheRootMapmust be a Read/Write Property Map, where the key type and the value type are the vertex descriptor type of the graph.

Default:aniterator_property_mapcreated from astd::vectorof vertex descriptors of sizenum_vertices(g)and using thei_mapfor the index map.

Python: Unsupported parameter.

This is used by the algorithm to keep track of the DFS ordering of the vertices. TheUTIL:TimeMapmust be a model of Read/Write Property Map and its value type must be an integer type. The key type must be the vertex descriptor type of the graph.

Default:aniterator_property_mapcreated from astd::vectorof integers with sizenum_vertices(g)and using thei_mapfor the index map.

Python: Unsupported parameter.

This is used by the algorithm to keep track of its progress through the graph. The typeIN:ColorMapmust be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.

Default:aniterator_property_mapcreated from astd::vectorofdefault_color_typeof sizenum_vertices(g)and using thei_mapfor the index map.

Python: Unsupported parameter.

This maps each vertex to an integer in the range[0, num_vertices(g)). This parameter is only necessary when a default is used for one of the other named parameters. The typeVertexIndexMapmust be a model of Readable 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:get(vertex_index, g)

Python: Unsupported parameter.

The time complexity for the strongly connected components algorithm is
*O(V + E)*.

See `examples/strong_components.cpp`.

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