algods 0.1.0

A collection of data structures 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

#[cfg(test)]
mod unit_test;
use crate::graph::VertexInfo;
use std::collections::HashSet;

pub struct UndirectedGraph {
    // implements an adjacency-list graph
    // where vertices have indices 0, ..., nb_objects
    // and each vertex is associated to its adjacent vertices
    data: Vec<HashSet<usize>>,
    nb_edges: usize,
    nb_vertices: usize,
}
impl Default for UndirectedGraph {
    fn default() -> Self {
        Self::new()
    }
}
impl UndirectedGraph {
    pub fn new() -> Self {
        Self {
            data: Vec::new(),
            nb_edges: 0,
            nb_vertices: 0,
        }
    }

    pub fn init(nb_objects: usize) -> Self {
        let mut graph = Self::new();
        graph.nb_vertices = nb_objects;
        graph.data = Vec::with_capacity(nb_objects);
        for _ in 0..nb_objects {
            graph.data.push(HashSet::<usize>::new());
        }
        graph
    }

    pub fn nb_edges(&self) -> usize {
        // run time complexity O(1)
        self.nb_edges
    }
    pub fn nb_vertices(&self) -> usize {
        // run time complexity O(1)
        self.nb_vertices
    }
    fn vertex_edges(&self, v: &usize) -> &HashSet<usize> {
        // gets all the vertices linked to a given vertex v,
        // that is the adjacent vertices of v
        // run time complexity O(1)
        &self.data[*v]
    }
    pub fn add_edge(&mut self, v: usize, w: usize) {
        // adds an edge to the graph
        // run time complexity O(1)
        assert!(self.nb_vertices >= std::cmp::max(v, w));
        let w_is_in: bool = self.data[v].insert(w);
        let v_is_in: bool = self.data[w].insert(v);
        if v_is_in && w_is_in {
            // v <--> w is a new undirected edge
            self.nb_edges += 1;
        }
    }
    pub fn add_vertex(&mut self) {
        self.data.push(HashSet::<usize>::new());
        self.nb_vertices += 1;
    }

    pub fn degree(&self, v: &usize) -> usize {
        self.vertex_edges(v).len()
    }

    pub fn average_degree(&self) -> usize {
        // gets the average number of degree of the graph
        // each edge is counted only once (by the self.add_edge() method)
        if self.nb_vertices > 0 {
            self.nb_edges / self.nb_vertices
        } else {
            panic!("No vertex in the graph");
        }
    }

    pub fn self_loop_number(&self) -> usize {
        self.data
            .iter()
            .enumerate()
            .map(|(v, e)| usize::from(e.contains(&v)))
            .sum()
    }
}
impl VertexInfo for UndirectedGraph {
    fn vertex_edges(&self, v: &usize) -> Vec<&usize> {
        // gets all the vertices linked to a given vertex v,
        // that is the adjacent vertices of v
        // run time complexity O(1)
        self.data[*v].iter().collect::<Vec<&usize>>()
    }
    fn nb_vertices(&self) -> usize {
        // run time complexity O(1)
        self.nb_vertices
    }
}