algeon-cugraph 0.1.3

mod array_owner;
mod betweenness_owner;
mod bfs_owner;
mod degrees_owner;
mod dtype_contracts_gpu;
mod layout_owner;
mod null_guards_and_distances_gpu;
mod pagerank_owner;
mod result_decoding_gpu;
mod typed_vec_gpu;

use cudf::testing::run_named_cases;
use cugraph_sys::{
    cugraph_data_type_id_t, cugraph_error_code_t, cugraph_error_free,
    cugraph_type_erased_device_array_view_copy_from_host, cugraph_type_erased_device_array_view_create,
    cugraph_type_erased_device_array_view_free,
};

#[path = "../support/common/mod.rs"]
mod common;

use std::{collections::HashMap, num::NonZeroUsize, ptr};

use common::{
    cudf::explicit_runtime,
    support::{
        ALL_PAIRS_JACCARD_F32, ALL_PAIRS_JACCARD_FIRST_I32, ALL_PAIRS_JACCARD_SECOND_I32, DEGREE_QUERY_I64,
        DEGREE_SUBSET_DST_I64, DEGREE_SUBSET_SRC_I64, DIRECTED_STAR_DST_I64, DIRECTED_STAR_SRC_I64,
        DISCONNECTED_TWO_CYCLES_DST_I32, DISCONNECTED_TWO_CYCLES_SRC_I32, FOUR_VERTEX_CHAIN_DST_I32,
        FOUR_VERTEX_CHAIN_DST_I64, FOUR_VERTEX_CHAIN_SRC_I32, FOUR_VERTEX_CHAIN_SRC_I64, LOUVAIN_GRAPH_DST_I32,
        LOUVAIN_GRAPH_SRC_I32, LOUVAIN_GRAPH_WEIGHT_F32, SIMILARITY_COSINE_F32, SIMILARITY_JACCARD_F32,
        SIMILARITY_OVERLAP_F32, SIMILARITY_PAIR_FIRST_I32, SIMILARITY_PAIR_SECOND_I32, SIMILARITY_SORENSEN_F32,
        SSSP_GRAPH_DST_I32, SSSP_GRAPH_SRC_I32, SSSP_GRAPH_WEIGHT_F32, SSSP_GRAPH_WEIGHT_F64,
        TEST_LAYOUT_SECONDARY_SEED, TEST_LAYOUT_SMOKE_ITERATIONS, TRIANGLE_VERTEX_IDS_I64, UNDIRECTED_TRIANGLE_DST_I32,
        UNDIRECTED_TRIANGLE_DST_I64, UNDIRECTED_TRIANGLE_SRC_I32, UNDIRECTED_TRIANGLE_SRC_I64,
        UNDIRECTED_TRIANGLE_UNIT_WEIGHT_F64, bfs_distance_map_i64_result,
    },
};
use cugraph::{
    DeviceArray, Forward, Graph, GraphBuilder, ResourceHandle, Transposed, VertexSelection,
    centrality::{
        BetweennessCentralityParams, EdgeBetweennessCentralityParams, EigenvectorCentralityParams, HitsInitialHubs,
        HitsParams, InitialGuess, KatzCentralityParams, PageRankParams, PersonalizationVector,
        PersonalizedPageRankParams, PrecomputedWeights,
    },
    community::{
        EcgParams, ExtractEgoParams, KTrussSubgraphParams, LeidenParams, LouvainParams, SpectralClusteringParams,
        TriangleCountParams,
    },
    error::ErrorKind,
    labeling::ConnectedComponentsParams,
    layout::{ForceAtlas2Params, ForceAtlas2VertexAttrs, InitialPositions},
    params::{IterationCount, NonNegativeF64, PositiveF64},
    random::RngState,
    sampling::{
        NeighborSamplingParams, Node2VecRandomWalkParams, RandomWalkParams, RandomWalkResult, SampleResult,
        TemporalSamplingComparison,
    },
    similarity::{AllPairsSimilarityParams, SimilarityParams},
    structure::{CoreNumberParams, Distances, IntegerValues, KCoreDegreeType, KCoreParams, ScoreValues, VertexIds},
    traversal::{BfsParams, SsspParams},
    tree::MinimumSpanningTreeParams,
    types::GraphProperties,
};

// Planted-partition graph seeds and resolutions on which libcugraph's Leiden returned two
// disconnected communities each, and a modularity off by 0.003 to 0.009, before the flat
// partition was split into connected components and its modularity recomputed.
const LEIDEN_CONNECTIVITY_CASES: &[(u64, f64)] = &[(2, 1.0), (8, 1.0), (14, 3.0)];

fn test_handle() -> ResourceHandle {
    let runtime = std::sync::Arc::new(explicit_runtime());
    ResourceHandle::for_runtime(std::sync::Arc::clone(&runtime)).expect("handle")
}

fn assert_f32_close(actual: &[f32], expected: &[f32]) {
    assert_eq!(actual.len(), expected.len(), "score length mismatch");
    for (index, (&actual, &expected)) in actual.iter().zip(expected).enumerate() {
        assert!((actual - expected).abs() < 1.0e-4, "score[{index}] expected {expected}, got {actual}");
    }
}

fn similarity_fixture_graph(handle: &cugraph::EnteredContext<'_>) -> Graph<Forward> {
    let src = DeviceArray::from_slice(handle, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(handle, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(handle)
        .expect("graph")
}

#[test]
fn gpu_cases_1() {
    run_named_cases(&[
        ("bfs_accepts_i64_sources_for_i64_graphs", bfs_accepts_i64_sources_for_i64_graphs),
        ("betweenness_accepts_i64_seed_vertices", betweenness_accepts_i64_seed_vertices),
        (
            "betweenness_rejects_out_of_range_seed_vertex_with_default_params",
            betweenness_rejects_out_of_range_seed_vertex_with_default_params,
        ),
        ("degrees_accept_i64_vertex_subsets", degrees_accept_i64_vertex_subsets),
        ("in_degrees_checked_accepts_all_vertices", in_degrees_checked_accepts_all_vertices),
        ("out_degrees_checked_accepts_all_vertices", out_degrees_checked_accepts_all_vertices),
        (
            "pairwise_similarity_coefficients_match_reference_values",
            pairwise_similarity_coefficients_match_reference_values,
        ),
        (
            "pairwise_similarity_preserves_explicit_pair_multisets_and_rejects_invalid_endpoints",
            pairwise_similarity_preserves_explicit_pair_multisets_and_rejects_invalid_endpoints,
        ),
        (
            "pairwise_jaccard_consumes_weights_and_rejects_weighted_calls_without_a_weight_binding",
            pairwise_jaccard_consumes_weights_and_rejects_weighted_calls_without_a_weight_binding,
        ),
        (
            "weighted_cosine_returns_zero_for_disjoint_nonempty_neighborhoods",
            weighted_cosine_returns_zero_for_disjoint_nonempty_neighborhoods,
        ),
        ("all_pairs_jaccard_returns_generated_vertex_pairs", all_pairs_jaccard_returns_generated_vertex_pairs),
        (
            "all_pairs_similarity_methods_return_consistent_columns",
            all_pairs_similarity_methods_return_consistent_columns,
        ),
        ("vertex_pairs_rejects_mismatched_pair_lengths", vertex_pairs_rejects_mismatched_pair_lengths),
        (
            "random_walk_algorithms_return_dense_paths_and_weights",
            random_walk_algorithms_return_dense_paths_and_weights,
        ),
        ("unweighted_random_walks_omit_weights", unweighted_random_walks_omit_weights),
        ("select_random_vertices_returns_owned_device_array", select_random_vertices_returns_owned_device_array),
        (
            "homogeneous_neighbor_sampling_returns_expected_columns",
            homogeneous_neighbor_sampling_returns_expected_columns,
        ),
        (
            "temporal_neighbor_sampling_is_callable_with_start_times",
            temporal_neighbor_sampling_is_callable_with_start_times,
        ),
        (
            "temporal_neighbor_sampling_rejects_start_time_length_mismatch",
            temporal_neighbor_sampling_rejects_start_time_length_mismatch,
        ),
        ("bfs_rejects_vertex_selection_all", bfs_rejects_vertex_selection_all),
    ]);
}

#[test]
fn gpu_cases_2() {
    run_named_cases(&[
        (
            "sssp_weighted_graph_returns_float_distances_and_predecessors",
            sssp_weighted_graph_returns_float_distances_and_predecessors,
        ),
        ("sssp_unweighted_graph_uses_unit_edge_costs", sssp_unweighted_graph_uses_unit_edge_costs),
        ("sssp_without_predecessors_omits_predecessor_column", sssp_without_predecessors_omits_predecessor_column),
        ("extract_paths_from_bfs_and_sssp_results", extract_paths_from_bfs_and_sssp_results),
        ("extract_paths_rejects_results_without_predecessors", extract_paths_rejects_results_without_predecessors),
        ("sssp_rejects_source_dtype_mismatch", sssp_rejects_source_dtype_mismatch),
        ("force_atlas2_accepts_i64_vertices_and_f32_helpers", force_atlas2_accepts_i64_vertices_and_f32_helpers),
        ("force_atlas2_rejects_sparse_mass_helpers", force_atlas2_rejects_sparse_mass_helpers),
        (
            "louvain_returns_vertex_partitions_and_finite_modularity",
            louvain_returns_vertex_partitions_and_finite_modularity,
        ),
        (
            "leiden_returns_vertex_partitions_and_finite_modularity",
            leiden_returns_vertex_partitions_and_finite_modularity,
        ),
        (
            "leiden_communities_induce_connected_subgraphs_and_report_their_modularity",
            leiden_communities_induce_connected_subgraphs_and_report_their_modularity,
        ),
        ("ecg_returns_vertex_partitions_and_finite_modularity", ecg_returns_vertex_partitions_and_finite_modularity),
        (
            "weakly_connected_components_labels_two_symmetric_components",
            weakly_connected_components_labels_two_symmetric_components,
        ),
        (
            "strongly_connected_components_labels_directed_components",
            strongly_connected_components_labels_directed_components,
        ),
        (
            "core_number_on_triangle_tail_returns_stable_core_values",
            core_number_on_triangle_tail_returns_stable_core_values,
        ),
        (
            "triangle_count_all_and_start_vertices_return_expected_counts",
            triangle_count_all_and_start_vertices_return_expected_counts,
        ),
        (
            "k_core_with_and_without_precomputed_core_numbers_returns_triangle_edges",
            k_core_with_and_without_precomputed_core_numbers_returns_triangle_edges,
        ),
        (
            "k_core_degree_type_selects_the_degree_that_defines_cores",
            k_core_degree_type_selects_the_degree_that_defines_cores,
        ),
        (
            "native_precondition_failure_is_invalid_input_with_the_bare_reason",
            native_precondition_failure_is_invalid_input_with_the_bare_reason,
        ),
        ("minimum_spanning_tree_returns_weighted_edge_result", minimum_spanning_tree_returns_weighted_edge_result),
    ]);
}

#[test]
fn gpu_cases_3() {
    run_named_cases(&[
        ("k_truss_subgraph_returns_expected_offsets_and_edges", k_truss_subgraph_returns_expected_offsets_and_edges),
        ("extract_ego_returns_per_seed_offsets", extract_ego_returns_per_seed_offsets),
        ("pagerank_on_single_vertex_graph_returns_score_one", pagerank_on_single_vertex_graph_returns_score_one),
        (
            "pagerank_on_disconnected_graph_returns_normalized_positive_scores",
            pagerank_on_disconnected_graph_returns_normalized_positive_scores,
        ),
        ("pagerank_reports_nonconvergence_without_failing", pagerank_reports_nonconvergence_without_failing),
        ("personalized_pagerank_accepts_personalization_vector", personalized_pagerank_accepts_personalization_vector),
        (
            "personalized_pagerank_rejects_mismatched_personalization_lengths",
            personalized_pagerank_rejects_mismatched_personalization_lengths,
        ),
        (
            "personalized_pagerank_rejects_out_of_range_personalization_vertex_with_default_params",
            personalized_pagerank_rejects_out_of_range_personalization_vertex_with_default_params,
        ),
        (
            "pagerank_rejects_out_of_range_precomputed_weight_vertex_with_default_params",
            pagerank_rejects_out_of_range_precomputed_weight_vertex_with_default_params,
        ),
        (
            "pagerank_rejects_out_of_range_initial_guess_vertex_with_default_params",
            pagerank_rejects_out_of_range_initial_guess_vertex_with_default_params,
        ),
        (
            "vertex_centrality_expansion_algorithms_return_vertex_scores",
            vertex_centrality_expansion_algorithms_return_vertex_scores,
        ),
        ("eigenvector_nonconvergence_is_typed_and_permanent", eigenvector_nonconvergence_is_typed_and_permanent),
        ("katz_nonconvergence_is_typed_and_names_alpha", katz_nonconvergence_is_typed_and_names_alpha),
        ("hits_nonconvergence_is_typed_and_names_its_remedy", hits_nonconvergence_is_typed_and_names_its_remedy),
        ("hits_returns_hub_authority_scores_and_metadata", hits_returns_hub_authority_scores_and_metadata),
        (
            "hits_rejects_out_of_range_initial_hub_vertex_with_default_params",
            hits_rejects_out_of_range_initial_hub_vertex_with_default_params,
        ),
        (
            "edge_betweenness_exposes_edge_shaped_scores_and_optional_edge_ids",
            edge_betweenness_exposes_edge_shaped_scores_and_optional_edge_ids,
        ),
        (
            "edge_betweenness_rejects_out_of_range_seed_vertex_with_default_params",
            edge_betweenness_rejects_out_of_range_seed_vertex_with_default_params,
        ),
        (
            "spectral_clustering_returns_partitions_and_analysis_scores",
            spectral_clustering_returns_partitions_and_analysis_scores,
        ),
        (
            "clustering_analysis_accepts_explicit_partition_columns",
            clustering_analysis_accepts_explicit_partition_columns,
        ),
        ("degrees_all_on_empty_graph_returns_empty_results", degrees_all_on_empty_graph_returns_empty_results),
    ]);
}

fn bfs_accepts_i64_sources_for_i64_graphs() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("bfs_accepts_i64_sources_for_i64_graphs").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I64).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let sources = DeviceArray::from_slice(&entered, &[0i64]).expect("sources");
    let sources_view = sources.view().expect("sources_view");

    let result = graph.bfs(&entered, &sources_view, &BfsParams::default().with_predecessors()).expect("bfs");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I64(_)));
    let distances = result.distances().expect("distances");
    assert!(matches!(distances, Distances::I64(_)));
    let predecessors = result.predecessors().expect("predecessors").expect("predecessor values");
    assert!(matches!(predecessors, VertexIds::I64(_)));

    let distance_map = bfs_distance_map_i64_result(&entered, &result);

    assert_eq!(distance_map[&0], 0);
    assert_eq!(distance_map[&1], 1);
    assert_eq!(distance_map[&2], 2);
    assert_eq!(distance_map[&3], 3);
}

