guppy/petgraph_support/
dfs.rs

Help
1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use petgraph::{
5    prelude::*,
6    visit::{
7        DfsPostOrder, IntoEdgeReferences, IntoEdges, IntoEdgesDirected, Reversed,
8        ReversedEdgeReference, VisitMap,
9    },
10};
11
12/// `DfsPostOrder::next`, adapted for a buffered filter that's also FnMut.
13pub fn dfs_next_buffered_filter<N, VM, G>(
14    dfs: &mut DfsPostOrder<N, VM>,
15    graph: G,
16    mut buffered_filter: impl BufferedEdgeFilter<G>,
17) -> Option<N>
18where
19    N: Copy + PartialEq,
20    VM: VisitMap<N>,
21    G: IntoEdges<NodeId = N>,
22{
23    // Adapted from DfsPostOrder::next in petgraph 0.5.0.
24    while let Some(&nx) = dfs.stack.last() {
25        if dfs.discovered.visit(nx) {
26            // First time visiting `nx`: Push neighbors, don't pop `nx`
27            let neighbors = graph.edges(nx).flat_map(|edge| {
28                buffered_filter
29                    .filter(edge)
30                    .into_iter()
31                    .map(|edge| edge.target())
32            });
33            for succ in neighbors {
34                if !dfs.discovered.is_visited(&succ) {
35                    dfs.stack.push(succ);
36                }
37            }
38        } else {
39            dfs.stack.pop();
40            if dfs.finished.visit(nx) {
41                // Second time: All reachable nodes must have been finished
42                return Some(nx);
43            }
44        }
45    }
46    None
47}
48
49/// A buffered filter is a graph traversal edge filter that can buffer up some edges to be
50/// returned later.
51pub trait BufferedEdgeFilter<G>
52where
53    G: IntoEdges,
54{
55    /// Returns a list of edge references to follow.
56    type Iter: IntoIterator<Item = G::EdgeRef>;
57
58    fn filter(&mut self, edge: G::EdgeRef) -> Self::Iter;
59}
60
61impl<G, T> BufferedEdgeFilter<G> for &mut T
62where
63    T: BufferedEdgeFilter<G>,
64    G: IntoEdges,
65{
66    /// Returns a list of node IDs to follow.
67    type Iter = T::Iter;
68
69    #[inline]
70    fn filter(&mut self, edge: G::EdgeRef) -> Self::Iter {
71        (*self).filter(edge)
72    }
73}
74
75#[derive(Debug)]
76pub struct SimpleEdgeFilterFn<F>(pub F);
77
78impl<F, G> BufferedEdgeFilter<G> for SimpleEdgeFilterFn<F>
79where
80    F: FnMut(G::EdgeRef) -> bool,
81    G: IntoEdges,
82{
83    type Iter = Option<G::EdgeRef>;
84
85    #[inline]
86    fn filter(&mut self, edge: G::EdgeRef) -> Self::Iter {
87        if (self.0)(edge) { Some(edge) } else { None }
88    }
89}
90
91#[derive(Debug)]
92pub struct BufferedEdgeFilterFn<F>(pub F);
93
94impl<F, G, I> BufferedEdgeFilter<G> for BufferedEdgeFilterFn<F>
95where
96    F: FnMut(G::EdgeRef) -> I,
97    G: IntoEdges,
98    I: IntoIterator<Item = G::EdgeRef>,
99{
100    type Iter = I;
101
102    #[inline]
103    fn filter(&mut self, edge: G::EdgeRef) -> Self::Iter {
104        (self.0)(edge)
105    }
106}
107
108#[derive(Debug)]
109pub struct ReversedBufferedFilter<T>(pub T);
110
111impl<T, G> BufferedEdgeFilter<Reversed<G>> for ReversedBufferedFilter<T>
112where
113    T: BufferedEdgeFilter<G>,
114    G: IntoEdgesDirected,
115{
116    type Iter =
117        ReversedEdgeReferences<<<T as BufferedEdgeFilter<G>>::Iter as IntoIterator>::IntoIter>;
118
119    fn filter(&mut self, edge: <Reversed<G> as IntoEdgeReferences>::EdgeRef) -> Self::Iter {
120        ReversedEdgeReferences {
121            iter: self.0.filter(edge.into_unreversed()).into_iter(),
122        }
123    }
124}
125
126// TODO: replace with upstream impl
127pub struct ReversedEdgeReferences<I> {
128    iter: I,
129}
130
131impl<I> Iterator for ReversedEdgeReferences<I>
132where
133    I: Iterator,
134{
135    type Item = ReversedEdgeReference<I::Item>;
136
137    #[inline]
138    fn next(&mut self) -> Option<Self::Item> {
139        // Ugh this sucks! Should be supported upstream.
140        // SAFETY: this is just a newtype. This is SUCH a horrible hack.
141        let item = self.iter.next()?;
142        Some(unsafe { horrible_transmute::<I::Item, ReversedEdgeReference<I::Item>>(item) })
143    }
144
145    #[inline]
146    fn size_hint(&self) -> (usize, Option<usize>) {
147        self.iter.size_hint()
148    }
149}
150
151unsafe fn horrible_transmute<A, B>(a: A) -> B {
152    let b = ::core::ptr::read(&a as *const A as *const B);
153    ::core::mem::forget(a);
154    b
155}
156
157// Check that the above transmute is actually safe.
158static_assertions::assert_eq_size!((), ReversedEdgeReference<()>);
guppy/petgraph_support/dfs.rs

guppy/petgraph_support/
dfs.rs
