实用函数#

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

按顶点提取子图。

.*

此函数将标识连接顶点列表中的成对顶点的所有边，并返回一个包含这些边的 COO 图。

抛出:

cugraph::logic_error – 发生错误时。

模板参数:

  • VT – 顶点标识符的类型。支持的值：int (有符号, 32位)

  • ET – 边标识符的类型。支持的值：int (有符号, 32位)

  • WT – 边权重的类型。支持的值：float 或 double。

参数:

  • graph – [in] 输入图对象 (COO)

  • vertices – [in] 指向顶点 ID 数组的设备指针

  • num_vertices – [in] 数组 vertices 中的顶点数量

  • result – [out] 包含子图中边的 COO 格式的图

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

查找贪心顶点着色。

顶点着色是将颜色或标签分配给图的每个顶点，使得没有两个相邻顶点具有相同的颜色或标签。找到为图顶点着色所需的最小颜色数量是一个 NP-hard 问题，因此在实际应用中通常使用贪心着色。这里我们基于最大独立集提供了一种贪心顶点着色的实现。更多信息请参见 https://research.nvidia.com/sites/default/files/pubs/2015-05_Parallel-Graph-Coloring/nvr-2015-001.pdf。

模板参数:

  • vertex_t – 顶点标识符的类型。必须是整数类型。

  • edge_t – 边标识符的类型。必须是整数类型。

  • multi_gpu – 指示模板实例化是否应针对单 GPU (false) 的标志

参数:

  • handle – 用于封装资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）以运行图算法的 RAFT 句柄对象。

  • graph_view – 图视图对象。

  • rng_state – 保存伪随机数生成器状态的 RngState 实例。

返回:

一个设备向量，包含每个顶点的颜色。

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

近似带权匹配。

.*

无向图 G = (V, E) 中的匹配是指将相邻顶点配对，使得每个顶点最多与一个其他顶点匹配，其目标是尽可能多地匹配顶点或最大化匹配边的权重总和。这里我们提供了一种带权最大匹配的近似算法实现。更多信息请参见 https://web.archive.org/web/20081031230449id_/http://www.ii.uib.no/~fredrikm/fredrik/papers/CP75.pdf。

模板参数:

  • vertex_t – 顶点标识符的类型。必须是整数类型。

  • edge_t – 边标识符的类型。必须是整数类型。

  • multi_gpu – 指示模板实例化是否应针对单 GPU (false) 的标志

参数:

  • handle – [in] 用于封装资源（例如 CUDA 流、通信器以及各种 CUDA 库的句柄）以运行图算法的 RAFT 句柄对象。

  • graph_view – [in] 图视图对象。

  • edge_weight_view – [in] 保存 graph_view 边权重的视图对象。

返回:

一个设备向量的元组，包含匹配顶点的 ID 和匹配边的权重总和。