solvr/graph/cpu/
mst.rs

1//! CPU implementation of minimum spanning tree algorithms.
2
3use crate::graph::impl_generic::kruskal_impl;
4use crate::graph::traits::mst::MSTAlgorithms;
5use crate::graph::traits::types::{GraphData, MSTResult};
6use numr::error::Result;
7use numr::runtime::cpu::{CpuClient, CpuRuntime};
8
9impl MSTAlgorithms<CpuRuntime> for CpuClient {
10    fn minimum_spanning_tree(
11        &self,
12        graph: &GraphData<CpuRuntime>,
13    ) -> Result<MSTResult<CpuRuntime>> {
14        kruskal_impl(self, graph)
15    }
16}
17
18#[cfg(test)]
19mod tests {
20    use super::*;
21    use numr::runtime::cpu::CpuDevice;
22
23    #[test]
24    fn test_mst() {
25        let device = CpuDevice::new();
26        let client = CpuClient::new(device.clone());
27
28        // Triangle: 0-1 (1), 1-2 (2), 0-2 (3)
29        let graph = GraphData::from_edge_list::<f64>(
30            &[0, 1, 0],
31            &[1, 2, 2],
32            Some(&[1.0, 2.0, 3.0]),
33            3,
34            false,
35            &device,
36        )
37        .unwrap();
38
39        let result = client.minimum_spanning_tree(&graph).unwrap();
40        assert!((result.total_weight - 3.0).abs() < 1e-10); // edges 1+2=3
41    }
42}
solvr/graph/cpu/mst.rs

solvr/graph/cpu/
mst.rs
