sprs_rssn/sparse/linalg/
etree.rs

1//! Data structures to work with elimination trees (etree).
2//! etrees arise when considering cholesky factorization, QR factorization, ...
3
4use std::ops::{Deref, DerefMut};
5
6pub type Parent = Option<usize>;
7
8/// Store an etree as the parent information of each node.
9/// This reflects the fact that etrees can in fact have multiple roots.
10#[derive(Debug, Clone)]
11pub struct Parents<S>
12where
13    S: Deref<Target = [Parent]>,
14{
15    parents: S,
16}
17
18pub type ParentsView<'a> = Parents<&'a [Parent]>;
19pub type ParentsViewMut<'a> = Parents<&'a mut [Parent]>;
20pub type ParentsOwned = Parents<Vec<Parent>>;
21
22impl<S: Deref<Target = [Parent]>> Parents<S> {
23    /// Get the parent of a node. Returns None if the node is a root.
24    ///
25    /// # Panics
26    ///
27    /// * if node is out of bounds
28    pub fn get_parent(&self, node: usize) -> Option<usize> {
29        self.parents[node]
30    }
31
32    /// Test whether a node is a root.
33    ///
34    /// # Panics
35    ///
36    /// * if node is out of bounds
37    pub fn is_root(&self, node: usize) -> bool {
38        self.parents[node].is_none()
39    }
40
41    /// The number of nodes in this tree.
42    pub fn nb_nodes(&self) -> usize {
43        self.parents.len()
44    }
45
46    /// Get a view of this object
47    pub fn view(&self) -> ParentsView<'_> {
48        ParentsView {
49            parents: &self.parents[..],
50        }
51    }
52}
53
54impl<S: DerefMut<Target = [Parent]>> Parents<S> {
55    /// Set the parent of a node.
56    ///
57    /// # Panics
58    ///
59    /// * if node is out of bounds
60    /// * if parent is out of bounds
61    pub fn set_parent(&mut self, node: usize, parent: usize) {
62        assert!(parent < self.nb_nodes(), "parent is out of bounds");
63        self.parents[node] = Some(parent);
64    }
65
66    /// Set a node as a root.
67    ///
68    /// # Panics
69    ///
70    /// * if node is out of bounds
71    pub fn set_root(&mut self, node: usize) {
72        self.parents[node] = None;
73    }
74
75    /// Give a parent to a root of the tree. No-op if the node was not a parent.
76    ///
77    /// # Panics
78    ///
79    /// if either node or parent is out of bounds
80    pub fn uproot(&mut self, node: usize, parent: usize) {
81        assert!(parent < self.nb_nodes(), "parent is out of bounds");
82        if self.is_root(node) {
83            self.set_parent(node, parent);
84        }
85    }
86
87    pub fn view_mut(&mut self) -> ParentsViewMut<'_> {
88        ParentsViewMut {
89            parents: &mut self.parents[..],
90        }
91    }
92}
93
94impl ParentsOwned {
95    /// Create a new tree with all nodes set as root
96    pub fn new(nb_nodes: usize) -> Self {
97        Self {
98            parents: vec![None; nb_nodes],
99        }
100    }
101}
sprs_rssn/sparse/linalg/etree.rs

sprs_rssn/sparse/linalg/
etree.rs
