abd_clam/chaoda/graph/
vertex.rs

1//! A `Vertex` for a `Graph`.
2
3use core::{
4    cmp::Ordering,
5    fmt::{Display, Formatter},
6    hash::{Hash, Hasher},
7    marker::PhantomData,
8};
9
10use distances::Number;
11use serde::{
12    de::{MapAccess, SeqAccess, Visitor},
13    ser::SerializeStruct,
14    Deserialize, Deserializer, Serialize, Serializer,
15};
16
17use crate::{core::cluster::Children, utils, Cluster, Dataset, Instance, PartitionCriterion, UniBall};
18
19/// The ratios used for anomaly detection.
20pub type Ratios = [f64; 6];
21
22/// A `Vertex` for a `Graph`.
23#[derive(Debug, Clone)]
24pub struct Vertex<U: Number> {
25    /// The base `UniBall` of the `Vertex`.
26    uni_ball: UniBall<U>,
27    /// The ratios used for anomaly detection.
28    ratios: Ratios,
29    /// Child Vertices
30    children: Option<Children<U, Self>>,
31}
32
33impl<I: Instance, U: Number, D: Dataset<I, U>> crate::Tree<I, U, D, Vertex<U>> {
34    /// Sets the `Vertex` ratios for anomaly detection and related applications.
35    ///
36    /// This should only be called on the root `Cluster` after calling `partition`.
37    ///
38    /// # Arguments
39    ///
40    /// * `normalized`: Whether to apply Gaussian error normalization to the ratios.
41    #[must_use]
42    pub fn normalize_ratios(mut self) -> Self {
43        self.root = self.root.normalize_ratios();
44        self
45    }
46}
47
48impl<U: Number> Vertex<U> {
49    /// Creates a new `Vertex`.
50    pub const fn new(uni_ball: UniBall<U>, ratios: Ratios, children: Option<Children<U, Self>>) -> Self {
51        Self {
52            uni_ball,
53            ratios,
54            children,
55        }
56    }
57
58    /// Creates a new `Vertex` tree.
59    pub fn from_base_tree(root: UniBall<U>) -> Self {
60        Self::from_uni_ball(root).set_child_parent_ratios([1.0; 6])
61    }
62
63    /// Recursively creates a new `Vertex` tree.
64    fn from_uni_ball(mut uni_ball: UniBall<U>) -> Self {
65        match uni_ball.children {
66            Some(children) => {
67                uni_ball.children = None;
68                let left = Box::new(Self::from_uni_ball(*children.left));
69                let right = Box::new(Self::from_uni_ball(*children.right));
70                let children = Children {
71                    left,
72                    right,
73                    arg_l: children.arg_l,
74                    arg_r: children.arg_r,
75                    polar_distance: children.polar_distance,
76                };
77                Self::new(uni_ball, [1.0; 6], Some(children))
78            }
79            None => Self::new(uni_ball, [1.0; 6], None),
80        }
81    }
82
83    /// Set the child-parent ratios.
84    #[must_use]
85    #[allow(clippy::similar_names)]
86    pub(crate) fn set_child_parent_ratios(mut self, parent_ratios: Ratios) -> Self {
87        let [pc, pr, pl, pc_, pr_, pl_] = parent_ratios;
88
89        let c = self.cardinality().as_f64() / pc;
90        let r = self.radius().as_f64() / pr;
91        let l = self.lfd() / pl;
92
93        let c_ = utils::next_ema(c, pc_);
94        let r_ = utils::next_ema(r, pr_);
95        let l_ = utils::next_ema(l, pl_);
96
97        let ratios = [c, r, l, c_, r_, l_];
98        self.ratios = ratios;
99
100        if let Some(Children {
101            left,
102            right,
103            arg_l,
104            arg_r,
105            polar_distance,
106        }) = self.children
107        {
108            let left = Box::new(left.set_child_parent_ratios(ratios));
109            let right = Box::new(right.set_child_parent_ratios(ratios));
110            let children = Children {
111                left,
112                right,
113                arg_l,
114                arg_r,
115                polar_distance,
116            };
117            self.children = Some(children);
118        }
119
120        self
121    }
122
123    /// Normalizes the ratios in the subtree.
124    #[must_use]
125    pub fn normalize_ratios(mut self) -> Self {
126        let all_ratios = self.subtree().into_iter().map(Self::ratios).collect::<Vec<_>>();
127
128        let all_ratios = utils::rows_to_cols(&all_ratios);
129
130        // mean of each column
131        let means = utils::calc_row_means(&all_ratios);
132
133        // sd of each column
134        let sds = utils::calc_row_sds(&all_ratios);
135
136        self.set_normalized_ratios(means, sds);
137
138        self
139    }
140
141    /// Recursively applies Gaussian error normalization to the ratios in the subtree.
142    fn set_normalized_ratios(&mut self, means: Ratios, sds: Ratios) {
143        let normalized_ratios: Vec<_> = self
144            .ratios
145            .into_iter()
146            .zip(means)
147            .zip(sds)
148            .map(|((value, mean), std)| (value - mean) / std.mul_add(core::f64::consts::SQRT_2, f64::EPSILON))
149            .map(libm::erf)
150            .map(|v| (1. + v) / 2.)
151            .collect();
152
153        if let Ok(normalized_ratios) = normalized_ratios.try_into() {
154            self.ratios = normalized_ratios;
155        }
156
157        match &mut self.children {
158            Some(children) => {
159                children.left.set_normalized_ratios(means, sds);
160                children.right.set_normalized_ratios(means, sds);
161            }
162            None => (),
163        }
164    }
165
166    /// The base `UniBall` of the `Vertex`.
167    pub const fn uni_ball(&self) -> &UniBall<U> {
168        &self.uni_ball
169    }
170
171    /// The ratios of the `Vertex`.
172    pub const fn ratios(&self) -> Ratios {
173        self.ratios
174    }
175}
176
177impl<U: Number> Cluster<U> for Vertex<U> {
178    fn new_root<I: Instance, D: Dataset<I, U>>(data: &D, seed: Option<u64>) -> Self {
179        let uni_ball = UniBall::new_root(data, seed);
180        let ratios = [0.0; 6];
181        Self::new(uni_ball, ratios, None)
182    }
183
184    fn partition<I, D, P>(self, data: &mut D, criteria: &P, seed: Option<u64>) -> Self
185    where
186        I: Instance,
187        D: Dataset<I, U>,
188        P: PartitionCriterion<U>,
189    {
190        let uni_ball = self.uni_ball.partition(data, criteria, seed);
191        Self::from_base_tree(uni_ball)
192    }
193
194    fn offset(&self) -> usize {
195        self.uni_ball.offset()
196    }
197
198    fn cardinality(&self) -> usize {
199        self.uni_ball.cardinality()
200    }
201
202    fn depth(&self) -> usize {
203        self.uni_ball.depth()
204    }
205
206    fn arg_center(&self) -> usize {
207        self.uni_ball.arg_center()
208    }
209
210    fn radius(&self) -> U {
211        self.uni_ball.radius()
212    }
213
214    fn arg_radial(&self) -> usize {
215        self.uni_ball.arg_radial()
216    }
217
218    fn lfd(&self) -> f64 {
219        self.uni_ball.lfd()
220    }
221
222    fn children(&self) -> Option<[&Self; 2]> {
223        self.children.as_ref().map(|c| [c.left.as_ref(), c.right.as_ref()])
224    }
225
226    fn polar_distance(&self) -> Option<U> {
227        self.uni_ball.polar_distance()
228    }
229
230    fn arg_poles(&self) -> Option<[usize; 2]> {
231        self.uni_ball.arg_poles()
232    }
233}
234
235impl<U: Number> PartialEq for Vertex<U> {
236    fn eq(&self, other: &Self) -> bool {
237        self.uni_ball.eq(&other.uni_ball)
238    }
239}
240
241impl<U: Number> Eq for Vertex<U> {}
242
243impl<U: Number> PartialOrd for Vertex<U> {
244    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
245        Some(self.cmp(other))
246    }
247}
248
249impl<U: Number> Ord for Vertex<U> {
250    fn cmp(&self, other: &Self) -> Ordering {
251        self.uni_ball.cmp(&other.uni_ball)
252    }
253}
254
255impl<U: Number> Hash for Vertex<U> {
256    fn hash<H: Hasher>(&self, state: &mut H) {
257        self.uni_ball.hash(state);
258    }
259}
260
261impl<U: Number> Display for Vertex<U> {
262    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
263        write!(f, "{}", self.uni_ball)
264    }
265}
266
267impl<U: Number> Serialize for Vertex<U> {
268    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
269        let mut state = serializer.serialize_struct("Vertex", 3)?;
270        state.serialize_field("uni_ball", &self.uni_ball)?;
271        state.serialize_field("ratios", &self.ratios)?;
272        state.serialize_field("children", &self.children)?;
273        state.end()
274    }
275}
276
277impl<'de, U: Number> Deserialize<'de> for Vertex<U> {
278    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
279        /// The fields in the `Vertex` struct.
280        #[derive(Deserialize)]
281        #[serde(field_identifier, rename_all = "lowercase")]
282        enum Field {
283            /// The base `UniBall` of the `Vertex`.
284            UniBall,
285            /// The ratios of the `Vertex`.
286            Ratios,
287            /// The children of the `Vertex`.
288            Children,
289        }
290
291        /// The `Visitor` for the `Vertex` struct.
292        struct VertexVisitor<U: Number>(PhantomData<U>);
293
294        impl<'de, U: Number> Visitor<'de> for VertexVisitor<U> {
295            type Value = Vertex<U>;
296
297            fn expecting(&self, formatter: &mut core::fmt::Formatter) -> core::fmt::Result {
298                formatter.write_str("struct Vertex")
299            }
300
301            fn visit_seq<V: SeqAccess<'de>>(self, mut seq: V) -> Result<Self::Value, V::Error> {
302                let uni_ball = seq
303                    .next_element()?
304                    .ok_or_else(|| serde::de::Error::invalid_length(0, &self))?;
305                let ratios = seq
306                    .next_element()?
307                    .ok_or_else(|| serde::de::Error::invalid_length(1, &self))?;
308                let children = seq
309                    .next_element()?
310                    .ok_or_else(|| serde::de::Error::invalid_length(2, &self))?;
311                Ok(Vertex::new(uni_ball, ratios, children))
312            }
313
314            fn visit_map<V: MapAccess<'de>>(self, mut map: V) -> Result<Self::Value, V::Error> {
315                let mut uni_ball = None;
316                let mut ratios = None;
317                let mut children = None;
318
319                while let Some(key) = map.next_key()? {
320                    match key {
321                        Field::UniBall => {
322                            if uni_ball.is_some() {
323                                return Err(serde::de::Error::duplicate_field("uni_ball"));
324                            }
325                            uni_ball = Some(map.next_value()?);
326                        }
327                        Field::Ratios => {
328                            if ratios.is_some() {
329                                return Err(serde::de::Error::duplicate_field("ratios"));
330                            }
331                            ratios = Some(map.next_value()?);
332                        }
333                        Field::Children => {
334                            if children.is_some() {
335                                return Err(serde::de::Error::duplicate_field("children"));
336                            }
337                            children = Some(map.next_value()?);
338                        }
339                    }
340                }
341
342                let uni_ball = uni_ball.ok_or_else(|| serde::de::Error::missing_field("uni_ball"))?;
343                let ratios = ratios.ok_or_else(|| serde::de::Error::missing_field("ratios"))?;
344                let children = children.ok_or_else(|| serde::de::Error::missing_field("children"))?;
345
346                Ok(Vertex::new(uni_ball, ratios, children))
347            }
348        }
349
350        /// The `Field` names.
351        const FIELDS: &[&str] = &["uni_ball", "ratios", "children"];
352        deserializer.deserialize_struct("Vertex", FIELDS, VertexVisitor(PhantomData))
353    }
354}
abd_clam/chaoda/graph/vertex.rs

abd_clam/chaoda/graph/
vertex.rs
