Struct nekolib::graph::FunctionalGraph

pub struct FunctionalGraph { /* private fields */ }

function graph。

Todo

辺にモノイドを持たせて n 個進んだときの fold をするのは ダブリングテーブルとかが必要になって、周期検出をしたいだけのときには オーバーヘッドが大きそう。

なので、FoldableFunctionalGraph とかを別に作ってみる。 それの内部でこれを持っても使えそう。

Complexity

$O(n)$ time.

Examples

+---> 1 ----+     +--- 6 <--- 5
|           |     |
|           v     |
|           2 <---+--- 7     12
0           |
^           v                 8
|           3 <------ 11      |
|           |                 v
+---- 4 <---+     10 <------> 9

$i$	0	1	2	3	4	5	6	7	8	9	10	11	12
$f(i)$	1	2	3	4	0	6	2	2	9	10	9	3	12
$\mu_i$	0	0	0	0	0	2	1	1	1	0	0	1	0
$\lambda_i$	5	5	5	5	5	5	5	5	2	2	2	5	1

use nekolib::graph::FunctionalGraph;

let f = vec![1, 2, 3, 4, 0, 6, 2, 2, 9, 10, 9, 3, 12];
let n = f.len();
let g: FunctionalGraph = f.into();
let mu = vec![0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 0, 1, 0];
let lambda = vec![5, 5, 5, 5, 5, 5, 5, 5, 2, 2, 2, 5, 1];
for i in 0..n {
    assert_eq!(g.mu_lambda(i), (mu[i], lambda[i]));
}

Implementations

impl FunctionalGraph

pub fn mu_lambda(&self, i: usize) -> (usize, usize)

$(\mu_i, \lambda_i)$ を返す。

Trait Implementations

impl Clone for FunctionalGraph

fn clone(&self) -> FunctionalGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for FunctionalGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<Vec<usize, Global>> for FunctionalGraph

fn from(f: Vec<usize>) -> Self

Converts to this type from the input type.

impl PartialEq<FunctionalGraph> for FunctionalGraph

fn eq(&self, other: &FunctionalGraph) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for FunctionalGraph

impl StructuralEq for FunctionalGraph

impl StructuralPartialEq for FunctionalGraph