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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

//! CPU implementation of connectivity algorithms.

use crate::graph::impl_generic::{connected_components_impl, tarjan_impl};
use crate::graph::traits::connectivity::ConnectivityAlgorithms;
use crate::graph::traits::types::{ComponentResult, GraphData};
use numr::error::Result;
use numr::runtime::cpu::{CpuClient, CpuRuntime};

impl ConnectivityAlgorithms<CpuRuntime> for CpuClient {
    fn connected_components(
        &self,
        graph: &GraphData<CpuRuntime>,
    ) -> Result<ComponentResult<CpuRuntime>> {
        connected_components_impl(self, graph)
    }

    fn strongly_connected_components(
        &self,
        graph: &GraphData<CpuRuntime>,
    ) -> Result<ComponentResult<CpuRuntime>> {
        tarjan_impl(self, graph)
    }

    fn is_connected(&self, graph: &GraphData<CpuRuntime>) -> Result<bool> {
        let result = connected_components_impl(self, graph)?;
        Ok(result.num_components == 1)
    }

    fn is_strongly_connected(&self, graph: &GraphData<CpuRuntime>) -> Result<bool> {
        let result = tarjan_impl(self, graph)?;
        Ok(result.num_components == 1)
    }
}

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

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

        // Two components: {0,1} and {2,3}
        let graph =
            GraphData::from_edge_list::<f64>(&[0, 2], &[1, 3], None, 4, false, &device).unwrap();

        let result = client.connected_components(&graph).unwrap();
        assert_eq!(result.num_components, 2);
    }

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

        let graph =
            GraphData::from_edge_list::<f64>(&[0, 1], &[1, 2], None, 3, false, &device).unwrap();

        assert!(client.is_connected(&graph).unwrap());
    }
}