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

use crate::graph::VertexInfo;
use std::collections::LinkedList;

/// Function that runs the depth-first search algorithm
pub fn dfs<G>(
    graph: &G,
    marked: &mut [bool],
    edge_to: &mut Vec<usize>,
    origin: usize,
    component: usize,
    mut_edge_to: bool, // indicates whether or not not mutate edge_to
    is_component: bool, // indicates whether or not to dfs is launched
                       // for connected component-like algorithms
) where
    G: VertexInfo,
{
    // finds all reachable vertices from origin and adds them to the connected component w
    // run time complexity O(sum of degrees of all reachable vertices from origin)
    assert!(VertexInfo::nb_vertices(graph) >= std::cmp::max(origin, component));
    // mark vertex w as visited
    marked[origin] = true;

    // define how to mutate the edge_to list
    let source = if is_component { component } else { origin };
    // recursively visit all unmarked adjacent vertices to w
    let adjacent_vertices = graph.vertex_edges(&origin);
    if mut_edge_to {
        for u in adjacent_vertices {
            if !marked[*u] {
                dfs(
                    graph,
                    marked,
                    edge_to,
                    *u,
                    component,
                    mut_edge_to,
                    is_component,
                );
                edge_to[*u] = source;
            }
        }
    } else {
        for u in adjacent_vertices {
            if !marked[*u] {
                dfs(
                    graph,
                    marked,
                    edge_to,
                    *u,
                    component,
                    mut_edge_to,
                    is_component,
                );
            }
        }
        edge_to.push(origin);
    }
}

/// Function that runs the breadth-first search algorithm
pub fn bfs<G>(graph: &G, marked: &mut [bool], edge_to: &mut [usize], w: usize)
where
    G: VertexInfo,
{
    assert!(VertexInfo::nb_vertices(graph) >= w);
    let mut queue = LinkedList::<usize>::new();
    // mark the vertex w as visited and add it to the queue
    queue.push_back(w);
    marked[w] = true;

    while let Some(x) = queue.pop_front() {
        // remove the first vertex in the queue
        // add to the queue all unmarked vertices adjacent to v and mark them
        let adj_x = graph.vertex_edges(&x);
        for u in adj_x {
            if !marked[*u] {
                queue.push_back(*u);
                marked[*u] = true;
                edge_to[*u] = x;
            }
        }
    }
}