cugraph/graph/
algorithms.rs

1//! Algorithm wrappers on graphs keyed by transposition state.
2
3use std::num::NonZeroUsize;
4
5use super::{Forward, Graph, Transposed, Transposition};
6use crate::{
7    array::DeviceArrayView,
8    centrality::{
9        BetweennessCentralityParams, BetweennessCentralityResult, CentralityResult, EdgeBetweennessCentralityParams,
10        EdgeBetweennessCentralityResult, HitsResult,
11        betweenness::betweenness_centrality,
12        edge_betweenness::edge_betweenness_centrality,
13        hits::{HitsInitialHubs, HitsParams, hits},
14        pagerank::{
15            InitialGuess, PageRankParams, PersonalizationVector, PersonalizedPageRankParams, PrecomputedWeights,
16            pagerank, personalized_pagerank,
17        },
18        vertex::{EigenvectorCentralityParams, KatzCentralityParams, eigenvector_centrality, katz_centrality},
19    },
20    community::{
21        EcgResult, ExtractEgoParams, ExtractEgoResult, KTrussSubgraphParams, KTrussSubgraphResult, LeidenResult,
22        LouvainResult, SpectralClusteringResult, TriangleCountResult,
23        clustering::{
24            SpectralClusteringParams, analyze_clustering_edge_cut, analyze_clustering_modularity,
25            analyze_clustering_ratio_cut, spectral_modularity_maximization,
26        },
27        ecg::{EcgParams, ecg},
28        leiden::{LeidenParams, leiden},
29        louvain::{LouvainParams, louvain},
30        subgraph::{extract_ego, k_truss_subgraph},
31        triangle_count::{TriangleCountParams, triangle_count},
32    },
33    error::Result,
34    handle::EnteredContext,
35    labeling::{
36        ConnectedComponentsParams, LabelingResult,
37        connected_components::{strongly_connected_components, weakly_connected_components},
38    },
39    layout::force_atlas2::{ForceAtlas2Params, ForceAtlas2VertexAttrs, InitialPositions, LayoutResult, force_atlas2},
40    random::RngState,
41    sampling::{
42        NeighborSamplingParams, Node2VecRandomWalkParams, RandomWalkParams, RandomWalkResult, SampleResult,
43        biased_random_walks, homogeneous_biased_neighbor_sample, homogeneous_biased_temporal_neighbor_sample,
44        homogeneous_uniform_neighbor_sample, homogeneous_uniform_temporal_neighbor_sample, node2vec_random_walks,
45        uniform_random_walks,
46    },
47    similarity::{
48        AllPairsSimilarityParams, CosineSimilarityResult, JaccardSimilarityResult, OverlapSimilarityResult,
49        SimilarityParams, SorensenSimilarityResult, VertexPairs, all_pairs_cosine_similarity_coefficients,
50        all_pairs_jaccard_coefficients, all_pairs_overlap_coefficients, all_pairs_sorensen_coefficients,
51        cosine_similarity_coefficients, create_vertex_pairs, jaccard_coefficients, overlap_coefficients,
52        sorensen_coefficients,
53    },
54    structure::{
55        CoreNumberParams, CoreNumberResult, DegreesResult, InDegreesResult, KCoreParams, KCoreResult, OutDegreesResult,
56        VertexSelection,
57        core::{core_number, k_core},
58        degrees::{degrees, in_degrees, out_degrees},
59    },
60    traversal::{
61        bfs::{BfsParams, BfsPredicateParams, BfsResult, bfs, bfs_with_predicates},
62        sssp::{SsspParams, SsspResult, sssp},
63    },
64    tree::{MinimumSpanningTreeParams, MinimumSpanningTreeResult, minimum_spanning_tree::minimum_spanning_tree},
65    types::CugraphElement,
66};
67
68// ═══════════════════════════════════════════════════════════════════════════
69// Algorithm methods on Graph<T>
70// ═══════════════════════════════════════════════════════════════════════════
71
72impl Graph<Transposed> {
73    /// Compute PageRank on this transposed graph.
74    ///
75    /// Returns a [`CentralityResult`]
76    /// containing vertex ids, scores, iteration count, and convergence status.
77    ///
78    /// Runs PageRank without auxiliary input arrays. For precomputed weights
79    /// or initial scores, see [`pagerank_with`](Self::pagerank_with).
80    pub fn pagerank(&mut self, handle: &EnteredContext<'_>, params: &PageRankParams) -> Result<CentralityResult> {
81        pagerank::<i32, f32>(handle, self, params, None, None)
82    }
83
84    /// Compute PageRank with optional precomputed weights and/or initial guess.
85    ///
86    /// Accepts precomputed out-weight sums and initial score guesses for
87    /// iterative refinement.
88    pub fn pagerank_with<V: CugraphElement, W: CugraphElement>(
89        &mut self,
90        handle: &EnteredContext<'_>,
91        params: &PageRankParams,
92        precomputed_weights: Option<&PrecomputedWeights<'_, V, W>>,
93        initial_guess: Option<&InitialGuess<'_, V, W>>,
94    ) -> Result<CentralityResult> {
95        pagerank(handle, self, params, precomputed_weights, initial_guess)
96    }
97
98    /// Compute personalized PageRank using the allow-nonconvergence native API.
99    pub fn personalized_pagerank<V: CugraphElement, W: CugraphElement>(
100        &mut self,
101        handle: &EnteredContext<'_>,
102        params: &PersonalizedPageRankParams,
103        personalization: &PersonalizationVector<'_, V, W>,
104    ) -> Result<CentralityResult> {
105        personalized_pagerank(handle, self, params, personalization, None, None)
106    }
107
108    /// Compute personalized PageRank with optional precomputed weights and/or initial guess.
109    pub fn personalized_pagerank_with<V: CugraphElement, W: CugraphElement>(
110        &mut self,
111        handle: &EnteredContext<'_>,
112        params: &PersonalizedPageRankParams,
113        personalization: &PersonalizationVector<'_, V, W>,
114        precomputed_weights: Option<&PrecomputedWeights<'_, V, W>>,
115        initial_guess: Option<&InitialGuess<'_, V, W>>,
116    ) -> Result<CentralityResult> {
117        personalized_pagerank(handle, self, params, personalization, precomputed_weights, initial_guess)
118    }
119
120    /// Compute eigenvector centrality.
121    pub fn eigenvector_centrality(
122        &mut self,
123        handle: &EnteredContext<'_>,
124        params: &EigenvectorCentralityParams,
125    ) -> Result<CentralityResult> {
126        eigenvector_centrality(handle, self, params)
127    }
128
129    /// Compute Katz centrality using a scalar beta value.
130    ///
131    /// The local cuGraph C API accepts a per-vertex beta array parameter, but
132    /// the current implementation does not forward it to the native algorithm.
133    /// This safe method therefore exposes only the scalar-beta path.
134    pub fn katz_centrality(
135        &mut self,
136        handle: &EnteredContext<'_>,
137        params: &KatzCentralityParams,
138    ) -> Result<CentralityResult> {
139        katz_centrality(handle, self, params)
140    }
141
142    /// Compute HITS hub and authority scores.
143    pub fn hits(&mut self, handle: &EnteredContext<'_>, params: &HitsParams) -> Result<HitsResult> {
144        hits::<i32, f32>(handle, self, params, None)
145    }
146
147    /// Compute HITS hub and authority scores with an optional initial hub guess.
148    pub fn hits_with_initial_hubs<V: CugraphElement, W: CugraphElement>(
149        &mut self,
150        handle: &EnteredContext<'_>,
151        params: &HitsParams,
152        initial_hubs: Option<&HitsInitialHubs<'_, V, W>>,
153    ) -> Result<HitsResult> {
154        hits(handle, self, params, initial_hubs)
155    }
156
157    /// Compute both in-degrees and out-degrees for vertices in this graph.
158    ///
159    /// Pass [`VertexSelection::All`] to compute degrees for every vertex,
160    /// [`VertexSelection::Device`] with a device view, or
161    /// [`VertexSelection::Host`] with a host slice (uploaded on demand).
162    ///
163    /// # Errors
164    ///
165    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `vertices` uses a vertex
166    /// dtype that does not match the graph.
167    pub fn degrees<'a, V: CugraphElement + 'a>(
168        &mut self,
169        handle: &EnteredContext<'_>,
170        vertices: impl Into<VertexSelection<'a, V>>,
171    ) -> Result<DegreesResult> {
172        let vertices = vertices.into();
173        self.validate_vertex_selection(&vertices, "Graph::degrees", "vertices", true)?;
174        let resolved = vertices.resolve(handle)?;
175        let view = resolved.view()?;
176        degrees(handle, self, view.as_ref(), false)
177    }
178
179    /// Compute degrees with optional expensive input validation.
180    pub fn degrees_checked<'a, V: CugraphElement + 'a>(
181        &mut self,
182        handle: &EnteredContext<'_>,
183        vertices: impl Into<VertexSelection<'a, V>>,
184        do_expensive_check: bool,
185    ) -> Result<DegreesResult> {
186        let vertices = vertices.into();
187        self.validate_vertex_selection(&vertices, "Graph::degrees", "vertices", true)?;
188        let resolved = vertices.resolve(handle)?;
189        let view = resolved.view()?;
190        degrees(handle, self, view.as_ref(), do_expensive_check)
191    }
192
193    /// Compute degrees for every vertex in the graph.
194    pub fn degrees_all(&mut self, handle: &EnteredContext<'_>) -> Result<DegreesResult> {
195        self.degrees(handle, VertexSelection::<i32>::All)
196    }
197
198    /// Compute only in-degrees for vertices in this graph.
199    ///
200    /// Pass [`VertexSelection::All`] to compute degrees for every vertex,
201    /// [`VertexSelection::Device`] with a device view, or
202    /// [`VertexSelection::Host`] with a host slice (uploaded on demand).
203    ///
204    /// # Errors
205    ///
206    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `vertices` uses a vertex
207    /// dtype that does not match the graph.
208    pub fn in_degrees<'a, V: CugraphElement + 'a>(
209        &mut self,
210        handle: &EnteredContext<'_>,
211        vertices: impl Into<VertexSelection<'a, V>>,
212    ) -> Result<InDegreesResult> {
213        let vertices = vertices.into();
214        self.validate_vertex_selection(&vertices, "Graph::in_degrees", "vertices", true)?;
215        let resolved = vertices.resolve(handle)?;
216        let view = resolved.view()?;
217        in_degrees(handle, self, view.as_ref(), false)
218    }
219
220    /// Compute in-degrees with optional expensive input validation.
221    pub fn in_degrees_checked<'a, V: CugraphElement + 'a>(
222        &mut self,
223        handle: &EnteredContext<'_>,
224        vertices: impl Into<VertexSelection<'a, V>>,
225        do_expensive_check: bool,
226    ) -> Result<InDegreesResult> {
227        let vertices = vertices.into();
228        self.validate_vertex_selection(&vertices, "Graph::in_degrees", "vertices", true)?;
229        let resolved = vertices.resolve(handle)?;
230        let view = resolved.view()?;
231        in_degrees(handle, self, view.as_ref(), do_expensive_check)
232    }
233
234    /// Compute in-degrees for every vertex in the graph.
235    pub fn in_degrees_all(&mut self, handle: &EnteredContext<'_>) -> Result<InDegreesResult> {
236        self.in_degrees(handle, VertexSelection::<i32>::All)
237    }
238}
239
240impl Graph<Forward> {
241    /// Perform breadth-first search from one or more source vertices.
242    ///
243    /// Returns a [`BfsResult`] containing vertex
244    /// ids, distances, and optionally predecessors.
245    ///
246    /// # Errors
247    ///
248    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `sources` uses a vertex
249    /// dtype that does not match the graph.
250    pub fn bfs<'a, V: CugraphElement + 'a>(
251        &mut self,
252        handle: &EnteredContext<'_>,
253        sources: impl Into<VertexSelection<'a, V>>,
254        params: &BfsParams,
255    ) -> Result<BfsResult> {
256        let sources = sources.into();
257        self.validate_vertex_selection(&sources, "Graph::bfs", "sources", false)?;
258        let resolved = sources.resolve(handle)?;
259        let view = self.resolved_vertex_view(&resolved, "Graph::bfs", "sources")?;
260        bfs(handle, self, &view, params)
261    }
262
263    /// Perform breadth-first search with optional edge, vertex, and target predicates.
264    ///
265    /// Predicate inputs must already be concrete device arrays. Higher layers
266    /// are responsible for SQL planning, relation-backed edge alignment, and
267    /// logical-to-physical vertex-id mapping before calling this API.
268    pub fn bfs_with_predicates<'a, V, E>(
269        &mut self,
270        handle: &EnteredContext<'_>,
271        sources: impl Into<VertexSelection<'a, V>>,
272        params: &BfsParams,
273        predicates: &BfsPredicateParams<'a, V, E>,
274    ) -> Result<BfsResult>
275    where
276        V: CugraphElement + 'a,
277        E: CugraphElement + 'a,
278    {
279        let sources = sources.into();
280        self.validate_vertex_selection(&sources, "Graph::bfs_with_predicates", "sources", false)?;
281        let resolved = sources.resolve(handle)?;
282        let view = self.resolved_vertex_view(&resolved, "Graph::bfs_with_predicates", "sources")?;
283        bfs_with_predicates(handle, self, &view, params, predicates)
284    }
285
286    /// Perform single-source shortest path from one source vertex.
287    ///
288    /// Returns an [`SsspResult`] containing
289    /// vertex ids, weighted distances, and optionally predecessors.
290    pub fn sssp<V>(&mut self, handle: &EnteredContext<'_>, source: V, params: &SsspParams) -> Result<SsspResult>
291    where V: CugraphElement + TryInto<usize> + Copy + std::fmt::Debug {
292        self.validate_vertex_input_dtype(V::data_type(), "Graph::sssp", "source")?;
293        let weight_mode = if self.has_weights { "weighted" } else { "unit_weight" };
294        sssp(handle, self, source, params).map_err(|error| error.with_context("weight_mode", weight_mode))
295    }
296
297    /// Compute uniform random walks from explicit start vertices.
298    pub fn uniform_random_walks<V: CugraphElement>(
299        &mut self,
300        handle: &EnteredContext<'_>,
301        rng_state: &mut RngState,
302        start_vertices: &DeviceArrayView<'_, V>,
303        params: &RandomWalkParams,
304    ) -> Result<RandomWalkResult> {
305        uniform_random_walks(handle, rng_state, self, start_vertices, params)
306    }
307
308    /// Compute biased random walks from explicit start vertices.
309    pub fn biased_random_walks<V: CugraphElement>(
310        &mut self,
311        handle: &EnteredContext<'_>,
312        rng_state: &mut RngState,
313        start_vertices: &DeviceArrayView<'_, V>,
314        params: &RandomWalkParams,
315    ) -> Result<RandomWalkResult> {
316        biased_random_walks(handle, rng_state, self, start_vertices, params)
317    }
318
319    /// Compute node2vec random walks from explicit start vertices.
320    pub fn node2vec_random_walks<V: CugraphElement>(
321        &mut self,
322        handle: &EnteredContext<'_>,
323        rng_state: &mut RngState,
324        start_vertices: &DeviceArrayView<'_, V>,
325        params: &Node2VecRandomWalkParams,
326    ) -> Result<RandomWalkResult> {
327        node2vec_random_walks(handle, rng_state, self, start_vertices, params)
328    }
329
330    /// Sample homogeneous neighborhoods uniformly from explicit start vertices.
331    pub fn homogeneous_uniform_neighbor_sample<V: CugraphElement>(
332        &mut self,
333        handle: &EnteredContext<'_>,
334        rng_state: &mut RngState,
335        start_vertices: &DeviceArrayView<'_, V>,
336        starting_vertex_label_offsets: Option<&DeviceArrayView<'_, usize>>,
337        params: &NeighborSamplingParams,
338    ) -> Result<SampleResult> {
339        homogeneous_uniform_neighbor_sample(
340            handle,
341            rng_state,
342            self,
343            start_vertices,
344            starting_vertex_label_offsets,
345            params,
346        )
347    }
348
349    /// Sample homogeneous neighborhoods with biased sampling from explicit start vertices.
350    pub fn homogeneous_biased_neighbor_sample<V: CugraphElement>(
351        &mut self,
352        handle: &EnteredContext<'_>,
353        rng_state: &mut RngState,
354        start_vertices: &DeviceArrayView<'_, V>,
355        starting_vertex_label_offsets: Option<&DeviceArrayView<'_, usize>>,
356        params: &NeighborSamplingParams,
357    ) -> Result<SampleResult> {
358        homogeneous_biased_neighbor_sample(
359            handle,
360            rng_state,
361            self,
362            start_vertices,
363            starting_vertex_label_offsets,
364            params,
365        )
366    }
367
368    /// Sample homogeneous temporal neighborhoods uniformly from explicit start vertices.
369    pub fn homogeneous_uniform_temporal_neighbor_sample<V, Tm>(
370        &mut self,
371        handle: &EnteredContext<'_>,
372        rng_state: &mut RngState,
373        temporal_property_name: &str,
374        start_vertices: &DeviceArrayView<'_, V>,
375        starting_vertex_times: Option<&DeviceArrayView<'_, Tm>>,
376        starting_vertex_label_offsets: Option<&DeviceArrayView<'_, usize>>,
377        params: &NeighborSamplingParams,
378    ) -> Result<SampleResult>
379    where
380        V: CugraphElement,
381        Tm: CugraphElement,
382    {
383        homogeneous_uniform_temporal_neighbor_sample(
384            handle,
385            rng_state,
386            self,
387            temporal_property_name,
388            start_vertices,
389            starting_vertex_times,
390            starting_vertex_label_offsets,
391            params,
392        )
393    }
394
395    /// Sample homogeneous temporal neighborhoods with biased sampling from explicit start vertices.
396    pub fn homogeneous_biased_temporal_neighbor_sample<V, Tm>(
397        &mut self,
398        handle: &EnteredContext<'_>,
399        rng_state: &mut RngState,
400        temporal_property_name: &str,
401        start_vertices: &DeviceArrayView<'_, V>,
402        starting_vertex_times: Option<&DeviceArrayView<'_, Tm>>,
403        starting_vertex_label_offsets: Option<&DeviceArrayView<'_, usize>>,
404        params: &NeighborSamplingParams,
405    ) -> Result<SampleResult>
406    where
407        V: CugraphElement,
408        Tm: CugraphElement,
409    {
410        homogeneous_biased_temporal_neighbor_sample(
411            handle,
412            rng_state,
413            self,
414            temporal_property_name,
415            start_vertices,
416            starting_vertex_times,
417            starting_vertex_label_offsets,
418            params,
419        )
420    }
421
422    /// Compute Louvain communities on this forward-stored graph.
423    ///
424    /// Louvain is an undirected community-detection algorithm. This wrapper
425    /// preserves the crate's type-state requirement that the graph must be
426    /// stored in forward (non-transposed) layout, but it does not add a new
427    /// Rust-side hard check that the graph was constructed with undirected
428    /// properties.
429    ///
430    /// Returns a [`LouvainResult`]
431    /// containing vertex ids, per-vertex partitions, and modularity.
432    pub fn louvain(&mut self, handle: &EnteredContext<'_>, params: &LouvainParams) -> Result<LouvainResult> {
433        louvain(handle, self, params)
434    }
435
436    /// Compute Leiden communities on this forward-stored graph.
437    ///
438    /// Leiden is an undirected community-detection algorithm. This wrapper
439    /// requires forward graph storage; libcugraph rejects a directed graph as
440    /// [`ErrorKind::InvalidInput`](crate::ErrorKind::InvalidInput). Every
441    /// returned community induces a connected subgraph, and the reported
442    /// modularity is that of the returned partition.
443    pub fn leiden(
444        &mut self,
445        handle: &EnteredContext<'_>,
446        rng_state: &mut RngState,
447        params: &LeidenParams,
448    ) -> Result<LeidenResult> {
449        leiden(handle, rng_state, self, params)
450    }
451
452    /// Compute ECG communities on this forward-stored graph.
453    ///
454    /// ECG is an undirected community-detection algorithm built from a Louvain
455    /// ensemble. This wrapper requires forward graph storage but leaves
456    /// graph-property validation to the native library.
457    pub fn ecg(
458        &mut self,
459        handle: &EnteredContext<'_>,
460        rng_state: &mut RngState,
461        params: &EcgParams,
462    ) -> Result<EcgResult> {
463        ecg(handle, rng_state, self, params)
464    }
465
466    /// Compute legacy spectral modularity maximization clusters.
467    ///
468    /// cuGraph requires a symmetric graph for this algorithm. This wrapper
469    /// keeps that validation in the native library, matching the rest of the
470    /// community-detection surface.
471    pub fn spectral_modularity_maximization(
472        &mut self,
473        handle: &EnteredContext<'_>,
474        rng_state: &mut RngState,
475        params: &SpectralClusteringParams,
476    ) -> Result<SpectralClusteringResult> {
477        spectral_modularity_maximization(handle, rng_state, self, params)
478    }
479
480    /// Compute modularity for explicit clustering columns.
481    pub fn analyze_clustering_modularity<V: CugraphElement>(
482        &mut self,
483        handle: &EnteredContext<'_>,
484        n_clusters: NonZeroUsize,
485        vertices: &DeviceArrayView<'_, V>,
486        clusters: &DeviceArrayView<'_, V>,
487    ) -> Result<f64> {
488        analyze_clustering_modularity(handle, self, n_clusters, vertices, clusters)
489    }
490
491    /// Compute edge cut for explicit clustering columns.
492    pub fn analyze_clustering_edge_cut<V: CugraphElement>(
493        &mut self,
494        handle: &EnteredContext<'_>,
495        n_clusters: NonZeroUsize,
496        vertices: &DeviceArrayView<'_, V>,
497        clusters: &DeviceArrayView<'_, V>,
498    ) -> Result<f64> {
499        analyze_clustering_edge_cut(handle, self, n_clusters, vertices, clusters)
500    }
501
502    /// Compute ratio cut for explicit clustering columns.
503    pub fn analyze_clustering_ratio_cut<V: CugraphElement>(
504        &mut self,
505        handle: &EnteredContext<'_>,
506        n_clusters: NonZeroUsize,
507        vertices: &DeviceArrayView<'_, V>,
508        clusters: &DeviceArrayView<'_, V>,
509    ) -> Result<f64> {
510        analyze_clustering_ratio_cut(handle, self, n_clusters, vertices, clusters)
511    }
512}
513
514impl<T: Transposition> Graph<T> {
515    /// Compute vertex betweenness centrality on this graph.
516    ///
517    /// Pass [`VertexSelection::All`] for exact computation, or provide seed
518    /// vertices for approximate computation via [`VertexSelection::Device`] or
519    /// [`VertexSelection::Host`].
520    ///
521    /// # Errors
522    ///
523    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `vertex_list` uses a vertex
524    /// dtype that does not match the graph.
525    pub fn betweenness_centrality<'a, V: CugraphElement + 'a>(
526        &mut self,
527        handle: &EnteredContext<'_>,
528        vertex_list: impl Into<VertexSelection<'a, V>>,
529        params: &BetweennessCentralityParams,
530    ) -> Result<BetweennessCentralityResult> {
531        let vertex_list = vertex_list.into();
532        self.validate_vertex_selection(&vertex_list, "Graph::betweenness_centrality", "vertex_list", true)?;
533        let resolved = vertex_list.resolve(handle)?;
534        let view = resolved.view()?;
535        betweenness_centrality(handle, self, view.as_ref(), params)
536    }
537
538    /// Compute exact betweenness centrality over all vertices.
539    pub fn betweenness_centrality_all(
540        &mut self,
541        handle: &EnteredContext<'_>,
542        params: &BetweennessCentralityParams,
543    ) -> Result<BetweennessCentralityResult> {
544        self.betweenness_centrality(handle, VertexSelection::<i32>::All, params)
545    }
546
547    /// Compute edge betweenness centrality on this graph.
548    ///
549    /// Pass [`VertexSelection::All`] for exact computation, or provide seed
550    /// vertices for approximate computation via [`VertexSelection::Device`] or
551    /// [`VertexSelection::Host`].
552    pub fn edge_betweenness_centrality<'a, V: CugraphElement + 'a>(
553        &mut self,
554        handle: &EnteredContext<'_>,
555        vertex_list: impl Into<VertexSelection<'a, V>>,
556        params: &EdgeBetweennessCentralityParams,
557    ) -> Result<EdgeBetweennessCentralityResult> {
558        let vertex_list = vertex_list.into();
559        self.validate_vertex_selection(&vertex_list, "Graph::edge_betweenness_centrality", "vertex_list", true)?;
560        let resolved = vertex_list.resolve(handle)?;
561        let view = resolved.view()?;
562        edge_betweenness_centrality(handle, self, view.as_ref(), params)
563    }
564
565    /// Compute exact edge betweenness centrality over all vertices.
566    pub fn edge_betweenness_centrality_all(
567        &mut self,
568        handle: &EnteredContext<'_>,
569        params: &EdgeBetweennessCentralityParams,
570    ) -> Result<EdgeBetweennessCentralityResult> {
571        self.edge_betweenness_centrality(handle, VertexSelection::<i32>::All, params)
572    }
573
574    /// Compute weakly connected components.
575    ///
576    /// cuGraph requires the input graph to be symmetric for this algorithm.
577    /// This wrapper does not add a Rust-side graph-property hard failure; use
578    /// `do_expensive_check` in [`ConnectedComponentsParams`] to request native
579    /// validation.
580    ///
581    /// [`ConnectedComponentsParams`]: crate::labeling::ConnectedComponentsParams
582    pub fn weakly_connected_components(
583        &mut self,
584        handle: &EnteredContext<'_>,
585        params: &ConnectedComponentsParams,
586    ) -> Result<LabelingResult> {
587        weakly_connected_components(handle, self, params)
588    }
589
590    /// Compute strongly connected components.
591    pub fn strongly_connected_components(
592        &mut self,
593        handle: &EnteredContext<'_>,
594        params: &ConnectedComponentsParams,
595    ) -> Result<LabelingResult> {
596        strongly_connected_components(handle, self, params)
597    }
598
599    /// Compute core numbers for all vertices.
600    pub fn core_number(&mut self, handle: &EnteredContext<'_>, params: &CoreNumberParams) -> Result<CoreNumberResult> {
601        core_number(handle, self, params)
602    }
603
604    /// Extract a k-core subgraph, computing core numbers internally.
605    pub fn k_core(&mut self, handle: &EnteredContext<'_>, params: &KCoreParams) -> Result<KCoreResult> {
606        k_core(handle, self, params, None)
607    }
608
609    /// Extract a k-core subgraph using a precomputed core-number result.
610    pub fn k_core_with_core_numbers(
611        &mut self,
612        handle: &EnteredContext<'_>,
613        params: &KCoreParams,
614        core_numbers: &CoreNumberResult,
615    ) -> Result<KCoreResult> {
616        k_core(handle, self, params, Some(core_numbers))
617    }
618
619    /// Compute a minimum spanning tree.
620    pub fn minimum_spanning_tree(
621        &mut self,
622        handle: &EnteredContext<'_>,
623        params: &MinimumSpanningTreeParams,
624    ) -> Result<MinimumSpanningTreeResult> {
625        minimum_spanning_tree(handle, self, params)
626    }
627
628    /// Create an owned vertex-pair collection for pairwise similarity algorithms.
629    ///
630    /// `first` and `second` must be explicit vertex selections with matching
631    /// lengths and the same vertex dtype as this graph. `VertexSelection::All`
632    /// is rejected because pairwise similarity requires aligned input pairs.
633    pub fn vertex_pairs<'a, V: CugraphElement + 'a>(
634        &mut self,
635        handle: &EnteredContext<'_>,
636        first: impl Into<VertexSelection<'a, V>>,
637        second: impl Into<VertexSelection<'a, V>>,
638    ) -> Result<VertexPairs> {
639        let first = first.into();
640        let second = second.into();
641        self.validate_vertex_selection(&first, "Graph::vertex_pairs", "first", false)?;
642        self.validate_vertex_selection(&second, "Graph::vertex_pairs", "second", false)?;
643        let first = first.resolve(handle)?;
644        let second = second.resolve(handle)?;
645        let first_view = self.resolved_vertex_view(&first, "Graph::vertex_pairs", "first")?;
646        let second_view = self.resolved_vertex_view(&second, "Graph::vertex_pairs", "second")?;
647        create_vertex_pairs(handle, self, &first_view, &second_view)
648            .map_err(|error| error.with_operation("Graph::vertex_pairs"))
649    }
650
651    /// Compute Jaccard similarity coefficients for explicit vertex pairs.
652    ///
653    /// cuGraph requires a symmetric graph for this algorithm; native
654    /// validation reports detailed graph-property errors.
655    pub fn jaccard_coefficients(
656        &mut self,
657        handle: &EnteredContext<'_>,
658        pairs: VertexPairs,
659        params: &SimilarityParams,
660    ) -> Result<JaccardSimilarityResult> {
661        jaccard_coefficients(handle, self, pairs, params)
662    }
663
664    /// Compute Sorensen similarity coefficients for explicit vertex pairs.
665    ///
666    /// cuGraph requires a symmetric graph for this algorithm; native
667    /// validation reports detailed graph-property errors.
668    pub fn sorensen_coefficients(
669        &mut self,
670        handle: &EnteredContext<'_>,
671        pairs: VertexPairs,
672        params: &SimilarityParams,
673    ) -> Result<SorensenSimilarityResult> {
674        sorensen_coefficients(handle, self, pairs, params)
675    }
676
677    /// Compute overlap similarity coefficients for explicit vertex pairs.
678    ///
679    /// cuGraph requires a symmetric graph for this algorithm; native
680    /// validation reports detailed graph-property errors.
681    pub fn overlap_coefficients(
682        &mut self,
683        handle: &EnteredContext<'_>,
684        pairs: VertexPairs,
685        params: &SimilarityParams,
686    ) -> Result<OverlapSimilarityResult> {
687        overlap_coefficients(handle, self, pairs, params)
688    }
689
690    /// Compute cosine similarity coefficients for explicit vertex pairs.
691    ///
692    /// cuGraph requires a symmetric graph for this algorithm; native
693    /// validation reports detailed graph-property errors.
694    pub fn cosine_similarity_coefficients(
695        &mut self,
696        handle: &EnteredContext<'_>,
697        pairs: VertexPairs,
698        params: &SimilarityParams,
699    ) -> Result<CosineSimilarityResult> {
700        cosine_similarity_coefficients(handle, self, pairs, params)
701    }
702
703    /// Compute all-pairs Jaccard similarity coefficients.
704    ///
705    /// Pass [`VertexSelection::All`] to use all vertices or an explicit subset
706    /// to seed pair generation. cuGraph requires a symmetric graph.
707    pub fn all_pairs_jaccard_coefficients<'a, V: CugraphElement + 'a>(
708        &mut self,
709        handle: &EnteredContext<'_>,
710        vertices: impl Into<VertexSelection<'a, V>>,
711        params: &AllPairsSimilarityParams,
712    ) -> Result<JaccardSimilarityResult> {
713        let vertices = vertices.into();
714        self.validate_vertex_selection(&vertices, "Graph::all_pairs_jaccard_coefficients", "vertices", true)?;
715        let resolved = vertices.resolve(handle)?;
716        let view = resolved.view()?;
717        all_pairs_jaccard_coefficients(handle, self, view.as_ref(), params)
718    }
719
720    /// Compute all-pairs Sorensen similarity coefficients.
721    ///
722    /// Pass [`VertexSelection::All`] to use all vertices or an explicit subset
723    /// to seed pair generation. cuGraph requires a symmetric graph.
724    pub fn all_pairs_sorensen_coefficients<'a, V: CugraphElement + 'a>(
725        &mut self,
726        handle: &EnteredContext<'_>,
727        vertices: impl Into<VertexSelection<'a, V>>,
728        params: &AllPairsSimilarityParams,
729    ) -> Result<SorensenSimilarityResult> {
730        let vertices = vertices.into();
731        self.validate_vertex_selection(&vertices, "Graph::all_pairs_sorensen_coefficients", "vertices", true)?;
732        let resolved = vertices.resolve(handle)?;
733        let view = resolved.view()?;
734        all_pairs_sorensen_coefficients(handle, self, view.as_ref(), params)
735    }
736
737    /// Compute all-pairs overlap similarity coefficients.
738    ///
739    /// Pass [`VertexSelection::All`] to use all vertices or an explicit subset
740    /// to seed pair generation. cuGraph requires a symmetric graph.
741    pub fn all_pairs_overlap_coefficients<'a, V: CugraphElement + 'a>(
742        &mut self,
743        handle: &EnteredContext<'_>,
744        vertices: impl Into<VertexSelection<'a, V>>,
745        params: &AllPairsSimilarityParams,
746    ) -> Result<OverlapSimilarityResult> {
747        let vertices = vertices.into();
748        self.validate_vertex_selection(&vertices, "Graph::all_pairs_overlap_coefficients", "vertices", true)?;
749        let resolved = vertices.resolve(handle)?;
750        let view = resolved.view()?;
751        all_pairs_overlap_coefficients(handle, self, view.as_ref(), params)
752    }
753
754    /// Compute all-pairs cosine similarity coefficients.
755    ///
756    /// Pass [`VertexSelection::All`] to use all vertices or an explicit subset
757    /// to seed pair generation. cuGraph requires a symmetric graph.
758    pub fn all_pairs_cosine_similarity_coefficients<'a, V: CugraphElement + 'a>(
759        &mut self,
760        handle: &EnteredContext<'_>,
761        vertices: impl Into<VertexSelection<'a, V>>,
762        params: &AllPairsSimilarityParams,
763    ) -> Result<CosineSimilarityResult> {
764        let vertices = vertices.into();
765        self.validate_vertex_selection(&vertices, "Graph::all_pairs_cosine_similarity_coefficients", "vertices", true)?;
766        let resolved = vertices.resolve(handle)?;
767        let view = resolved.view()?;
768        all_pairs_cosine_similarity_coefficients(handle, self, view.as_ref(), params)
769    }
770
771    /// Compute a Force Atlas 2 layout for this graph.
772    ///
773    /// Returns a [`LayoutResult`] containing
774    /// vertex ids and (x, y) coordinates.
775    ///
776    /// For advanced features (per-vertex mass/radius, initial positions for
777    /// refinement passes), use [`force_atlas2_with`](Self::force_atlas2_with).
778    pub fn force_atlas2(
779        &mut self,
780        handle: &EnteredContext<'_>,
781        rng_state: &mut RngState,
782        params: &ForceAtlas2Params,
783    ) -> Result<LayoutResult> {
784        force_atlas2::<T, i32, f32>(handle, rng_state, self, params, None, None)
785    }
786
787    /// Compute a Force Atlas 2 layout with optional per-vertex attributes
788    /// and/or initial positions.
789    ///
790    /// Accepts initial positions for refinement passes or per-vertex
791    /// radius, mobility, and mass attributes.
792    pub fn force_atlas2_with<V: CugraphElement, W: CugraphElement>(
793        &mut self,
794        handle: &EnteredContext<'_>,
795        rng_state: &mut RngState,
796        params: &ForceAtlas2Params,
797        vertex_attrs: Option<&ForceAtlas2VertexAttrs<'_, V, W>>,
798        initial_positions: Option<&InitialPositions<'_, V, W>>,
799    ) -> Result<LayoutResult> {
800        force_atlas2(handle, rng_state, self, params, vertex_attrs, initial_positions)
801    }
802
803    /// Compute only out-degrees for vertices in this graph.
804    ///
805    /// Pass [`VertexSelection::All`] to compute degrees for every vertex,
806    /// [`VertexSelection::Device`] with a device view, or
807    /// [`VertexSelection::Host`] with a host slice (uploaded on demand).
808    ///
809    /// # Errors
810    ///
811    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `vertices` uses a vertex
812    /// dtype that does not match the graph.
813    pub fn out_degrees<'a, V: CugraphElement + 'a>(
814        &mut self,
815        handle: &EnteredContext<'_>,
816        vertices: impl Into<VertexSelection<'a, V>>,
817    ) -> Result<OutDegreesResult> {
818        let vertices = vertices.into();
819        self.validate_vertex_selection(&vertices, "Graph::out_degrees", "vertices", true)?;
820        let resolved = vertices.resolve(handle)?;
821        let view = resolved.view()?;
822        out_degrees(handle, self, view.as_ref(), false)
823    }
824
825    /// Compute out-degrees with optional expensive input validation.
826    pub fn out_degrees_checked<'a, V: CugraphElement + 'a>(
827        &mut self,
828        handle: &EnteredContext<'_>,
829        vertices: impl Into<VertexSelection<'a, V>>,
830        do_expensive_check: bool,
831    ) -> Result<OutDegreesResult> {
832        let vertices = vertices.into();
833        self.validate_vertex_selection(&vertices, "Graph::out_degrees", "vertices", true)?;
834        let resolved = vertices.resolve(handle)?;
835        let view = resolved.view()?;
836        out_degrees(handle, self, view.as_ref(), do_expensive_check)
837    }
838
839    /// Compute out-degrees for every vertex in the graph.
840    pub fn out_degrees_all(&mut self, handle: &EnteredContext<'_>) -> Result<OutDegreesResult> {
841        self.out_degrees(handle, VertexSelection::<i32>::All)
842    }
843
844    /// Compute triangle counts for all vertices or an explicit start-vertex list.
845    ///
846    /// Pass [`VertexSelection::All`] to count triangles for every vertex,
847    /// [`VertexSelection::Device`] with a device view, or
848    /// [`VertexSelection::Host`] with a host slice uploaded on demand.
849    ///
850    /// # Errors
851    ///
852    /// Returns [`ErrorKind::UnsupportedType`](crate::ErrorKind::UnsupportedType) if `start_vertices` uses a
853    /// vertex dtype that does not match the graph.
854    pub fn triangle_count<'a, V: CugraphElement + 'a>(
855        &mut self,
856        handle: &EnteredContext<'_>,
857        start_vertices: impl Into<VertexSelection<'a, V>>,
858        params: &TriangleCountParams,
859    ) -> Result<TriangleCountResult> {
860        let start_vertices = start_vertices.into();
861        self.validate_vertex_selection(&start_vertices, "Graph::triangle_count", "start_vertices", true)?;
862        let resolved = start_vertices.resolve(handle)?;
863        let view = resolved.view()?;
864        triangle_count(handle, self, view.as_ref(), params)
865    }
866
867    /// Compute triangle counts for every vertex in the graph.
868    pub fn triangle_count_all(
869        &mut self,
870        handle: &EnteredContext<'_>,
871        params: &TriangleCountParams,
872    ) -> Result<TriangleCountResult> {
873        self.triangle_count(handle, VertexSelection::<i32>::All, params)
874    }
875
876    /// Extract a k-truss subgraph.
877    pub fn k_truss_subgraph(
878        &mut self,
879        handle: &EnteredContext<'_>,
880        params: &KTrussSubgraphParams,
881    ) -> Result<KTrussSubgraphResult> {
882        k_truss_subgraph(handle, self, params)
883    }
884
885    /// Extract ego subgraphs for explicit source vertices.
886    ///
887    /// `VertexSelection::All` is rejected because the native API requires an
888    /// explicit source vertex list.
889    pub fn extract_ego<'a, V: CugraphElement + 'a>(
890        &mut self,
891        handle: &EnteredContext<'_>,
892        source_vertices: impl Into<VertexSelection<'a, V>>,
893        params: &ExtractEgoParams,
894    ) -> Result<ExtractEgoResult> {
895        let source_vertices = source_vertices.into();
896        self.validate_vertex_selection(&source_vertices, "Graph::extract_ego", "source_vertices", false)?;
897        let resolved = source_vertices.resolve(handle)?;
898        let view = self.resolved_vertex_view(&resolved, "Graph::extract_ego", "source_vertices")?;
899        extract_ego(handle, self, &view, params)
900    }
901}
cugraph/graph/algorithms.rs

cugraph/graph/
algorithms.rs
