wolf_graph/
forest.rs

1use std::borrow::Cow;
2
3use anyhow::Result;
4#[cfg(feature = "serde")]
5use serde::{ser::Serialize, de::Deserialize};
6
7use crate::{EdgeID, Edges, Error, MutableForest, MutableTree, NodeID, Nodes, VisitableForest, VisitableGraph};
8
9/// A forest is a graph that is a collection of trees.
10///
11/// Unlike a tree, a forest can have multiple roots.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct Forest<InnerTree>
14where
15    InnerTree: MutableTree<GData = (), NData = (), EData = ()>,
16{
17    tree: InnerTree,
18}
19
20/// A convenience type for a forest with no additional data on nodes or edges.
21pub type BlankForest = Forest<crate::BlankTree>;
22
23impl<Inner> Forest<Inner>
24where
25    Inner: MutableTree<GData = (), NData = (), EData = ()>,
26{
27    pub fn new_with_tree(tree: Inner) -> Self {
28        Forest { tree }
29    }
30}
31
32impl<Inner> Forest<Inner>
33where
34    Inner: MutableTree<GData = (), NData = (), EData = ()> + Default,
35{
36    pub fn new() -> Self {
37        Self::new_with_tree(Inner::default())
38    }
39}
40
41impl<Inner> Forest<Inner>
42where
43    Inner: MutableTree<GData = (), NData = (), EData = ()>,
44{
45    fn is_tree_root(&self, node: &NodeID) -> bool {
46        node == &self.tree.root()
47    }
48
49    fn check_not_tree_root(&self, node: &NodeID) -> Result<()> {
50        if self.is_tree_root(node) {
51            return Err(Error::NodeNotFound(node.clone()).into());
52        }
53        Ok(())
54    }
55}
56
57impl<Inner> Default for Forest<Inner>
58where
59    Inner: MutableTree<GData = (), NData = (), EData = ()> + Default,
60{
61    fn default() -> Self {
62        Self::new()
63    }
64}
65
66impl<Inner> VisitableGraph for Forest<Inner>
67where
68    Inner: VisitableGraph + MutableTree<GData = (), NData = (), EData = ()>,
69{
70    type GData = Inner::GData;
71    type NData = Inner::NData;
72    type EData = Inner::EData;
73
74    fn data(&self) -> &Self::GData {
75        self.tree.data()
76    }
77
78    fn node_data(&self, id: impl AsRef<NodeID>) -> Result<Cow<'static, Self::NData>> {
79        self.check_not_tree_root(id.as_ref())?;
80        self.tree.node_data(id)
81    }
82
83    fn edge_data(&self, id: impl AsRef<EdgeID>) -> Result<Cow<'static, Self::EData>> {
84        let id = id.as_ref();
85        self.check_not_tree_root(&self.tree.source(id)?)?;
86        self.tree.edge_data(id)
87    }
88
89    fn is_empty(&self) -> bool {
90        self.tree.node_count() < 1
91    }
92
93    fn node_count(&self) -> usize {
94        self.tree.node_count() - 1
95    }
96
97    fn edge_count(&self) -> usize {
98        self.tree.edge_count() - self.tree.out_degree(&self.tree.root()).unwrap()
99    }
100
101    fn all_nodes(&self) -> Nodes {
102        self.tree.non_roots()
103    }
104
105    fn all_edges(&self) -> Edges {
106        self.tree.all_edges()
107            .into_iter().filter(|edge| {
108                let source = self.tree.source(edge).unwrap();
109                !self.is_tree_root(&source)
110            })
111            .collect()
112    }
113
114    fn has_node(&self, node: impl AsRef<NodeID>) -> bool {
115        let node = node.as_ref();
116        !self.is_tree_root(node) && self.tree.has_node(node)
117    }
118
119    fn has_edge(&self, edge: impl AsRef<EdgeID>) -> bool {
120        self.source(edge).map_or(false, |source| !self.is_tree_root(&source))
121    }
122
123    fn has_edge_from_to(&self, source: impl AsRef<NodeID>, target: impl AsRef<NodeID>) -> bool {
124        let source = source.as_ref();
125        let target = target.as_ref();
126        !self.is_tree_root(source) && self.tree.has_edge_from_to(source, target)
127    }
128
129    fn has_edge_between(&self, a: impl AsRef<NodeID>, b: impl AsRef<NodeID>) -> bool {
130        let a = a.as_ref();
131        let b = b.as_ref();
132        !self.is_tree_root(a) && !self.is_tree_root(b) && self.tree.has_edge_between(a, b)
133    }
134
135    fn source(&self, id: impl AsRef<EdgeID>) -> Result<NodeID> {
136        let id = id.as_ref();
137        let source = self.tree.source(id)?;
138        if self.is_tree_root(&source) {
139            return Err(Error::EdgeNotFound(id.clone()).into());
140        }
141        Ok(source)
142    }
143
144    fn target(&self, id: impl AsRef<EdgeID>) -> Result<NodeID> {
145        let id = id.as_ref();
146        let source = self.tree.source(id)?;
147        if self.is_tree_root(&source) {
148            return Err(Error::EdgeNotFound(id.clone()).into());
149        }
150        self.tree.target(id)
151    }
152
153    fn endpoints(&self, id: impl AsRef<EdgeID>) -> Result<(NodeID, NodeID)> {
154        let id = id.as_ref();
155        let (source, target) = self.tree.endpoints(id)?;
156        if self.is_tree_root(&source) {
157            return Err(Error::EdgeNotFound(id.clone()).into());
158        }
159        Ok((source, target))
160    }
161
162    fn out_degree(&self, id: impl AsRef<NodeID>) -> Result<usize> {
163        let id = id.as_ref();
164        self.check_not_tree_root(id)?;
165        self.tree.out_degree(id)
166    }
167
168    fn in_degree(&self, id: impl AsRef<NodeID>) -> Result<usize> {
169        let id = id.as_ref();
170        self.check_not_tree_root(id)?;
171        if self.is_root(id)? {
172            return Ok(0);
173        }
174        self.tree.in_degree(id)
175    }
176
177    fn degree(&self, id: impl AsRef<NodeID>) -> Result<usize> {
178        let id = id.as_ref();
179        self.check_not_tree_root(id)?;
180        Ok(self.in_degree(id)? + self.out_degree(id)?)
181    }
182
183    fn out_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges> {
184        let id = id.as_ref();
185        self.check_not_tree_root(id)?;
186        self.tree.out_edges(id)
187    }
188
189    fn in_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges> {
190        let id = id.as_ref();
191        self.check_not_tree_root(id)?;
192        if self.is_root(id)? {
193            return Ok(Edges::default());
194        }
195        self.tree.in_edges(id)
196    }
197
198    fn incident_edges(&self, id: impl AsRef<NodeID>) -> Result<Edges> {
199        let id = id.as_ref();
200        self.check_not_tree_root(id)?;
201        let incident_edges = self.tree.incident_edges(id)?;
202        let root = self.tree.root();
203        Ok(incident_edges.into_iter().filter(|edge| self.tree.source(edge).unwrap() != root).collect())
204    }
205
206    fn has_successors(&self, id: impl AsRef<NodeID>) -> Result<bool> {
207        let id = id.as_ref();
208        self.check_not_tree_root(id)?;
209        self.tree.has_successors(id)
210    }
211
212    fn has_predecessors(&self, id: impl AsRef<NodeID>) -> Result<bool> {
213        let id = id.as_ref();
214        self.check_not_tree_root(id)?;
215        if self.is_root(id)? {
216            return Ok(false);
217        }
218        self.tree.has_predecessors(id)
219    }
220
221    fn has_neighbors(&self, id: impl AsRef<NodeID>) -> Result<bool> {
222        let id = id.as_ref();
223        Ok(self.has_successors(id)? || self.has_predecessors(id)?)
224    }
225
226    fn successors(&self, id: impl AsRef<NodeID>) -> Result<Nodes> {
227        let id = id.as_ref();
228        self.check_not_tree_root(id)?;
229        self.tree.successors(id)
230    }
231
232    fn predecessors(&self, id: impl AsRef<NodeID>) -> Result<Nodes> {
233        let id = id.as_ref();
234        self.check_not_tree_root(id)?;
235        if self.is_root(id)? {
236            return Ok(Nodes::default());
237        }
238        self.tree.predecessors(id)
239    }
240
241    fn neighbors(&self, id: impl AsRef<NodeID>) -> Result<Nodes> {
242        let id = id.as_ref();
243        self.check_not_tree_root(id)?;
244        Ok(self.tree.neighbors(id)?.into_iter().filter(|node| *node != self.tree.root()).collect())
245    }
246
247    fn all_roots(&self) -> Nodes {
248        self.tree.successors(&self.tree.root()).unwrap_or_default()
249    }
250
251    fn all_leaves(&self) -> Nodes {
252        self.tree.all_leaves().into_iter().filter(|node| *node != self.tree.root()).collect()
253    }
254
255    fn non_roots(&self) -> Nodes {
256        let roots = self.all_roots();
257        self.all_nodes().into_iter().filter(|node| !roots.contains(node)).collect()
258    }
259
260    fn non_leaves(&self) -> Nodes {
261        let leaves = self.all_leaves();
262        self.all_nodes().into_iter().filter(|node| !leaves.contains(node)).collect()
263    }
264
265    fn all_internals(&self) -> Nodes {
266        let leaves = self.all_leaves();
267        self.all_nodes().into_iter().filter(|node| !leaves.contains(node)).collect()
268    }
269
270    fn is_leaf(&self, node: impl AsRef<NodeID>) -> Result<bool> {
271        let node = node.as_ref();
272        self.check_not_tree_root(node)?;
273        self.tree.is_leaf(node)
274    }
275
276    fn is_root(&self, node: impl AsRef<NodeID>) -> Result<bool> {
277        let node = node.as_ref();
278        if node == &self.tree.root() {
279            return Err(Error::NodeNotFound(node.clone()).into());
280        }
281        let in_edge = self.tree.in_edge(node)?.unwrap();
282        Ok(self.tree.source(&in_edge)? == self.tree.root())
283    }
284
285    fn is_internal(&self, node: impl AsRef<NodeID>) -> Result<bool> {
286        let node = node.as_ref();
287        self.check_not_tree_root(node)?;
288        if self.is_root(node)? {
289            return Ok(false);
290        }
291        self.tree.is_internal(node)
292    }
293}
294
295impl<Inner> VisitableForest for Forest<Inner>
296where
297    Inner: VisitableForest + MutableTree<GData = (), NData = (), EData = ()>,
298{
299    fn in_edge(&self, node: impl AsRef<NodeID>) -> Result<Option<EdgeID>> {
300        let node = node.as_ref();
301        self.check_not_tree_root(node)?;
302        self.tree.in_edge(node)
303    }
304
305    fn in_edge_with_root(&self, node: impl AsRef<NodeID>) -> Result<Option<EdgeID>> {
306        self.tree.in_edge(node.as_ref())
307    }
308
309    fn parent(&self, node: impl AsRef<NodeID>) -> Result<Option<NodeID>> {
310        let node = node.as_ref();
311        self.check_not_tree_root(node)?;
312        if self.is_root(node)? {
313            return Ok(None);
314        }
315        self.tree.parent(node)
316    }
317
318    fn children(&self, node: Option<impl AsRef<NodeID>>) -> Result<Nodes> {
319        let node = node.as_ref();
320        if let Some(node) = node {
321            self.check_not_tree_root(node.as_ref())?;
322        }
323        self.tree.children(node)
324    }
325
326    fn has_children(&self, node: impl AsRef<NodeID>) -> Result<bool> {
327        let node = node.as_ref();
328        self.check_not_tree_root(node)?;
329        self.tree.has_children(node)
330    }
331
332    fn child_count(&self, node: impl AsRef<NodeID>) -> Result<usize> {
333        let node = node.as_ref();
334        self.check_not_tree_root(node)?;
335        self.tree.child_count(node)
336    }
337}
338
339// MutableForest implementation
340impl<Inner> MutableForest for Forest<Inner>
341where
342    Inner: MutableForest + MutableTree<GData = (), NData = (), EData = ()>,
343{
344    fn add_node_with_node_and_edge_data(&mut self, node: impl AsRef<NodeID>, parent: Option<impl AsRef<NodeID>>, edge: impl AsRef<EdgeID>, node_data: Self::NData, edge_data: Self::EData) -> Result<()> {
345        self.tree.add_node_with_node_and_edge_data(node, parent, edge, node_data, edge_data)
346    }
347
348    fn remove_node_ungrouping(&mut self, id: impl AsRef<NodeID>) -> Result<()> {
349        let id = id.as_ref();
350        self.check_not_tree_root(id)?;
351        self.tree.remove_node_ungrouping(id)
352    }
353
354    fn remove_node_and_children(&mut self, id: impl AsRef<NodeID>) -> Result<Nodes> {
355        let id = id.as_ref();
356        self.check_not_tree_root(id)?;
357        self.tree.remove_node_and_children(id)
358    }
359
360    fn remove_children(&mut self, id: impl AsRef<NodeID>) -> Result<Nodes> {
361        self.tree.remove_children(id)
362    }
363
364    fn move_node(&mut self, id: impl AsRef<NodeID>, new_parent: Option<impl AsRef<NodeID>>) -> Result<()> {
365        let id = id.as_ref();
366        self.check_not_tree_root(id)?;
367        self.tree.move_node(id, new_parent)
368    }
369
370    fn set_data(&mut self, data: Self::GData) {
371        self.tree.set_data(data)
372    }
373
374    fn set_node_data(&mut self, id: impl AsRef<NodeID>, data: Self::NData) -> Result<()> {
375        let id = id.as_ref();
376        self.check_not_tree_root(id)?;
377        self.tree.set_node_data(id, data)
378    }
379
380    fn set_edge_data(&mut self, id: impl AsRef<EdgeID>, data: Self::EData) -> Result<()> {
381        let id = id.as_ref();
382        let source = self.tree.source(id)?;
383        self.check_not_tree_root(&source)?;
384        self.tree.set_edge_data(id, data)
385    }
386
387    fn with_data(&mut self, transform: &dyn Fn(&mut Self::GData)) {
388        self.tree.with_data(transform);
389    }
390
391    fn with_node_data(&mut self, id: impl AsRef<NodeID>, transform: &dyn Fn(&mut Self::NData)) -> Result<()> {
392        self.tree.with_node_data(id, transform)
393    }
394
395    fn with_edge_data(&mut self, id: impl AsRef<EdgeID>, transform: &dyn Fn(&mut Self::EData)) -> Result<()> {
396        self.tree.with_edge_data(id, transform)
397    }
398}
399
400#[cfg(feature = "serde")]
401impl<Inner> Serialize for Forest<Inner>
402where
403    Inner: Serialize + MutableTree<GData = (), NData = (), EData = ()>
404{
405    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
406    where
407        S: serde::ser::Serializer,
408    {
409        self.tree.serialize(serializer)
410    }
411}
412
413#[cfg(feature = "serde")]
414impl<'de, Inner> Deserialize<'de> for Forest<Inner>
415where
416    Inner: Deserialize<'de> + MutableTree<GData = (), NData = (), EData = ()>
417{
418    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
419    where
420        D: serde::de::Deserializer<'de>,
421    {
422        Inner::deserialize(deserializer).map(Self::new_with_tree)
423    }
424}
425
426// If Serde and SerdeJSON are both present, add conveniences to serialize a Tree
427// to JSON.
428#[cfg(all(feature = "serde", feature = "serde_json"))]
429impl<Inner> Forest<Inner>
430where
431    Inner: Serialize + MutableTree<GData = (), NData = (), EData = ()>
432{
433    pub fn to_json(&self) -> Result<String> {
434        serde_json::to_string(self).map_err(Into::into)
435    }
436}
437
438// If Serde and SerdeJSON are both present, add conveniences to serialize a Tree
439// to JSON.
440#[cfg(all(feature = "serde", feature = "serde_json"))]
441impl<'de, Inner> Forest<Inner>
442where
443    Inner: MutableTree<GData = (), NData = (), EData = ()> + Deserialize<'de>,
444{
445    pub fn from_json(json: &'de str) -> Result<Self, serde_json::Error> {
446        serde_json::from_str(json)
447    }
448}
449
450#[cfg(all(feature = "serde", feature = "serde_json"))]
451impl<Inner> std::fmt::Display for Forest<Inner>
452where
453    Inner: MutableTree<GData = (), NData = (), EData = ()> + Serialize,
454{
455    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
456        write!(f, "{}", self.to_json().unwrap())
457    }
458}
wolf_graph/forest.rs

wolf_graph/
forest.rs
