cugraph.strongly_connected_components#

cugraph.strongly_connected_components(G, directed=None, connection=None, return_labels=None)[source]#

Generate the Strongly 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=None)

Added for SciPy compatibility, can only be specified for non-Graph-type (eg. sparse matrix) values of G only (raises TypeError if used with a Graph object), and can only be set to “strong” for this API.

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.strongly_connected_components(G)