wolf_graph/
dag.rs

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

wolf_graph/
dag.rs