fn betweenness_accepts_i64_seed_vertices() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("betweenness_accepts_i64_seed_vertices").expect("entered");
    let src = DeviceArray::from_slice(&entered, DIRECTED_STAR_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, DIRECTED_STAR_DST_I64).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let seeds = DeviceArray::from_slice(&entered, &[0i64, 1]).expect("seeds");
    let seeds_view = seeds.view().expect("seeds_view");

    let result = graph
        .betweenness_centrality(&entered, &seeds_view, &BetweennessCentralityParams::default())
        .expect("betweenness");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I64(_)));
    assert_eq!(vertex_ids.len(), 4);

    let scores = result.scores().expect("scores");
    let values = scores.to_vec_f64(&entered).expect("score copy");
    assert_eq!(values.len(), 4);
    assert!(values.iter().all(|v| v.is_finite() && *v >= 0.0));
}

fn betweenness_rejects_out_of_range_seed_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("betweenness_rejects_out_of_range_seed_vertex_with_default_params").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let seeds = DeviceArray::from_slice(&entered, &[999i32]).expect("seeds");
    let seeds_view = seeds.view().expect("seeds_view");

    let err = graph
        .betweenness_centrality(&entered, &seeds_view, &BetweennessCentralityParams::default())
        .expect_err("out-of-range seed must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "betweenness_centrality");
}

fn degrees_accept_i64_vertex_subsets() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("degrees_accept_i64_vertex_subsets").expect("entered");
    let src = DeviceArray::from_slice(&entered, DEGREE_SUBSET_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, DEGREE_SUBSET_DST_I64).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");
    let query = DeviceArray::from_slice(&entered, DEGREE_QUERY_I64).expect("query");
    let query_view = query.view().expect("query_view");

    let result = graph.degrees(&entered, &query_view).expect("degrees");

    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i64(&entered).expect("vertex copy");
    let in_degrees = result.in_degrees().expect("in_degrees").to_vec_i64(&entered).expect("in copy");
    let out_degrees = result.out_degrees().expect("out_degrees").to_vec_i64(&entered).expect("out copy");

    let degree_map: HashMap<i64, (i64, i64)> =
        vertices.into_iter().zip(in_degrees.into_iter().zip(out_degrees)).collect();

    assert_eq!(degree_map.len(), 2);
    assert_eq!(degree_map[&0], (1, 1));
    assert_eq!(degree_map[&2], (1, 2));
}

fn in_degrees_checked_accepts_all_vertices() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("in_degrees_checked_accepts_all_vertices").expect("entered");
    let src = DeviceArray::from_slice(&entered, DIRECTED_STAR_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, DIRECTED_STAR_DST_I64).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");

    let result = graph.in_degrees_checked(&entered, VertexSelection::<i64>::All, true).expect("in_degrees_checked");

    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i64(&entered).expect("vertex copy");
    let in_degrees = result.in_degrees().expect("in_degrees").to_vec_i64(&entered).expect("in copy");
    let degree_map: HashMap<i64, i64> = vertices.into_iter().zip(in_degrees).collect();

    assert_eq!(degree_map[&0], 3);
    for v in [1_i64, 2, 3] {
        assert_eq!(degree_map[&v], 1, "leaf vertex {v} should have in-degree 1");
    }
}

fn out_degrees_checked_accepts_all_vertices() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("out_degrees_checked_accepts_all_vertices").expect("entered");
    let src = DeviceArray::from_slice(&entered, DIRECTED_STAR_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, DIRECTED_STAR_DST_I64).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");

    let result = graph.out_degrees_checked(&entered, VertexSelection::<i64>::All, true).expect("out_degrees_checked");

    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i64(&entered).expect("vertex copy");
    let out_degrees = result.out_degrees().expect("out_degrees").to_vec_i64(&entered).expect("out copy");
    let degree_map: HashMap<i64, i64> = vertices.into_iter().zip(out_degrees).collect();

    assert_eq!(degree_map[&0], 3);
    for v in [1_i64, 2, 3] {
        assert_eq!(degree_map[&v], 1, "leaf vertex {v} should have out-degree 1");
    }
}

fn pairwise_similarity_coefficients_match_reference_values() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("pairwise_similarity_coefficients_match_reference_values").expect("entered");
    let mut graph = similarity_fixture_graph(&entered);
    let params = SimilarityParams::default();

    macro_rules! assert_pairwise {
        ($method:ident, $expected:expr) => {{
            let pairs = graph
                .vertex_pairs(&entered, SIMILARITY_PAIR_FIRST_I32, SIMILARITY_PAIR_SECOND_I32)
                .expect("vertex_pairs");
            let result = graph.$method(&entered, pairs, &params).expect(stringify!($method));
            assert_eq!(
                result.first().expect("first").to_vec_i32(&entered).expect("first copy"),
                SIMILARITY_PAIR_FIRST_I32
            );
            assert_eq!(
                result.second().expect("second").to_vec_i32(&entered).expect("second copy"),
                SIMILARITY_PAIR_SECOND_I32
            );
            let scores = result.scores().expect("scores").to_vec_f32(&entered).expect("score copy");
            assert_f32_close(&scores, $expected);
        }};
    }

    assert_pairwise!(jaccard_coefficients, SIMILARITY_JACCARD_F32);
    assert_pairwise!(sorensen_coefficients, SIMILARITY_SORENSEN_F32);
    assert_pairwise!(overlap_coefficients, SIMILARITY_OVERLAP_F32);
    assert_pairwise!(cosine_similarity_coefficients, SIMILARITY_COSINE_F32);
}

fn pairwise_similarity_preserves_explicit_pair_multisets_and_rejects_invalid_endpoints() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle
        .enter("pairwise_similarity_preserves_explicit_pair_multisets_and_rejects_invalid_endpoints")
        .expect("entered");
    let mut graph = similarity_fixture_graph(&entered);
    let checked = SimilarityParams { use_weight: false, do_expensive_check: true };

    let first = [0i32, 0, 1, 0];
    let second = [1i32, 1, 0, 0];
    let pairs = graph.vertex_pairs(&entered, first.as_slice(), second.as_slice()).expect("vertex pairs");
    let result = graph.jaccard_coefficients(&entered, pairs, &checked).expect("Jaccard");
    assert_eq!(result.first().expect("first").to_vec_i32(&entered).expect("first copy"), first);
    assert_eq!(result.second().expect("second").to_vec_i32(&entered).expect("second copy"), second);

    let invalid_first = [99i32];
    let invalid_second = [0i32];
    let invalid_pairs = graph
        .vertex_pairs(&entered, invalid_first.as_slice(), invalid_second.as_slice())
        .expect("vertex-pair container");
    let error = graph
        .jaccard_coefficients(&entered, invalid_pairs, &checked)
        .expect_err("expensive pairwise validation must reject an endpoint absent from the graph");
    assert_eq!(error.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(error.operation(), "jaccard_coefficients");
}

fn pairwise_jaccard_consumes_weights_and_rejects_weighted_calls_without_a_weight_binding() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle
        .enter("pairwise_jaccard_consumes_weights_and_rejects_weighted_calls_without_a_weight_binding")
        .expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 0, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 2, 3]).expect("dst");
    let weights = DeviceArray::from_slice(&entered, &[1.0f32, 2.0, 7.0, 5.0]).expect("weights");
    let src_view = src.view().expect("src view");
    let dst_view = dst.view().expect("dst view");
    let weights_view = weights.view().expect("weights view");
    let mut weighted_graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("weighted graph");
    // `(0, 1)` shares vertex 2.  Its deliberately unequal incident weights
    // make weighted and unweighted Jaccard scores observably distinct.
    let weighted_pair_first = [0i32];
    let weighted_pair_second = [1i32];
    let weighted_pairs = weighted_graph
        .vertex_pairs(&entered, weighted_pair_first.as_slice(), weighted_pair_second.as_slice())
        .expect("weighted pairs");
    let weighted = weighted_graph
        .jaccard_coefficients(
            &entered,
            weighted_pairs,
            &SimilarityParams { use_weight: true, do_expensive_check: true },
        )
        .expect("weighted Jaccard")
        .scores()
        .expect("weighted scores")
        .to_vec_f32(&entered)
        .expect("weighted score copy");
    assert_f32_close(&weighted, &[0.25]);

    let mut unweighted_graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("unweighted graph");
    let unweighted_pair_first = [0i32];
    let unweighted_pair_second = [1i32];
    let unweighted_pairs = unweighted_graph
        .vertex_pairs(&entered, unweighted_pair_first.as_slice(), unweighted_pair_second.as_slice())
        .expect("unweighted pairs");
    let unweighted = unweighted_graph
        .jaccard_coefficients(
            &entered,
            unweighted_pairs,
            &SimilarityParams { use_weight: false, do_expensive_check: true },
        )
        .expect("unweighted Jaccard")
        .scores()
        .expect("unweighted scores")
        .to_vec_f32(&entered)
        .expect("unweighted score copy");
    assert_f32_close(&unweighted, &[0.5]);
    assert!((weighted[0] - unweighted[0]).abs() > 1.0e-4, "weighted Jaccard must not silently use unit weights");

    let missing_weight_pair_first = [0i32];
    let missing_weight_pair_second = [1i32];
    let missing_weight_pairs = unweighted_graph
        .vertex_pairs(&entered, missing_weight_pair_first.as_slice(), missing_weight_pair_second.as_slice())
        .expect("missing-weight pairs");
    let error = unweighted_graph
        .jaccard_coefficients(
            &entered,
            missing_weight_pairs,
            &SimilarityParams { use_weight: true, do_expensive_check: true },
        )
        .expect_err("weighted Jaccard requires a graph weight binding");
    assert_eq!(error.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(error.operation(), "jaccard_coefficients");
}

