grafos_tools/algorithms/
breadth_first_search.rs

1use crate::{adjacency_list::ToAdjacencyList, Edge, Graph, Vertice};
2use std::{collections::HashSet, fmt::Debug, hash::Hash};
3
4use super::AlgorithmResult;
5
6#[derive(Debug)]
7pub enum BreadthFirstSearchError {
8    FromVerticeNotInGraph,
9    ToVerticeNotInGraph,
10}
11
12pub fn breadth_first_search_queue<G, T, E>(
13    graph: &G,
14    from: &Vertice<T>,
15    to: &Vertice<T>,
16) -> Result<AlgorithmResult<T>, BreadthFirstSearchError>
17where
18    T: PartialOrd + Debug + Clone + Eq + Hash,
19    G: Graph<T, E> + ToAdjacencyList<T>,
20    E: Edge<T>,
21{
22    use super::BreadthFirstSearchError::*;
23
24    let adjacency_list = graph.to_adjacency_list();
25
26    // If doesn't contain from or to, error
27    if !graph.vertices().contains(&from) {
28        return Err(FromVerticeNotInGraph);
29    }
30    if !graph.vertices().contains(&to) {
31        return Err(ToVerticeNotInGraph);
32    }
33
34    // Due to the way this algorithm works,
35    // we need to iterate over a mutable
36    // array, thus we have to use a `while`
37    // loop.
38
39    // Here, I use a vector because this
40    // is an ordered list
41
42    // Create a Queue
43    // where
44    //  queue:        graph:
45    //  |A|            A - C ⌍
46    //  |C|            | / | E
47    //  |B|            B - D ⌏
48    //  |D|
49    //  |E|
50    //
51    // Queue may vary depending on the order
52    // the graph is read
53
54    let mut queue: Vec<Vertice<T>> = Vec::with_capacity(adjacency_list.0.len());
55    queue.push(from.clone());
56    let mut current_index = 0;
57
58    // queue builder
59    while current_index < adjacency_list.0.len() {
60        // get current vertice from queue
61        let current_vertice = queue
62            .get(current_index)
63            .expect("Vertice not in queue somehow");
64
65        // check if vertice match the destination
66        if *current_vertice == *to {
67            break; // return the queue
68        }
69
70        // add neighbours to the queue
71        for neighbor in adjacency_list
72            .0
73            .get(current_vertice)
74            .expect("Vertice not in adjacency list somehow")
75        {
76            queue.push(neighbor.clone());
77            // check if neighbor is destination
78            if *neighbor == *to {
79                break;
80            }
81        }
82
83        current_index += 1;
84    }
85
86    // Now we have to analyze the queue
87
88    // For this, we have to find the neighbor
89    // of the last element who is the closest
90    // to the starting node `vec[0]`
91    // Then again and again, and so on. Until
92    // we get to the very first element (the zeroth?)
93
94    let mut last_vertice_in_path = queue
95        .last()
96        .expect("Not last element in queue found")
97        .clone();
98    let mut path: Vec<Vertice<T>> = vec![];
99    let mut current_nearest = last_vertice_in_path.clone();
100
101    // rev() stands for reverse
102    for current_vertice in queue.iter().rev() {
103        let is_neighbour_of_last =
104            adjacency_list.check_neighbor_for(&last_vertice_in_path, current_vertice);
105        println!("{:?} is now current nearest", current_vertice);
106
107        if current_vertice == to || current_vertice == from {
108            path.insert(0, current_vertice.clone());
109        } else if is_neighbour_of_last {
110            current_nearest = current_vertice.clone();
111        } else {
112            path.push(current_vertice.clone());
113            last_vertice_in_path = current_nearest.clone()
114        }
115    }
116
117    let mut visited = HashSet::new();
118    queue.iter().for_each(|vertice| {
119        visited.insert(vertice.clone());
120    });
121
122    Ok(AlgorithmResult { path, visited })
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128    use crate::simple_graph;
129
130    #[test]
131    fn check_two_vertice_simple_graph_path() {
132        let graph = simple_graph::SimpleGraph::new_two();
133
134        let vertices: Vec<&Vertice<usize>> = graph.vertices().iter().collect();
135
136        let from = *vertices.first().unwrap();
137        let to = *vertices.last().unwrap();
138
139        let result = breadth_first_search_queue(&graph, from, to).unwrap();
140
141        println!("from: {from:?} | to {to:?} | result {result:?}");
142
143        assert_eq!(result.path.len(), 2);
144        assert_eq!(result.visited.len(), 2);
145    }
146}
grafos_tools/algorithms/breadth_first_search.rs

grafos_tools/algorithms/
breadth_first_search.rs
