guppy/petgraph_support/
scc.rs

1// Copyright (c) The cargo-guppy Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use ahash::AHashMap;
5use fixedbitset::FixedBitSet;
6use nested::Nested;
7use petgraph::{
8    algo::kosaraju_scc,
9    graph::IndexType,
10    prelude::*,
11    visit::{IntoNeighborsDirected, IntoNodeIdentifiers, VisitMap, Visitable},
12};
13use std::slice;
14
15#[derive(Clone, Debug)]
16pub(crate) struct Sccs<Ix: IndexType> {
17    sccs: Nested<Vec<NodeIndex<Ix>>>,
18    // Map of node indexes to the index of the SCC they belong to. If a node is not part of an SCC,
19    // then the corresponding index is not stored here.
20    multi_map: AHashMap<NodeIndex<Ix>, usize>,
21}
22
23impl<Ix: IndexType> Sccs<Ix> {
24    /// Creates a new instance from the provided graph and the given sorter.
25    pub fn new<G>(graph: G, mut scc_sorter: impl FnMut(&mut Vec<NodeIndex<Ix>>)) -> Self
26    where
27        G: IntoNeighborsDirected<NodeId = NodeIndex<Ix>> + Visitable + IntoNodeIdentifiers,
28        <G as Visitable>::Map: VisitMap<NodeIndex<Ix>>,
29    {
30        // Use kosaraju_scc since it is iterative (tarjan_scc is recursive) and package graphs
31        // have unbounded depth.
32        let sccs = kosaraju_scc(graph);
33        let sccs: Nested<Vec<_>> = sccs
34            .into_iter()
35            .map(|mut scc| {
36                if scc.len() > 1 {
37                    scc_sorter(&mut scc);
38                }
39                scc
40            })
41            // kosaraju_scc returns its sccs in reverse topological order. Reverse it again for
42            // forward topological order.
43            .rev()
44            .collect();
45        let mut multi_map = AHashMap::new();
46        for (idx, scc) in sccs.iter().enumerate() {
47            if scc.len() > 1 {
48                multi_map.extend(scc.iter().map(|ix| (*ix, idx)));
49            }
50        }
51        Self { sccs, multi_map }
52    }
53
54    /// Returns true if `a` and `b` are in the same scc.
55    pub fn is_same_scc(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
56        if a == b {
57            return true;
58        }
59        match (self.multi_map.get(&a), self.multi_map.get(&b)) {
60            (Some(a_scc), Some(b_scc)) => a_scc == b_scc,
61            _ => false,
62        }
63    }
64
65    /// Returns all the SCCs with more than one element.
66    pub fn multi_sccs(&self) -> impl DoubleEndedIterator<Item = &[NodeIndex<Ix>]> {
67        self.sccs.iter().filter(|scc| scc.len() > 1)
68    }
69
70    /// Returns all the nodes of this graph that have no incoming edges to them, and all the nodes
71    /// in an SCC into which there are no incoming edges.
72    pub fn externals<'a, G>(&'a self, graph: G) -> impl Iterator<Item = NodeIndex<Ix>> + 'a
73    where
74        G: 'a + IntoNodeIdentifiers + IntoNeighborsDirected<NodeId = NodeIndex<Ix>>,
75        Ix: IndexType,
76    {
77        // Consider each SCC as one logical node.
78        let mut external_sccs = FixedBitSet::with_capacity(self.sccs.len());
79        let mut internal_sccs = FixedBitSet::with_capacity(self.sccs.len());
80        graph
81            .node_identifiers()
82            .filter(move |ix| match self.multi_map.get(ix) {
83                Some(&scc_idx) => {
84                    // Consider one node identifier for each scc -- whichever one comes first.
85                    if external_sccs.contains(scc_idx) {
86                        return true;
87                    }
88                    if internal_sccs.contains(scc_idx) {
89                        return false;
90                    }
91
92                    let scc = &self.sccs[scc_idx];
93                    let is_external = scc
94                        .iter()
95                        .flat_map(|ix| {
96                            // Look at all incoming nodes from every SCC member.
97                            graph.neighbors_directed(*ix, Incoming)
98                        })
99                        .all(|neighbor_ix| {
100                            // * Accept any nodes are in the same SCC.
101                            // * Any other results imply that this isn't an external scc.
102                            match self.multi_map.get(&neighbor_ix) {
103                                Some(neighbor_scc_idx) => neighbor_scc_idx == &scc_idx,
104                                None => false,
105                            }
106                        });
107                    if is_external {
108                        external_sccs.insert(scc_idx);
109                    } else {
110                        internal_sccs.insert(scc_idx);
111                    }
112                    is_external
113                }
114                None => {
115                    // Not part of an SCC -- just look at whether there are any incoming nodes
116                    // at all.
117                    graph.neighbors_directed(*ix, Incoming).next().is_none()
118                }
119            })
120    }
121
122    /// Iterate over all nodes in the direction specified.
123    pub fn node_iter(&self, direction: Direction) -> NodeIter<Ix> {
124        NodeIter {
125            node_ixs: self.sccs.data().iter(),
126            direction,
127        }
128    }
129}
130
131/// An iterator over the nodes of strongly connected components.
132#[derive(Clone, Debug)]
133pub(crate) struct NodeIter<'a, Ix> {
134    node_ixs: slice::Iter<'a, NodeIndex<Ix>>,
135    direction: Direction,
136}
137
138impl<Ix> NodeIter<'_, Ix> {
139    /// Returns the direction this iteration is happening in.
140    #[allow(dead_code)]
141    pub fn direction(&self) -> Direction {
142        self.direction
143    }
144}
145
146impl<Ix: IndexType> Iterator for NodeIter<'_, Ix> {
147    type Item = NodeIndex<Ix>;
148
149    fn next(&mut self) -> Option<NodeIndex<Ix>> {
150        // Note that outgoing implies iterating over the sccs in forward order, while incoming means
151        // sccs in reverse order.
152        match self.direction {
153            Direction::Outgoing => self.node_ixs.next().copied(),
154            Direction::Incoming => self.node_ixs.next_back().copied(),
155        }
156    }
157}
guppy/petgraph_support/scc.rs

guppy/petgraph_support/
scc.rs
