1 use rustc_index::vec::Idx;
2
3 pub mod dominators;
4 pub mod implementation;
5 pub mod iterate;
6 mod reference;
7 pub mod scc;
8 pub mod vec_graph;
9
10 #[cfg(test)]
11 mod tests;
12
13 pub trait DirectedGraph {
14 type Node: Idx;
15 }
16
17 pub trait WithNumNodes: DirectedGraph {
num_nodes(&self) -> usize18 fn num_nodes(&self) -> usize;
19 }
20
21 pub trait WithNumEdges: DirectedGraph {
num_edges(&self) -> usize22 fn num_edges(&self) -> usize;
23 }
24
25 pub trait WithSuccessors: DirectedGraph
26 where
27 Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
28 {
successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter29 fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter;
30
depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self> where Self: WithNumNodes,31 fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self>
32 where
33 Self: WithNumNodes,
34 {
35 iterate::DepthFirstSearch::new(self).with_start_node(from)
36 }
37 }
38
39 #[allow(unused_lifetimes)]
40 pub trait GraphSuccessors<'graph> {
41 type Item;
42 type Iter: Iterator<Item = Self::Item>;
43 }
44
45 pub trait WithPredecessors: DirectedGraph
46 where
47 Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
48 {
predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter49 fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter;
50 }
51
52 #[allow(unused_lifetimes)]
53 pub trait GraphPredecessors<'graph> {
54 type Item;
55 type Iter: Iterator<Item = Self::Item>;
56 }
57
58 pub trait WithStartNode: DirectedGraph {
start_node(&self) -> Self::Node59 fn start_node(&self) -> Self::Node;
60 }
61
62 pub trait ControlFlowGraph:
63 DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes
64 {
65 // convenient trait
66 }
67
68 impl<T> ControlFlowGraph for T where
69 T: DirectedGraph + WithStartNode + WithPredecessors + WithSuccessors + WithNumNodes
70 {
71 }
72
73 /// Returns `true` if the graph has a cycle that is reachable from the start node.
is_cyclic<G>(graph: &G) -> bool where G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes,74 pub fn is_cyclic<G>(graph: &G) -> bool
75 where
76 G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes,
77 {
78 iterate::TriColorDepthFirstSearch::new(graph)
79 .run_from_start(&mut iterate::CycleDetector)
80 .is_some()
81 }
82