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
).