guppy/petgraph_support/
walk.rs

Help
1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::petgraph_support::edge_triple;
5use petgraph::visit::{IntoEdges, VisitMap, Visitable, Walker};
6use std::iter;
7
8#[derive(Clone, Debug)]
9pub(crate) struct EdgeDfs<E, N, VM> {
10    /// The queue of (source, target, edge) to visit.
11    pub stack: Vec<(N, N, E)>,
12    /// The map of discovered nodes
13    pub discovered: VM,
14}
15
16impl<E, N, VM> EdgeDfs<E, N, VM>
17where
18    E: Copy + PartialEq,
19    N: Copy + PartialEq,
20    VM: VisitMap<N>,
21{
22    /// Creates a new EdgeDfs, using the graph's visitor map, and puts all edges out of `initials`
23    /// in the queue of edges to visit.
24    pub(crate) fn new<G>(graph: G, initials: impl IntoIterator<Item = N>) -> Self
25    where
26        G: Visitable<Map = VM> + IntoEdges<NodeId = N, EdgeId = E>,
27    {
28        let mut discovered = graph.visit_map();
29        let stack = initials
30            .into_iter()
31            .filter_map(|node_ix| {
32                // This check ensures that if a node is repeated in initials, its edges are only
33                // added once.
34                if discovered.visit(node_ix) {
35                    Some(graph.edges(node_ix).map(edge_triple))
36                } else {
37                    None
38                }
39            })
40            .flatten()
41            .collect();
42        Self { stack, discovered }
43    }
44
45    /// Creates a new EdgeDfs, using the graph's visitor map, and puts all edges out of `start`
46    /// in the queue of edges to visit.
47    #[allow(dead_code)]
48    pub(crate) fn new_single<G>(graph: G, start: N) -> Self
49    where
50        G: Visitable<Map = VM> + IntoEdges<NodeId = N, EdgeId = E>,
51    {
52        Self::new(graph, iter::once(start))
53    }
54
55    /// Returns the next edge in the dfs, or `None` if no more edges remain.
56    pub fn next<G>(&mut self, graph: G) -> Option<(N, N, E)>
57    where
58        G: IntoEdges<NodeId = N, EdgeId = E>,
59    {
60        let (source, target, edge) = self.stack.pop()?;
61        if self.discovered.visit(target) {
62            self.stack.extend(graph.edges(target).map(edge_triple));
63        }
64        Some((source, target, edge))
65    }
66}
67
68impl<G> Walker<G> for EdgeDfs<G::EdgeId, G::NodeId, G::Map>
69where
70    G: IntoEdges + Visitable,
71{
72    type Item = (G::NodeId, G::NodeId, G::EdgeId);
73
74    fn walk_next(&mut self, context: G) -> Option<Self::Item> {
75        self.next(context)
76    }
77}
guppy/petgraph_support/walk.rs

guppy/petgraph_support/
walk.rs
