algorithms_fourth 0.1.10

用rust实现算法4书中的算法，作为rust的学习实践
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

//! 计算强连通分量
//! # 使用例子
//! ```
//!use algorithms_fourth::{
//!        add_edge,
//!        digraph::{connect::KosarajuSCC, Digraph},
//!    };
//!        let mut g = Digraph::new(13);
//!        add_edge!(g, 0, 1, 5);
//!        add_edge!(g, 2, 3, 0);
//!        add_edge!(g, 3, 2, 5);
//!        add_edge!(g, 4, 2, 3);
//!        add_edge!(g, 5, 4);
//!        add_edge!(g, 6, 0, 4, 9);
//!        add_edge!(g, 7, 6, 8);
//!        add_edge!(g, 8, 7, 9);
//!        add_edge!(g, 9, 10, 11);
//!        add_edge!(g, 10, 12);
//!        add_edge!(g, 11, 4, 12);
//!        add_edge!(g, 12, 9);
//!        // g.print_dot("digraph.dot");
//!        // g.reverse().print_dot("digraph_reverse.dot");
//!        let scc = KosarajuSCC::new(&g);
//!        assert_eq!(scc.count(), 5);
//!        for i in 0..scc.count() {
//!            let points: Vec<usize> = (0..g.vertex_count())
//!                .into_iter()
//!                .filter(|f| scc.id(*f) == i)
//!                .collect();
//!            println!("{}:{:?}", i, points);
//!        }
//! ```

use super::{depth_first_order::DepthFirstOrder, Digraph};

pub struct KosarajuSCC {
    /// 已访问过的顶点
    marked: Vec<bool>,
    /// 强连通分量的标识符
    id: Vec<usize>,
    /// 强连通分量的数量
    count: usize,
}

impl KosarajuSCC {
    pub fn new(g: &Digraph) -> Self {
        let marked = vec![false; g.vertex_count()];
        let id = vec![usize::MAX; g.vertex_count()];
        let order = DepthFirstOrder::new(&g.reverse());
        let mut scc = KosarajuSCC {
            marked,
            id,
            count: 0,
        };
        let mut points = order.reverse_post();
        while let Some(s) = points.pop() {
            if !scc.marked[s] {
                scc.dfs(g, s);
                scc.count += 1;
            }
        }
        scc
    }

    fn dfs(&mut self, g: &Digraph, v: usize) {
        self.marked[v] = true;
        self.id[v] = self.count;
        for w in g.adj(v) {
            if !self.marked[*w] {
                self.dfs(g, *w);
            }
        }
    }
    pub fn strongly_connected(&self, v: usize, w: usize) -> bool {
        self.id[v] == self.id[w]
    }
    pub fn id(&self, v: usize) -> usize {
        self.id[v]
    }
    pub fn count(&self) -> usize {
        self.count
    }
}
#[cfg(test)]
mod test {
    use crate::{
        add_edge,
        digraph::{connect::KosarajuSCC, Digraph},
    };

    #[test]
    fn test() {
        let mut g = Digraph::new(13);
        add_edge!(g, 0, 1, 5);
        add_edge!(g, 2, 3, 0);
        add_edge!(g, 3, 2, 5);
        add_edge!(g, 4, 2, 3);
        add_edge!(g, 5, 4);
        add_edge!(g, 6, 0, 4, 9);
        add_edge!(g, 7, 6, 8);
        add_edge!(g, 8, 7, 9);
        add_edge!(g, 9, 10, 11);
        add_edge!(g, 10, 12);
        add_edge!(g, 11, 4, 12);
        add_edge!(g, 12, 9);
        // g.print_dot("digraph.dot");
        // g.reverse().print_dot("digraph_reverse.dot");
        let scc = KosarajuSCC::new(&g);
        assert_eq!(scc.count(), 5);
        for i in 0..scc.count() {
            let points: Vec<usize> = (0..g.vertex_count())
                .into_iter()
                .filter(|f| scc.id(*f) == i)
                .collect();
            println!("{}:{:?}", i, points);
        }
    }
}