bambam_osm/algorithm/
search.rs

1use crate::model::osm::{
2    graph::{OsmGraph, OsmNodeId},
3    OsmError,
4};
5use itertools::Itertools;
6use std::collections::{HashSet, LinkedList};
7
8/// finds the set of indices that are part of the same geometry cluster
9/// using a breadth-first search over an undirected graph of geometry
10/// intersection relations.
11///
12/// # Arguments
13///
14/// * `src` - origin of tree
15/// * `graph` - graph to search
16/// * `valid_set` - set of valid nodes to visit, or None if all are acceptable.
17///
18/// # Returns
19///
20/// The set of node ids connected by the minimum spanning tree within the valid_set.
21pub fn bfs_undirected(
22    src: OsmNodeId,
23    graph: &OsmGraph,
24    valid_set: Option<&HashSet<OsmNodeId>>,
25) -> Result<HashSet<OsmNodeId>, OsmError> {
26    // initial search state. if a NodeOsmid has been visited, it is appended
27    // to the visited set.
28    // breadth-first search is modeled here with a linked list FIFO queue.
29    let mut visited: HashSet<OsmNodeId> = HashSet::new();
30    let mut frontier: LinkedList<OsmNodeId> = LinkedList::new();
31    frontier.push_back(src);
32
33    while let Some(next_id) = frontier.pop_front() {
34        // add to the search tree
35        visited.insert(next_id);
36
37        // expand the frontier
38        let next_out = graph.get_out_neighbors(&next_id).unwrap_or_default();
39        let next_in = graph.get_in_neighbors(&next_id).unwrap_or_default();
40
41        // neighbors are only reviewed here that are "valid" (all fall within the spatial cluster).
42        // they are sorted for algorithmic determinism (frontier insertion order).
43        let valid_neighbors = next_in
44            .union(&next_out)
45            .filter(|n| match &valid_set {
46                Some(valid) => valid.contains(*n),
47                None => true,
48            })
49            .sorted();
50        for neighbor in valid_neighbors {
51            if !visited.contains(neighbor) {
52                // frontier.push(Reverse((next_depth + 1, *neighbor))); // min heap
53                frontier.push_back(*neighbor); // min heap
54            }
55        }
56    }
57
58    Ok(visited)
59}
bambam_osm/algorithm/search.rs

bambam_osm/algorithm/
search.rs
