| 69 | } |
| 70 | |
| 71 | fn random_traversal<D>( |
| 72 | length: usize, |
| 73 | remove_after_traverse: bool, |
| 74 | graph: &mut GeometryGraph<D>, |
| 75 | rng: &mut StdRng, |
| 76 | ) -> Option<LineString> |
| 77 | where |
| 78 | D: EdgeType, |
| 79 | { |
| 80 | if graph.edge_count() == 0 { |
| 81 | tracing::warn!("Graph has no edges. Can't do a traversal"); |
| 82 | return None; |
| 83 | } |
| 84 | |
| 85 | let mut result = Vec::<Point>::with_capacity(length); |
| 86 | |
| 87 | // Pick a random starting point |
| 88 | let node_dist = Uniform::new(0, graph.node_count()).unwrap(); |
| 89 | let mut start_index = node_dist.sample(rng).into(); |
| 90 | |
| 91 | let point = graph[start_index]; |
| 92 | result.push(point); |
| 93 | |
| 94 | let mut buffer = Vec::new(); |
| 95 | for _ in 0..length { |
| 96 | let neighbors = graph.neighbors(start_index); |
| 97 | buffer.clear(); |
| 98 | buffer.extend(neighbors); // use extend to avoid repeated alloc/free on every loop |
| 99 | |
| 100 | // Pick the next node to visit |
| 101 | let next_index = match buffer.len().cmp(&1) { |
| 102 | Ordering::Greater => { |
| 103 | let dist = Uniform::new(0, buffer.len()).unwrap(); |
| 104 | let next_index = dist.sample(rng); |
| 105 | buffer[next_index] |
| 106 | } |
| 107 | Ordering::Equal => buffer[0], |
| 108 | Ordering::Less => break, |
| 109 | }; |
| 110 | let point = graph[next_index]; |
| 111 | result.push(point); |
| 112 | |
| 113 | // Remove the traversed edge |
| 114 | if remove_after_traverse { |
| 115 | let traversed_edge = graph.find_edge(start_index, next_index).unwrap(); |
| 116 | graph.remove_edge(traversed_edge); |
| 117 | |
| 118 | // If removing the traversed edge left behind orphan nodes, remove them too. |
| 119 | if buffer.len() < 2 { |
| 120 | graph.remove_node(start_index); |
| 121 | } |
| 122 | } |
| 123 | let neighbors = graph.neighbors(next_index).count(); |
| 124 | if neighbors < 2 { |
| 125 | if remove_after_traverse { |
| 126 | graph.remove_node(next_index); |
| 127 | } |
| 128 | tracing::debug!("Hit the end of a connected component - nowhere to go!"); |