petgraph/
acyclic.rs

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

petgraph/
acyclic.rs