fn weighted_cosine_returns_zero_for_disjoint_nonempty_neighborhoods() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("weighted_cosine_returns_zero_for_disjoint_nonempty_neighborhoods").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 4, 4]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[2i32, 3, 2, 3]).expect("dst");
    let weights = DeviceArray::from_slice(&entered, &[2.0f32, 3.0, 5.0, 7.0]).expect("weights");
    let src_view = src.view().expect("src view");
    let dst_view = dst.view().expect("dst view");
    let weights_view = weights.view().expect("weights view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");
    let first = [0i32, 0];
    let second = [1i32, 4];
    let pairs =
        graph.vertex_pairs(&entered, first.as_slice(), second.as_slice()).expect("disjoint and shared-neighbor pairs");

    let scores = graph
        .cosine_similarity_coefficients(
            &entered,
            pairs,
            &SimilarityParams { use_weight: true, do_expensive_check: true },
        )
        .expect("weighted cosine")
        .scores()
        .expect("scores")
        .to_vec_f32(&entered)
        .expect("score copy");

    assert_eq!(scores[0], 0.0);
    // 10 / (2 * sqrt(74)) over full neighborhoods {2:2} and {2:5, 3:7}.
    assert!((scores[1] - 0.581_238_2).abs() < 1.0e-5, "weighted cosine expected 0.5812382, got {}", scores[1]);
}

fn all_pairs_jaccard_returns_generated_vertex_pairs() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("all_pairs_jaccard_returns_generated_vertex_pairs").expect("entered");
    let mut graph = similarity_fixture_graph(&entered);

    let result = graph
        .all_pairs_jaccard_coefficients(&entered, VertexSelection::<i32>::All, &AllPairsSimilarityParams::default())
        .expect("all_pairs_jaccard");

    let first = result.first().expect("first").to_vec_i32(&entered).expect("first copy");
    let second = result.second().expect("second").to_vec_i32(&entered).expect("second copy");
    let scores = result.scores().expect("scores").to_vec_f32(&entered).expect("score copy");
    assert_eq!(first.len(), ALL_PAIRS_JACCARD_F32.len());
    assert_eq!(second.len(), ALL_PAIRS_JACCARD_F32.len());
    assert_eq!(scores.len(), ALL_PAIRS_JACCARD_F32.len());

    let score_map: HashMap<(i32, i32), f32> = first.into_iter().zip(second).zip(scores).collect();
    for ((&first, &second), &expected) in
        ALL_PAIRS_JACCARD_FIRST_I32.iter().zip(ALL_PAIRS_JACCARD_SECOND_I32).zip(ALL_PAIRS_JACCARD_F32)
    {
        let actual = score_map
            .get(&(first, second))
            .copied()
            .unwrap_or_else(|| panic!("missing all-pairs score for ({first}, {second})"));
        assert_f32_close(&[actual], &[expected]);
    }
}

fn all_pairs_similarity_methods_return_consistent_columns() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("all_pairs_similarity_methods_return_consistent_columns").expect("entered");
    let mut graph = similarity_fixture_graph(&entered);
    let params = AllPairsSimilarityParams::default();

    macro_rules! assert_all_pairs_shape {
        ($method:ident) => {{
            let result = graph.$method(&entered, VertexSelection::<i32>::All, &params).expect(stringify!($method));
            let first = result.first().expect("first");
            let second = result.second().expect("second");
            let scores = result.scores().expect("scores");
            assert_eq!(first.len(), second.len());
            assert_eq!(first.len(), scores.len());
            assert!(!scores.is_empty(), "{} should return at least one score", stringify!($method));
            let scores = scores.to_vec_f32(&entered).expect("score copy");
            assert!(scores.iter().all(|score| score.is_finite() && *score >= 0.0 && *score <= 1.0));
        }};
    }

    assert_all_pairs_shape!(all_pairs_sorensen_coefficients);
    assert_all_pairs_shape!(all_pairs_overlap_coefficients);
    assert_all_pairs_shape!(all_pairs_cosine_similarity_coefficients);
}

fn vertex_pairs_rejects_mismatched_pair_lengths() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("vertex_pairs_rejects_mismatched_pair_lengths").expect("entered");
    let mut graph = similarity_fixture_graph(&entered);

    let err = graph
        .vertex_pairs(&entered, &[0i32, 1][..], &[1i32][..])
        .expect_err("mismatched pair lengths should be rejected");
    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "Graph::vertex_pairs");
}

fn random_walk_fixture(handle: &cugraph::EnteredContext<'_>) -> (Graph<Forward>, DeviceArray<i32>) {
    let src = DeviceArray::from_slice(handle, &[0i32, 1, 1, 2, 2, 2, 3, 4]).expect("src");
    let dst = DeviceArray::from_slice(handle, &[1i32, 3, 4, 0, 1, 3, 5, 5]).expect("dst");
    let weights = DeviceArray::from_slice(handle, &[1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]).expect("weights");
    let starts = DeviceArray::from_slice(handle, &[2i32, 2]).expect("starts");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");
    let graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .renumber()
        .build::<Forward>(handle)
        .expect("graph");

    (graph, starts)
}

fn neighbor_sampling_fixture(
    handle: &cugraph::EnteredContext<'_>,
) -> (Graph<Forward>, DeviceArray<i32>, DeviceArray<i32>) {
    let src = DeviceArray::from_slice(handle, &[0i32, 1, 1, 2, 2, 2, 3, 4]).expect("src");
    let dst = DeviceArray::from_slice(handle, &[1i32, 3, 4, 0, 1, 3, 5, 5]).expect("dst");
    let weights = DeviceArray::from_slice(handle, &[0.1f32, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8]).expect("weights");
    let edge_ids = DeviceArray::from_slice(handle, &[0i32, 1, 2, 3, 4, 5, 6, 7]).expect("edge_ids");
    let edge_types = DeviceArray::from_slice(handle, &[7i32, 6, 5, 4, 3, 2, 1, 0]).expect("edge_types");
    let start_times = DeviceArray::from_slice(handle, &[0i32, 1, 2, 3, 4, 5, 6, 7]).expect("start_times");
    let end_times = DeviceArray::from_slice(handle, &[1i32, 2, 3, 4, 5, 6, 7, 8]).expect("end_times");
    let starts = DeviceArray::from_slice(handle, &[2i32, 3]).expect("starts");
    let vertex_times = DeviceArray::from_slice(handle, &[0i32, 0]).expect("vertex_times");

    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");
    let edge_ids_view = edge_ids.view().expect("edge_ids_view");
    let edge_types_view = edge_types.view().expect("edge_types_view");
    let start_times_view = start_times.view().expect("start_times_view");
    let end_times_view = end_times.view().expect("end_times_view");
    let graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .edge_ids(&edge_ids_view)
        .edge_type_ids(&edge_types_view)
        .edge_start_time_ids(&start_times_view)
        .edge_end_time_ids(&end_times_view)
        .renumber()
        .build::<Forward>(handle)
        .expect("graph");

    (graph, starts, vertex_times)
}

fn assert_random_walk_shape(
    handle: &cugraph::EnteredContext<'_>,
    result: &RandomWalkResult,
    starts: &[i32],
    max_length: usize,
) {
    assert_eq!(result.max_path_length(), max_length);
    let paths = result.paths().expect("paths");
    let path_values = match paths {
        VertexIds::I32(paths) => paths.to_vec(handle).expect("path copy"),
        _ => panic!("expected i32 random-walk paths"),
    };
    assert_eq!(path_values.len(), starts.len() * (max_length + 1));
    for (row, &start) in starts.iter().enumerate() {
        assert_eq!(path_values[row * (max_length + 1)], start);
    }

    let weights = result.weights().expect("weights").expect("weighted graph should produce weights");
    assert_eq!(weights.len(), starts.len() * max_length);
    let weight_values = match weights {
        ScoreValues::F32(weights) => weights.to_vec(handle).expect("weight copy"),
        _ => panic!("expected f32 random-walk weights"),
    };
    assert_eq!(weight_values.len(), starts.len() * max_length);
}

fn neighbor_sampling_params() -> NeighborSamplingParams {
    let mut params = NeighborSamplingParams::new(vec![2]);
    params.options.return_hops = true;
    params.options.temporal_sampling_comparison = TemporalSamplingComparison::MonotonicallyIncreasing;
    params
}

fn assert_neighbor_sample_columns(
    handle: &cugraph::EnteredContext<'_>,
    result: &SampleResult,
    expect_temporal_columns: bool,
) {
    let minors = result.minors().expect("minors");
    let len = minors.len();
    assert!(len > 0, "sample should contain at least one edge");

    let majors = result.majors().expect("majors").expect("COO output should include majors");
    assert_eq!(majors.len(), len);
    assert!(result.major_offsets().expect("major_offsets").is_none());

    let edge_weights = result.edge_weights().expect("edge_weights").expect("weighted graph should produce weights");
    assert_eq!(edge_weights.len(), len);
    let edge_ids = result.edge_ids().expect("edge_ids").expect("graph edge ids should be returned");
    assert_eq!(edge_ids.len(), len);
    let edge_types = result.edge_types().expect("edge_types").expect("graph edge types should be returned");
    assert_eq!(edge_types.len(), len);
    let hops = result.hops().expect("hops");

    assert_eq!(minors.to_vec_i32(handle).expect("minor copy").len(), len);
    assert_eq!(majors.to_vec_i32(handle).expect("major copy").len(), len);
    assert_eq!(edge_weights.to_vec_f32(handle).expect("weight copy").len(), len);
    assert_eq!(edge_ids.to_vec_i32(handle).expect("edge id copy").len(), len);
    assert_eq!(edge_types.to_vec_i32(handle).expect("edge type copy").len(), len);
    if let Some(hops) = hops {
        assert_eq!(hops.len(), len);
        assert_eq!(hops.to_vec_i32(handle).expect("hop copy").len(), len);
    }

    if expect_temporal_columns {
        let edge_start_times = result.edge_start_times().expect("edge_start_times");
        let edge_end_times = result.edge_end_times().expect("edge_end_times");
        if let Some(edge_start_times) = edge_start_times {
            assert_eq!(edge_start_times.len(), len);
        }
        if let Some(edge_end_times) = edge_end_times {
            assert_eq!(edge_end_times.len(), len);
        }
    }
}

fn random_walk_algorithms_return_dense_paths_and_weights() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("random_walk_algorithms_return_dense_paths_and_weights").expect("entered");
    let starts_data = [2i32, 2];
    let params = RandomWalkParams { max_length: NonZeroUsize::new(3).expect("max length") };

    let (mut graph, starts) = random_walk_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph.uniform_random_walks(&entered, &mut rng, &starts_view, &params).expect("uniform walks");
    assert_random_walk_shape(&entered, &result, &starts_data, params.max_length.get());

    let (mut graph, starts) = random_walk_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph.biased_random_walks(&entered, &mut rng, &starts_view, &params).expect("biased walks");
    assert_random_walk_shape(&entered, &result, &starts_data, params.max_length.get());

    let (mut graph, starts) = random_walk_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let node2vec_params = Node2VecRandomWalkParams {
        max_length: params.max_length,
        p: PositiveF64::new(5.0).expect("p"),
        q: PositiveF64::new(9.0).expect("q"),
    };
    let result =
        graph.node2vec_random_walks(&entered, &mut rng, &starts_view, &node2vec_params).expect("node2vec walks");
    assert_random_walk_shape(&entered, &result, &starts_data, node2vec_params.max_length.get());
}

fn unweighted_random_walks_omit_weights() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("unweighted_random_walks_omit_weights").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 3, 0]).expect("dst");
    let starts = DeviceArray::from_slice(&entered, &[0i32]).expect("starts");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let starts_view = starts.view().expect("starts_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let params = RandomWalkParams { max_length: NonZeroUsize::new(2).expect("max length") };

    let result = graph.uniform_random_walks(&entered, &mut rng, &starts_view, &params).expect("uniform walks");

    assert_eq!(result.max_path_length(), 2);
    assert!(result.weights().expect("weights").is_none());
    assert_eq!(result.paths().expect("paths").len(), 3);
}

fn select_random_vertices_returns_owned_device_array() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("select_random_vertices_returns_owned_device_array").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2, 2, 2, 3, 4]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 3, 4, 0, 1, 3, 5, 5]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let mut rng = RngState::new(&entered, 0).expect("rng");

    let vertices: DeviceArray<i32> = graph.select_random_vertices(&entered, &mut rng, 3).expect("sample vertices");
    let values = vertices.view().expect("sample view").to_vec(&entered).expect("sample copy");

    assert_eq!(values.len(), 3);
    for vertex in values {
        assert!((0..=5).contains(&vertex), "sampled vertex {vertex} should belong to the graph");
    }
}

