label_biconnected_components

graph_tool.topology.label_biconnected_components(g, eprop=None, vprop=None)

Label the edges of biconnected components, and the vertices which are articulation points.

An edge property map with the component labels is returned, together a boolean vertex map marking the articulation points, and an histogram of component labels.

Parameters:

gGraph

Graph to be used.

epropEdgePropertyMap (optional, default: None)

Edge property to label the biconnected components.

vpropVertexPropertyMap (optional, default: None)

Vertex property to mark the articulation points. If none is supplied, one is created.

Returns:

bicompEdgePropertyMap

Edge property map with the biconnected component labels.

articulationVertexPropertyMap

Boolean vertex property map which has value 1 for each vertex which is an articulation point, and zero otherwise.

ncint

Number of biconnected components.

Notes

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. Vertices can be present in multiple biconnected components, but each edge can only be contained in a single biconnected component.

The algorithm runs in \(O(V + E)\) time.

Examples

>>> g = gt.random_graph(100, lambda: poisson(2), directed=False)
>>> comp, art, hist = gt.label_biconnected_components(g)
>>> print(comp.a)
[31 31 31  0 31 31 31 31 31 15 27 31 28 31 31 14 31 31 31 31  3 31 31 31
 32 31 31 19 16 29 20 31 31 31 31 31 31 31 31 31 31 31 31 10 24 31  4  8
 22 31 31 31 31  2 31 31 31 31 31 18 31 31 31 31 31 11 21 23  1 31 31 30
  7 31 31 31 25 31 31 31 31 31 31  6 26 17 31 31 31 13 31 31 31 12  9 31
 31 31 31  5 31 31 31]
>>> print(art.a)
[1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0
 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0]
>>> print(hist)
[ 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1 71  1]