pylibcugraph.strongly_connected_components#

pylibcugraph.strongly_connected_components(ResourceHandle resource_handle, _GPUGraph graph, offsets, indices, weights, labels, bool_t do_expensive_check)[source]#

Generate the Strongly Connected Components from either an input graph or CSR arrays (‘offsets’, ‘indices’, ‘weights’) and attach a component label to each vertex.

Parameters:

resource_handleResourceHandle: Handle to the underlying device resources needed for referencing data and running algorithms.
graphSGGraph or MGGraph: The input graph.
offsetsobject supporting a __cuda_array_interface__ interface: Array containing the offsets values of a Compressed Sparse Row matrix that represents the graph.
indicesobject supporting a __cuda_array_interface__ interface: Array containing the indices values of a Compressed Sparse Row matrix that represents the graph.
weightsobject supporting a __cuda_array_interface__ interface: Array containing the weights values of a Compressed Sparse Row matrix that represents the graph
labelsoptional, object supporting __cuda_array_interface__: If provided, component labels are copied into this array; otherwise labels are returned in the result tuple.
do_expensive_checkbool_t: If True, performs more extensive tests on the inputs to ensure validitity, at the expense of increased run time.

Returns:

tuple or None: If labels is None, returns (vertices, labels) as device arrays. If labels is provided, returns None (output written in-place).

Examples

>>> import pylibcugraph, cupy, numpy
>>> from pylibcugraph import strongly_connected_components
>>> srcs = cupy.asarray([0, 0, 1, 1, 2, 2], dtype=numpy.int32)
>>> dsts = cupy.asarray([1, 2, 1, 2, 0, 1], dtype=numpy.int32)
>>> weights = cupy.asarray(
...     [1.0, 1.0, 1.0, 1.0, 1.0, 1.0], dtype=numpy.float32)
>>> resource_handle = pylibcugraph.ResourceHandle()
>>> graph_props = pylibcugraph.GraphProperties(
...      is_symmetric=False, is_multigraph=False)
>>> G = pylibcugraph.SGGraph(
...     resource_handle, graph_props, srcs, dsts, weight_array=weights,
...     store_transposed=False, renumber=True, do_expensive_check=False)
>>> (vertices, labels) = strongly_connected_components(
...     resource_handle, G, None, None, None, None, False)

>>> vertices
[0, 1, 2]
>>> labels
[0, 0, 0]

>>> import cupy as cp
>>> import numpy as np
>>> from scipy.sparse import csr_matrix
>>>
>>> graph = [
... [0, 1, 1, 0, 0],
... [0, 0, 1, 0, 0],
... [0, 0, 0, 0, 0],
... [0, 0, 0, 0, 1],
... [0, 0, 0, 0, 0],
... ]
>>> scipy_csr = csr_matrix(graph)
>>>
>>> cp_offsets = cp.asarray(scipy_csr.indptr)
>>> cp_indices = cp.asarray(scipy_csr.indices, dtype=np.int32)
>>>
>>> resource_handle = pylibcugraph.ResourceHandle()
>>> _, cp_labels = strongly_connected_components(
...     resource_handle=resource_handle,
...     graph=None,
...     offsets=cp_offsets,
...     indices=cp_indices,
...     weights=None,
...     labels=None,
...     do_expensive_check=False,
... )
>>> print(f"{len(set(cp_labels.tolist()))} - {cp_labels}")
5 - [0 1 2 3 4]