fn homogeneous_neighbor_sampling_returns_expected_columns() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("homogeneous_neighbor_sampling_returns_expected_columns").expect("entered");
    let params = neighbor_sampling_params();

    let (mut graph, starts, _) = neighbor_sampling_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph
        .homogeneous_uniform_neighbor_sample(&entered, &mut rng, &starts_view, None, &params)
        .expect("uniform neighbor sample");
    assert_neighbor_sample_columns(&entered, &result, false);

    let (mut graph, starts, _) = neighbor_sampling_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph
        .homogeneous_biased_neighbor_sample(&entered, &mut rng, &starts_view, None, &params)
        .expect("biased neighbor sample");
    assert_neighbor_sample_columns(&entered, &result, false);
}

fn temporal_neighbor_sampling_is_callable_with_start_times() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("temporal_neighbor_sampling_is_callable_with_start_times").expect("entered");
    let params = neighbor_sampling_params();

    let (mut graph, starts, vertex_times) = neighbor_sampling_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let times_view = vertex_times.view().expect("times_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph
        .homogeneous_uniform_temporal_neighbor_sample(
            &entered,
            &mut rng,
            "edge_start_time",
            &starts_view,
            Some(&times_view),
            None,
            &params,
        )
        .expect("uniform temporal neighbor sample");
    assert_neighbor_sample_columns(&entered, &result, true);

    let (mut graph, starts, vertex_times) = neighbor_sampling_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let times_view = vertex_times.view().expect("times_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let result = graph
        .homogeneous_biased_temporal_neighbor_sample(
            &entered,
            &mut rng,
            "edge_start_time",
            &starts_view,
            Some(&times_view),
            None,
            &params,
        )
        .expect("biased temporal neighbor sample");
    assert_neighbor_sample_columns(&entered, &result, true);
}

fn temporal_neighbor_sampling_rejects_start_time_length_mismatch() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("temporal_neighbor_sampling_rejects_start_time_length_mismatch").expect("entered");
    let params = neighbor_sampling_params();
    let (mut graph, starts, _) = neighbor_sampling_fixture(&entered);
    let starts_view = starts.view().expect("starts_view");
    let wrong_times = DeviceArray::from_slice(&entered, &[0i32]).expect("wrong_times");
    let wrong_times_view = wrong_times.view().expect("wrong_times_view");
    let mut rng = RngState::new(&entered, 0).expect("rng");

    let err = graph
        .homogeneous_uniform_temporal_neighbor_sample(
            &entered,
            &mut rng,
            "edge_start_time",
            &starts_view,
            Some(&wrong_times_view),
            None,
            &params,
        )
        .expect_err("mismatched start times should be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "homogeneous_uniform_temporal_neighbor_sample");
}

fn bfs_rejects_vertex_selection_all() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("bfs_rejects_vertex_selection_all").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let err =
        graph.bfs(&entered, VertexSelection::<i32>::All, &BfsParams::default()).expect_err("bfs should reject All");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "Graph::bfs");
}

fn sssp_weighted_graph_returns_float_distances_and_predecessors() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("sssp_weighted_graph_returns_float_distances_and_predecessors").expect("entered");
    let src = DeviceArray::from_slice(&entered, SSSP_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, SSSP_GRAPH_DST_I32).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, SSSP_GRAPH_WEIGHT_F32).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&wgt_view)
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let params = SsspParams::default().with_cutoff(NonNegativeF64::new(10.0).expect("cutoff")).with_predecessors();
    let result = graph.sssp(&entered, 0i32, &params).expect("sssp");

    assert!(matches!(result.distances().expect("distances"), Distances::F32(_)));
    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertices");
    let distances = result.distances().expect("distances").to_vec_f32(&entered).expect("distances");
    let predecessors = result
        .predecessors()
        .expect("predecessors")
        .expect("predecessors should exist")
        .to_vec_i32(&entered)
        .expect("predecessors");

    let distance_map: HashMap<i32, f32> = vertices.iter().copied().zip(distances).collect();
    let predecessor_map: HashMap<i32, i32> = vertices.into_iter().zip(predecessors).collect();

    assert!((distance_map[&0] - 0.0).abs() < 1.0e-5);
    assert!((distance_map[&1] - 0.1).abs() < 1.0e-5);
    assert!(distance_map[&2] > 1.0e30, "unreachable vertex should use f32::MAX sentinel");
    assert!((distance_map[&3] - 2.2).abs() < 1.0e-5);
    assert!((distance_map[&4] - 1.2).abs() < 1.0e-5);
    assert!((distance_map[&5] - 4.4).abs() < 1.0e-5);
    assert_eq!(predecessor_map[&0], -1);
    assert_eq!(predecessor_map[&1], 0);
    assert_eq!(predecessor_map[&2], -1);
    assert_eq!(predecessor_map[&3], 1);
    assert_eq!(predecessor_map[&4], 1);
    assert_eq!(predecessor_map[&5], 4);
}

fn sssp_unweighted_graph_uses_unit_edge_costs() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("sssp_unweighted_graph_uses_unit_edge_costs").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 3]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");

    let result = graph
        .sssp(&entered, 0i32, &SsspParams::default().with_predecessors())
        .expect("unweighted SSSP must remain process-safe");
    let vertices = result.vertex_ids().expect("vertices").to_vec_i32(&entered).expect("vertices");
    let distances = result.distances().expect("distances").to_vec_f32(&entered).expect("distances");
    let distance_map = vertices.into_iter().zip(distances).collect::<HashMap<_, _>>();

    assert_eq!(distance_map[&0], 0.0);
    assert_eq!(distance_map[&1], 1.0);
    assert_eq!(distance_map[&2], 2.0);
    assert_eq!(distance_map[&3], 3.0);
}

fn sssp_without_predecessors_omits_predecessor_column() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("sssp_without_predecessors_omits_predecessor_column").expect("entered");
    let src = DeviceArray::from_slice(&entered, SSSP_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, SSSP_GRAPH_DST_I32).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, SSSP_GRAPH_WEIGHT_F64).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&wgt_view)
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result = graph.sssp(&entered, 0i32, &SsspParams::default()).expect("sssp");

    assert!(matches!(result.distances().expect("distances"), Distances::F64(_)));
    assert!(result.predecessors().expect("predecessors").is_none());
}

fn extract_paths_from_bfs_and_sssp_results() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("extract_paths_from_bfs_and_sssp_results").expect("entered");
    let src = DeviceArray::from_slice(&entered, SSSP_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, SSSP_GRAPH_DST_I32).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, SSSP_GRAPH_WEIGHT_F32).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph =
        GraphBuilder::new(&src_view, &dst_view).weights(&wgt_view).build::<Forward>(&entered).expect("graph");
    let sources = DeviceArray::from_slice(&entered, &[0i32]).expect("sources");
    let destinations = DeviceArray::from_slice(&entered, &[5i32]).expect("destinations");
    let sources_view = sources.view().expect("sources_view");
    let destinations_view = destinations.view().expect("destinations_view");

    let bfs_result = graph.bfs(&entered, &sources_view, &BfsParams::default().with_predecessors()).expect("bfs");
    let bfs_paths =
        bfs_result.extract_paths(&entered, &mut graph, &sources_view, &destinations_view).expect("bfs extract paths");
    assert_eq!(bfs_paths.max_path_length(), 4);
    let bfs_path_values = bfs_paths.paths().expect("paths").to_vec_i32(&entered).expect("paths");
    assert_eq!(bfs_path_values, vec![0, 1, 3, 5]);

    let sssp_result = graph.sssp(&entered, 0i32, &SsspParams::default().with_predecessors()).expect("sssp");
    let sssp_paths =
        sssp_result.extract_paths(&entered, &mut graph, &sources_view, &destinations_view).expect("sssp extract paths");
    assert_eq!(sssp_paths.max_path_length(), 4);
    let sssp_path_values = sssp_paths.paths().expect("paths").to_vec_i32(&entered).expect("paths");
    assert_eq!(sssp_path_values, vec![0, 1, 4, 5]);

    let destinations = DeviceArray::from_slice(&entered, &[5i32, 1, 0, 4, 5]).expect("destinations");
    let destinations_view = destinations.view().expect("destinations_view");
    let paths =
        sssp_result.extract_paths(&entered, &mut graph, &sources_view, &destinations_view).expect("ordered SSSP paths");
    assert_eq!(paths.max_path_length(), 4);
    assert_eq!(
        paths.paths().expect("paths").to_vec_i32(&entered).expect("paths"),
        vec![0, 1, 4, 5, -1, -1, 0, 1, -1, -1, -1, 0, -1, 0, 1, 4, 0, 1, 4, 5]
    );

    let src = DeviceArray::from_slice(&entered, &[10i64, 20, 10, 40]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[20i64, 30, 30, 50]).expect("dst");
    let weights = DeviceArray::from_slice(&entered, &[0.25f64, 0.5, 2.5, 1.0]).expect("weights");
    let (src_view, dst_view, weights_view) =
        (src.view().expect("src_view"), dst.view().expect("dst_view"), weights.view().expect("weights_view"));
    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .renumber()
        .build::<Forward>(&entered)
        .expect("i64/f64 graph");
    let sssp = graph.sssp(&entered, 10i64, &SsspParams::default().with_predecessors()).expect("sssp");
    let paths =
        sssp.extract_paths(&entered, &mut graph, &[10i64][..], &[30i64, 10, 20, 30][..]).expect("i64/f64 paths");
    assert_eq!(paths.max_path_length(), 3);
    assert_eq!(
        paths.paths().expect("paths").to_vec_i64(&entered).expect("paths"),
        vec![10, 20, 30, -1, -1, 10, -1, 10, 20, 10, 20, 30]
    );
    for (sources, destinations) in [
        (&[10i64, 20][..], &[30i64][..]),
        (&[10i64][..], &[50i64][..]),
        (&[10i64][..], &[99i64][..]),
        (&[20i64][..], &[10i64][..]),
    ] {
        let error = sssp.extract_paths(&entered, &mut graph, sources, destinations).expect_err("invalid extraction");
        assert_eq!(error.kind(), ErrorKind::InvalidInput);
        assert_eq!(error.operation(), "SsspResult::extract_paths");
    }

    let vertices = sssp.vertex_ids().expect("vertices").to_vec_i64(&entered).expect("vertices");
    let predecessors = sssp.predecessors().expect("predecessors").expect("computed predecessors");
    let VertexIds::I64(predecessors) = predecessors else { panic!("expected i64 predecessors") };
    let cycle: Vec<i64> = vertices
        .iter()
        .map(|vertex| match vertex {
            20 => 30,
            30 => 20,
            50 => 40,
            _ => -1,
        })
        .collect();
    // SAFETY: the result retains writable i64 predecessor storage, and `cycle` has one value
    // for every vertex. The entered handle orders the copy before extraction on the same
    // stream; `cycle` stays live through that extraction. Only temporary view metadata is freed.
    let (code, error) = unsafe {
        let view = cugraph_type_erased_device_array_view_create(
            predecessors.device_ptr(),
            predecessors.len(),
            cugraph_data_type_id_t::INT64,
        );
        assert!(!view.is_null());
        let mut error = ptr::null_mut();
        let code = cugraph_type_erased_device_array_view_copy_from_host(
            entered.handle_ptr(),
            view,
            cycle.as_ptr().cast(),
            &mut error,
        );
        cugraph_type_erased_device_array_view_free(view);
        (code, error)
    };
    if !error.is_null() {
        // SAFETY: the failed copy transfers ownership of this native error to the caller.
        unsafe { cugraph_error_free(error) };
    }
    assert_eq!(code, cugraph_error_code_t::CUGRAPH_SUCCESS);
    let error = sssp.extract_paths(&entered, &mut graph, &[10i64][..], &[30i64][..]).expect_err("predecessor cycle");
    assert_eq!(error.kind(), ErrorKind::InvalidState);
    assert_eq!(error.operation(), "SsspResult::extract_paths");
    for (destinations, expected_kind) in [
        (&[50i64, 30][..], ErrorKind::InvalidInput),
        (&[30i64, 50][..], ErrorKind::InvalidState),
        (&[30i64, 99][..], ErrorKind::InvalidState),
        (&[99i64, 30][..], ErrorKind::InvalidInput),
    ] {
        let error = sssp
            .extract_paths(&entered, &mut graph, &[10i64][..], destinations)
            .expect_err("first failing destination defines the error");
        assert_eq!(error.kind(), expected_kind);
    }
}

