petgraph/
acyclic.rs

Help
1//! A wrapper around graph types that enforces an acyclicity invariant.
2
3use alloc::collections::{BTreeMap, BTreeSet};
4use core::{
5    cell::RefCell,
6    cmp::Ordering,
7    convert::TryFrom,
8    ops::{Deref, RangeBounds},
9};
10
11use crate::{
12    adj::IndexType,
13    algo::Cycle,
14    data::{Build, Create, DataMap, DataMapMut},
15    graph::NodeIndex,
16    prelude::DiGraph,
17    visit::{
18        dfs_visitor, Control, Data, DfsEvent, EdgeCount, EdgeIndexable, GetAdjacencyMatrix,
19        GraphBase, GraphProp, IntoEdgeReferences, IntoEdges, IntoEdgesDirected, IntoNeighbors,
20        IntoNeighborsDirected, IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable,
21        NodeCount, NodeIndexable, Reversed, Time, Visitable,
22    },
23    Direction,
24};
25
26#[cfg(feature = "stable_graph")]
27use crate::stable_graph::StableDiGraph;
28
29mod order_map;
30use fixedbitset::FixedBitSet;
31use order_map::OrderMap;
32pub use order_map::TopologicalPosition;
33
34/// A directed acyclic graph.
35///
36/// Wrap directed acyclic graphs and expose an API that ensures the invariant
37/// is maintained, i.e. no cycles can be created. This uses a topological order
38/// that is dynamically updated when edges are added. In the worst case, the
39/// runtime may be linear in the number of vertices, but it has been shown to
40/// be fast in practice, particularly on sparse graphs (Pierce and Kelly, 2004).
41///
42/// To be modifiable (and hence to be useful), the graphs of generic type `G`
43/// should implement the [`Build`] trait. Good candidates for `G` are thus
44/// [`crate::graph::DiGraph`] and [`crate::stable_graph::StableDiGraph`].
45///
46/// ## Algorithm
47/// This implements the PK algorithm for dynamic topological sort described in
48/// "A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs" by
49/// D. Pierce and P. Kelly, JEA, 2004. It maintains a topological order of the
50/// nodes that can be efficiently updated when edges are added. Achieves a good
51/// balance between simplicity and performance in practice, see the paper for
52/// discussions of the running time.
53///
54/// ## Graph traits
55/// All graph traits are delegated to the inner graph, with the exception of
56/// the graph construction trait [`Build`]. The wrapped graph can thus only
57/// be modified through the wrapped API that ensures no cycles are created.
58///
59/// ## Behaviour on cycles
60/// By design, edge additions to this datatype may fail. It is recommended to
61/// prefer the dedicated [`Acyclic::try_add_edge`] and
62/// [`Acyclic::try_update_edge`] methods whenever possible. The
63/// [`Build::update_edge`] methods will panic if it is attempted to add an edge
64/// that would create a cycle. The [`Build::add_edge`] on the other hand method
65/// will return `None` if the edge cannot be added (either it already exists on
66/// a graph type that does not support it or would create a cycle).
67#[derive(Clone, Debug)]
68pub struct Acyclic<G: Visitable> {
69    /// The underlying graph, accessible through the `inner` method.
70    graph: G,
71    /// The current topological order of the nodes.
72    order_map: OrderMap<G::NodeId>,
73
74    // We fix the internal DFS maps to FixedBitSet instead of G::VisitMap to do
75    // faster resets (by just setting bits to false)
76    /// Helper map for DFS tracking discovered nodes.
77    discovered: RefCell<FixedBitSet>,
78    /// Helper map for DFS tracking finished nodes.
79    finished: RefCell<FixedBitSet>,
80}
81
82/// An error that can occur during edge addition for acyclic graphs.
83#[derive(Clone, Debug, PartialEq)]
84pub enum AcyclicEdgeError<N> {
85    /// The edge would create a cycle.
86    Cycle(Cycle<N>),
87    /// The edge would create a self-loop.
88    SelfLoop,
89    /// Could not successfully add the edge to the underlying graph.
90    InvalidEdge,
91}
92
93impl<N> From<Cycle<N>> for AcyclicEdgeError<N> {
94    fn from(cycle: Cycle<N>) -> Self {
95        AcyclicEdgeError::Cycle(cycle)
96    }
97}
98
99impl<G: Visitable> Acyclic<G> {
100    /// Create a new empty acyclic graph.
101    pub fn new() -> Self
102    where
103        G: Default,
104    {
105        Default::default()
106    }
107
108    /// Get an iterator over the nodes, ordered by their position.
109    pub fn nodes_iter(&self) -> impl Iterator<Item = G::NodeId> + '_ {
110        self.order_map.nodes_iter()
111    }
112
113    /// Get an iterator over the nodes within the range of positions.
114    ///
115    /// The nodes are ordered by their position in the topological sort.
116    pub fn range<'r>(
117        &'r self,
118        range: impl RangeBounds<TopologicalPosition> + 'r,
119    ) -> impl Iterator<Item = G::NodeId> + 'r {
120        self.order_map.range(range)
121    }
122
123    /// Get the underlying graph.
124    pub fn inner(&self) -> &G {
125        &self.graph
126    }
127
128    /// Get the underlying graph mutably.
129    ///
130    /// This cannot be public because it might break the acyclicity invariant.
131    fn inner_mut(&mut self) -> &mut G {
132        &mut self.graph
133    }
134
135    /// Consume the `Acyclic` wrapper and return the underlying graph.
136    pub fn into_inner(self) -> G {
137        self.graph
138    }
139}
140
141impl<G: Visitable + NodeIndexable> Acyclic<G>
142where
143    for<'a> &'a G: IntoNeighborsDirected + IntoNodeIdentifiers + GraphBase<NodeId = G::NodeId>,
144{
145    /// Wrap a graph into an acyclic graph.
146    ///
147    /// The graph types [`DiGraph`] and [`StableDiGraph`] also implement
148    /// [`TryFrom`], which can be used instead of this method and have looser
149    /// type bounds.
150    pub fn try_from_graph(graph: G) -> Result<Self, Cycle<G::NodeId>> {
151        let order_map = OrderMap::try_from_graph(&graph)?;
152        let discovered = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
153        let finished = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
154        Ok(Self {
155            graph,
156            order_map,
157            discovered,
158            finished,
159        })
160    }
161
162    /// Add an edge to the graph using [`Build::add_edge`].
163    ///
164    /// Returns the id of the added edge, or an [`AcyclicEdgeError`] if the edge
165    /// would create a cycle, a self-loop or if the edge addition failed in
166    /// the underlying graph.
167    ///
168    /// In cases where edge addition cannot fail in the underlying graph (e.g.
169    /// when multi-edges are allowed, as in [`DiGraph`] and [`StableDiGraph`]),
170    /// this will return an error if and only if [`Self::is_valid_edge`]
171    /// returns `false`.
172    ///
173    /// **Panics** if `a` or `b` are not found.
174    #[track_caller]
175    pub fn try_add_edge(
176        &mut self,
177        a: G::NodeId,
178        b: G::NodeId,
179        weight: G::EdgeWeight,
180    ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>
181    where
182        G: Build,
183        G::NodeId: IndexType,
184    {
185        if a == b {
186            // No self-loops allowed
187            return Err(AcyclicEdgeError::SelfLoop);
188        }
189        self.update_ordering(a, b)?;
190        self.graph
191            .add_edge(a, b, weight)
192            .ok_or(AcyclicEdgeError::InvalidEdge)
193    }
194
195    /// Update an edge in a graph using [`Build::update_edge`].
196    ///
197    /// Returns the id of the updated edge, or an [`AcyclicEdgeError`] if the edge
198    /// would create a cycle or a self-loop. If the edge does not exist, the
199    /// edge is created.
200    ///
201    /// This will return an error if and only if [`Self::is_valid_edge`] returns
202    /// `false`.
203    ///
204    /// **Panics** if `a` or `b` are not found.
205    pub fn try_update_edge(
206        &mut self,
207        a: G::NodeId,
208        b: G::NodeId,
209        weight: G::EdgeWeight,
210    ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>
211    where
212        G: Build,
213        G::NodeId: IndexType,
214    {
215        if a == b {
216            // No self-loops allowed
217            return Err(AcyclicEdgeError::SelfLoop);
218        }
219        self.update_ordering(a, b)?;
220        Ok(self.graph.update_edge(a, b, weight))
221    }
222
223    /// Check if an edge would be valid, i.e. adding it would not create a cycle.
224    ///
225    /// **Panics** if `a` or `b` are not found.
226    pub fn is_valid_edge(&self, a: G::NodeId, b: G::NodeId) -> bool
227    where
228        G::NodeId: IndexType,
229    {
230        if a == b {
231            false // No self-loops
232        } else if self.get_position(a) < self.get_position(b) {
233            true // valid edge in the current topological order
234        } else {
235            // Check if the future of `b` is disjoint from the past of `a`
236            // (in which case the topological order could be adjusted)
237            self.causal_cones(b, a).is_ok()
238        }
239    }
240
241    /// Update the ordering of the nodes in the order map resulting from adding an
242    /// edge a -> b.
243    ///
244    /// If a cycle is detected, an error is returned and `self` remains unchanged.
245    ///
246    /// Implements the core update logic of the PK algorithm.
247    #[track_caller]
248    fn update_ordering(&mut self, a: G::NodeId, b: G::NodeId) -> Result<(), Cycle<G::NodeId>>
249    where
250        G::NodeId: IndexType,
251    {
252        let min_order = self.get_position(b);
253        let max_order = self.get_position(a);
254        if min_order >= max_order {
255            // Order is already correct
256            return Ok(());
257        }
258
259        // Get the nodes reachable from `b` and the nodes that can reach `a`
260        // between `min_order` and `max_order`
261        let (b_fut, a_past) = self.causal_cones(b, a)?;
262
263        // Now reorder of nodes in a_past and b_fut such that
264        //  i) within each vec, the nodes are in topological order,
265        // ii) all elements of b_fut come before all elements of a_past in the new order.
266        let all_positions: BTreeSet<_> = b_fut.keys().chain(a_past.keys()).copied().collect();
267        let all_nodes = a_past.values().chain(b_fut.values()).copied();
268
269        debug_assert_eq!(all_positions.len(), b_fut.len() + a_past.len());
270
271        for (pos, node) in all_positions.into_iter().zip(all_nodes) {
272            self.order_map.set_position(node, pos, &self.graph);
273        }
274        Ok(())
275    }
276
277    /// Use DFS to find the future causal cone of `min_node` and the past causal
278    /// cone of `max_node`.
279    ///
280    /// The cones are trimmed to the range `[min_order, max_order]`. The cones
281    /// are returned if they are disjoint. Otherwise, a [`Cycle`] error is returned.
282    ///
283    /// If `return_result` is false, then the cones are not constructed and the
284    /// method only checks for disjointness.
285    #[allow(clippy::type_complexity)]
286    fn causal_cones(
287        &self,
288        min_node: G::NodeId,
289        max_node: G::NodeId,
290    ) -> Result<
291        (
292            BTreeMap<TopologicalPosition, G::NodeId>,
293            BTreeMap<TopologicalPosition, G::NodeId>,
294        ),
295        Cycle<G::NodeId>,
296    >
297    where
298        G::NodeId: IndexType,
299    {
300        debug_assert!(self.discovered.borrow().is_clear());
301        debug_assert!(self.finished.borrow().is_clear());
302
303        let min_order = self.get_position(min_node);
304        let max_order = self.get_position(max_node);
305
306        // Prepare DFS scratch space: make sure the maps have enough capacity
307        if self.discovered.borrow().len() < self.graph.node_bound() {
308            self.discovered.borrow_mut().grow(self.graph.node_bound());
309            self.finished.borrow_mut().grow(self.graph.node_bound());
310        }
311
312        // Get all nodes reachable from b with min_order <= order < max_order
313        let mut forward_cone = BTreeMap::new();
314        let mut backward_cone = BTreeMap::new();
315
316        // The main logic: run DFS twice. We run this in a closure to catch
317        // errors and reset the maps properly at the end.
318        let mut run_dfs = || {
319            // Get all nodes reachable from min_node with min_order < order <= max_order
320            self.future_cone(min_node, min_order, max_order, &mut forward_cone)?;
321
322            // Get all nodes that can reach a with min_order < order <= max_order
323            // These are disjoint from the nodes in the forward cone, otherwise
324            // we would have a cycle.
325            self.past_cone(max_node, min_order, max_order, &mut backward_cone)
326                .expect("cycles already checked in future_cone");
327
328            Ok(())
329        };
330
331        let success = run_dfs();
332
333        // Cleanup: reset map to 0. This is faster than a full reset, especially
334        // on large sparse graphs.
335        for &v in forward_cone.values().chain(backward_cone.values()) {
336            self.discovered.borrow_mut().set(v.index(), false);
337            self.finished.borrow_mut().set(v.index(), false);
338        }
339        debug_assert!(self.discovered.borrow().is_clear());
340        debug_assert!(self.finished.borrow().is_clear());
341
342        match success {
343            Ok(()) => Ok((forward_cone, backward_cone)),
344            Err(cycle) => Err(cycle),
345        }
346    }
347
348    fn future_cone(
349        &self,
350        start: G::NodeId,
351        min_position: TopologicalPosition,
352        max_position: TopologicalPosition,
353        res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
354    ) -> Result<(), Cycle<G::NodeId>>
355    where
356        G::NodeId: IndexType,
357    {
358        dfs(
359            &self.graph,
360            start,
361            &self.order_map,
362            |order| {
363                debug_assert!(order >= min_position, "invalid topological order");
364                match order.cmp(&max_position) {
365                    Ordering::Less => Ok(true),           // node within [min_node, max_node]
366                    Ordering::Equal => Err(Cycle(start)), // cycle!
367                    Ordering::Greater => Ok(false),       // node beyond [min_node, max_node]
368                }
369            },
370            res,
371            &mut self.discovered.borrow_mut(),
372            &mut self.finished.borrow_mut(),
373        )
374    }
375
376    fn past_cone(
377        &self,
378        start: G::NodeId,
379        min_position: TopologicalPosition,
380        max_position: TopologicalPosition,
381        res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
382    ) -> Result<(), Cycle<G::NodeId>>
383    where
384        G::NodeId: IndexType,
385    {
386        dfs(
387            Reversed(&self.graph),
388            start,
389            &self.order_map,
390            |order| {
391                debug_assert!(order <= max_position, "invalid topological order");
392                match order.cmp(&min_position) {
393                    Ordering::Less => Ok(false), // node beyond [min_node, max_node]
394                    Ordering::Equal => unreachable!("checked by future_cone"), // cycle!
395                    Ordering::Greater => Ok(true), // node within [min_node, max_node]
396                }
397            },
398            res,
399            &mut self.discovered.borrow_mut(),
400            &mut self.finished.borrow_mut(),
401        )
402    }
403}
404
405impl<G: Visitable> GraphBase for Acyclic<G> {
406    type NodeId = G::NodeId;
407    type EdgeId = G::EdgeId;
408}
409
410impl<G: Default + Visitable> Default for Acyclic<G> {
411    fn default() -> Self {
412        let graph: G = Default::default();
413        let order_map = Default::default();
414        let discovered = RefCell::new(FixedBitSet::default());
415        let finished = RefCell::new(FixedBitSet::default());
416        Self {
417            graph,
418            order_map,
419            discovered,
420            finished,
421        }
422    }
423}
424
425impl<G: Build + Visitable + NodeIndexable> Build for Acyclic<G>
426where
427    for<'a> &'a G: IntoNeighborsDirected
428        + IntoNodeIdentifiers
429        + Visitable<Map = G::Map>
430        + GraphBase<NodeId = G::NodeId>,
431    G::NodeId: IndexType,
432{
433    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
434        let n = self.graph.add_node(weight);
435        self.order_map.add_node(n, &self.graph);
436        n
437    }
438
439    fn add_edge(
440        &mut self,
441        a: Self::NodeId,
442        b: Self::NodeId,
443        weight: Self::EdgeWeight,
444    ) -> Option<Self::EdgeId> {
445        self.try_add_edge(a, b, weight).ok()
446    }
447
448    fn update_edge(
449        &mut self,
450        a: Self::NodeId,
451        b: Self::NodeId,
452        weight: Self::EdgeWeight,
453    ) -> Self::EdgeId {
454        self.try_update_edge(a, b, weight).unwrap()
455    }
456}
457
458impl<G: Create + Visitable + NodeIndexable> Create for Acyclic<G>
459where
460    for<'a> &'a G: IntoNeighborsDirected
461        + IntoNodeIdentifiers
462        + Visitable<Map = G::Map>
463        + GraphBase<NodeId = G::NodeId>,
464    G::NodeId: IndexType,
465{
466    fn with_capacity(nodes: usize, edges: usize) -> Self {
467        let graph = G::with_capacity(nodes, edges);
468        let order_map = OrderMap::with_capacity(nodes);
469        let discovered = FixedBitSet::with_capacity(nodes);
470        let finished = FixedBitSet::with_capacity(nodes);
471        Self {
472            graph,
473            order_map,
474            discovered: RefCell::new(discovered),
475            finished: RefCell::new(finished),
476        }
477    }
478}
479
480impl<G: Visitable> Deref for Acyclic<G> {
481    type Target = G;
482
483    fn deref(&self) -> &Self::Target {
484        &self.graph
485    }
486}
487
488/// Traverse nodes in `graph` in DFS order, starting from `start`, for as long
489/// as the predicate `valid_order` returns `true` on the current node's order.
490fn dfs<G: NodeIndexable + IntoNeighborsDirected + IntoNodeIdentifiers + Visitable>(
491    graph: G,
492    start: G::NodeId,
493    order_map: &OrderMap<G::NodeId>,
494    // A predicate that returns whether to continue the search from a node,
495    // or an error to stop and shortcircuit the search.
496    mut valid_order: impl FnMut(TopologicalPosition) -> Result<bool, Cycle<G::NodeId>>,
497    res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
498    discovered: &mut FixedBitSet,
499    finished: &mut FixedBitSet,
500) -> Result<(), Cycle<G::NodeId>>
501where
502    G::NodeId: IndexType,
503{
504    dfs_visitor(
505        graph,
506        start,
507        &mut |ev| -> Result<Control<()>, Cycle<G::NodeId>> {
508            match ev {
509                DfsEvent::Discover(u, _) => {
510                    // We are visiting u
511                    let order = order_map.get_position(u, &graph);
512                    res.insert(order, u);
513                    Ok(Control::Continue)
514                }
515                DfsEvent::TreeEdge(_, u) => {
516                    // Should we visit u?
517                    let order = order_map.get_position(u, &graph);
518                    match valid_order(order) {
519                        Ok(true) => Ok(Control::Continue),
520                        Ok(false) => Ok(Control::Prune),
521                        Err(cycle) => Err(cycle),
522                    }
523                }
524                _ => Ok(Control::Continue),
525            }
526        },
527        discovered,
528        finished,
529        &mut Time::default(),
530    )?;
531
532    Ok(())
533}
534
535/////////////////////// Pass-through graph traits ///////////////////////
536// We implement all the following traits by delegating to the inner graph:
537// - Data
538// - DataMap
539// - DataMapMut
540// - EdgeCount
541// - EdgeIndexable
542// - GetAdjacencyMatrix
543// - GraphProp
544// - NodeCompactIndexable
545// - NodeCount
546// - NodeIndexable
547// - Visitable
548//
549// Furthermore, we also implement the `remove_node` and `remove_edge` methods,
550// as well as the following traits for `DiGraph` and `StableDiGraph` (these
551// are hard/impossible to implement generically):
552// - TryFrom
553// - IntoEdgeReferences
554// - IntoEdges
555// - IntoEdgesDirected
556// - IntoNeighbors
557// - IntoNeighborsDirected
558// - IntoNodeIdentifiers
559// - IntoNodeReferences
560
561impl<G: Visitable + Data> Data for Acyclic<G> {
562    type NodeWeight = G::NodeWeight;
563    type EdgeWeight = G::EdgeWeight;
564}
565
566impl<G: Visitable + DataMap> DataMap for Acyclic<G> {
567    fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
568        self.inner().node_weight(id)
569    }
570
571    fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
572        self.inner().edge_weight(id)
573    }
574}
575
576impl<G: Visitable + DataMapMut> DataMapMut for Acyclic<G> {
577    fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
578        self.inner_mut().node_weight_mut(id)
579    }
580
581    fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
582        self.inner_mut().edge_weight_mut(id)
583    }
584}
585
586impl<G: Visitable + EdgeCount> EdgeCount for Acyclic<G> {
587    fn edge_count(&self) -> usize {
588        self.inner().edge_count()
589    }
590}
591
592impl<G: Visitable + EdgeIndexable> EdgeIndexable for Acyclic<G> {
593    fn edge_bound(&self) -> usize {
594        self.inner().edge_bound()
595    }
596
597    fn to_index(&self, a: Self::EdgeId) -> usize {
598        self.inner().to_index(a)
599    }
600
601    fn from_index(&self, i: usize) -> Self::EdgeId {
602        self.inner().from_index(i)
603    }
604}
605
606impl<G: Visitable + GetAdjacencyMatrix> GetAdjacencyMatrix for Acyclic<G> {
607    type AdjMatrix = G::AdjMatrix;
608
609    fn adjacency_matrix(&self) -> Self::AdjMatrix {
610        self.inner().adjacency_matrix()
611    }
612
613    fn is_adjacent(&self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool {
614        self.inner().is_adjacent(matrix, a, b)
615    }
616}
617
618impl<G: Visitable + GraphProp> GraphProp for Acyclic<G> {
619    type EdgeType = G::EdgeType;
620}
621
622impl<G: Visitable + NodeCompactIndexable> NodeCompactIndexable for Acyclic<G> {}
623
624impl<G: Visitable + NodeCount> NodeCount for Acyclic<G> {
625    fn node_count(&self) -> usize {
626        self.inner().node_count()
627    }
628}
629
630impl<G: Visitable + NodeIndexable> NodeIndexable for Acyclic<G> {
631    fn node_bound(&self) -> usize {
632        self.inner().node_bound()
633    }
634
635    fn to_index(&self, a: Self::NodeId) -> usize {
636        self.inner().to_index(a)
637    }
638
639    fn from_index(&self, i: usize) -> Self::NodeId {
640        self.inner().from_index(i)
641    }
642}
643
644impl<G: Visitable> Visitable for Acyclic<G> {
645    type Map = G::Map;
646
647    fn visit_map(&self) -> Self::Map {
648        self.inner().visit_map()
649    }
650
651    fn reset_map(&self, map: &mut Self::Map) {
652        self.inner().reset_map(map)
653    }
654}
655
656macro_rules! impl_graph_traits {
657    ($graph_type:ident) => {
658        // Remove edge and node methods (not available through traits)
659        impl<N, E, Ix: IndexType> Acyclic<$graph_type<N, E, Ix>> {
660            /// Remove an edge and return its edge weight, or None if it didn't exist.
661            ///
662            /// Pass through to underlying graph.
663            pub fn remove_edge(
664                &mut self,
665                e: <$graph_type<N, E, Ix> as GraphBase>::EdgeId,
666            ) -> Option<E> {
667                self.graph.remove_edge(e)
668            }
669
670            /// Remove a node from the graph if it exists, and return its
671            /// weight. If it doesn't exist in the graph, return None.
672            ///
673            /// This updates the order in O(v) runtime and removes the node in
674            /// the underlying graph.
675            pub fn remove_node(
676                &mut self,
677                n: <$graph_type<N, E, Ix> as GraphBase>::NodeId,
678            ) -> Option<N> {
679                self.order_map.remove_node(n, &self.graph);
680                self.graph.remove_node(n)
681            }
682        }
683
684        impl<N, E, Ix: IndexType> TryFrom<$graph_type<N, E, Ix>>
685            for Acyclic<$graph_type<N, E, Ix>>
686        {
687            type Error = Cycle<NodeIndex<Ix>>;
688
689            fn try_from(graph: $graph_type<N, E, Ix>) -> Result<Self, Self::Error> {
690                let order_map = OrderMap::try_from_graph(&graph)?;
691                let discovered = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
692                let finished = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
693                Ok(Self {
694                    graph,
695                    order_map,
696                    discovered,
697                    finished,
698                })
699            }
700        }
701
702        impl<'a, N, E, Ix: IndexType> IntoEdgeReferences for &'a Acyclic<$graph_type<N, E, Ix>> {
703            type EdgeRef = <&'a $graph_type<N, E, Ix> as IntoEdgeReferences>::EdgeRef;
704            type EdgeReferences = <&'a $graph_type<N, E, Ix> as IntoEdgeReferences>::EdgeReferences;
705
706            fn edge_references(self) -> Self::EdgeReferences {
707                self.inner().edge_references()
708            }
709        }
710
711        impl<'a, N, E, Ix: IndexType> IntoEdges for &'a Acyclic<$graph_type<N, E, Ix>> {
712            type Edges = <&'a $graph_type<N, E, Ix> as IntoEdges>::Edges;
713
714            fn edges(self, a: Self::NodeId) -> Self::Edges {
715                self.inner().edges(a)
716            }
717        }
718
719        impl<'a, N, E, Ix: IndexType> IntoEdgesDirected for &'a Acyclic<$graph_type<N, E, Ix>> {
720            type EdgesDirected = <&'a $graph_type<N, E, Ix> as IntoEdgesDirected>::EdgesDirected;
721
722            fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
723                self.inner().edges_directed(a, dir)
724            }
725        }
726
727        impl<'a, N, E, Ix: IndexType> IntoNeighbors for &'a Acyclic<$graph_type<N, E, Ix>> {
728            type Neighbors = <&'a $graph_type<N, E, Ix> as IntoNeighbors>::Neighbors;
729
730            fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
731                self.inner().neighbors(a)
732            }
733        }
734
735        impl<'a, N, E, Ix: IndexType> IntoNeighborsDirected for &'a Acyclic<$graph_type<N, E, Ix>> {
736            type NeighborsDirected =
737                <&'a $graph_type<N, E, Ix> as IntoNeighborsDirected>::NeighborsDirected;
738
739            fn neighbors_directed(self, n: Self::NodeId, d: Direction) -> Self::NeighborsDirected {
740                self.inner().neighbors_directed(n, d)
741            }
742        }
743
744        impl<'a, N, E, Ix: IndexType> IntoNodeIdentifiers for &'a Acyclic<$graph_type<N, E, Ix>> {
745            type NodeIdentifiers =
746                <&'a $graph_type<N, E, Ix> as IntoNodeIdentifiers>::NodeIdentifiers;
747
748            fn node_identifiers(self) -> Self::NodeIdentifiers {
749                self.inner().node_identifiers()
750            }
751        }
752
753        impl<'a, N, E, Ix: IndexType> IntoNodeReferences for &'a Acyclic<$graph_type<N, E, Ix>> {
754            type NodeRef = <&'a $graph_type<N, E, Ix> as IntoNodeReferences>::NodeRef;
755            type NodeReferences = <&'a $graph_type<N, E, Ix> as IntoNodeReferences>::NodeReferences;
756
757            fn node_references(self) -> Self::NodeReferences {
758                self.inner().node_references()
759            }
760        }
761    };
762}
763
764impl_graph_traits!(DiGraph);
765#[cfg(feature = "stable_graph")]
766impl_graph_traits!(StableDiGraph);
767
768#[cfg(test)]
769mod tests {
770    use alloc::vec::Vec;
771
772    use super::*;
773    use crate::prelude::DiGraph;
774    use crate::visit::IntoNodeReferences;
775
776    #[cfg(feature = "stable_graph")]
777    use crate::prelude::StableDiGraph;
778
779    #[test]
780    fn test_acyclic_graph() {
781        // Create an acyclic DiGraph
782        let mut graph = DiGraph::<(), ()>::new();
783        let a = graph.add_node(());
784        let c = graph.add_node(());
785        let b = graph.add_node(());
786        graph.add_edge(a, b, ());
787        graph.add_edge(b, c, ());
788
789        // Create an Acyclic object
790        let mut acyclic = Acyclic::try_from_graph(graph).unwrap();
791
792        // Test initial topological order
793        assert_valid_topological_order(&acyclic);
794
795        // Add a valid edge
796        assert!(acyclic.try_add_edge(a, c, ()).is_ok());
797        assert_valid_topological_order(&acyclic);
798
799        // Try to add an edge that would create a cycle
800        assert!(acyclic.try_add_edge(c, a, ()).is_err());
801
802        // Add another valid edge
803        let d = acyclic.add_node(());
804        assert!(acyclic.try_add_edge(c, d, ()).is_ok());
805        assert_valid_topological_order(&acyclic);
806
807        // Try to add an edge that would create a cycle (using the Build trait)
808        assert!(acyclic.add_edge(d, a, ()).is_none());
809    }
810
811    #[cfg(feature = "stable_graph")]
812    #[test]
813    fn test_acyclic_graph_add_remove() {
814        // Create an initial Acyclic graph with two nodes and one edge
815        let mut acyclic = Acyclic::<StableDiGraph<(), ()>>::new();
816        let a = acyclic.add_node(());
817        let b = acyclic.add_node(());
818        assert!(acyclic.try_add_edge(a, b, ()).is_ok());
819
820        // Check initial topological order
821        assert_valid_topological_order(&acyclic);
822
823        // Add a new node and an edge
824        let c = acyclic.add_node(());
825        assert!(acyclic.try_add_edge(b, c, ()).is_ok());
826
827        // Check topological order after addition
828        assert_valid_topological_order(&acyclic);
829
830        // Remove the node connected to two edges (node b)
831        acyclic.remove_node(b);
832
833        // Check topological order after removal
834        assert_valid_topological_order(&acyclic);
835
836        // Verify the remaining structure
837        let remaining_nodes: Vec<_> = acyclic
838            .inner()
839            .node_references()
840            .map(|(id, _)| id)
841            .collect();
842        assert_eq!(remaining_nodes.len(), 2);
843        assert!(remaining_nodes.contains(&a));
844        assert!(remaining_nodes.contains(&c));
845        assert!(!acyclic.inner().contains_edge(a, c));
846    }
847
848    fn assert_valid_topological_order<'a, G>(acyclic: &'a Acyclic<G>)
849    where
850        G: Visitable + NodeCount + NodeIndexable,
851        &'a G: NodeIndexable
852            + IntoNodeReferences
853            + IntoNeighborsDirected
854            + GraphBase<NodeId = G::NodeId>,
855        G::NodeId: core::fmt::Debug,
856    {
857        let ordered_nodes: Vec<_> = acyclic.nodes_iter().collect();
858        assert_eq!(ordered_nodes.len(), acyclic.node_count());
859        let nodes: Vec<_> = acyclic.inner().node_identifiers().collect();
860
861        // Check that the nodes are in topological order
862        let mut last_position = None;
863        for (idx, &node) in ordered_nodes.iter().enumerate() {
864            assert!(nodes.contains(&node));
865
866            // Check that the node positions are monotonically increasing
867            let pos = acyclic.get_position(node);
868            assert!(Some(pos) > last_position);
869            last_position = Some(pos);
870
871            // Check that the neighbors are in the future of the current node
872            for neighbor in acyclic.inner().neighbors(node) {
873                let neighbour_idx = ordered_nodes.iter().position(|&n| n == neighbor).unwrap();
874                assert!(neighbour_idx > idx);
875            }
876        }
877    }
878}
petgraph/acyclic.rs

petgraph/
acyclic.rs
