filtration_domination/
lib.rs

1//! Algorithms and utilities to work with bifiltered graphs. In particular,
2//! algorithms to remove edges from a bifiltered graph while maintaining the topological
3//! properties of its clique complex, see [crate::removal].
4
5#![warn(clippy::shadow_unrelated)]
6#![warn(clippy::needless_pass_by_value)]
7#![allow(clippy::needless_range_loop)]
8#![warn(clippy::disallowed_types)]
9
10use num::{Bounded, Zero};
11use std::cmp::Ordering;
12use std::fmt::Formatter;
13use std::hash::Hash;
14use std::ops::{Index, IndexMut};
15use std::slice::Iter;
16
17pub mod edges;
18
19pub mod datasets;
20pub mod distance_matrix;
21pub mod mpfree;
22pub mod points;
23pub mod removal;
24
25mod chain_complex;
26mod filtration;
27mod io_utils;
28mod simplicial_complex;
29
30/// A generic value, like usize or i32, that we can use as grades in a bifiltered graph.
31pub trait Value:
32    Zero
33    + Ord
34    + Bounded
35    + Copy
36    + Clone
37    + Hash
38    + std::fmt::Debug
39    + std::fmt::Display
40    + std::marker::Send
41    + std::marker::Sync
42{
43}
44
45impl<T> Value for T where
46    T: Zero
47        + Ord
48        + Bounded
49        + Copy
50        + Clone
51        + Hash
52        + std::fmt::Debug
53        + std::fmt::Display
54        + std::marker::Send
55        + std::marker::Sync
56{
57}
58
59/// The grade in which a simplex enters a filtration.
60pub trait CriticalGrade:
61    Clone + PartialOrd + Ord + std::fmt::Debug + std::marker::Sync + std::marker::Send
62{
63    /// Minimum possible value.
64    fn min_value() -> Self;
65    /// Maximum possible value.
66    fn max_value() -> Self;
67    /// Zero value.
68    fn zero() -> Self;
69
70    /// The least upper bound of the given grades.
71    #[must_use]
72    fn join(&self, other: &Self) -> Self;
73
74    /// Less than or equal to the other grade.
75    fn lte(&self, other: &Self) -> bool;
76    /// Grater than or equal to the other grade.
77    fn gte(&self, other: &Self) -> bool;
78
79    /// Returns true if self is incomparable to other, meaning that neither self <= other and neither
80    /// self >= other.
81    fn is_incomparable_to(&self, other: &Self) -> bool {
82        !self.lte(other) && !self.gte(other)
83    }
84
85    /// Number of parameters.
86    fn parameters() -> usize;
87}
88
89/// A 1-critical grade. The default order is lexicographic.
90#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
91pub struct OneCriticalGrade<VF, const N: usize>(pub [VF; N]);
92
93impl<VF: Value, const N: usize> OneCriticalGrade<VF, N> {
94    pub fn iter(&self) -> Iter<'_, VF> {
95        self.0.iter()
96    }
97}
98
99impl<VF: Value, const N: usize> OneCriticalGrade<VF, N> {
100    pub fn cmp_colexicographically(&self, b: &Self) -> Ordering {
101        for i in (0..N).rev() {
102            match self.0[i].cmp(&b.0[i]) {
103                Ordering::Less => {
104                    return Ordering::Less;
105                }
106                Ordering::Equal => {
107                    continue;
108                }
109                Ordering::Greater => {
110                    return Ordering::Greater;
111                }
112            }
113        }
114        Ordering::Equal
115    }
116}
117
118impl<VF: Value, const N: usize> CriticalGrade for OneCriticalGrade<VF, N> {
119    fn min_value() -> OneCriticalGrade<VF, N> {
120        OneCriticalGrade([VF::min_value(); N])
121    }
122
123    fn max_value() -> OneCriticalGrade<VF, N> {
124        OneCriticalGrade([VF::max_value(); N])
125    }
126
127    fn zero() -> OneCriticalGrade<VF, N> {
128        OneCriticalGrade([VF::zero(); N])
129    }
130
131    fn join(&self, other: &Self) -> Self {
132        let mut join = *self;
133        for n in 0..N {
134            join[n] = std::cmp::max(join[n], other[n]);
135        }
136        join
137    }
138
139    /// Returns true if, for all i in 0..(N-1), the i'th value of self is less than or equal to
140    /// the i'th value of the other.
141    fn lte(&self, other: &Self) -> bool {
142        for n in 0..N {
143            if self[n] > other[n] {
144                return false;
145            }
146        }
147        true
148    }
149
150    fn gte(&self, other: &Self) -> bool {
151        for n in 0..N {
152            if self[n] < other[n] {
153                return false;
154            }
155        }
156        true
157    }
158
159    fn parameters() -> usize {
160        N
161    }
162}
163
164impl<VF: Value, const N: usize> Index<usize> for OneCriticalGrade<VF, N> {
165    type Output = VF;
166
167    fn index(&self, index: usize) -> &Self::Output {
168        &self.0[index]
169    }
170}
171
172impl<VF: Value, const N: usize> IndexMut<usize> for OneCriticalGrade<VF, N> {
173    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
174        &mut self.0[index]
175    }
176}
177
178impl<VF: Value, const N: usize> From<[VF; N]> for OneCriticalGrade<VF, N> {
179    fn from(grade: [VF; N]) -> Self {
180        Self(grade)
181    }
182}
183
184impl<VF: Value> From<VF> for OneCriticalGrade<VF, 1> {
185    fn from(grade: VF) -> Self {
186        Self([grade])
187    }
188}
189
190impl<VF: Value, const N: usize> std::fmt::Display for OneCriticalGrade<VF, N> {
191    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
192        for i in 0..N {
193            write!(f, "{}", self.0[i])?;
194            if i != N - 1 {
195                write!(f, " ")?;
196            }
197        }
198        Ok(())
199    }
200}
filtration_domination/lib.rs

filtration_domination/
lib.rs
