rustc_data_structures/graph/
mod.rs
1use rustc_index::Idx;
2
3pub mod dominators;
4pub mod implementation;
5pub mod iterate;
6mod reference;
7pub mod reversed;
8pub mod scc;
9pub mod vec_graph;
10
11#[cfg(test)]
12mod tests;
13
14pub trait DirectedGraph {
15 type Node: Idx;
16
17 fn num_nodes(&self) -> usize;
24
25 fn iter_nodes(
30 &self,
31 ) -> impl Iterator<Item = Self::Node> + DoubleEndedIterator + ExactSizeIterator {
32 (0..self.num_nodes()).map(<Self::Node as Idx>::new)
33 }
34}
35
36pub trait NumEdges: DirectedGraph {
37 fn num_edges(&self) -> usize;
38}
39
40pub trait StartNode: DirectedGraph {
41 fn start_node(&self) -> Self::Node;
42}
43
44pub trait Successors: DirectedGraph {
45 fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>;
46}
47
48pub trait Predecessors: DirectedGraph {
49 fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node>;
50}
51
52pub trait ControlFlowGraph: DirectedGraph + StartNode + Predecessors + Successors {}
54impl<T> ControlFlowGraph for T where T: DirectedGraph + StartNode + Predecessors + Successors {}
55
56pub fn is_cyclic<G>(graph: &G) -> bool
58where
59 G: ?Sized + DirectedGraph + StartNode + Successors,
60{
61 iterate::TriColorDepthFirstSearch::new(graph)
62 .run_from_start(&mut iterate::CycleDetector)
63 .is_some()
64}
65
66pub fn depth_first_search<G>(graph: G, from: G::Node) -> iterate::DepthFirstSearch<G>
67where
68 G: Successors,
69{
70 iterate::DepthFirstSearch::new(graph).with_start_node(from)
71}
72
73pub fn depth_first_search_as_undirected<G>(
74 graph: G,
75 from: G::Node,
76) -> iterate::DepthFirstSearch<impl Successors<Node = G::Node>>
77where
78 G: Successors + Predecessors,
79{
80 struct AsUndirected<G>(G);
81
82 impl<G: DirectedGraph> DirectedGraph for AsUndirected<G> {
83 type Node = G::Node;
84
85 fn num_nodes(&self) -> usize {
86 self.0.num_nodes()
87 }
88 }
89
90 impl<G: Successors + Predecessors> Successors for AsUndirected<G> {
91 fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
92 self.0.successors(node).chain(self.0.predecessors(node))
93 }
94 }
95
96 iterate::DepthFirstSearch::new(AsUndirected(graph)).with_start_node(from)
97}