fn extract_paths_rejects_results_without_predecessors() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("extract_paths_rejects_results_without_predecessors").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Forward>(&entered).expect("graph");
    let sources = DeviceArray::from_slice(&entered, &[0i32]).expect("sources");
    let destinations = DeviceArray::from_slice(&entered, &[3i32]).expect("destinations");
    let sources_view = sources.view().expect("sources_view");
    let destinations_view = destinations.view().expect("destinations_view");
    let result = graph.bfs(&entered, &sources_view, &BfsParams::default()).expect("bfs");

    let err = result
        .extract_paths(&entered, &mut graph, &sources_view, &destinations_view)
        .expect_err("extract paths should require predecessors");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "BfsResult::extract_paths");

    let result = graph.sssp(&entered, 0i32, &SsspParams::default()).expect("sssp");
    let error = result
        .extract_paths(&entered, &mut graph, &sources_view, &destinations_view)
        .expect_err("SSSP extraction requires predecessors");
    assert_eq!(error.kind(), ErrorKind::InvalidInput);
    assert_eq!(error.operation(), "SsspResult::extract_paths");
}

fn sssp_rejects_source_dtype_mismatch() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("sssp_rejects_source_dtype_mismatch").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I32).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, &[1.0f32, 1.0, 1.0]).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph =
        GraphBuilder::new(&src_view, &dst_view).weights(&wgt_view).build::<Forward>(&entered).expect("graph");

    let err = graph.sssp(&entered, 0i64, &SsspParams::default()).expect_err("i64 source should not match i32 graph");

    assert_eq!(err.kind(), cugraph::ErrorKind::UnsupportedType);
    assert_eq!(err.operation(), "Graph::sssp");
}

fn force_atlas2_accepts_i64_vertices_and_f32_helpers() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("force_atlas2_accepts_i64_vertices_and_f32_helpers").expect("entered");
    let mut rng = RngState::new(&entered, TEST_LAYOUT_SECONDARY_SEED).expect("rng");

    let src = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_SRC_I64).expect("src");
    let dst = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_DST_I64).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_UNIT_WEIGHT_F64).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&wgt_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let pos_vertices = DeviceArray::from_slice(&entered, TRIANGLE_VERTEX_IDS_I64).expect("pos vertices");
    let x = DeviceArray::from_slice(&entered, &[0.0f32, 1.0, -1.0]).expect("x");
    let y = DeviceArray::from_slice(&entered, &[0.0f32, 0.5, -0.5]).expect("y");
    let mass_values = DeviceArray::from_slice(&entered, &[1.0f32, 1.5, 2.0]).expect("mass");
    let pos_vertices_view = pos_vertices.view().expect("pos_vertices_view");
    let x_view = x.view().expect("x_view");
    let y_view = y.view().expect("y_view");
    let mass_values_view = mass_values.view().expect("mass_values_view");

    let params = ForceAtlas2Params {
        max_iter: IterationCount::new(TEST_LAYOUT_SMOKE_ITERATIONS).expect("iter"),
        ..Default::default()
    };
    let init_pos = InitialPositions { vertices: &pos_vertices_view, x: &x_view, y: &y_view };
    let attrs = ForceAtlas2VertexAttrs { mass: Some((&pos_vertices_view, &mass_values_view)), ..Default::default() };

    let result =
        graph.force_atlas2_with(&entered, &mut rng, &params, Some(&attrs), Some(&init_pos)).expect("force_atlas2");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I64(_)));

    let x_coords = result.x().expect("x");
    let y_coords = result.y().expect("y");
    assert!(matches!(x_coords, ScoreValues::F32(_)));
    assert!(matches!(y_coords, ScoreValues::F32(_)));

    let x_values = x_coords.to_vec_f32(&entered).expect("x copy");
    let y_values = y_coords.to_vec_f32(&entered).expect("y copy");
    assert_eq!(x_values.len(), 3);
    assert_eq!(y_values.len(), 3);
    assert!(x_values.iter().all(|v| v.is_finite()));
    assert!(y_values.iter().all(|v| v.is_finite()));
}

fn force_atlas2_rejects_sparse_mass_helpers() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("force_atlas2_rejects_sparse_mass_helpers").expect("entered");
    let mut rng = RngState::new(&entered, TEST_LAYOUT_SECONDARY_SEED).expect("rng");

    let vertex_count = 128i32;
    let mut src_data = Vec::with_capacity(((vertex_count - 1) * 2) as usize);
    let mut dst_data = Vec::with_capacity(((vertex_count - 1) * 2) as usize);
    for v in 0..(vertex_count - 1) {
        src_data.push(v);
        dst_data.push(v + 1);
        src_data.push(v + 1);
        dst_data.push(v);
    }

    let src = DeviceArray::from_slice(&entered, &src_data).expect("src");
    let dst = DeviceArray::from_slice(&entered, &dst_data).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let sparse_mass_vertices = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("mass vertices");
    let sparse_mass_values = DeviceArray::from_slice(&entered, &[1.0f32, 2.0, 3.0]).expect("mass values");
    let sparse_mass_vertices_view = sparse_mass_vertices.view().expect("mass vertices view");
    let sparse_mass_values_view = sparse_mass_values.view().expect("mass values view");

    let params = ForceAtlas2Params { max_iter: IterationCount::new(1).expect("iter"), ..Default::default() };
    let attrs = ForceAtlas2VertexAttrs {
        mass: Some((&sparse_mass_vertices_view, &sparse_mass_values_view)),
        ..Default::default()
    };

    let err = graph
        .force_atlas2_with(&entered, &mut rng, &params, Some(&attrs), None)
        .expect_err("sparse mass helper should be rejected before reaching CUDA");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "force_atlas2");
    assert!(
        err.to_string().contains("vertex mass must provide one value for each graph vertex"),
        "unexpected error: {err}"
    );
}

fn louvain_returns_vertex_partitions_and_finite_modularity() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("louvain_returns_vertex_partitions_and_finite_modularity").expect("entered");
    let src = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let weights = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_WEIGHT_F32).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result = graph.louvain(&entered, &LouvainParams::default()).expect("louvain");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I32(_)));
    let clusters = result.clusters().expect("clusters");
    assert!(matches!(clusters, VertexIds::I32(_)));
    assert_eq!(vertex_ids.len(), clusters.len());
    assert!(!vertex_ids.is_empty());
    assert!(result.modularity().is_finite());
}

fn leiden_returns_vertex_partitions_and_finite_modularity() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("leiden_returns_vertex_partitions_and_finite_modularity").expect("entered");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let src = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let weights = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_WEIGHT_F32).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result = graph.leiden(&entered, &mut rng, &LeidenParams::default()).expect("leiden");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I32(_)));
    let clusters = result.clusters().expect("clusters");
    assert!(matches!(clusters, VertexIds::I32(_)));
    assert_eq!(vertex_ids.len(), clusters.len());
    assert!(!vertex_ids.is_empty());
    assert!(result.modularity().is_finite());
}

/// Seeded planted-partition graph: communities of uneven size with sparse internal edges, and
/// random bridging edges across communities. Weights mimic a similarity graph. Returns each
/// undirected edge once with `src < dst`.
fn planted_partition_graph(seed: u64, vertex_count: i32) -> Vec<(i32, i32, f32)> {
    let mut state = seed;
    let mut next = move || {
        // xorshift64*
        state ^= state >> 12;
        state ^= state << 25;
        state ^= state >> 27;
        state.wrapping_mul(0x2545_f491_4f6c_dd1d)
    };
    let mut community_starts = vec![0i32];
    while *community_starts.last().unwrap() < vertex_count {
        let size = 8 + (next() % 120) as i32;
        community_starts.push((community_starts.last().unwrap() + size).min(vertex_count));
    }
    let mut edges = std::collections::BTreeMap::new();
    let mut add = |a: i32, b: i32, weight: f32| {
        if a != b {
            edges.entry((a.min(b), a.max(b))).or_insert(weight);
        }
    };
    for window in community_starts.windows(2) {
        let (first, last) = (window[0], window[1]);
        let size = (last - first) as u64;
        for _ in 0..size * 3 {
            let a = first + (next() % size) as i32;
            let b = first + (next() % size) as i32;
            add(a, b, 0.05 + (next() % 1000) as f32 / 1000.0);
        }
    }
    for _ in 0..vertex_count as u64 {
        let a = (next() % vertex_count as u64) as i32;
        let b = (next() % vertex_count as u64) as i32;
        add(a, b, 0.02 + (next() % 200) as f32 / 1000.0);
    }
    edges.into_iter().map(|((a, b), weight)| (a, b, weight)).collect()
}

/// Modularity of a partition of an undirected weighted graph given once per edge, in the form
/// libcugraph uses: the intra-community weight fraction minus `resolution` times the sum of
/// squared community degree fractions.
fn partition_modularity(edges: &[(i32, i32, f32)], vertices: &[i32], clusters: &[i32], resolution: f64) -> f64 {
    let cluster_of: HashMap<i32, i32> = vertices.iter().copied().zip(clusters.iter().copied()).collect();
    let mut total_weight = 0.0;
    let mut intra_weight = 0.0;
    let mut cluster_degree: HashMap<i32, f64> = HashMap::new();
    for &(a, b, weight) in edges {
        let weight = f64::from(weight);
        total_weight += weight;
        if cluster_of[&a] == cluster_of[&b] {
            intra_weight += weight;
        }
        *cluster_degree.entry(cluster_of[&a]).or_default() += weight;
        *cluster_degree.entry(cluster_of[&b]).or_default() += weight;
    }
    let squared_degree_fractions =
        cluster_degree.values().map(|degree| (degree / (2.0 * total_weight)).powi(2)).sum::<f64>();
    intra_weight / total_weight - resolution * squared_degree_fractions
}

/// Number of communities whose members induce a disconnected subgraph.
fn disconnected_community_count(edges: &[(i32, i32, f32)], vertices: &[i32], clusters: &[i32]) -> usize {
    let cluster_of: HashMap<i32, i32> = vertices.iter().copied().zip(clusters.iter().copied()).collect();
    let mut parent: HashMap<i32, i32> = vertices.iter().map(|&vertex| (vertex, vertex)).collect();
    fn root(parent: &mut HashMap<i32, i32>, vertex: i32) -> i32 {
        let mut current = vertex;
        while parent[&current] != current {
            let grandparent = parent[&parent[&current]];
            parent.insert(current, grandparent);
            current = grandparent;
        }
        current
    }
    for &(a, b, _) in edges {
        if cluster_of[&a] == cluster_of[&b] {
            let (root_a, root_b) = (root(&mut parent, a), root(&mut parent, b));
            parent.insert(root_a, root_b);
        }
    }
    let mut components_per_cluster: HashMap<i32, std::collections::HashSet<i32>> = HashMap::new();
    for &vertex in vertices {
        let component = root(&mut parent, vertex);
        components_per_cluster.entry(cluster_of[&vertex]).or_default().insert(component);
    }
    components_per_cluster.values().filter(|components| components.len() > 1).count()
}

fn leiden_communities_induce_connected_subgraphs_and_report_their_modularity() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered =
        handle.enter("leiden_communities_induce_connected_subgraphs_and_report_their_modularity").expect("entered");
    for &(graph_seed, resolution) in LEIDEN_CONNECTIVITY_CASES {
        let edges = planted_partition_graph(graph_seed, 30_000);
        let (src, dst, weights): (Vec<i32>, Vec<i32>, Vec<f32>) = edges
            .iter()
            .flat_map(|&(a, b, weight)| [(a, b, weight), (b, a, weight)])
            .fold((Vec::new(), Vec::new(), Vec::new()), |(mut src, mut dst, mut weights), (a, b, weight)| {
                src.push(a);
                dst.push(b);
                weights.push(weight);
                (src, dst, weights)
            });
        let src = DeviceArray::from_slice(&entered, &src).expect("src");
        let dst = DeviceArray::from_slice(&entered, &dst).expect("dst");
        let weights = DeviceArray::from_slice(&entered, &weights).expect("weights");
        let src_view = src.view().expect("src_view");
        let dst_view = dst.view().expect("dst_view");
        let weights_view = weights.view().expect("weights_view");
        let mut graph = GraphBuilder::new(&src_view, &dst_view)
            .weights(&weights_view)
            .properties(GraphProperties::undirected())
            .renumber()
            .build::<Forward>(&entered)
            .expect("graph");
        let mut rng = RngState::new(&entered, 42).expect("rng");
        let params = LeidenParams { resolution: PositiveF64::new(resolution).unwrap(), ..LeidenParams::default() };

        let result = graph.leiden(&entered, &mut rng, &params).expect("leiden");

        let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertices");
        let clusters = result.clusters().expect("clusters").to_vec_i32(&entered).expect("clusters");
        let case = format!("graph seed {graph_seed}, resolution {resolution}");
        assert_eq!(disconnected_community_count(&edges, &vertices, &clusters), 0, "{case}");
        let modularity = partition_modularity(&edges, &vertices, &clusters, resolution);
        assert!(
            (result.modularity() - modularity).abs() < 1e-4,
            "{case}: reported {} for {modularity}",
            result.modularity()
        );
    }
}

