diff options
| author | Manish Goregaokar <manishsmail@gmail.com> | 2020-07-03 17:17:05 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2020-07-03 17:17:05 -0700 |
| commit | 70c4b2ff6098b06229c1c04ea4f8e7cd0b8cdd19 (patch) | |
| tree | 9fc421a5375a5212d760c11bf7ea722fee939e35 | |
| parent | 60cad20b41d93c94c247cd32873e5c176effc7d2 (diff) | |
| parent | 20caf634bd3c9783a7822e86811a7e77a88d378f (diff) | |
| download | rust-70c4b2ff6098b06229c1c04ea4f8e7cd0b8cdd19.tar.gz rust-70c4b2ff6098b06229c1c04ea4f8e7cd0b8cdd19.zip | |
Rollup merge of #73984 - pierwill:pierwill-tarjan, r=jonas-schievink
Edit docs for rustc_data_structures::graph::scc - Add newline to provide concise module summary - Add wikipedia link - Italicize O notation
| -rw-r--r-- | src/librustc_data_structures/graph/scc/mod.rs | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/src/librustc_data_structures/graph/scc/mod.rs b/src/librustc_data_structures/graph/scc/mod.rs index 57eaf56f268..2db8e466e11 100644 --- a/src/librustc_data_structures/graph/scc/mod.rs +++ b/src/librustc_data_structures/graph/scc/mod.rs @@ -1,7 +1,9 @@ -//! Routine to compute the strongly connected components (SCCs) of a -//! graph, as well as the resulting DAG if each SCC is replaced with a -//! node in the graph. This uses Tarjan's algorithm that completes in -//! O(n) time. +//! Routine to compute the strongly connected components (SCCs) of a graph. +//! +//! Also computes as the resulting DAG if each SCC is replaced with a +//! node in the graph. This uses [Tarjan's algorithm]( +//! https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) +//! that completes in *O(n)* time. use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; |