traitgraph_algo/traversal/
mod.rs

1use crate::queue::BidirectedQueue;
2use std::collections::VecDeque;
3use std::iter::IntoIterator;
4use std::marker::PhantomData;
5use traitgraph::index::{GraphIndex, OptionalGraphIndex};
6use traitgraph::interface::NodeOrEdge;
7use traitgraph::interface::{
8    GraphBase, ImmutableGraphContainer, NavigableGraph, Neighbor, StaticGraph,
9};
10
11/// Functions and structures related to univocal traversals.
12/// Univocal traversals are traversals along unique out-edges or unique in-edges in a graph.
13pub mod univocal_traversal;
14
15/// A normal forward BFS in a directed graph.
16pub type PreOrderForwardBfs<'a, Graph> = PreOrderTraversal<
17    'a,
18    Graph,
19    ForwardNeighborStrategy,
20    BfsQueueStrategy,
21    VecDeque<<Graph as GraphBase>::NodeIndex>,
22>;
23/// A normal backward BFS in a directed graph.
24pub type PreOrderBackwardBfs<'a, Graph> = PreOrderTraversal<
25    'a,
26    Graph,
27    BackwardNeighborStrategy,
28    BfsQueueStrategy,
29    VecDeque<<Graph as GraphBase>::NodeIndex>,
30>;
31/// A BFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.
32pub type PreOrderUndirectedBfs<'a, Graph> = PreOrderTraversal<
33    'a,
34    Graph,
35    UndirectedNeighborStrategy,
36    BfsQueueStrategy,
37    VecDeque<<Graph as GraphBase>::NodeIndex>,
38>;
39
40/// A normal forward DFS in a directed graph.
41pub type PreOrderForwardDfs<'a, Graph> = PreOrderTraversal<
42    'a,
43    Graph,
44    ForwardNeighborStrategy,
45    DfsQueueStrategy,
46    VecDeque<<Graph as GraphBase>::NodeIndex>,
47>;
48/// A normal backward DFS in a directed graph.
49pub type PreOrderBackwardDfs<'a, Graph> = PreOrderTraversal<
50    'a,
51    Graph,
52    BackwardNeighborStrategy,
53    DfsQueueStrategy,
54    VecDeque<<Graph as GraphBase>::NodeIndex>,
55>;
56/// A DFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.
57pub type PreOrderUndirectedDfs<'a, Graph> = PreOrderTraversal<
58    'a,
59    Graph,
60    UndirectedNeighborStrategy,
61    DfsQueueStrategy,
62    VecDeque<<Graph as GraphBase>::NodeIndex>,
63>;
64
65/// A post-order forward DFS in a directed graph.
66pub type PostOrderForwardDfs<Graph> = DfsPostOrderTraversal<
67    Graph,
68    ForwardNeighborStrategy,
69    VecDeque<<Graph as GraphBase>::NodeIndex>,
70>;
71/// A post-order forward DFS in a directed graph.
72pub type PostOrderBackwardDfs<Graph> = DfsPostOrderTraversal<
73    Graph,
74    BackwardNeighborStrategy,
75    VecDeque<<Graph as GraphBase>::NodeIndex>,
76>;
77/// A post-order forward DFS in a directed graph.
78pub type PostOrderUndirectedDfs<Graph> = DfsPostOrderTraversal<
79    Graph,
80    UndirectedNeighborStrategy,
81    VecDeque<<Graph as GraphBase>::NodeIndex>,
82>;
83
84/// A generic preorder graph traversal.
85///
86/// The traversal is generic over the graph implementation,
87/// as well as the direction of the search (`NeighborStrategy`),
88/// the order of processing (`QueueStrategy`) and the queue implementation itself (`Queue`).
89///
90/// Moreover, the traversal computes the preorder rank of each visited node.
91/// Also, the traversal operates with edge-granularity, meaning that not just nodes are returned by the `next` method, but the traversed edges of each node as well.
92/// Additionally, a forbidden subgraph can be passed using the `next_with_forbidden_subgraph` method to disable some edges and nodes in the traversal.
93pub struct PreOrderTraversal<
94    'a,
95    Graph: GraphBase,
96    NeighborStrategy: 'a + TraversalNeighborStrategy<Graph>,
97    QueueStrategy,
98    Queue: BidirectedQueue<Graph::NodeIndex>,
99> {
100    graph: &'a Graph,
101    queue: Queue,
102    rank: Vec<Graph::OptionalNodeIndex>,
103    current_rank: Graph::NodeIndex,
104    neighbor_iterator: Option<NeighborStrategy::Iterator<'a>>,
105    neighbor_strategy: PhantomData<NeighborStrategy>,
106    queue_strategy: PhantomData<QueueStrategy>,
107}
108
109impl<
110        'a,
111        Graph: StaticGraph,
112        NeighborStrategy: TraversalNeighborStrategy<Graph>,
113        QueueStrategy: TraversalQueueStrategy<Graph, Queue>,
114        Queue: BidirectedQueue<Graph::NodeIndex>,
115    > PreOrderTraversal<'a, Graph, NeighborStrategy, QueueStrategy, Queue>
116{
117    /// Creates a new traversal that operates on the given graph starting from the given node.
118    pub fn new(graph: &'a Graph, start: Graph::NodeIndex) -> Self {
119        let mut queue = Queue::default();
120        QueueStrategy::push(&mut queue, start);
121        let mut rank = vec![Graph::OptionalNodeIndex::new_none(); graph.node_count()];
122        rank[start.as_usize()] = Some(0).into();
123        Self {
124            graph,
125            queue,
126            rank,
127            current_rank: 1.into(),
128            neighbor_iterator: None,
129            neighbor_strategy: Default::default(),
130            queue_strategy: Default::default(),
131        }
132    }
133
134    /// Creates a new traversal that operates on the given graph.
135    /// Does not start the traversal.
136    pub fn new_without_start(graph: &'a Graph) -> Self {
137        let queue = Queue::default();
138        let rank = vec![Graph::OptionalNodeIndex::new_none(); graph.node_count()];
139        Self {
140            graph,
141            queue,
142            rank,
143            current_rank: 0.into(),
144            neighbor_iterator: None,
145            neighbor_strategy: Default::default(),
146            queue_strategy: Default::default(),
147        }
148    }
149
150    /// Resets the traversal to start from the given node.
151    pub fn reset(&mut self, start: Graph::NodeIndex) {
152        self.queue.clear();
153        QueueStrategy::push(&mut self.queue, start);
154        for rank in &mut self.rank {
155            *rank = Graph::OptionalNodeIndex::new_none();
156        }
157        self.rank[start.as_usize()] = Some(0).into();
158        self.current_rank = 1.into();
159        self.neighbor_iterator = None;
160    }
161
162    /// Resets the traversal to start from the given node without resetting the visited nodes.
163    /// Returns the rank of the starting node.
164    pub fn continue_traversal_from(&mut self, start: Graph::NodeIndex) -> Graph::NodeIndex {
165        debug_assert!(self.queue.is_empty());
166        debug_assert!(self.neighbor_iterator.is_none());
167        QueueStrategy::push(&mut self.queue, start);
168        self.rank[start.as_usize()] = Some(self.current_rank).into();
169        let result = self.current_rank;
170        self.current_rank = self.current_rank + 1;
171        result
172    }
173
174    /// Advances the traversal, ignoring all nodes and edges forbidden by `forbidden_subgraph`.
175    pub fn next_with_forbidden_subgraph<FN: ForbiddenSubgraph<Graph>>(
176        &mut self,
177        forbidden_subgraph: &FN,
178    ) -> Option<NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
179        self.next_internal(forbidden_subgraph)
180    }
181
182    #[inline]
183    fn next_internal<FS: ForbiddenSubgraph<Graph>>(
184        &mut self,
185        forbidden_subgraph: &FS,
186    ) -> Option<NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
187        if let Some(neighbor_iterator) = self.neighbor_iterator.as_mut() {
188            for neighbor in neighbor_iterator {
189                if forbidden_subgraph.is_edge_forbidden(neighbor.edge_id) {
190                    continue;
191                }
192
193                if !forbidden_subgraph.is_node_forbidden(neighbor.node_id) {
194                    let rank_entry = &mut self.rank[neighbor.node_id.as_usize()];
195                    if rank_entry.is_none() {
196                        *rank_entry = self.current_rank.into();
197                        self.current_rank = self.current_rank + 1;
198                        QueueStrategy::push(&mut self.queue, neighbor.node_id);
199                    }
200                }
201
202                return Some(NodeOrEdge::Edge(neighbor.edge_id));
203            }
204
205            self.neighbor_iterator = None;
206        }
207
208        if let Some(first) = QueueStrategy::pop(&mut self.queue) {
209            debug_assert!(
210                !forbidden_subgraph.is_node_forbidden(first),
211                "A node became forbidden after being added to the queue. This is not supported."
212            );
213            self.neighbor_iterator = Some(NeighborStrategy::neighbor_iterator(self.graph, first));
214
215            Some(NodeOrEdge::Node(first))
216        } else {
217            None
218        }
219    }
220
221    /// Returns the rank of the given node, or `None` if the node has not yet been visited.
222    pub fn rank_of(&self, node: Graph::NodeIndex) -> Option<Graph::NodeIndex> {
223        let rank = self.rank[node.as_usize()];
224        rank.into()
225    }
226}
227impl<
228        Graph: StaticGraph,
229        NeighborStrategy: TraversalNeighborStrategy<Graph>,
230        QueueStrategy: TraversalQueueStrategy<Graph, Queue>,
231        Queue: BidirectedQueue<Graph::NodeIndex>,
232    > Iterator for PreOrderTraversal<'_, Graph, NeighborStrategy, QueueStrategy, Queue>
233{
234    type Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>;
235
236    fn next(&mut self) -> Option<Self::Item> {
237        self.next_internal(&NoForbiddenSubgraph)
238    }
239}
240
241/// A generic depth first postorder graph traversal.
242///
243/// The traversal is generic over the graph implementation,
244/// as well as the direction of the search (`NeighborStrategy`)
245/// and the queue implementation (`Queue`).
246///
247/// Moreover, the traversal computes the postorder rank of each visited node.
248/// This traversal operates with node-granularity, meaning that the `next` method returns nodes.
249pub struct DfsPostOrderTraversal<
250    Graph: GraphBase,
251    NeighborStrategy,
252    Queue: BidirectedQueue<Graph::NodeIndex>,
253> {
254    queue: Queue,
255    rank: Vec<Graph::OptionalNodeIndex>,
256    current_rank: Graph::NodeIndex,
257    graph: PhantomData<Graph>,
258    neighbor_strategy: PhantomData<NeighborStrategy>,
259}
260
261impl<
262        Graph: StaticGraph,
263        NeighborStrategy: TraversalNeighborStrategy<Graph>,
264        Queue: BidirectedQueue<Graph::NodeIndex>,
265    > DfsPostOrderTraversal<Graph, NeighborStrategy, Queue>
266{
267    /// Creates a new traversal that operates on the given graph, starting from the given node.
268    pub fn new(graph: &Graph, start: Graph::NodeIndex) -> Self {
269        let mut queue = Queue::default();
270        queue.push_back(start);
271        let rank = vec![Graph::OptionalNodeIndex::new_none(); graph.node_count()];
272        Self {
273            queue,
274            rank,
275            current_rank: 0.into(),
276            graph: Default::default(),
277            neighbor_strategy: Default::default(),
278        }
279    }
280
281    /// Creates a new traversal that operates on the given graph.
282    /// There is no starting node given, and to start the search, one of the `reset` methods needs to be used.
283    pub fn new_without_start(graph: &Graph) -> Self {
284        let queue = Queue::default();
285        let rank = vec![Graph::OptionalNodeIndex::new_none(); graph.node_count()];
286        Self {
287            queue,
288            rank,
289            current_rank: 0.into(),
290            graph: Default::default(),
291            neighbor_strategy: Default::default(),
292        }
293    }
294
295    /// Resets the traversal to start from the given node.
296    pub fn reset(&mut self, start: Graph::NodeIndex) {
297        self.queue.clear();
298        self.queue.push_back(start);
299        for rank in &mut self.rank {
300            *rank = Graph::OptionalNodeIndex::new_none();
301        }
302        self.current_rank = 0.into();
303    }
304
305    /// Resets the traversal to start from the given node without resetting the visited nodes.
306    pub fn continue_traversal_from(&mut self, start: Graph::NodeIndex) {
307        assert!(self.queue.is_empty());
308        self.queue.push_back(start);
309    }
310
311    /// Computes and returns the next node in depth-first search postorder.
312    pub fn next(&mut self, graph: &'_ Graph) -> Option<Graph::NodeIndex> {
313        while let Some(first) = self.queue.pop_back() {
314            let rank_entry = &mut self.rank[first.as_usize()];
315            if *rank_entry == Self::explored_rank() {
316                debug_assert_ne!(self.current_rank.into(), Self::explored_rank());
317                *rank_entry = self.current_rank.into();
318                self.current_rank = self.current_rank + 1;
319
320                return Some(first);
321            } else if rank_entry.is_none() {
322                self.queue.push_back(first);
323                *rank_entry = Self::explored_rank();
324
325                for neighbor in NeighborStrategy::neighbor_iterator(graph, first) {
326                    let rank_entry = &mut self.rank[neighbor.node_id.as_usize()];
327                    if rank_entry.is_none() {
328                        self.queue.push_back(neighbor.node_id);
329                    }
330                }
331            }
332        }
333
334        None
335    }
336
337    /// Returns the rank of a node in depth-first search postorder, or `None` if the node has not yet been processed completely.
338    pub fn rank_of(&self, node: Graph::NodeIndex) -> Option<Graph::NodeIndex> {
339        let rank = self.rank[node.as_usize()];
340        rank.into()
341    }
342
343    fn explored_rank() -> Graph::OptionalNodeIndex {
344        Some(Graph::OptionalNodeIndex::new_none().as_usize_unchecked() - 1).into()
345    }
346}
347
348/// A type with this trait can tell if a node or edge is forbidden in a graph traversal.
349pub trait ForbiddenSubgraph<Graph: GraphBase> {
350    /// Returns true if the given node is forbidden.
351    fn is_node_forbidden(&self, node: Graph::NodeIndex) -> bool;
352
353    /// Returns true if the given edge is forbidden.
354    fn is_edge_forbidden(&self, edge: Graph::EdgeIndex) -> bool;
355}
356
357/// A type that defines the strategy for computing the neighborhood of a node or edge, i.e. forward, backward or undirected.
358pub trait TraversalNeighborStrategy<Graph: GraphBase> {
359    /// The iterator type used to iterate over the neighbors of a node.
360    type Iterator<'a>: Iterator<Item = Neighbor<Graph::NodeIndex, Graph::EdgeIndex>>
361    where
362        Self: 'a,
363        Graph: 'a;
364    /// The iterator type used to iterate over the neighbors of an edge.
365    type EdgeNeighborIterator<'a>: Iterator<Item = Graph::NodeIndex>
366    where
367        Self: 'a,
368        Graph: 'a;
369
370    /// Returns an iterator over the neighbors of a given node.
371    fn neighbor_iterator(graph: &Graph, node: Graph::NodeIndex) -> Self::Iterator<'_>;
372
373    /// Returns an iterator over the neighbors of an edge.
374    fn edge_neighbor_iterator(
375        graph: &Graph,
376        edge: Graph::EdgeIndex,
377    ) -> Self::EdgeNeighborIterator<'_>;
378}
379
380/// A type that defines the order of node processing in a traversal, i.e. queue-based or stack-based.
381pub trait TraversalQueueStrategy<Graph: GraphBase, Queue: BidirectedQueue<Graph::NodeIndex>> {
382    /// Insert a node into the queue.
383    fn push(queue: &mut Queue, node: Graph::NodeIndex);
384    /// Remove and return a node from the queue.
385    fn pop(queue: &mut Queue) -> Option<Graph::NodeIndex>;
386}
387
388/// A type implementing [ForbiddenSubgraph](ForbiddenSubgraph) that allows all nodes in a graph traversal.
389pub struct NoForbiddenSubgraph;
390impl<Graph: GraphBase> ForbiddenSubgraph<Graph> for NoForbiddenSubgraph {
391    fn is_node_forbidden(&self, _: Graph::NodeIndex) -> bool {
392        false
393    }
394
395    fn is_edge_forbidden(&self, _: Graph::EdgeIndex) -> bool {
396        false
397    }
398}
399
400/// A type implementing [ForbiddenSubgraph](ForbiddenSubgraph) that allows all nodes set to true in a boolean vector.
401pub struct AllowedNodesForbiddenSubgraph<'a> {
402    allowed_nodes: &'a [bool],
403}
404impl<'a> AllowedNodesForbiddenSubgraph<'a> {
405    /// Creates a new `AllowedNodesForbiddenSubgraph` with the given boolean vector that contains `true` for each allowed node and `false` for each forbidden node.
406    pub fn new(allowed_nodes: &'a [bool]) -> Self {
407        Self { allowed_nodes }
408    }
409}
410impl<Graph: GraphBase> ForbiddenSubgraph<Graph> for AllowedNodesForbiddenSubgraph<'_> {
411    fn is_node_forbidden(&self, node: Graph::NodeIndex) -> bool {
412        !self.allowed_nodes[node.as_usize()]
413    }
414
415    fn is_edge_forbidden(&self, _: Graph::EdgeIndex) -> bool {
416        false
417    }
418}
419
420/// A [ForbiddenSubgraph](ForbiddenSubgraph) that forbids a single edge.
421pub struct ForbiddenEdge<EdgeIndex> {
422    edge_id: EdgeIndex,
423}
424impl<EdgeIndex> ForbiddenEdge<EdgeIndex> {
425    /// Construct a new `ForbiddenEdge` that forbids the given edge.
426    pub fn new(forbidden_edge: EdgeIndex) -> Self {
427        Self {
428            edge_id: forbidden_edge,
429        }
430    }
431}
432impl<Graph: GraphBase> ForbiddenSubgraph<Graph> for ForbiddenEdge<Graph::EdgeIndex> {
433    fn is_node_forbidden(&self, _: Graph::NodeIndex) -> bool {
434        false
435    }
436
437    fn is_edge_forbidden(&self, edge: Graph::EdgeIndex) -> bool {
438        edge == self.edge_id
439    }
440}
441
442/// A [ForbiddenSubgraph](ForbiddenSubgraph) that forbids a single node.
443pub struct ForbiddenNode<NodeIndex> {
444    node_id: NodeIndex,
445}
446impl<NodeIndex> ForbiddenNode<NodeIndex> {
447    /// Construct a new `ForbiddenNode` that forbids the given node.
448    pub fn new(forbidden_node: NodeIndex) -> Self {
449        Self {
450            node_id: forbidden_node,
451        }
452    }
453}
454impl<Graph: GraphBase> ForbiddenSubgraph<Graph> for ForbiddenNode<Graph::NodeIndex> {
455    fn is_node_forbidden(&self, node: Graph::NodeIndex) -> bool {
456        node == self.node_id
457    }
458
459    fn is_edge_forbidden(&self, _: Graph::EdgeIndex) -> bool {
460        false
461    }
462}
463
464/// A neighbor strategy that traverses all outgoing edges of a node.
465pub struct ForwardNeighborStrategy;
466/*pub type NeighborsIntoNodes<NodeIndex, EdgeIndex, Neighbors> = std::iter::Map<
467    <Neighbors as IntoIterator>::IntoIter,
468    fn(crate::interface::Neighbor<NodeIndex, EdgeIndex>) -> NodeIndex,
469>;*/
470
471impl<Graph: NavigableGraph + ImmutableGraphContainer> TraversalNeighborStrategy<Graph>
472    for ForwardNeighborStrategy
473{
474    type Iterator<'a>
475        = Graph::OutNeighbors<'a>
476    where
477        Self: 'a,
478        Graph: 'a;
479    type EdgeNeighborIterator<'a>
480        = std::iter::Once<Graph::NodeIndex>
481    where
482        Graph: 'a;
483
484    fn neighbor_iterator(graph: &Graph, node: Graph::NodeIndex) -> Self::Iterator<'_> {
485        graph.out_neighbors(node)
486    }
487
488    fn edge_neighbor_iterator(
489        graph: &Graph,
490        edge: Graph::EdgeIndex,
491    ) -> Self::EdgeNeighborIterator<'_> {
492        std::iter::once(graph.edge_endpoints(edge).to_node)
493    }
494}
495
496/// A neighbor strategy that traverses all incoming edges of a node.
497pub struct BackwardNeighborStrategy;
498
499impl<Graph: NavigableGraph + ImmutableGraphContainer> TraversalNeighborStrategy<Graph>
500    for BackwardNeighborStrategy
501{
502    type Iterator<'a>
503        = Graph::InNeighbors<'a>
504    where
505        Self: 'a,
506        Graph: 'a;
507    type EdgeNeighborIterator<'a>
508        = std::iter::Once<Graph::NodeIndex>
509    where
510        Graph: 'a;
511
512    fn neighbor_iterator(graph: &Graph, node: Graph::NodeIndex) -> Self::Iterator<'_> {
513        graph.in_neighbors(node)
514    }
515
516    fn edge_neighbor_iterator(
517        graph: &Graph,
518        edge: Graph::EdgeIndex,
519    ) -> Self::EdgeNeighborIterator<'_> {
520        std::iter::once(graph.edge_endpoints(edge).from_node)
521    }
522}
523
524/// A neighbor strategy that traverses all incoming and all outgoing edges of a node.
525pub struct UndirectedNeighborStrategy;
526type InOutNeighborsChain<OutNeighbors, InNeighbors> = std::iter::Chain<
527    <OutNeighbors as IntoIterator>::IntoIter,
528    <InNeighbors as IntoIterator>::IntoIter,
529>;
530
531impl<Graph: NavigableGraph + ImmutableGraphContainer> TraversalNeighborStrategy<Graph>
532    for UndirectedNeighborStrategy
533{
534    type Iterator<'a>
535        = InOutNeighborsChain<Graph::OutNeighbors<'a>, Graph::InNeighbors<'a>>
536    where
537        Self: 'a,
538        Graph: 'a;
539    type EdgeNeighborIterator<'a>
540        = std::iter::Chain<std::iter::Once<Graph::NodeIndex>, std::iter::Once<Graph::NodeIndex>>
541    where
542        Graph: 'a;
543
544    fn neighbor_iterator(graph: &Graph, node: Graph::NodeIndex) -> Self::Iterator<'_> {
545        graph.out_neighbors(node).chain(graph.in_neighbors(node))
546    }
547
548    fn edge_neighbor_iterator(
549        graph: &Graph,
550        edge: Graph::EdgeIndex,
551    ) -> Self::EdgeNeighborIterator<'_> {
552        std::iter::once(graph.edge_endpoints(edge).to_node)
553            .chain(std::iter::once(graph.edge_endpoints(edge).from_node))
554    }
555}
556
557/// A queue strategy that works by the first-in first-out principle.
558pub struct BfsQueueStrategy;
559
560impl<Graph: GraphBase, Queue: BidirectedQueue<Graph::NodeIndex>>
561    TraversalQueueStrategy<Graph, Queue> for BfsQueueStrategy
562{
563    fn push(queue: &mut Queue, node: Graph::NodeIndex) {
564        queue.push_back(node)
565    }
566
567    fn pop(queue: &mut Queue) -> Option<Graph::NodeIndex> {
568        queue.pop_front()
569    }
570}
571
572/// A queue strategy that works by the last-in first-out principle.
573pub struct DfsQueueStrategy;
574
575impl<Graph: GraphBase, Queue: BidirectedQueue<Graph::NodeIndex>>
576    TraversalQueueStrategy<Graph, Queue> for DfsQueueStrategy
577{
578    fn push(queue: &mut Queue, node: Graph::NodeIndex) {
579        queue.push_back(node)
580    }
581
582    fn pop(queue: &mut Queue) -> Option<Graph::NodeIndex> {
583        queue.pop_back()
584    }
585}
586
587#[cfg(test)]
588mod test {
589    use crate::traversal::{DfsPostOrderTraversal, ForwardNeighborStrategy};
590    use std::collections::VecDeque;
591    use traitgraph::implementation::petgraph_impl::PetGraph;
592    use traitgraph::interface::{MutableGraphContainer, NavigableGraph};
593
594    #[test]
595    fn test_postorder_traversal_simple() {
596        let mut graph = PetGraph::new();
597        let n0 = graph.add_node(0);
598        let n1 = graph.add_node(1);
599        let n2 = graph.add_node(2);
600        let n3 = graph.add_node(3);
601        graph.add_edge(n0, n1, 10);
602        graph.add_edge(n1, n2, 11);
603        graph.add_edge(n2, n3, 12);
604        graph.add_edge(n3, n0, 13);
605        graph.add_edge(n1, n0, 14);
606        graph.add_edge(n2, n1, 15);
607        graph.add_edge(n3, n2, 16);
608        graph.add_edge(n0, n3, 17);
609
610        let mut ordering =
611            DfsPostOrderTraversal::<_, ForwardNeighborStrategy, VecDeque<_>>::new(&graph, n0);
612        debug_assert_eq!(
613            graph.out_neighbors(n0).map(|n| n.node_id).next(),
614            Some(3.into())
615        );
616        debug_assert_eq!(ordering.next(&graph), Some(n3));
617        debug_assert_eq!(ordering.next(&graph), Some(n2));
618        debug_assert_eq!(ordering.next(&graph), Some(n1));
619        debug_assert_eq!(ordering.next(&graph), Some(n0));
620        debug_assert_eq!(ordering.next(&graph), None);
621    }
622}
traitgraph_algo/traversal/mod.rs

traitgraph_algo/traversal/
mod.rs
