strongly_connected_components/internal/
graph.rs

1use crate::internal::node::Node;
2use crate::internal::scc_decomposition::SccDecomposition;
3use crate::internal::tarjan_algorithm::TarjanAlgorithm;
4
5/// Represents the graph on which SCC decomposition will be done.
6/// Consists of [`Node`]s, connected by directed edges.
7///
8/// ```
9/// # use strongly_connected_components::Graph;
10/// let mut graph = Graph::new();
11/// let v0 = graph.new_node();
12/// let v1 = graph.new_node();
13/// let v2 = graph.new_node();
14/// let v3 = graph.new_node();
15/// graph.new_edge(v0, v1);
16/// graph.new_edge(v1, v3);
17/// graph.new_edge(v1, v1);
18/// // Graph looks like this:
19/// // ┌───┐  ┌───┐  ┌───┐ ┌───┐
20/// // │ 0 ├─►│ 1 ├─►│ 3 │ │ 2 │
21/// // └───┘  └▲─┬┘  └───┘ └───┘
22/// //         └─┘
23/// ```
24#[derive(Clone, Default)]
25pub struct Graph {
26    pub(super) edges: Vec<Vec<usize>>,
27}
28
29impl Graph {
30    /// Creates an empty graph with no nodes and no edges.
31    /// [`Node`]s can be added by calling [`Graph::new_node`].
32    /// Edges can be added by calling [`Graph::new_edge`].
33    pub fn new() -> Self {
34        Self { edges: Vec::new() }
35    }
36
37    /// Creates a new node of the graph with no incoming/outgoing edges.
38    /// Edges can be added by calling [`Graph::new_edge`].
39    pub fn new_node(&mut self) -> Node {
40        let node = Node {
41            id: self.edges.len(),
42        };
43        self.edges.push(Vec::new());
44        node
45    }
46
47    /// Creates a new directed edge between two nodes.
48    pub fn new_edge(&mut self, from: Node, to: Node) {
49        assert!(from.id < self.edges.len());
50        assert!(to.id < self.edges.len());
51        self.edges[from.id].push(to.id);
52    }
53
54    /// Computes the Strongly Connected Components decomposition of this graph.
55    /// Uses [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
56    /// which runs in O(|N| + |E|) time and uses O(|N| + |E|) memory.
57    pub fn find_sccs(&self) -> SccDecomposition {
58        TarjanAlgorithm::new(self).solve()
59    }
60
61    /// Returns the number of nodes in this graph.
62    pub fn len(&self) -> usize {
63        self.edges.len()
64    }
65
66    /// Returns `true` if the graph has no nodes.
67    pub fn is_empty(&self) -> bool {
68        self.edges.is_empty()
69    }
70
71    /// Iterates over all nodes that belong to this graph, in no particular order.
72    pub fn iter_nodes(&self) -> impl Iterator<Item = Node> {
73        (0..self.edges.len()).map(|id| Node { id })
74    }
75
76    /// Iterates over all successors of the given node, in no particular order.
77    pub fn iter_successors(&self, node: Node) -> impl Iterator<Item = Node> {
78        assert!(node.id < self.edges.len());
79        self.edges[node.id].iter().copied().map(|id| Node { id })
80    }
81}
strongly_connected_components/internal/graph.rs

strongly_connected_components/internal/
graph.rs
