label_components

graph_tool.topology.label_components(g, vprop=None, directed=None, attractors=False)

Label the components to which each vertex in the graph belongs. If the graph is directed, it finds the strongly connected components.

A property map with the component labels is returned, together with an histogram of component labels.

Parameters:

gGraph

Graph to be used.

vpropVertexPropertyMap (optional, default: None)

Vertex property to store the component labels. If none is supplied, one is created.

directedbool (optional, default: None)

Treat graph as directed or not, independently of its actual directionality.

attractorsbool (optional, default: False)

If True, and the graph is directed, an additional array with Boolean values is returned, specifying if the strongly connected components are attractors or not.

Returns:

compVertexPropertyMap

Vertex property map with component labels.

histnumpy.ndarray

Histogram of component labels.

is_attractornumpy.ndarray

A Boolean array specifying if the strongly connected components are attractors or not. This returned only if attractors == True, and the graph is directed.

Notes

The components are arbitrarily labeled from 0 to N-1, where N is the total number of components.

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

Examples

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