geometric-traits 0.1.0

Trait-based algebraic and graph algorithms for Rust, supporting no_std environments
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

//! Submodule declaring `K_4` homeomorph detection for simple undirected
//! graphs.
//!
//! The current implementation is a boolean detector layered on the crate's
//! internal Boyer-style edge-addition embedding engine.

use num_traits::AsPrimitive;

use super::topology_wrapper_macros::define_planarity_derived_error;
use crate::traits::{
    UndirectedMonopartiteMonoplexGraph,
    algorithms::{PlanarityError, planarity_detection},
};

define_planarity_derived_error!(
    /// Error type for `K_4` homeomorph detection.
    pub enum K4HomeomorphError => K4HomeomorphError,
    mapper = map_planarity_error_to_k4_homeomorph_error,
    self_loop = "The K4 homeomorph algorithm currently supports only simple undirected graphs and does not accept self-loops.",
    parallel = "The K4 homeomorph algorithm currently supports only simple undirected graphs and does not accept parallel edges."
);

/// Trait providing `K_4` homeomorph detection for simple undirected graphs.
pub trait K4HomeomorphDetection: UndirectedMonopartiteMonoplexGraph {
    /// Returns whether the graph contains a subgraph homeomorphic to `K_4`.
    ///
    /// The current implementation is a boolean detector driven by the crate's
    /// internal Boyer-style edge-addition embedding engine.
    ///
    /// # Errors
    ///
    /// Returns an error when the graph violates the simple-undirected contract,
    /// such as by containing self-loops, parallel edges, or malformed edge
    /// endpoints from a custom graph implementation.
    #[inline]
    fn has_k4_homeomorph(&self) -> Result<bool, crate::errors::MonopartiteError<Self>>
    where
        Self: Sized,
        Self::NodeId: AsPrimitive<usize>,
    {
        has_k4_homeomorph_simple_undirected_graph(self)
            .map_err(map_planarity_error_to_k4_homeomorph_error::<Self>)
    }
}

impl<G: ?Sized + UndirectedMonopartiteMonoplexGraph> K4HomeomorphDetection for G {}

pub(crate) fn has_k4_homeomorph_simple_undirected_graph<G>(
    graph: &G,
) -> Result<bool, PlanarityError>
where
    G: UndirectedMonopartiteMonoplexGraph,
    G::NodeId: AsPrimitive<usize>,
{
    planarity_detection::has_k4_homeomorph_simple_undirected_graph(graph)
}

#[cfg(test)]
mod tests {
    use super::{K4HomeomorphError, map_planarity_error_to_k4_homeomorph_error};
    use crate::{
        errors::{
            MonopartiteError, monopartite_graph_error::algorithms::MonopartiteAlgorithmError,
        },
        prelude::UndiGraph,
        traits::algorithms::planarity_detection::{
            preprocessing::LocalSimpleGraph, run_k4_homeomorph_engine,
        },
    };

    #[test]
    fn test_map_planarity_parallel_edge_error_to_k4_error() {
        let error: MonopartiteError<UndiGraph<usize>> = map_planarity_error_to_k4_homeomorph_error(
            crate::traits::algorithms::PlanarityError::ParallelEdgesUnsupported,
        );

        assert!(matches!(
            error,
            MonopartiteError::AlgorithmError(MonopartiteAlgorithmError::K4HomeomorphError(
                K4HomeomorphError::ParallelEdgesUnsupported
            ))
        ));
    }

    #[test]
    fn test_map_planarity_invalid_endpoint_error_to_k4_error() {
        let error: MonopartiteError<UndiGraph<usize>> = map_planarity_error_to_k4_homeomorph_error(
            crate::traits::algorithms::PlanarityError::InvalidEdgeEndpoint {
                endpoint: 9,
                node_count: 4,
            },
        );

        assert!(matches!(
            error,
            MonopartiteError::AlgorithmError(MonopartiteAlgorithmError::K4HomeomorphError(
                K4HomeomorphError::InvalidEdgeEndpoint { endpoint: 9, node_count: 4 }
            ))
        ));
    }

    #[test]
    fn test_run_k4_engine_detects_k4() {
        let graph =
            LocalSimpleGraph::from_edges(4, &[[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]])
                .unwrap();

        assert!(run_k4_homeomorph_engine(&graph.preprocess()));
    }

    #[test]
    fn test_run_k4_engine_rejects_theta() {
        let graph =
            LocalSimpleGraph::from_edges(5, &[[0, 2], [2, 1], [0, 3], [3, 1], [0, 4], [4, 1]])
                .unwrap();

        assert!(!run_k4_homeomorph_engine(&graph.preprocess()));
    }
}