competitive_library/graph/
util.rs

1//! 隣接行列 ←→ 隣接リスト
2pub fn to_adjacency_matrix(g: &[Vec<i64>]) -> Vec<Vec<Option<i64>>> {
3    let mut v = vec![vec![None; g.len()]; g.len()];
4    g.iter()
5        .enumerate()
6        .for_each(|(from, vec)| vec.iter().for_each(|to| v[from][*to as usize] = Some(1)));
7    v
8}
9
10pub fn adjacency_list(matrix: &[Vec<i64>]) -> Vec<Vec<i64>> {
11    matrix
12        .iter()
13        .map(|v| {
14            v.iter()
15                .enumerate()
16                .filter(|&(_, &v)| v > 0)
17                .map(|(j, _)| j as i64)
18                .collect()
19        })
20        .collect()
21}
22
23#[cfg(test)]
24mod tests {
25    use super::*;
26    #[test]
27    fn test_to_adjacency_matrix() {
28        let m = to_adjacency_matrix(&[
29            vec![1, 2, 4],
30            vec![0, 2, 3],
31            vec![0, 1, 3, 4],
32            vec![1, 2, 4],
33            vec![0, 2, 3],
34        ]);
35
36        let ans = [
37            vec![0, 1, 1, 0, 1],
38            vec![1, 0, 1, 1, 0],
39            vec![1, 1, 0, 1, 1],
40            vec![0, 1, 1, 0, 1],
41            vec![1, 0, 1, 1, 0],
42        ];
43        dbg!(&m);
44        for i in 0..ans.len() {
45            for j in 0..ans.len() {
46                let v = m[i][j].unwrap_or(0);
47                assert_eq!(ans[i][j], v);
48            }
49        }
50    }
51    #[test]
52    fn test_adjacency_list() {
53        let al = adjacency_list(&[
54            vec![0, 1, 1, 0, 1],
55            vec![1, 0, 1, 1, 0],
56            vec![1, 1, 0, 1, 1],
57            vec![0, 1, 1, 0, 1],
58            vec![1, 0, 1, 1, 0],
59        ]);
60
61        assert_eq!(
62            &vec![
63                vec![1, 2, 4],
64                vec![0, 2, 3],
65                vec![0, 1, 3, 4],
66                vec![1, 2, 4],
67                vec![0, 2, 3],
68            ],
69            &al
70        );
71    }
72}
competitive_library/graph/util.rs

competitive_library/graph/
util.rs
