Components#

template<typename VT, typename ET, typename WT>
void connected_components(legacy::GraphCSRView<VT, ET, WT> const &graph, cugraph_cc_t connectivity_type, VT *labels)#

Compute connected components.

The weak version (for undirected graphs, only) was imported from cuML. This implementation comes from [1] and solves component labeling problem in parallel on CSR-indexes based upon the vertex degree and adjacency graph.

[1] Hawick, K.A et al, 2010. “Parallel graph component labelling with GPUs and CUDA”

The strong version (for directed or undirected graphs) is based on: [2] Gilbert, J. et al, 2011. “Graph Algorithms in the Language of Linear Algebra”

C = I | A | A^2 |…| A^k where matrix multiplication is via semi-ring: (combine, reduce) == (&, |) (bitwise ops) Then: X = C & transpose(C); and finally, apply get_labels(X);

Throws:

cugraph::logic_error – when an error occurs.

Template Parameters:

  • VT – Type of vertex identifiers. Supported value : int (signed, 32-bit)

  • ET – Type of edge identifiers. Supported value : int (signed, 32-bit)

  • WT – Type of edge weights. Supported values : float or double.

Parameters:

  • graph – [in] cuGraph graph descriptor, should contain the connectivity information as a CSR

  • connectivity_type – [in] STRONG or WEAK

  • labels – [out] Device array of component labels (labels[i] indicates the label associated with vertex id i.

template<typename vertex_t, typename edge_t, bool multi_gpu>
void weakly_connected_components(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, vertex_t *components, bool do_expensive_check = false)#

Finds (weakly-connected-)component IDs of each vertices in the input graph.

.*

The input graph must be symmetric. Component IDs can be arbitrary integers (they can be non-consecutive and are not ordered by component size or any other criterion).

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • components – Pointer to the output component ID array.

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).