nekolib/graph/
functional_graph.rs

1//! functional graph。
2
3use std::fmt::Debug;
4
5/// function graph。
6///
7/// # Todo
8/// 辺にモノイドを持たせて n 個進んだときの fold をするのは
9/// ダブリングテーブルとかが必要になって、周期検出をしたいだけのときには
10/// オーバーヘッドが大きそう。
11///
12/// なので、`FoldableFunctionalGraph` とかを別に作ってみる。
13/// それの内部でこれを持っても使えそう。
14///
15/// # Complexity
16/// $O(n)$ time.
17///
18/// # Examples
19/// ```text
20/// +---> 1 ----+     +--- 6 <--- 5
21/// |           |     |
22/// |           v     |
23/// |           2 <---+--- 7     12
24/// 0           |
25/// ^           v                 8
26/// |           3 <------ 11      |
27/// |           |                 v
28/// +---- 4 <---+     10 <------> 9
29/// ```
30/// |$i$|0|1|2|3|4|5|6|7|8|9|10|11|12|
31/// |---|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
32/// |$f(i)$|1|2|3|4|0|6|2|2|9|10|9|3|12|
33/// |$\\mu\_i$|0|0|0|0|0|2|1|1|1|0|0|1|0|
34/// |$\\lambda\_i$|5|5|5|5|5|5|5|5|2|2|2|5|1|
35/// ```
36/// use nekolib::graph::FunctionalGraph;
37///
38/// let f = vec![1, 2, 3, 4, 0, 6, 2, 2, 9, 10, 9, 3, 12];
39/// let n = f.len();
40/// let g: FunctionalGraph = f.into();
41/// let mu = vec![0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 0, 1, 0];
42/// let lambda = vec![5, 5, 5, 5, 5, 5, 5, 5, 2, 2, 2, 5, 1];
43/// for i in 0..n {
44///     assert_eq!(g.mu_lambda(i), (mu[i], lambda[i]));
45/// }
46/// ```
47#[derive(Clone, Debug, Eq, PartialEq)]
48pub struct FunctionalGraph {
49    to: Vec<usize>,
50    mu_lambda: Vec<(usize, usize)>,
51}
52
53impl From<Vec<usize>> for FunctionalGraph {
54    fn from(f: Vec<usize>) -> Self {
55        let n = f.len();
56        let none = (n, 0);
57        let mut mu_lambda = vec![none; n];
58        let mut stack = vec![];
59        let mut index = vec![n; n];
60        for mut i in 0..n {
61            while mu_lambda[i] == none {
62                if index[i] < n {
63                    break;
64                }
65                index[i] = stack.len();
66                stack.push(i);
67                i = f[i];
68            }
69            if mu_lambda[i] == none {
70                let lambda = stack.len() - index[i];
71                let seen = i;
72                while let Some(j) = stack.pop() {
73                    mu_lambda[j] = (0, lambda);
74                    if j == seen {
75                        break;
76                    }
77                }
78            }
79            while let Some(j) = stack.pop() {
80                mu_lambda[j] = mu_lambda[f[j]];
81                mu_lambda[j].0 += 1;
82            }
83        }
84        Self { to: f, mu_lambda }
85    }
86}
87
88impl FunctionalGraph {
89    /// $(\\mu\_i, \\lambda\_i)$ を返す。
90    pub fn mu_lambda(&self, i: usize) -> (usize, usize) { self.mu_lambda[i] }
91}
nekolib/graph/functional_graph.rs

nekolib/graph/
functional_graph.rs
