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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

mod first_search;
mod shortest_path;
#[cfg(test)]
mod unit_test;
use crate::graph::{EdgeWeightedDigraph, VertexInfo, Weight};
pub use first_search::{bfs, dfs};
pub use shortest_path::{bellman_ford, dijkstra, shortest_path_ewdag};
use std::marker::PhantomData;

pub struct DepthFirstSearch<G> {
    // Indicates whether or not a vertex w in the graph is visited
    marked: Vec<bool>,
    // Indicates what is the previous vertex leading to the current vertex
    // when edge_to[w]=w, then no path is found yet from v to w
    edge_to: Vec<usize>,
    // vertex for which paths are computed
    v: usize,
    // type of the graph
    graph_type: PhantomData<G>,
}
impl<G: VertexInfo> DepthFirstSearch<G> {
    pub fn init(nb_vertices: usize, origin: usize) -> Self {
        Self {
            marked: vec![false; nb_vertices],
            edge_to: (0..nb_vertices).collect::<Vec<usize>>(),
            v: origin,
            graph_type: PhantomData,
        }
    }

    pub fn find_paths(&mut self, graph: &G) {
        // finds all paths from self.v in self.graph
        dfs(
            graph,
            &mut self.marked,
            &mut self.edge_to,
            self.v,
            self.v,
            true,
            false,
        );
    }

    pub fn path_to(&self, w: usize) -> Option<Vec<usize>> {
        // finds the path from v to w
        // run time complexity O(length of the path)
        // can be very time consuming for some applications

        if !self.marked[w] {
            return None;
        }
        let mut path = Vec::<usize>::new();
        let mut x = w;
        while x != self.v {
            path.push(x);
            x = self.edge_to[x];
        }
        path.push(self.v);
        Some(path)
    }
}

pub struct BreadthFirstSearch<G> {
    // Indicates wether or not a vertex w in the graph is visited
    marked: Vec<bool>,
    // Indicates what is the previous vertex leading to the current vertex
    // when edge_to[w]=w, then no path is found yet from v to w
    edge_to: Vec<usize>,
    // Vertex for which paths are computed
    v: usize,
    // type of the graph
    graph_type: PhantomData<G>,
}
impl<G: VertexInfo> BreadthFirstSearch<G> {
    pub fn init(nb_vertices: usize, origin: usize) -> Self {
        Self {
            marked: vec![false; nb_vertices],
            edge_to: (0..nb_vertices).collect::<Vec<usize>>(),
            v: origin,
            graph_type: PhantomData,
        }
    }

    pub fn find_paths(&mut self, graph: &G) {
        // finds all reachable vertices from w
        bfs(graph, &mut self.marked, &mut self.edge_to, self.v);
    }

    pub fn path_to(&self, w: usize) -> Option<Vec<usize>> {
        // finds the path from v to w
        // run time complexity O(length of the path)
        // computes shortest paths
        if !self.marked[w] {
            return None;
        }
        let mut path = Vec::<usize>::new();
        let mut x = w;
        while x != self.v {
            path.push(x);
            x = self.edge_to[x];
        }
        path.push(self.v);
        Some(path)
    }
}

pub enum ShortestPathAlgo {
    Dijkstra,
    SpDag,
    BellmanFord,
}
impl Default for ShortestPathAlgo {
    fn default() -> Self {
        Self::Dijkstra
    }
}
pub struct ShortestPath<T> {
    // the source vertex from where the shortest
    // paths are computed
    source: usize,
    // the algorithm used to compute the shortest paths
    algo: ShortestPathAlgo,
    // stores the length of the shortest path from
    // the source to an edge
    dist_to: Vec<T>,
    // stores the vertex that is the closest
    // to an edge in the shortest path
    edge_to: Vec<usize>,
}
impl<T: Weight + Clone + std::hash::Hash> ShortestPath<T> {
    pub fn init(from: usize, algorithm: ShortestPathAlgo, nb_vertices: usize) -> Self {
        Self {
            source: from,
            algo: algorithm,
            dist_to: vec![Weight::max(); nb_vertices],
            edge_to: vec![usize::MAX; nb_vertices],
        }
    }
}

impl<T> ShortestPath<T> {
    pub fn dist_to(&self, v: usize) -> &T {
        &self.dist_to[v]
    }
    pub fn edge_to(&self, v: usize) -> usize {
        self.edge_to[v]
    }
}
impl<T: Eq + Weight> ShortestPath<T> {
    pub fn path_to(&self, v: usize) -> Option<Vec<usize>> {
        if self.dist_to[v] == Weight::max() {
            return None;
        }
        let mut path = Vec::new();
        let mut origin = v;
        while origin != self.source {
            path.push(origin);
            origin = self.edge_to[origin];
        }
        path.push(self.source);
        Some(path)
    }
}

impl<T: Ord + Weight + std::ops::Add<Output = T> + std::hash::Hash> ShortestPath<T> {
    pub fn find_paths(&mut self, graph: &EdgeWeightedDigraph<T>) {
        match self.algo {
            ShortestPathAlgo::Dijkstra => {
                dijkstra(graph, self.source, &mut self.edge_to, &mut self.dist_to);
            }
            ShortestPathAlgo::SpDag => {
                shortest_path_ewdag(graph, self.source, &mut self.edge_to, &mut self.dist_to);
            }
            ShortestPathAlgo::BellmanFord => {
                bellman_ford(graph, self.source, &mut self.edge_to, &mut self.dist_to);
            }
        }
    }
}