fn ecg_returns_vertex_partitions_and_finite_modularity() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("ecg_returns_vertex_partitions_and_finite_modularity").expect("entered");
    let mut rng = RngState::new(&entered, 0).expect("rng");
    let src = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let weights = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_WEIGHT_F32).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result = graph.ecg(&entered, &mut rng, &EcgParams::default()).expect("ecg");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I32(_)));
    let clusters = result.clusters().expect("clusters");
    assert!(matches!(clusters, VertexIds::I32(_)));
    assert_eq!(vertex_ids.len(), clusters.len());
    assert!(!vertex_ids.is_empty());
    assert!(result.modularity().is_finite());
}

fn weakly_connected_components_labels_two_symmetric_components() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("weakly_connected_components_labels_two_symmetric_components").expect("entered");
    let src = DeviceArray::from_slice(&entered, DISCONNECTED_TWO_CYCLES_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, DISCONNECTED_TWO_CYCLES_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result = graph.weakly_connected_components(&entered, &ConnectedComponentsParams::default()).expect("wcc");

    let vertex_ids = result.vertex_ids().expect("vertex_ids");
    assert!(matches!(vertex_ids, VertexIds::I32(_)));
    let labels = result.labels().expect("labels");
    assert!(matches!(labels, IntegerValues::I32(_)));

    let vertices = vertex_ids.to_vec_i32(&entered).expect("vertices");
    let labels = labels.to_vec_i32(&entered).expect("labels");
    let label_map: HashMap<i32, i32> = vertices.into_iter().zip(labels).collect();

    assert_eq!(label_map[&0], label_map[&1]);
    assert_eq!(label_map[&2], label_map[&3]);
    assert_ne!(label_map[&0], label_map[&2]);
}

fn strongly_connected_components_labels_directed_components() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("strongly_connected_components_labels_directed_components").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2, 3]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 0, 2, 3, 2]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");

    let result = graph.strongly_connected_components(&entered, &ConnectedComponentsParams::default()).expect("scc");

    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertices");
    let labels = result.labels().expect("labels").to_vec_i32(&entered).expect("labels");
    let label_map: HashMap<i32, i32> = vertices.into_iter().zip(labels).collect();

    assert_eq!(label_map[&0], label_map[&1]);
    assert_eq!(label_map[&2], label_map[&3]);
    assert_ne!(label_map[&0], label_map[&2]);
}

fn core_number_on_triangle_tail_returns_stable_core_values() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("core_number_on_triangle_tail_returns_stable_core_values").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2, 1, 2, 0, 2, 3]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0, 0, 1, 2, 3, 2]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let params = CoreNumberParams { degree_type: KCoreDegreeType::Out, do_expensive_check: false };
    let result = graph.core_number(&entered, &params).expect("core_number");

    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertices");
    let core_numbers = result.core_numbers().expect("core_numbers").to_vec_i32(&entered).expect("core numbers");
    let core_map: HashMap<i32, i32> = vertices.into_iter().zip(core_numbers).collect();

    assert_eq!(core_map[&0], 2);
    assert_eq!(core_map[&1], 2);
    assert_eq!(core_map[&2], 2);
    assert_eq!(core_map[&3], 1);
}

fn triangle_count_all_and_start_vertices_return_expected_counts() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("triangle_count_all_and_start_vertices_return_expected_counts").expect("entered");
    let src = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let params = TriangleCountParams::default();
    let all = graph.triangle_count_all(&entered, &params).expect("triangle_count all");
    let all_vertices = all.vertex_ids().expect("vertices").to_vec_i32(&entered).expect("vertices");
    let all_counts = all.counts().expect("counts").to_vec_i32(&entered).expect("counts");
    let all_map: HashMap<i32, i32> = all_vertices.into_iter().zip(all_counts).collect();

    assert_eq!(all_map.len(), 3);
    assert_eq!(all_map[&0], 1);
    assert_eq!(all_map[&1], 1);
    assert_eq!(all_map[&2], 1);

    let start = DeviceArray::from_slice(&entered, &[0i32, 2]).expect("start");
    let start_view = start.view().expect("start_view");
    let subset = graph.triangle_count(&entered, &start_view, &params).expect("triangle_count subset");
    let subset_vertices = subset.vertex_ids().expect("vertices").to_vec_i32(&entered).expect("vertices");
    let subset_counts = subset.counts().expect("counts").to_vec_i32(&entered).expect("counts");
    let subset_map: HashMap<i32, i32> = subset_vertices.into_iter().zip(subset_counts).collect();

    assert_eq!(subset_map.len(), 2);
    assert_eq!(subset_map[&0], 1);
    assert_eq!(subset_map[&2], 1);
}

fn k_core_with_and_without_precomputed_core_numbers_returns_triangle_edges() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered =
        handle.enter("k_core_with_and_without_precomputed_core_numbers_returns_triangle_edges").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2, 1, 2, 0, 2, 3]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0, 0, 1, 2, 3, 2]).expect("dst");
    let wgt = DeviceArray::from_slice(&entered, &[1.0f32; 8]).expect("wgt");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let wgt_view = wgt.view().expect("wgt_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&wgt_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let params = KCoreParams {
        k: NonZeroUsize::new(2).expect("k"),
        degree_type: KCoreDegreeType::Out,
        do_expensive_check: false,
    };
    let result = graph.k_core(&entered, &params).expect("k_core");
    assert!(result.weights().expect("weights").is_some());
    let sources = result.sources().expect("sources").to_vec_i32(&entered).expect("sources");
    let destinations = result.destinations().expect("destinations").to_vec_i32(&entered).expect("destinations");
    assert_eq!(sources.len(), destinations.len());
    assert!(sources.iter().zip(&destinations).all(|(src, dst)| *src < 3 && *dst < 3));

    let core_numbers = graph
        .core_number(&entered, &CoreNumberParams { degree_type: KCoreDegreeType::Out, do_expensive_check: false })
        .expect("core_number");
    let precomputed =
        graph.k_core_with_core_numbers(&entered, &params, &core_numbers).expect("k_core with core numbers");
    assert_eq!(precomputed.sources().expect("sources").len(), result.sources().expect("sources").len());
}

fn k_core_degree_type_selects_the_degree_that_defines_cores() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("k_core_degree_type_selects_the_degree_that_defines_cores").expect("entered");
    // A triangle with pendant vertex 3. Core numbers require an undirected graph, where in- and
    // out-degree coincide and in-out degree doubles them: only `InOut` lifts the pendant into
    // the 2-core.
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2, 1, 2, 0, 2, 3]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0, 0, 1, 2, 3, 2]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let mut core_vertices = |degree_type| {
        let params = KCoreParams { k: NonZeroUsize::new(2).expect("k"), degree_type, do_expensive_check: false };
        let result = graph.k_core(&entered, &params).expect("k_core");
        let mut vertices = result.sources().expect("sources").to_vec_i32(&entered).expect("sources");
        vertices.extend(result.destinations().expect("destinations").to_vec_i32(&entered).expect("destinations"));
        vertices.sort_unstable();
        vertices.dedup();
        vertices
    };

    assert_eq!(core_vertices(KCoreDegreeType::In), vec![0, 1, 2]);
    assert_eq!(core_vertices(KCoreDegreeType::Out), vec![0, 1, 2]);
    assert_eq!(core_vertices(KCoreDegreeType::InOut), vec![0, 1, 2, 3]);
}

fn native_precondition_failure_is_invalid_input_with_the_bare_reason() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("native_precondition_failure_is_invalid_input_with_the_bare_reason").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");

    // `CUGRAPH_EXPECTS` in libcugraph's core-number implementation rejects a directed graph.
    let error = graph
        .core_number(&entered, &CoreNumberParams { degree_type: KCoreDegreeType::InOut, do_expensive_check: false })
        .expect_err("core numbers of a directed graph must be rejected");

    assert_eq!(error.kind(), cugraph::ErrorKind::InvalidInput);
    assert!(error.is_permanent());
    // The reason crosses the C API without the source location and call stack of `what()`.
    assert_eq!(error.message(), "Invalid input argument: core_number currently supports only undirected graphs.");
}

fn minimum_spanning_tree_returns_weighted_edge_result() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("minimum_spanning_tree_returns_weighted_edge_result").expect("entered");
    let src = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let weights = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_WEIGHT_F32).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let result =
        graph.minimum_spanning_tree(&entered, &MinimumSpanningTreeParams::default()).expect("minimum_spanning_tree");
    let sources = result.sources().expect("sources").to_vec_i32(&entered).expect("sources");
    let destinations = result.destinations().expect("destinations").to_vec_i32(&entered).expect("destinations");
    let weights = result.weights().expect("weights").expect("weight column").to_vec_f32(&entered).expect("weights");
    let offsets =
        result.subgraph_offsets().expect("offsets").expect("offset column").to_vec_usize(&entered).expect("offsets");

    assert_eq!(sources.len(), destinations.len());
    assert_eq!(sources.len(), weights.len());
    assert_eq!(sources.len(), 10);
    assert_eq!(offsets, vec![0, sources.len()]);
    assert!(result.edge_ids().expect("edge ids").is_none());
    assert!(result.edge_type_ids().expect("edge type ids").is_none());
}

fn k_truss_subgraph_returns_expected_offsets_and_edges() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("k_truss_subgraph_returns_expected_offsets_and_edges").expect("entered");
    let src = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_DST_I32).expect("dst");
    let weights = DeviceArray::from_slice(&entered, LOUVAIN_GRAPH_WEIGHT_F32).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");

    let params = KTrussSubgraphParams { k: NonZeroUsize::new(3).expect("k"), do_expensive_check: false };
    let result = graph.k_truss_subgraph(&entered, &params).expect("k_truss_subgraph");
    let sources = result.sources().expect("sources").to_vec_i32(&entered).expect("sources");
    let destinations = result.destinations().expect("destinations").to_vec_i32(&entered).expect("destinations");
    let offsets =
        result.subgraph_offsets().expect("offsets").expect("offset column").to_vec_usize(&entered).expect("offsets");

    assert_eq!(sources.len(), destinations.len());
    assert_eq!(sources.len(), 10);
    assert_eq!(offsets, vec![0, sources.len()]);
    assert!(result.weights().expect("weights").is_some());
}

fn extract_ego_returns_per_seed_offsets() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("extract_ego_returns_per_seed_offsets").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2, 2, 2, 3, 3, 4]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 3, 4, 0, 1, 3, 4, 5, 5]).expect("dst");
    let weights =
        DeviceArray::from_slice(&entered, &[0.1f32, 2.1, 1.1, 5.1, 3.1, 4.1, 7.2, 3.2, 6.1]).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");
    let seeds = DeviceArray::from_slice(&entered, &[0i32, 1]).expect("seeds");
    let seeds_view = seeds.view().expect("seeds_view");
    let params = ExtractEgoParams { radius: NonZeroUsize::new(2).expect("radius"), do_expensive_check: false };

    let result = graph.extract_ego(&entered, &seeds_view, &params).expect("extract_ego");
    let sources = result.sources().expect("sources").to_vec_i32(&entered).expect("sources");
    let destinations = result.destinations().expect("destinations").to_vec_i32(&entered).expect("destinations");
    let offsets =
        result.subgraph_offsets().expect("offsets").expect("offset column").to_vec_usize(&entered).expect("offsets");

    assert_eq!(sources.len(), destinations.len());
    assert_eq!(offsets, vec![0, 4, 9]);
    assert_eq!(sources.len(), *offsets.last().expect("last offset"));
}

