dsalgo 0.3.10

A package for Datastructures and Algorithms.
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

pub fn bfs() {}

pub fn dfs() {}

use crate::graph::edge::{
    From,
    Reversed,
    To,
    ToDirected,
};

/// return edge ids.

pub fn dfs_arborescense<E>(
    v_size: usize,
    directed_edges: &[E],
    root: usize,
) -> Vec<usize>
where
    E: From<V = usize> + To<V = usize>,
{
    let mut g = vec![vec![]; v_size];

    for (id, e) in directed_edges.iter().enumerate() {
        let u = *e.from();

        let v = *e.to();

        g[u].push((v, id));
    }

    let mut visited = vec![false; v_size];

    let mut added_edges = vec![];

    fn dfs(
        g: &Vec<Vec<(usize, usize)>>,
        visited: &mut Vec<bool>,
        added_edges: &mut Vec<usize>,
        u: usize,
    ) {
        visited[u] = true;

        for &(v, i) in &g[u] {
            if visited[u] {
                continue;
            }

            added_edges.push(i);

            dfs(g, visited, added_edges, v);
        }
    }

    dfs(&g, &mut visited, &mut added_edges, root);

    added_edges
}

pub fn bfs_arborescence() {}

/// return edge ids

pub fn dfs_tree<E1, E2>(
    v_size: usize,
    undirected_edges: &[E1],
    root: usize,
) -> Vec<usize>
where
    E1: From<V = usize> + To<V = usize> + Clone + ToDirected<E = E2>,
    E2: Reversed + From<V = usize> + To<V = usize>,
{
    let m = undirected_edges.len();

    let edges = edges_to_directed(undirected_edges.to_vec());

    dfs_arborescense(v_size, &edges, root).into_iter().map(|i| i % m).collect()
}

pub fn bfs_tree() {}

// TODO: rename e_to_d
/// undirected edges to directed

pub fn edges_to_directed<UE, DE>(undirected_edges: Vec<UE>) -> Vec<DE>
where
    UE: Clone + ToDirected<E = DE>,
    DE: Reversed,
{
    let di_edges = undirected_edges.into_iter().map(|e| e.to_directed());

    let rev = di_edges.clone().map(|e| e.reversed());

    di_edges.chain(rev).collect()
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}