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

wolf_graph/
compound.rs