fn pagerank_on_single_vertex_graph_returns_score_one() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("pagerank_on_single_vertex_graph_returns_score_one").expect("entered");
    let empty: [i32; 0] = [];
    let src = DeviceArray::from_slice(&entered, &empty).expect("src");
    let dst = DeviceArray::from_slice(&entered, &empty).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[0i32]).expect("vertices");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");

    let mut graph =
        GraphBuilder::new(&src_view, &dst_view).vertices(&vertices_view).build::<Transposed>(&entered).expect("graph");

    let result = graph.pagerank(&entered, &PageRankParams::default()).expect("pagerank");
    let returned_vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertex copy");
    let scores = result.scores().expect("scores").to_vec_f32(&entered).expect("score copy");

    assert_eq!(returned_vertices, vec![0]);
    assert_eq!(scores.len(), 1);
    assert!((scores[0] - 1.0).abs() < 1e-6, "single-vertex PageRank should be 1.0, got {}", scores[0]);
    assert!(result.converged().expect("converged"));
}

fn pagerank_on_disconnected_graph_returns_normalized_positive_scores() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("pagerank_on_disconnected_graph_returns_normalized_positive_scores").expect("entered");
    let src = DeviceArray::from_slice(&entered, DISCONNECTED_TWO_CYCLES_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, DISCONNECTED_TWO_CYCLES_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Transposed>(&entered).expect("graph");

    let result = graph.pagerank(&entered, &PageRankParams::default()).expect("pagerank");
    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertex copy");
    let scores = result.scores().expect("scores").to_vec_f32(&entered).expect("score copy");

    let score_map: HashMap<i32, f32> = vertices.into_iter().zip(scores.iter().copied()).collect();
    let total_score: f32 = scores.iter().sum();

    assert_eq!(score_map.len(), 4);
    assert!(scores.iter().all(|score| score.is_finite() && *score > 0.0));
    assert!((total_score - 1.0).abs() < 1e-5, "scores should be normalized, got sum {}", total_score);
    assert!((score_map[&0] - score_map[&1]).abs() < 1e-6);
    assert!((score_map[&2] - score_map[&3]).abs() < 1e-6);
}

fn pagerank_reports_nonconvergence_without_failing() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("pagerank_reports_nonconvergence_without_failing").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Transposed>(&entered).expect("graph");
    let params = PageRankParams {
        epsilon: NonNegativeF64::new(0.0).expect("zero epsilon"),
        max_iterations: IterationCount::new(1).expect("one iteration"),
        ..Default::default()
    };

    let result = graph.pagerank(&entered, &params).expect("pagerank");
    assert!(!result.converged().expect("converged flag"));
}

fn personalized_pagerank_accepts_personalization_vector() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("personalized_pagerank_accepts_personalization_vector").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("vertices");
    let values = DeviceArray::from_slice(&entered, &[1.0f32, 0.0, 0.0]).expect("values");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let values_view = values.view().expect("values_view");
    let personalization = PersonalizationVector { vertices: &vertices_view, values: &values_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Transposed>(&entered).expect("graph");

    let result = graph
        .personalized_pagerank(&entered, &PersonalizedPageRankParams::default(), &personalization)
        .expect("personalized pagerank");
    let vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertex copy");
    let scores = result.scores().expect("scores").to_vec_f32(&entered).expect("score copy");

    assert_eq!(vertices.len(), 3);
    assert_eq!(scores.len(), 3);
    assert!(scores.iter().all(|score| score.is_finite() && *score >= 0.0));
    assert!((scores.iter().sum::<f32>() - 1.0).abs() < 1e-5);
}

fn personalized_pagerank_rejects_mismatched_personalization_lengths() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("personalized_pagerank_rejects_mismatched_personalization_lengths").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("vertices");
    let values = DeviceArray::from_slice(&entered, &[1.0f32, 0.0]).expect("values");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let values_view = values.view().expect("values_view");
    let personalization = PersonalizationVector { vertices: &vertices_view, values: &values_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Transposed>(&entered).expect("graph");

    let err = graph
        .personalized_pagerank(&entered, &PersonalizedPageRankParams::default(), &personalization)
        .expect_err("mismatched personalization must be rejected");
    assert_eq!(err.kind(), ErrorKind::InvalidInput);
}

fn personalized_pagerank_rejects_out_of_range_personalization_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle
        .enter("personalized_pagerank_rejects_out_of_range_personalization_vertex_with_default_params")
        .expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[999i32]).expect("vertices");
    let values = DeviceArray::from_slice(&entered, &[1.0f32]).expect("values");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let values_view = values.view().expect("values_view");
    let personalization = PersonalizationVector { vertices: &vertices_view, values: &values_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).build::<Transposed>(&entered).expect("graph");

    let err = graph
        .personalized_pagerank(&entered, &PersonalizedPageRankParams::default(), &personalization)
        .expect_err("out-of-range personalization vertex must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "personalized_pagerank");
}

fn pagerank_rejects_out_of_range_precomputed_weight_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered =
        handle.enter("pagerank_rejects_out_of_range_precomputed_weight_vertex_with_default_params").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[999i32]).expect("vertices");
    let sums = DeviceArray::from_slice(&entered, &[1.0f32]).expect("sums");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let sums_view = sums.view().expect("sums_view");
    let precomputed = PrecomputedWeights { vertices: &vertices_view, sums: &sums_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");

    let err = graph
        .pagerank_with(&entered, &PageRankParams::default(), Some(&precomputed), None)
        .expect_err("out-of-range precomputed weight vertex must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "pagerank");
}

fn pagerank_rejects_out_of_range_initial_guess_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered =
        handle.enter("pagerank_rejects_out_of_range_initial_guess_vertex_with_default_params").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 0]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[999i32]).expect("vertices");
    let values = DeviceArray::from_slice(&entered, &[1.0f32]).expect("values");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let values_view = values.view().expect("values_view");
    let initial_guess = InitialGuess { vertices: &vertices_view, values: &values_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");

    let err = graph
        .pagerank_with(&entered, &PageRankParams::default(), None, Some(&initial_guess))
        .expect_err("out-of-range initial guess vertex must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "pagerank");
}

fn vertex_centrality_expansion_algorithms_return_vertex_scores() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("vertex_centrality_expansion_algorithms_return_vertex_scores").expect("entered");
    let src = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, UNDIRECTED_TRIANGLE_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");

    let mut eigen_graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Transposed>(&entered)
        .expect("eigen graph");
    let eigen =
        eigen_graph.eigenvector_centrality(&entered, &EigenvectorCentralityParams::default()).expect("eigenvector");
    assert_eq!(eigen.vertex_ids().expect("eigen vertices").len(), 3);
    assert_eq!(eigen.scores().expect("eigen scores").len(), 3);

    let mut katz_graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Transposed>(&entered)
        .expect("katz graph");
    let katz = katz_graph.katz_centrality(&entered, &KatzCentralityParams::default()).expect("katz");
    assert_eq!(katz.vertex_ids().expect("katz vertices").len(), 3);
    assert_eq!(katz.scores().expect("katz scores").len(), 3);
}

fn eigenvector_nonconvergence_is_typed_and_permanent() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("eigenvector_nonconvergence_is_typed_and_permanent").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2, 2, 2, 3, 4, 1, 3, 4, 0, 1, 3, 5, 5]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 3, 4, 0, 1, 3, 5, 5, 0, 1, 1, 2, 2, 2, 3, 4]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");
    let params = EigenvectorCentralityParams {
        epsilon: NonNegativeF64::new(1e-20).unwrap(),
        max_iterations: IterationCount::new(1).unwrap(),
        ..EigenvectorCentralityParams::default()
    };

    let error = graph
        .eigenvector_centrality(&entered, &params)
        .expect_err("one power iteration must return typed nonconvergence");
    assert_eq!(error.kind(), cugraph::ErrorKind::NonConvergence);
    assert!(error.is_permanent());
    assert_eq!(error.operation(), "eigenvector_centrality");
    assert_eq!(error.context_value("algorithm"), Some("eigenvector_centrality"));
    assert_eq!(error.context_value("iterations"), Some("1"));
    assert_eq!(error.context_value("max_iterations"), Some("1"));
    assert_eq!(error.context_value("epsilon"), Some("0.00000000000000000001"));
}

fn katz_nonconvergence_is_typed_and_names_alpha() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("katz_nonconvergence_is_typed_and_names_alpha").expect("entered");
    // Complete directed graph on four vertices: the largest adjacency eigenvalue is 3, so any
    // alpha above 1/3 makes the Katz series diverge.
    let (src, dst): (Vec<i32>, Vec<i32>) =
        (0..4).flat_map(|from| (0..4).filter(move |&to| to != from).map(move |to| (from, to))).unzip();
    let src = DeviceArray::from_slice(&entered, &src).expect("src");
    let dst = DeviceArray::from_slice(&entered, &dst).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");
    let params = KatzCentralityParams {
        alpha: NonNegativeF64::new(0.9).unwrap(),
        max_iterations: IterationCount::new(50).unwrap(),
        ..KatzCentralityParams::default()
    };

    let error = graph.katz_centrality(&entered, &params).expect_err("a diverging Katz series must not converge");

    assert_eq!(error.kind(), cugraph::ErrorKind::NonConvergence);
    assert!(error.is_permanent());
    assert_eq!(error.operation(), "katz_centrality");
    assert_eq!(error.context_value("algorithm"), Some("katz_centrality"));
    assert_eq!(error.context_value("iterations"), Some("50"));
    assert_eq!(error.context_value("max_iterations"), Some("50"));
    assert_eq!(error.context_value("epsilon"), Some("0.000001"));
    let remedy = error.context_value("remedy").expect("Katz non-convergence names its remedy");
    assert!(remedy.contains("alpha (currently 0.9)"), "{remedy}");
    assert!(remedy.contains("max_iterations"), "{remedy}");
}

fn hits_nonconvergence_is_typed_and_names_its_remedy() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("hits_nonconvergence_is_typed_and_names_its_remedy").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 1, 2, 2, 2, 3, 4, 1, 3, 4, 0, 1, 3, 5, 5]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 3, 4, 0, 1, 3, 5, 5, 0, 1, 1, 2, 2, 2, 3, 4]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");
    let params = HitsParams {
        epsilon: NonNegativeF64::new(1e-20).unwrap(),
        max_iterations: IterationCount::new(1).unwrap(),
        ..HitsParams::default()
    };

    let error = graph.hits(&entered, &params).expect_err("one HITS iteration must return typed nonconvergence");

    assert_eq!(error.kind(), cugraph::ErrorKind::NonConvergence);
    assert!(error.is_permanent());
    assert_eq!(error.operation(), "hits");
    assert_eq!(error.context_value("algorithm"), Some("hits"));
    assert_eq!(error.context_value("iterations"), Some("1"));
    assert_eq!(error.context_value("max_iterations"), Some("1"));
    assert_eq!(error.context_value("epsilon"), Some("0.00000000000000000001"));
    assert_eq!(error.context_value("remedy"), Some("raise max_iterations or epsilon"));
}

fn hits_returns_hub_authority_scores_and_metadata() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("hits_returns_hub_authority_scores_and_metadata").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 0, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 2, 3]).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");

    let result = graph.hits(&entered, &HitsParams::default()).expect("hits");
    let vertices = result.vertex_ids().expect("vertices");
    let hubs = result.hub_scores().expect("hubs");
    let authorities = result.authority_scores().expect("authorities");

    assert_eq!(vertices.len(), 4);
    assert_eq!(hubs.len(), 4);
    assert_eq!(authorities.len(), 4);
    assert!(result.hub_score_differences().is_finite());
    assert!(result.number_of_iterations() > 0);
}

fn hits_rejects_out_of_range_initial_hub_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("hits_rejects_out_of_range_initial_hub_vertex_with_default_params").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 0, 1, 2]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 2, 2, 3]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[999i32]).expect("vertices");
    let values = DeviceArray::from_slice(&entered, &[1.0f32]).expect("values");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let values_view = values.view().expect("values_view");
    let initial_hubs = HitsInitialHubs { vertices: &vertices_view, values: &values_view };
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Transposed>(&entered).expect("graph");

    let err = graph
        .hits_with_initial_hubs(&entered, &HitsParams::default(), Some(&initial_hubs))
        .expect_err("out-of-range initial hub vertex must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "hits");
}

