solvr 0.2.0-beta.2

Advanced computing library for real-world problem solving - optimization, differential equations, interpolation, statistics, and more
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

//! CPU implementation of minimum spanning tree algorithms.

use crate::graph::impl_generic::kruskal_impl;
use crate::graph::traits::mst::MSTAlgorithms;
use crate::graph::traits::types::{GraphData, MSTResult};
use numr::error::Result;
use numr::runtime::cpu::{CpuClient, CpuRuntime};

impl MSTAlgorithms<CpuRuntime> for CpuClient {
    fn minimum_spanning_tree(
        &self,
        graph: &GraphData<CpuRuntime>,
    ) -> Result<MSTResult<CpuRuntime>> {
        kruskal_impl(self, graph)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use numr::runtime::cpu::CpuDevice;

    #[test]
    fn test_mst() {
        let device = CpuDevice::new();
        let client = CpuClient::new(device.clone());

        // Triangle: 0-1 (1), 1-2 (2), 0-2 (3)
        let graph = GraphData::from_edge_list::<f64>(
            &[0, 1, 0],
            &[1, 2, 2],
            Some(&[1.0, 2.0, 3.0]),
            3,
            false,
            &device,
        )
        .unwrap();

        let result = client.minimum_spanning_tree(&graph).unwrap();
        assert!((result.total_weight - 3.0).abs() < 1e-10); // edges 1+2=3
    }
}