algods/graph/processing/search/
first_search.rs

1use crate::graph::VertexInfo;
2use std::collections::LinkedList;
3
4/// Function that runs the depth-first search algorithm
5pub fn dfs<G>(
6    graph: &G,
7    marked: &mut [bool],
8    edge_to: &mut Vec<usize>,
9    origin: usize,
10    component: usize,
11    mut_edge_to: bool, // indicates whether or not not mutate edge_to
12    is_component: bool, // indicates whether or not to dfs is launched
13                       // for connected component-like algorithms
14) where
15    G: VertexInfo,
16{
17    // finds all reachable vertices from origin and adds them to the connected component w
18    // run time complexity O(sum of degrees of all reachable vertices from origin)
19    assert!(VertexInfo::nb_vertices(graph) >= std::cmp::max(origin, component));
20    // mark vertex w as visited
21    marked[origin] = true;
22
23    // define how to mutate the edge_to list
24    let source = if is_component { component } else { origin };
25    // recursively visit all unmarked adjacent vertices to w
26    let adjacent_vertices = graph.vertex_edges(&origin);
27    if mut_edge_to {
28        for u in adjacent_vertices {
29            if !marked[*u] {
30                dfs(
31                    graph,
32                    marked,
33                    edge_to,
34                    *u,
35                    component,
36                    mut_edge_to,
37                    is_component,
38                );
39                edge_to[*u] = source;
40            }
41        }
42    } else {
43        for u in adjacent_vertices {
44            if !marked[*u] {
45                dfs(
46                    graph,
47                    marked,
48                    edge_to,
49                    *u,
50                    component,
51                    mut_edge_to,
52                    is_component,
53                );
54            }
55        }
56        edge_to.push(origin);
57    }
58}
59
60/// Function that runs the breadth-first search algorithm
61pub fn bfs<G>(graph: &G, marked: &mut [bool], edge_to: &mut [usize], w: usize)
62where
63    G: VertexInfo,
64{
65    assert!(VertexInfo::nb_vertices(graph) >= w);
66    let mut queue = LinkedList::<usize>::new();
67    // mark the vertex w as visited and add it to the queue
68    queue.push_back(w);
69    marked[w] = true;
70
71    while let Some(x) = queue.pop_front() {
72        // remove the first vertex in the queue
73        // add to the queue all unmarked vertices adjacent to v and mark them
74        let adj_x = graph.vertex_edges(&x);
75        for u in adj_x {
76            if !marked[*u] {
77                queue.push_back(*u);
78                marked[*u] = true;
79                edge_to[*u] = x;
80            }
81        }
82    }
83}
algods/graph/processing/search/first_search.rs

algods/graph/processing/search/
first_search.rs