fn edge_betweenness_exposes_edge_shaped_scores_and_optional_edge_ids() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("edge_betweenness_exposes_edge_shaped_scores_and_optional_edge_ids").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I32).expect("dst");
    let edge_ids = DeviceArray::from_slice(&entered, &[10i32, 11, 12]).expect("edge_ids");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let edge_ids_view = edge_ids.view().expect("edge_ids_view");

    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .edge_ids(&edge_ids_view)
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");
    let result = graph
        .edge_betweenness_centrality_all(&entered, &EdgeBetweennessCentralityParams::default())
        .expect("edge betweenness");

    assert_eq!(result.sources().expect("sources").len(), 3);
    assert_eq!(result.destinations().expect("destinations").len(), 3);
    assert_eq!(result.scores().expect("scores").len(), 3);
    let returned_edge_ids =
        result.edge_ids().expect("edge ids").expect("edge id column").to_vec_i32(&entered).expect("edge ids copy");
    assert_eq!(returned_edge_ids.len(), 3);

    let mut graph_without_ids =
        GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let result_without_ids = graph_without_ids
        .edge_betweenness_centrality_all(&entered, &EdgeBetweennessCentralityParams::default())
        .expect("edge betweenness without ids");
    assert!(result_without_ids.edge_ids().expect("edge ids").is_none());
}

fn edge_betweenness_rejects_out_of_range_seed_vertex_with_default_params() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered =
        handle.enter("edge_betweenness_rejects_out_of_range_seed_vertex_with_default_params").expect("entered");
    let src = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_SRC_I32).expect("src");
    let dst = DeviceArray::from_slice(&entered, FOUR_VERTEX_CHAIN_DST_I32).expect("dst");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view).renumber().build::<Forward>(&entered).expect("graph");
    let seeds = DeviceArray::from_slice(&entered, &[999i32]).expect("seeds");
    let seeds_view = seeds.view().expect("seeds_view");

    let err = graph
        .edge_betweenness_centrality(&entered, &seeds_view, &EdgeBetweennessCentralityParams::default())
        .expect_err("out-of-range seed must be rejected");

    assert_eq!(err.kind(), cugraph::ErrorKind::InvalidInput);
    assert_eq!(err.operation(), "edge_betweenness_centrality");
}

fn spectral_clustering_returns_partitions_and_analysis_scores() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("spectral_clustering_returns_partitions_and_analysis_scores").expect("entered");
    let src_data = [0i32, 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5];
    let dst_data = [1i32, 2, 0, 2, 0, 1, 3, 2, 4, 5, 3, 5, 3, 4];
    let weights_data = [0.1f32, 0.2, 0.1, 1.2, 0.2, 1.2, 2.3, 2.3, 3.4, 3.5, 3.4, 4.5, 3.5, 4.5];
    let src = DeviceArray::from_slice(&entered, &src_data).expect("src");
    let dst = DeviceArray::from_slice(&entered, &dst_data).expect("dst");
    let weights = DeviceArray::from_slice(&entered, &weights_data).expect("weights");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let weights_view = weights.view().expect("weights_view");
    let params = SpectralClusteringParams::default();
    let n_clusters = NonZeroUsize::new(params.n_clusters.get()).expect("clusters");
    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .weights(&weights_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");
    let mut rng = RngState::new(&entered, 10).expect("rng");

    let result = graph.spectral_modularity_maximization(&entered, &mut rng, &params).expect("spectral clustering");

    let vertices = result.vertex_ids().expect("vertices");
    let clusters = result.clusters().expect("clusters");
    assert_eq!(vertices.len(), 6);
    assert_eq!(clusters.len(), 6);
    let edge_cut = match (vertices, clusters) {
        (VertexIds::I32(vertices), VertexIds::I32(clusters)) => {
            graph.analyze_clustering_edge_cut(&entered, n_clusters, &vertices, &clusters).expect("edge cut")
        },
        _ => panic!("expected i32 spectral clustering output"),
    };
    assert!(edge_cut.is_finite());
    assert!(edge_cut < 55.0, "edge cut should be bounded, got {edge_cut}");
}

/// Two `k`-cliques joined by one bridge edge have five distinct normalized-Laplacian eigenvalues,
/// so the Lanczos Krylov space turns invariant after about five vectors while the solver asks for
/// at least six once `k >= 4`. RAFT zeroed the basis at that breakdown and returned one community,
/// a bridge-endpoint cluster, an uneven split, or an eigensolver failure.
#[test]
fn spectral_clustering_splits_bridged_cliques_exactly() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("spectral_clustering_splits_bridged_cliques_exactly").expect("entered");
    let params = SpectralClusteringParams::default();
    let mut failures = Vec::new();

    for clique_size in [4i32, 8, 10, 15] {
        let mut src_data = Vec::new();
        let mut dst_data = Vec::new();
        let mut add_edge = |a: i32, b: i32| {
            src_data.extend([a, b]);
            dst_data.extend([b, a]);
        };
        for first in [0, clique_size] {
            for a in first..first + clique_size {
                for b in a + 1..first + clique_size {
                    add_edge(a, b);
                }
            }
        }
        add_edge(clique_size - 1, clique_size);
        let weights_data = vec![1.0f32; src_data.len()];
        let src = DeviceArray::from_slice(&entered, &src_data).expect("src");
        let dst = DeviceArray::from_slice(&entered, &dst_data).expect("dst");
        let weights = DeviceArray::from_slice(&entered, &weights_data).expect("weights");
        let src_view = src.view().expect("src_view");
        let dst_view = dst.view().expect("dst_view");
        let weights_view = weights.view().expect("weights_view");

        for seed in 0..8 {
            let mut graph = GraphBuilder::new(&src_view, &dst_view)
                .weights(&weights_view)
                .properties(GraphProperties::undirected())
                .renumber()
                .build::<Forward>(&entered)
                .expect("graph");
            let mut rng = RngState::new(&entered, seed).expect("rng");
            let result = match graph.spectral_modularity_maximization(&entered, &mut rng, &params) {
                Ok(result) => result,
                Err(error) => {
                    let message = error.to_string();
                    let first_line = message.lines().next().unwrap_or_default();
                    failures.push(format!("k={clique_size} seed={seed}: {first_line}"));
                    continue;
                },
            };
            let (vertices, clusters) =
                match (result.vertex_ids().expect("vertices"), result.clusters().expect("clusters")) {
                    (VertexIds::I32(vertices), VertexIds::I32(clusters)) => (
                        vertices.to_vec(&entered).expect("vertex copy"),
                        clusters.to_vec(&entered).expect("cluster copy"),
                    ),
                    _ => panic!("expected i32 spectral clustering output"),
                };
            assert_eq!(vertices.len(), (2 * clique_size) as usize);
            let mut clique_clusters = [Vec::new(), Vec::new()];
            for (&vertex, &cluster) in vertices.iter().zip(&clusters) {
                clique_clusters[usize::from(vertex >= clique_size)].push(cluster);
            }
            let [left, right] = clique_clusters.map(|mut ids| {
                ids.sort_unstable();
                ids.dedup();
                ids
            });
            if !(left.len() == 1 && right.len() == 1 && left[0] != right[0]) {
                failures.push(format!("k={clique_size} seed={seed}: clusters left={left:?} right={right:?}"));
            }
        }
    }

    assert!(failures.is_empty(), "expected one cluster per clique:\n{}", failures.join("\n"));
}

fn clustering_analysis_accepts_explicit_partition_columns() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("clustering_analysis_accepts_explicit_partition_columns").expect("entered");
    let src = DeviceArray::from_slice(&entered, &[0i32, 1, 2, 3]).expect("src");
    let dst = DeviceArray::from_slice(&entered, &[1i32, 0, 3, 2]).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &[0i32, 1, 2, 3]).expect("vertices");
    let clusters = DeviceArray::from_slice(&entered, &[0i32, 0, 1, 1]).expect("clusters");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");
    let clusters_view = clusters.view().expect("clusters_view");
    let mut graph = GraphBuilder::new(&src_view, &dst_view)
        .properties(GraphProperties::undirected())
        .renumber()
        .build::<Forward>(&entered)
        .expect("graph");
    let n_clusters = NonZeroUsize::new(2).expect("clusters");

    let modularity =
        graph.analyze_clustering_modularity(&entered, n_clusters, &vertices_view, &clusters_view).expect("modularity");
    let edge_cut =
        graph.analyze_clustering_edge_cut(&entered, n_clusters, &vertices_view, &clusters_view).expect("edge cut");
    let ratio_cut =
        graph.analyze_clustering_ratio_cut(&entered, n_clusters, &vertices_view, &clusters_view).expect("ratio cut");

    assert!(modularity.is_finite());
    assert!(edge_cut.abs() < 1e-6, "disconnected partition edge cut should be zero, got {edge_cut}");
    assert!(ratio_cut.abs() < 1e-6, "disconnected partition ratio cut should be zero, got {ratio_cut}");
}

fn degrees_all_on_empty_graph_returns_empty_results() {
    let _guard = common::cudf::cuda_test_serial_guard();
    let handle = test_handle();
    let entered = handle.enter("degrees_all_on_empty_graph_returns_empty_results").expect("entered");
    let empty: [i32; 0] = [];
    let src = DeviceArray::from_slice(&entered, &empty).expect("src");
    let dst = DeviceArray::from_slice(&entered, &empty).expect("dst");
    let vertices = DeviceArray::from_slice(&entered, &empty).expect("vertices");
    let src_view = src.view().expect("src_view");
    let dst_view = dst.view().expect("dst_view");
    let vertices_view = vertices.view().expect("vertices_view");

    let mut graph =
        GraphBuilder::new(&src_view, &dst_view).vertices(&vertices_view).build::<Transposed>(&entered).expect("graph");

    let result = graph.degrees_all(&entered).expect("degrees");
    let returned_vertices = result.vertex_ids().expect("vertex_ids").to_vec_i32(&entered).expect("vertex copy");
    let in_degrees = result.in_degrees().expect("in_degrees").to_vec_i64(&entered).expect("in copy");
    let out_degrees = result.out_degrees().expect("out_degrees").to_vec_i64(&entered).expect("out copy");

    assert!(returned_vertices.is_empty());
    assert!(in_degrees.is_empty());
    assert!(out_degrees.is_empty());
}

#[test]
fn centrality_owner_cases_1() {
    run_named_cases(&[
        (
            "centrality::betweenness::tests::test_betweenness_centrality_line_graph",
            betweenness_owner::test_betweenness_centrality_line_graph,
        ),
        (
            "centrality::betweenness::tests::test_betweenness_centrality_star_graph",
            betweenness_owner::test_betweenness_centrality_star_graph,
        ),
        (
            "centrality::betweenness::tests::test_betweenness_centrality_with_endpoints",
            betweenness_owner::test_betweenness_centrality_with_endpoints,
        ),
        (
            "centrality::betweenness::tests::test_betweenness_centrality_with_seed_vertices",
            betweenness_owner::test_betweenness_centrality_with_seed_vertices,
        ),
        (
            "centrality::pagerank::tests::test_pagerank_rejects_mismatched_initial_guess",
            pagerank_owner::test_pagerank_rejects_mismatched_initial_guess,
        ),
        (
            "centrality::pagerank::tests::test_pagerank_rejects_mismatched_precomputed_weights",
            pagerank_owner::test_pagerank_rejects_mismatched_precomputed_weights,
        ),
        ("centrality::pagerank::tests::test_pagerank_star_graph", pagerank_owner::test_pagerank_star_graph),
        (
            "centrality::betweenness::tests::test_betweenness_centrality_result_vertex_count_matches",
            betweenness_owner::test_betweenness_centrality_result_vertex_count_matches,
        ),
    ]);
}

#[test]
fn typed_runtime_result_cases_1() {
    run_named_cases(&[
        (
            "bfs_distances_i32_supports_runtime_decoding_and_widening",
            null_guards_and_distances_gpu::bfs_distances_i32_supports_runtime_decoding_and_widening,
        ),
        ("typed_results_refuse_lossy_narrowing", dtype_contracts_gpu::typed_results_refuse_lossy_narrowing),
        (
            "graph_reports_i64_vertex_and_f64_weight_dtypes",
            dtype_contracts_gpu::graph_reports_i64_vertex_and_f64_weight_dtypes,
        ),
        (
            "bfs_predecessors_are_none_when_not_requested",
            result_decoding_gpu::bfs_predecessors_are_none_when_not_requested,
        ),
        ("to_vec_i64_roundtrip", typed_vec_gpu::to_vec_i64_roundtrip),
        ("to_vec_empty_array_returns_empty_vec", typed_vec_gpu::to_vec_empty_array_returns_empty_vec),
        ("array::tests::test_device_array_roundtrip", array_owner::test_device_array_roundtrip),
        ("array::tests::test_device_array_f32_roundtrip", array_owner::test_device_array_f32_roundtrip),
        ("array::tests::test_to_vec_roundtrip_f64", array_owner::test_to_vec_roundtrip_f64),
    ]);
}