1 use rustc_index::vec::Idx;
4 pub mod implementation;
13 pub trait DirectedGraph {
17 pub trait WithNumNodes: DirectedGraph {
18 fn num_nodes(&self) -> usize;
21 pub trait WithNumEdges: DirectedGraph {
22 fn num_edges(&self) -> usize;
25 pub trait WithSuccessors: DirectedGraph
27 Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
29 fn successors(&self, node: Self::Node) -> <Self as GraphSuccessors<'_>>::Iter;
31 fn depth_first_search(&self, from: Self::Node) -> iterate::DepthFirstSearch<'_, Self>
35 iterate::DepthFirstSearch::new(self, from)
39 #[allow(unused_lifetimes)]
40 pub trait GraphSuccessors<'graph> {
42 type Iter: Iterator<Item = Self::Item>;
45 pub trait WithPredecessors: DirectedGraph
47 Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
49 fn predecessors(&self, node: Self::Node) -> <Self as GraphPredecessors<'_>>::Iter;
52 #[allow(unused_lifetimes)]
53 pub trait GraphPredecessors<'graph> {
55 type Iter: Iterator<Item = Self::Item>;
58 pub trait WithStartNode: DirectedGraph {
59 fn start_node(&self) -> Self::Node;
62 pub trait ControlFlowGraph:
63 DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
68 impl<T> ControlFlowGraph for T where
78 /// Returns `true` if the graph has a cycle that is reachable from the start node.
79 pub fn is_cyclic<G>(graph: &G) -> bool
81 G: ?Sized + DirectedGraph + WithStartNode + WithSuccessors + WithNumNodes,
83 iterate::TriColorDepthFirstSearch::new(graph)
84 .run_from_start(&mut iterate::CycleDetector)