cugraph.connected_components

cugraph.connected_components(G, directed=None, connection='weak', return_labels=None)

Generate either the strongly or weakly connected components and attach a component label to each vertex.

Parameters:

Gcugraph.Graph, networkx.Graph, CuPy or SciPy sparse matrix

Graph or matrix object, which should contain the connectivity information (edge weights are not used for this algorithm). If using a graph object, the graph can be either directed or undirected where an undirected edge is represented by a directed edge in both directions. The adjacency list will be computed if not already present. The number of vertices should fit into a 32b int.

directedbool, optional (default=True)

NOTE

For non-Graph-type (eg. sparse matrix) values of G only. Raises TypeError if used with a Graph object.

If True, then convert the input matrix to a Graph(directed=True) and only move from point i to point j along paths csgraph[i, j]. If False, then find the shortest path on an undirected graph: the algorithm can progress from point i to j along csgraph[i, j] or csgraph[j, i].

connectionstr, optional (default=’weak’)

NOTE

For Graph-type values of G, weak components are only supported for undirected graphs.

[‘weak’|’strong’]. Return either weakly or strongly connected components.

return_labelsbool, optional (default=True)

NOTE

For non-Graph-type (eg. sparse matrix) values of G only. Raises TypeError if used with a Graph object.

If True, then return the labels for each of the connected components.

Returns:

Return value type is based on the input type. If G is a cugraph.Graph,

returns:

cudf.DataFrame

GPU data frame containing two cudf.Series of size V: the vertex identifiers and the corresponding component identifier.

df[‘vertex’]

Contains the vertex identifier

df[‘labels’]

The component identifier

If G is a networkx.Graph, returns:

python dictionary, where keys are vertices and values are the component identifiers.

If G is a CuPy or SciPy matrix, returns:

CuPy ndarray (if CuPy matrix input) or Numpy ndarray (if SciPy matrix input) of shape (<num vertices>, 2), where column 0 contains component identifiers and column 1 contains vertices.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> df = cugraph.connected_components(G, connection="weak")