Utility Functions#

template<typename VT, typename ET, typename WT>
std::unique_ptr<legacy::GraphCOO<VT, ET, WT>> extract_subgraph_vertex(legacy::GraphCOOView<VT, ET, WT> const &graph, VT const *vertices, VT num_vertices)#

Extract subgraph by vertices.

.*

This function will identify all edges that connect pairs of vertices that are both contained in the vertices list and return a COO containing these edges.

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] input graph object (COO)

  • vertices – [in] device pointer to an array of vertex ids

  • num_vertices – [in] number of vertices in the array vertices

  • result – [out] a graph in COO format containing the edges in the subgraph

template<typename vertex_t, typename edge_t, bool multi_gpu>
rmm::device_uvector<vertex_t> vertex_coloring(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, raft::random::RngState &rng_state)#

Find a Greedy Vertex Coloring.

A vertex coloring is an assignment of colors or labels to each vertex of a graph so that no two adjacent vertices have the same color or label. Finding the minimum number of colors needed to color the vertices of a graph is an NP-hard problem and therefore for practical use cases greedy coloring is used. Here we provide an implementation of greedy vertex coloring based on maximal independent set. See https://research.nvidia.com/sites/default/files/pubs/2015-05_Parallel-Graph-Coloring/nvr-2015-001.pdf for further information.

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)

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.

  • rng_state – The RngState instance holding pseudo-random number generator state.

Returns:

A device vector containing color for each vertex.

template<typename vertex_t, typename edge_t, typename weight_t, bool multi_gpu>
std::tuple<rmm::device_uvector<vertex_t>, weight_t> approximate_weighted_matching(raft::handle_t const &handle, graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view, edge_property_view_t<edge_t, weight_t const*> edge_weight_view)#

Approximate Weighted Matching.

.*

A matching in an undirected graph G = (V, E) is a pairing of adjacent vertices such that each vertex is matched with at most one other vertex, the objective being to match as many vertices as possible or to maximise the sum of the weights of the matched edges. Here we provide an implementation of an approximation algorithm to the weighted Maximum matching. See https://web.archive.org/web/20081031230449id_/http://www.ii.uib.no/~fredrikm/fredrik/papers/CP75.pdf for further information.

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)

Parameters:

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

  • graph_view – [in] Graph view object.

  • edge_weight_view – [in] View object holding edge weights for graph_view.

Returns:

A tuple of device vector of matched vertex ids and sum of the weights of the matched edges.