petgraph/
acyclic.rs

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 using [`Build::add_edge`] cannot fail in
169    /// the underlying graph (e.g. when multi-edges are allowed, as in
170    /// [`DiGraph`] and [`StableDiGraph`]), this will return an error if and
171    /// only if [`Self::is_valid_edge`] returns `false`.
172    ///
173    /// Note that for some graph types, the semantics of [`Build::add_edge`] may
174    /// not coincide with the semantics of the `add_edge` method provided by the
175    /// graph type.
176    ///
177    /// **Panics** if `a` or `b` are not found.
178    #[track_caller]
179    pub fn try_add_edge(
180        &mut self,
181        a: G::NodeId,
182        b: G::NodeId,
183        weight: G::EdgeWeight,
184    ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>
185    where
186        G: Build,
187        G::NodeId: IndexType,
188    {
189        if a == b {
190            // No self-loops allowed
191            return Err(AcyclicEdgeError::SelfLoop);
192        }
193        self.update_ordering(a, b)?;
194        self.graph
195            .add_edge(a, b, weight)
196            .ok_or(AcyclicEdgeError::InvalidEdge)
197    }
198
199    /// Add or update an edge in a graph using [`Build::update_edge`].
200    ///
201    /// Returns the id of the updated edge, or an [`AcyclicEdgeError`] if the edge
202    /// would create a cycle or a self-loop. If the edge does not exist, the
203    /// edge is created.
204    ///
205    /// This will return an error if and only if [`Self::is_valid_edge`] returns
206    /// `false`.
207    ///
208    /// **Panics** if `a` or `b` are not found.
209    pub fn try_update_edge(
210        &mut self,
211        a: G::NodeId,
212        b: G::NodeId,
213        weight: G::EdgeWeight,
214    ) -> Result<G::EdgeId, AcyclicEdgeError<G::NodeId>>
215    where
216        G: Build,
217        G::NodeId: IndexType,
218    {
219        if a == b {
220            // No self-loops allowed
221            return Err(AcyclicEdgeError::SelfLoop);
222        }
223        self.update_ordering(a, b)?;
224        Ok(self.graph.update_edge(a, b, weight))
225    }
226
227    /// Check if an edge would be valid, i.e. adding it would not create a cycle.
228    ///
229    /// **Panics** if `a` or `b` are not found.
230    pub fn is_valid_edge(&self, a: G::NodeId, b: G::NodeId) -> bool
231    where
232        G::NodeId: IndexType,
233    {
234        if a == b {
235            false // No self-loops
236        } else if self.get_position(a) < self.get_position(b) {
237            true // valid edge in the current topological order
238        } else {
239            // Check if the future of `b` is disjoint from the past of `a`
240            // (in which case the topological order could be adjusted)
241            self.causal_cones(b, a).is_ok()
242        }
243    }
244
245    /// Update the ordering of the nodes in the order map resulting from adding an
246    /// edge a -> b.
247    ///
248    /// If a cycle is detected, an error is returned and `self` remains unchanged.
249    ///
250    /// Implements the core update logic of the PK algorithm.
251    #[track_caller]
252    fn update_ordering(&mut self, a: G::NodeId, b: G::NodeId) -> Result<(), Cycle<G::NodeId>>
253    where
254        G::NodeId: IndexType,
255    {
256        let min_order = self.get_position(b);
257        let max_order = self.get_position(a);
258        if min_order >= max_order {
259            // Order is already correct
260            return Ok(());
261        }
262
263        // Get the nodes reachable from `b` and the nodes that can reach `a`
264        // between `min_order` and `max_order`
265        let (b_fut, a_past) = self.causal_cones(b, a)?;
266
267        // Now reorder of nodes in a_past and b_fut such that
268        //  i) within each vec, the nodes are in topological order,
269        // ii) all elements of b_fut come before all elements of a_past in the new order.
270        let all_positions: BTreeSet<_> = b_fut.keys().chain(a_past.keys()).copied().collect();
271        let all_nodes = a_past.values().chain(b_fut.values()).copied();
272
273        debug_assert_eq!(all_positions.len(), b_fut.len() + a_past.len());
274
275        for (pos, node) in all_positions.into_iter().zip(all_nodes) {
276            self.order_map.set_position(node, pos, &self.graph);
277        }
278        Ok(())
279    }
280
281    /// Use DFS to find the future causal cone of `min_node` and the past causal
282    /// cone of `max_node`.
283    ///
284    /// The cones are trimmed to the range `[min_order, max_order]`. The cones
285    /// are returned if they are disjoint. Otherwise, a [`Cycle`] error is returned.
286    ///
287    /// If `return_result` is false, then the cones are not constructed and the
288    /// method only checks for disjointness.
289    #[allow(clippy::type_complexity)]
290    fn causal_cones(
291        &self,
292        min_node: G::NodeId,
293        max_node: G::NodeId,
294    ) -> Result<
295        (
296            BTreeMap<TopologicalPosition, G::NodeId>,
297            BTreeMap<TopologicalPosition, G::NodeId>,
298        ),
299        Cycle<G::NodeId>,
300    >
301    where
302        G::NodeId: IndexType,
303    {
304        debug_assert!(self.discovered.borrow().is_clear());
305        debug_assert!(self.finished.borrow().is_clear());
306
307        let min_order = self.get_position(min_node);
308        let max_order = self.get_position(max_node);
309
310        // Prepare DFS scratch space: make sure the maps have enough capacity
311        if self.discovered.borrow().len() < self.graph.node_bound() {
312            self.discovered.borrow_mut().grow(self.graph.node_bound());
313            self.finished.borrow_mut().grow(self.graph.node_bound());
314        }
315
316        // Get all nodes reachable from b with min_order <= order < max_order
317        let mut forward_cone = BTreeMap::new();
318        let mut backward_cone = BTreeMap::new();
319
320        // The main logic: run DFS twice. We run this in a closure to catch
321        // errors and reset the maps properly at the end.
322        let mut run_dfs = || {
323            // Get all nodes reachable from min_node with min_order < order <= max_order
324            self.future_cone(min_node, min_order, max_order, &mut forward_cone)?;
325
326            // Get all nodes that can reach a with min_order < order <= max_order
327            // These are disjoint from the nodes in the forward cone, otherwise
328            // we would have a cycle.
329            self.past_cone(max_node, min_order, max_order, &mut backward_cone)
330                .expect("cycles already checked in future_cone");
331
332            Ok(())
333        };
334
335        let success = run_dfs();
336
337        // Cleanup: reset map to 0. This is faster than a full reset, especially
338        // on large sparse graphs.
339        for &v in forward_cone.values().chain(backward_cone.values()) {
340            self.discovered.borrow_mut().set(v.index(), false);
341            self.finished.borrow_mut().set(v.index(), false);
342        }
343        debug_assert!(self.discovered.borrow().is_clear());
344        debug_assert!(self.finished.borrow().is_clear());
345
346        match success {
347            Ok(()) => Ok((forward_cone, backward_cone)),
348            Err(cycle) => Err(cycle),
349        }
350    }
351
352    fn future_cone(
353        &self,
354        start: G::NodeId,
355        min_position: TopologicalPosition,
356        max_position: TopologicalPosition,
357        res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
358    ) -> Result<(), Cycle<G::NodeId>>
359    where
360        G::NodeId: IndexType,
361    {
362        dfs(
363            &self.graph,
364            start,
365            &self.order_map,
366            |order| {
367                debug_assert!(order >= min_position, "invalid topological order");
368                match order.cmp(&max_position) {
369                    Ordering::Less => Ok(true),           // node within [min_node, max_node]
370                    Ordering::Equal => Err(Cycle(start)), // cycle!
371                    Ordering::Greater => Ok(false),       // node beyond [min_node, max_node]
372                }
373            },
374            res,
375            &mut self.discovered.borrow_mut(),
376            &mut self.finished.borrow_mut(),
377        )
378    }
379
380    fn past_cone(
381        &self,
382        start: G::NodeId,
383        min_position: TopologicalPosition,
384        max_position: TopologicalPosition,
385        res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
386    ) -> Result<(), Cycle<G::NodeId>>
387    where
388        G::NodeId: IndexType,
389    {
390        dfs(
391            Reversed(&self.graph),
392            start,
393            &self.order_map,
394            |order| {
395                debug_assert!(order <= max_position, "invalid topological order");
396                match order.cmp(&min_position) {
397                    Ordering::Less => Ok(false), // node beyond [min_node, max_node]
398                    Ordering::Equal => unreachable!("checked by future_cone"), // cycle!
399                    Ordering::Greater => Ok(true), // node within [min_node, max_node]
400                }
401            },
402            res,
403            &mut self.discovered.borrow_mut(),
404            &mut self.finished.borrow_mut(),
405        )
406    }
407}
408
409impl<G: Visitable> GraphBase for Acyclic<G> {
410    type NodeId = G::NodeId;
411    type EdgeId = G::EdgeId;
412}
413
414impl<G: Default + Visitable> Default for Acyclic<G> {
415    fn default() -> Self {
416        let graph: G = Default::default();
417        let order_map = Default::default();
418        let discovered = RefCell::new(FixedBitSet::default());
419        let finished = RefCell::new(FixedBitSet::default());
420        Self {
421            graph,
422            order_map,
423            discovered,
424            finished,
425        }
426    }
427}
428
429impl<G: Build + Visitable + NodeIndexable> Build for Acyclic<G>
430where
431    for<'a> &'a G: IntoNeighborsDirected
432        + IntoNodeIdentifiers
433        + Visitable<Map = G::Map>
434        + GraphBase<NodeId = G::NodeId>,
435    G::NodeId: IndexType,
436{
437    fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
438        let n = self.graph.add_node(weight);
439        self.order_map.add_node(n, &self.graph);
440        n
441    }
442
443    fn add_edge(
444        &mut self,
445        a: Self::NodeId,
446        b: Self::NodeId,
447        weight: Self::EdgeWeight,
448    ) -> Option<Self::EdgeId> {
449        self.try_add_edge(a, b, weight).ok()
450    }
451
452    fn update_edge(
453        &mut self,
454        a: Self::NodeId,
455        b: Self::NodeId,
456        weight: Self::EdgeWeight,
457    ) -> Self::EdgeId {
458        self.try_update_edge(a, b, weight).unwrap()
459    }
460}
461
462impl<G: Create + Visitable + NodeIndexable> Create for Acyclic<G>
463where
464    for<'a> &'a G: IntoNeighborsDirected
465        + IntoNodeIdentifiers
466        + Visitable<Map = G::Map>
467        + GraphBase<NodeId = G::NodeId>,
468    G::NodeId: IndexType,
469{
470    fn with_capacity(nodes: usize, edges: usize) -> Self {
471        let graph = G::with_capacity(nodes, edges);
472        let order_map = OrderMap::with_capacity(nodes);
473        let discovered = FixedBitSet::with_capacity(nodes);
474        let finished = FixedBitSet::with_capacity(nodes);
475        Self {
476            graph,
477            order_map,
478            discovered: RefCell::new(discovered),
479            finished: RefCell::new(finished),
480        }
481    }
482}
483
484impl<G: Visitable> Deref for Acyclic<G> {
485    type Target = G;
486
487    fn deref(&self) -> &Self::Target {
488        &self.graph
489    }
490}
491
492/// Traverse nodes in `graph` in DFS order, starting from `start`, for as long
493/// as the predicate `valid_order` returns `true` on the current node's order.
494fn dfs<G: NodeIndexable + IntoNeighborsDirected + IntoNodeIdentifiers + Visitable>(
495    graph: G,
496    start: G::NodeId,
497    order_map: &OrderMap<G::NodeId>,
498    // A predicate that returns whether to continue the search from a node,
499    // or an error to stop and shortcircuit the search.
500    mut valid_order: impl FnMut(TopologicalPosition) -> Result<bool, Cycle<G::NodeId>>,
501    res: &mut BTreeMap<TopologicalPosition, G::NodeId>,
502    discovered: &mut FixedBitSet,
503    finished: &mut FixedBitSet,
504) -> Result<(), Cycle<G::NodeId>>
505where
506    G::NodeId: IndexType,
507{
508    dfs_visitor(
509        graph,
510        start,
511        &mut |ev| -> Result<Control<()>, Cycle<G::NodeId>> {
512            match ev {
513                DfsEvent::Discover(u, _) => {
514                    // We are visiting u
515                    let order = order_map.get_position(u, &graph);
516                    res.insert(order, u);
517                    Ok(Control::Continue)
518                }
519                DfsEvent::TreeEdge(_, u) => {
520                    // Should we visit u?
521                    let order = order_map.get_position(u, &graph);
522                    match valid_order(order) {
523                        Ok(true) => Ok(Control::Continue),
524                        Ok(false) => Ok(Control::Prune),
525                        Err(cycle) => Err(cycle),
526                    }
527                }
528                _ => Ok(Control::Continue),
529            }
530        },
531        discovered,
532        finished,
533        &mut Time::default(),
534    )?;
535
536    Ok(())
537}
538
539/////////////////////// Pass-through graph traits ///////////////////////
540// We implement all the following traits by delegating to the inner graph:
541// - Data
542// - DataMap
543// - DataMapMut
544// - EdgeCount
545// - EdgeIndexable
546// - GetAdjacencyMatrix
547// - GraphProp
548// - NodeCompactIndexable
549// - NodeCount
550// - NodeIndexable
551// - Visitable
552//
553// Furthermore, we also implement the `remove_node` and `remove_edge` methods,
554// as well as the following traits for `DiGraph` and `StableDiGraph` (these
555// are hard/impossible to implement generically):
556// - TryFrom
557// - IntoEdgeReferences
558// - IntoEdges
559// - IntoEdgesDirected
560// - IntoNeighbors
561// - IntoNeighborsDirected
562// - IntoNodeIdentifiers
563// - IntoNodeReferences
564
565impl<G: Visitable + Data> Data for Acyclic<G> {
566    type NodeWeight = G::NodeWeight;
567    type EdgeWeight = G::EdgeWeight;
568}
569
570impl<G: Visitable + DataMap> DataMap for Acyclic<G> {
571    fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
572        self.inner().node_weight(id)
573    }
574
575    fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
576        self.inner().edge_weight(id)
577    }
578}
579
580impl<G: Visitable + DataMapMut> DataMapMut for Acyclic<G> {
581    fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
582        self.inner_mut().node_weight_mut(id)
583    }
584
585    fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
586        self.inner_mut().edge_weight_mut(id)
587    }
588}
589
590impl<G: Visitable + EdgeCount> EdgeCount for Acyclic<G> {
591    fn edge_count(&self) -> usize {
592        self.inner().edge_count()
593    }
594}
595
596impl<G: Visitable + EdgeIndexable> EdgeIndexable for Acyclic<G> {
597    fn edge_bound(&self) -> usize {
598        self.inner().edge_bound()
599    }
600
601    fn to_index(&self, a: Self::EdgeId) -> usize {
602        self.inner().to_index(a)
603    }
604
605    fn from_index(&self, i: usize) -> Self::EdgeId {
606        self.inner().from_index(i)
607    }
608}
609
610impl<G: Visitable + GetAdjacencyMatrix> GetAdjacencyMatrix for Acyclic<G> {
611    type AdjMatrix = G::AdjMatrix;
612
613    fn adjacency_matrix(&self) -> Self::AdjMatrix {
614        self.inner().adjacency_matrix()
615    }
616
617    fn is_adjacent(&self, matrix: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool {
618        self.inner().is_adjacent(matrix, a, b)
619    }
620}
621
622impl<G: Visitable + GraphProp> GraphProp for Acyclic<G> {
623    type EdgeType = G::EdgeType;
624}
625
626impl<G: Visitable + NodeCompactIndexable> NodeCompactIndexable for Acyclic<G> {}
627
628impl<G: Visitable + NodeCount> NodeCount for Acyclic<G> {
629    fn node_count(&self) -> usize {
630        self.inner().node_count()
631    }
632}
633
634impl<G: Visitable + NodeIndexable> NodeIndexable for Acyclic<G> {
635    fn node_bound(&self) -> usize {
636        self.inner().node_bound()
637    }
638
639    fn to_index(&self, a: Self::NodeId) -> usize {
640        self.inner().to_index(a)
641    }
642
643    fn from_index(&self, i: usize) -> Self::NodeId {
644        self.inner().from_index(i)
645    }
646}
647
648impl<G: Visitable> Visitable for Acyclic<G> {
649    type Map = G::Map;
650
651    fn visit_map(&self) -> Self::Map {
652        self.inner().visit_map()
653    }
654
655    fn reset_map(&self, map: &mut Self::Map) {
656        self.inner().reset_map(map)
657    }
658}
659
660macro_rules! impl_graph_traits {
661    ($graph_type:ident) => {
662        // Remove edge and node methods (not available through traits)
663        impl<N, E, Ix: IndexType> Acyclic<$graph_type<N, E, Ix>> {
664            /// Remove an edge and return its edge weight, or None if it didn't exist.
665            ///
666            /// Pass through to underlying graph.
667            pub fn remove_edge(
668                &mut self,
669                e: <$graph_type<N, E, Ix> as GraphBase>::EdgeId,
670            ) -> Option<E> {
671                self.graph.remove_edge(e)
672            }
673
674            /// Remove a node from the graph if it exists, and return its
675            /// weight. If it doesn't exist in the graph, return None.
676            ///
677            /// This updates the order in O(v) runtime and removes the node in
678            /// the underlying graph.
679            pub fn remove_node(
680                &mut self,
681                n: <$graph_type<N, E, Ix> as GraphBase>::NodeId,
682            ) -> Option<N> {
683                self.order_map.remove_node(n, &self.graph);
684                self.graph.remove_node(n)
685            }
686        }
687
688        impl<N, E, Ix: IndexType> TryFrom<$graph_type<N, E, Ix>>
689            for Acyclic<$graph_type<N, E, Ix>>
690        {
691            type Error = Cycle<NodeIndex<Ix>>;
692
693            fn try_from(graph: $graph_type<N, E, Ix>) -> Result<Self, Self::Error> {
694                let order_map = OrderMap::try_from_graph(&graph)?;
695                let discovered = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
696                let finished = RefCell::new(FixedBitSet::with_capacity(graph.node_bound()));
697                Ok(Self {
698                    graph,
699                    order_map,
700                    discovered,
701                    finished,
702                })
703            }
704        }
705
706        impl<'a, N, E, Ix: IndexType> IntoEdgeReferences for &'a Acyclic<$graph_type<N, E, Ix>> {
707            type EdgeRef = <&'a $graph_type<N, E, Ix> as IntoEdgeReferences>::EdgeRef;
708            type EdgeReferences = <&'a $graph_type<N, E, Ix> as IntoEdgeReferences>::EdgeReferences;
709
710            fn edge_references(self) -> Self::EdgeReferences {
711                self.inner().edge_references()
712            }
713        }
714
715        impl<'a, N, E, Ix: IndexType> IntoEdges for &'a Acyclic<$graph_type<N, E, Ix>> {
716            type Edges = <&'a $graph_type<N, E, Ix> as IntoEdges>::Edges;
717
718            fn edges(self, a: Self::NodeId) -> Self::Edges {
719                self.inner().edges(a)
720            }
721        }
722
723        impl<'a, N, E, Ix: IndexType> IntoEdgesDirected for &'a Acyclic<$graph_type<N, E, Ix>> {
724            type EdgesDirected = <&'a $graph_type<N, E, Ix> as IntoEdgesDirected>::EdgesDirected;
725
726            fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
727                self.inner().edges_directed(a, dir)
728            }
729        }
730
731        impl<'a, N, E, Ix: IndexType> IntoNeighbors for &'a Acyclic<$graph_type<N, E, Ix>> {
732            type Neighbors = <&'a $graph_type<N, E, Ix> as IntoNeighbors>::Neighbors;
733
734            fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
735                self.inner().neighbors(a)
736            }
737        }
738
739        impl<'a, N, E, Ix: IndexType> IntoNeighborsDirected for &'a Acyclic<$graph_type<N, E, Ix>> {
740            type NeighborsDirected =
741                <&'a $graph_type<N, E, Ix> as IntoNeighborsDirected>::NeighborsDirected;
742
743            fn neighbors_directed(self, n: Self::NodeId, d: Direction) -> Self::NeighborsDirected {
744                self.inner().neighbors_directed(n, d)
745            }
746        }
747
748        impl<'a, N, E, Ix: IndexType> IntoNodeIdentifiers for &'a Acyclic<$graph_type<N, E, Ix>> {
749            type NodeIdentifiers =
750                <&'a $graph_type<N, E, Ix> as IntoNodeIdentifiers>::NodeIdentifiers;
751
752            fn node_identifiers(self) -> Self::NodeIdentifiers {
753                self.inner().node_identifiers()
754            }
755        }
756
757        impl<'a, N, E, Ix: IndexType> IntoNodeReferences for &'a Acyclic<$graph_type<N, E, Ix>> {
758            type NodeRef = <&'a $graph_type<N, E, Ix> as IntoNodeReferences>::NodeRef;
759            type NodeReferences = <&'a $graph_type<N, E, Ix> as IntoNodeReferences>::NodeReferences;
760
761            fn node_references(self) -> Self::NodeReferences {
762                self.inner().node_references()
763            }
764        }
765    };
766}
767
768impl_graph_traits!(DiGraph);
769#[cfg(feature = "stable_graph")]
770impl_graph_traits!(StableDiGraph);
771
772#[cfg(test)]
773mod tests {
774    use alloc::vec::Vec;
775
776    use super::*;
777    use crate::prelude::DiGraph;
778    use crate::visit::IntoNodeReferences;
779
780    #[cfg(feature = "stable_graph")]
781    use crate::prelude::StableDiGraph;
782
783    #[test]
784    fn test_acyclic_graph() {
785        // Create an acyclic DiGraph
786        let mut graph = DiGraph::<(), ()>::new();
787        let a = graph.add_node(());
788        let c = graph.add_node(());
789        let b = graph.add_node(());
790        graph.add_edge(a, b, ());
791        graph.add_edge(b, c, ());
792
793        // Create an Acyclic object
794        let mut acyclic = Acyclic::try_from_graph(graph).unwrap();
795
796        // Test initial topological order
797        assert_valid_topological_order(&acyclic);
798
799        // Add a valid edge
800        assert!(acyclic.try_add_edge(a, c, ()).is_ok());
801        assert_valid_topological_order(&acyclic);
802
803        // Try to add an edge that would create a cycle
804        assert!(acyclic.try_add_edge(c, a, ()).is_err());
805
806        // Add another valid edge
807        let d = acyclic.add_node(());
808        assert!(acyclic.try_add_edge(c, d, ()).is_ok());
809        assert_valid_topological_order(&acyclic);
810
811        // Try to add an edge that would create a cycle (using the Build trait)
812        assert!(acyclic.add_edge(d, a, ()).is_none());
813    }
814
815    #[cfg(feature = "stable_graph")]
816    #[test]
817    fn test_acyclic_graph_add_remove() {
818        // Create an initial Acyclic graph with two nodes and one edge
819        let mut acyclic = Acyclic::<StableDiGraph<(), ()>>::new();
820        let a = acyclic.add_node(());
821        let b = acyclic.add_node(());
822        assert!(acyclic.try_add_edge(a, b, ()).is_ok());
823
824        // Check initial topological order
825        assert_valid_topological_order(&acyclic);
826
827        // Add a new node and an edge
828        let c = acyclic.add_node(());
829        assert!(acyclic.try_add_edge(b, c, ()).is_ok());
830
831        // Check topological order after addition
832        assert_valid_topological_order(&acyclic);
833
834        // Remove the node connected to two edges (node b)
835        acyclic.remove_node(b);
836
837        // Check topological order after removal
838        assert_valid_topological_order(&acyclic);
839
840        // Verify the remaining structure
841        let remaining_nodes: Vec<_> = acyclic
842            .inner()
843            .node_references()
844            .map(|(id, _)| id)
845            .collect();
846        assert_eq!(remaining_nodes.len(), 2);
847        assert!(remaining_nodes.contains(&a));
848        assert!(remaining_nodes.contains(&c));
849        assert!(!acyclic.inner().contains_edge(a, c));
850    }
851
852    fn assert_valid_topological_order<'a, G>(acyclic: &'a Acyclic<G>)
853    where
854        G: Visitable + NodeCount + NodeIndexable,
855        &'a G: NodeIndexable
856            + IntoNodeReferences
857            + IntoNeighborsDirected
858            + GraphBase<NodeId = G::NodeId>,
859        G::NodeId: core::fmt::Debug,
860    {
861        let ordered_nodes: Vec<_> = acyclic.nodes_iter().collect();
862        assert_eq!(ordered_nodes.len(), acyclic.node_count());
863        let nodes: Vec<_> = acyclic.inner().node_identifiers().collect();
864
865        // Check that the nodes are in topological order
866        let mut last_position = None;
867        for (idx, &node) in ordered_nodes.iter().enumerate() {
868            assert!(nodes.contains(&node));
869
870            // Check that the node positions are monotonically increasing
871            let pos = acyclic.get_position(node);
872            assert!(Some(pos) > last_position);
873            last_position = Some(pos);
874
875            // Check that the neighbors are in the future of the current node
876            for neighbor in acyclic.inner().neighbors(node) {
877                let neighbour_idx = ordered_nodes.iter().position(|&n| n == neighbor).unwrap();
878                assert!(neighbour_idx > idx);
879            }
880        }
881    }
882
883    #[cfg(feature = "graphmap")]
884    #[test]
885    fn test_multiedge_allowed() {
886        use crate::prelude::GraphMap;
887        use crate::Directed;
888
889        let mut graph = Acyclic::<GraphMap<usize, (), Directed>>::new();
890        graph.add_node(0);
891        graph.add_node(1);
892        graph.try_update_edge(0, 1, ()).unwrap();
893        graph.try_update_edge(0, 1, ()).unwrap(); // `Result::unwrap()` on an `Err` value: InvalidEdge
894    }
895}
petgraph/acyclic.rs

petgraph/
acyclic.rs
