routee_compass_core/model/network/
graph.rs

1use super::{Edge, EdgeId, EdgeList, NetworkError, Vertex, VertexId};
2use crate::algorithm::search::Direction;
3use crate::model::network::EdgeListId;
4use crate::model::network::GraphConfig;
5use crate::util::fs::read_utils;
6use indexmap::IndexMap;
7use itertools::Itertools;
8use kdam::tqdm;
9use kdam::Bar;
10
11/// Road network topology represented as an adjacency list.
12/// The `EdgeId` and `VertexId` values correspond to edge and
13/// vertex indices in the `edges` and `vertices` vectors.
14///
15/// # Arguments
16///
17/// * `adj` - the forward-oriented adjacency list
18/// * `rev` - the reverse-oriented adjacency list
19/// * `edges` - for each `EdgeId`, the corresponding `Edge` record
20/// * `vertices` - for each `VertexId`, the corresponding `Vertex` record
21///
22/// # Performance
23///
24/// Methods provided via the `Graph` type prefer avoiding copies.
25/// Operations on a single entity should be _O(1)_. Most methods returning
26/// collections will prefer chained iterators. A few will collect
27/// into Vecs because of error handling or lifetimes, but those cases will only produce a
28/// smaller subset of the source data.
29#[derive(Debug)]
30pub struct Graph {
31    pub vertices: Box<[Vertex]>,
32    pub edge_lists: Vec<EdgeList>,
33    pub adj: DenseAdjacencyList,
34    pub rev: DenseAdjacencyList,
35}
36
37/// a graph adjacency list with an entry (possibly empty) for each VertexId in the Graph.
38pub type DenseAdjacencyList = Box<[IndexMap<(EdgeListId, EdgeId), VertexId>]>;
39
40impl TryFrom<&GraphConfig> for Graph {
41    type Error = NetworkError;
42
43    /// create a graph from a JSON argument. it should be an object that contains
44    /// two keys, one for each file path.
45    fn try_from(config: &GraphConfig) -> Result<Self, Self::Error> {
46        let vertices: Box<[Vertex]> = read_utils::from_csv(
47            &config.vertex_list_input_file,
48            true,
49            Some(Bar::builder().desc(format!("graph vertices: {}", config.vertex_list_input_file))),
50            None,
51        )
52        .map_err(|e| NetworkError::CsvError { source: e })?;
53
54        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
55            vec![IndexMap::new(); vertices.len()];
56        let mut rev: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
57            vec![IndexMap::new(); vertices.len()];
58
59        // this callback is invoked when reading each line of the edge list input file and
60        // inserts the adjacency information of the edge (src)-[edge]->(dst).
61
62        let edge_lists = config
63            .edge_list
64            .iter()
65            .enumerate()
66            .map(|(idx, c)| EdgeList::new(&c.input_file, EdgeListId(idx)))
67            .collect::<Result<Vec<_>, _>>()?;
68
69        let total_edges = edge_lists.iter().map(|el| el.len()).sum::<usize>();
70        log::info!(
71            "loaded {} edge lists with a total of {} edges",
72            edge_lists.len(),
73            total_edges
74        );
75
76        let build_adjacencies_iter = tqdm!(
77            edge_lists.iter().flat_map(|el| el.edges()),
78            desc = "building adjacencies",
79            total = total_edges
80        );
81        let mut bad_refs: Vec<String> = vec![];
82        for edge in build_adjacencies_iter {
83            if let Err(e) = append_to_adjacency(edge, &mut adj, true) {
84                bad_refs.push(e);
85            }
86            if let Err(e) = append_to_adjacency(edge, &mut rev, false) {
87                bad_refs.push(e);
88            }
89        }
90
91        if !bad_refs.is_empty() {
92            let msg = format!("[{}]", bad_refs.iter().take(5).join("\n  "));
93            return Err(NetworkError::DatasetError(format!(
94                "invalid edge lists for vertex set. (up to) first five errors:\n  {msg}"
95            )));
96        }
97
98        let graph = Graph {
99            edge_lists,
100            vertices,
101            adj: adj.into_boxed_slice(),
102            rev: rev.into_boxed_slice(),
103        };
104
105        Ok(graph)
106    }
107}
108
109impl Graph {
110    /// access a specific EdgeList by its id
111    pub fn get_edge_list(&self, edge_list_id: &EdgeListId) -> Result<&EdgeList, NetworkError> {
112        self.edge_lists
113            .get(edge_list_id.0)
114            .ok_or(NetworkError::EdgeListNotFound(*edge_list_id))
115    }
116
117    pub fn n_edge_lists(&self) -> usize {
118        self.edge_lists.len()
119    }
120
121    /// number of edges in the Graph, not to be conflated with the list of edge ids
122    pub fn n_edges(&self) -> usize {
123        self.edge_lists.iter().map(|el| el.len()).sum::<usize>()
124    }
125
126    /// number of vertices in the Graph
127    pub fn n_vertices(&self) -> usize {
128        self.vertices.len()
129    }
130
131    /// helper function for creating a range of all edge ids in the graph.
132    /// uses the knowledge that all ids are unique and consecutive integers
133    /// beginning at zero.
134    pub fn edge_ids(
135        &self,
136        edge_list_id: &EdgeListId,
137    ) -> Result<Box<dyn Iterator<Item = EdgeId>>, NetworkError> {
138        self.get_edge_list(edge_list_id).map(|e| {
139            let iter: Box<dyn Iterator<Item = EdgeId>> = Box::new((0..e.len()).map(EdgeId));
140            iter
141        })
142    }
143
144    /// helper function for creating a range of all vertex ids in the graph.
145    /// uses the knowledge that all ids are unique and consecutive integers
146    /// beginning at zero.
147    pub fn vertex_ids(&self) -> Box<dyn Iterator<Item = VertexId>> {
148        let range = (0..self.n_vertices()).map(VertexId);
149        Box::new(range)
150    }
151
152    /// iterates through all edges in the graph
153    pub fn edges<'a>(&'a self) -> Box<dyn Iterator<Item = &'a Edge> + 'a> {
154        Box::new(self.edge_lists.iter().flat_map(|el| el.edges()))
155    }
156
157    /// retrieve an `Edge` record from the graph
158    ///
159    /// # Arguments
160    ///
161    /// * `edge_id` - the `EdgeId` for the `Edge` that we want to retrieve
162    ///
163    /// # Returns
164    ///
165    /// The associated `Edge` or an error if the id is missing
166    pub fn get_edge(
167        &self,
168        edge_list_id: &EdgeListId,
169        edge_id: &EdgeId,
170    ) -> Result<&Edge, NetworkError> {
171        match self.edge_lists.get(edge_list_id.0) {
172            None => Err(NetworkError::InternalError(format!(
173                "EdgeListId not found: {edge_list_id}"
174            ))),
175            Some(edge_list) => match edge_list.get(edge_id) {
176                None => Err(NetworkError::EdgeNotFound(*edge_id)),
177                Some(edge) => Ok(edge),
178            },
179        }
180    }
181
182    /// retrieve a `Vertex` record from the graph
183    ///
184    /// # Arguments
185    ///
186    /// * `vertex_id` - the `VertexId` for the `Vertex` that we want to retrieve
187    ///
188    /// # Returns
189    ///
190    /// The associated `Vertex` or an error if the id is missing
191    pub fn get_vertex(&self, vertex_id: &VertexId) -> Result<&Vertex, NetworkError> {
192        match self.vertices.get(vertex_id.0) {
193            None => Err(NetworkError::VertexNotFound(*vertex_id)),
194            Some(vertex) => Ok(vertex),
195        }
196    }
197
198    /// retrieve a list of `EdgeId`s for edges that depart from the given `VertexId`
199    ///
200    /// # Arguments
201    ///
202    /// * `src` - the `VertexId` for the source vertex of edges
203    ///
204    /// # Returns
205    ///
206    /// A list of `EdgeIds` for outbound edges that leave this `VertexId`, or an error
207    /// if the vertex is missing from the Graph adjacency matrix.
208    pub fn out_edges(&self, src: &VertexId) -> Vec<(EdgeListId, EdgeId)> {
209        self.out_edges_iter(src).cloned().collect_vec()
210    }
211
212    /// builds an iterator
213    pub fn out_edges_iter<'a>(
214        &'a self,
215        src: &'a VertexId,
216    ) -> Box<dyn Iterator<Item = &'a (EdgeListId, EdgeId)> + 'a> {
217        match self.adj.get(src.0) {
218            Some(out_map) => Box::new(out_map.keys()),
219            None => Box::new(std::iter::empty()),
220        }
221    }
222
223    /// retrieve a list of `EdgeId`s for edges that arrive at the given `VertexId`
224    ///
225    /// # Arguments
226    ///
227    /// * `dst` - the `VertexId` for the destination vertex of edges
228    ///
229    /// # Returns
230    ///
231    /// A list of `EdgeIds` for inbound edges that arrive at this `VertexId`, or an error
232    /// if the vertex is missing from the Graph adjacency matrix.
233    pub fn in_edges(&self, dst: &VertexId) -> Vec<(EdgeListId, EdgeId)> {
234        self.in_edges_iter(dst).cloned().collect_vec()
235    }
236
237    pub fn in_edges_iter<'a>(
238        &'a self,
239        src: &'a VertexId,
240    ) -> Box<dyn Iterator<Item = &'a (EdgeListId, EdgeId)> + 'a> {
241        match self.rev.get(src.0) {
242            Some(in_map) => Box::new(in_map.keys()),
243            None => Box::new(std::iter::empty()),
244        }
245    }
246
247    /// retrieve the source vertex id of an edge
248    ///
249    /// # Arguments
250    ///
251    /// * `edge_id` - the edge to find a source vertex id
252    ///
253    /// # Returns
254    ///
255    /// The source `VertexId` of an `Edge` or an error if the edge is missing
256    pub fn src_vertex_id(
257        &self,
258        edge_list_id: &EdgeListId,
259        edge_id: &EdgeId,
260    ) -> Result<VertexId, NetworkError> {
261        self.get_edge(edge_list_id, edge_id)
262            .map(|e| e.src_vertex_id)
263    }
264
265    /// retrieve the destination vertex id of an edge
266    ///
267    /// # Arguments
268    ///
269    /// * `edge_id` - the edge to find a destination vertex id
270    ///
271    /// # Returns
272    ///
273    /// The destination `VertexId` of an `Edge` or an error if the edge is missing
274    pub fn dst_vertex_id(
275        &self,
276        edge_list_id: &EdgeListId,
277        edge_id: &EdgeId,
278    ) -> Result<VertexId, NetworkError> {
279        self.get_edge(edge_list_id, edge_id)
280            .map(|e| e.dst_vertex_id)
281    }
282
283    /// helper function to give incident edges to a vertex based on a
284    /// traversal direction.
285    ///
286    /// # Arguments
287    ///
288    /// * `vertex_id` - vertex to find edges which connect to it
289    /// * `direction` - whether to find out edges (Forward) or in edges (Reverse)
290    ///
291    /// # Returns
292    ///
293    /// The incident `EdgeId`s or an error if the vertex is not connected.
294    pub fn incident_edges(
295        &self,
296        vertex_id: &VertexId,
297        direction: &Direction,
298    ) -> Vec<(EdgeListId, EdgeId)> {
299        match direction {
300            Direction::Forward => self.out_edges(vertex_id),
301            Direction::Reverse => self.in_edges(vertex_id),
302        }
303    }
304
305    /// helper function to give incident edges to a vertex based on a
306    /// traversal direction.
307    ///
308    /// # Arguments
309    ///
310    /// * `vertex_id` - vertex to find edges which connect to it
311    /// * `direction` - whether to find out edges (Forward) or in edges (Reverse)
312    ///
313    /// # Returns
314    ///
315    /// The incident `EdgeId`s or an error if the vertex is not connected.
316    pub fn incident_edges_iter<'a>(
317        &'a self,
318        vertex_id: &'a VertexId,
319        direction: &Direction,
320    ) -> Box<dyn Iterator<Item = &'a (EdgeListId, EdgeId)> + 'a> {
321        match direction {
322            Direction::Forward => self.out_edges_iter(vertex_id),
323            Direction::Reverse => self.in_edges_iter(vertex_id),
324        }
325    }
326
327    /// helper function to give the incident vertex to an edge based on a
328    /// traversal direction.
329    ///
330    /// # Arguments
331    ///
332    /// * `edge_id` - edge to find the vertex which connects to it
333    /// * `direction` - whether to find the destination (Forward) or source (Reverse) vertex
334    ///
335    /// # Returns
336    ///
337    /// The incident `VertexId` of an edge or an error if the edge is missing
338    pub fn incident_vertex(
339        &self,
340        edge_list_id: &EdgeListId,
341        edge_id: &EdgeId,
342        direction: &Direction,
343    ) -> Result<VertexId, NetworkError> {
344        match direction {
345            Direction::Forward => self.dst_vertex_id(edge_list_id, edge_id),
346            Direction::Reverse => self.src_vertex_id(edge_list_id, edge_id),
347        }
348    }
349
350    /// retrieve the triplet of `Vertex` -> `Edge` -> `Vertex` for some `EdgeId`
351    ///
352    /// # Arguments
353    ///
354    /// * `edge_id` - the id of the edge to collect attributes for
355    ///
356    /// # returns
357    ///
358    /// The triplet of attributes surrounding one `Edge` or an error if
359    /// any id is invalid.
360    pub fn edge_triplet(
361        &self,
362        edge_list_id: &EdgeListId,
363        edge_id: &EdgeId,
364    ) -> Result<(&Vertex, &Edge, &Vertex), NetworkError> {
365        let edge = self.get_edge(edge_list_id, edge_id)?;
366        let src = self.get_vertex(&edge.src_vertex_id)?;
367        let dst = self.get_vertex(&edge.dst_vertex_id)?;
368
369        Ok((src, edge, dst))
370    }
371
372    /// creates `VertexId` -> `EdgeId` -> `VertexId` triplets based on
373    /// a `VertexId` and a traversal `Direction`.
374    ///
375    /// Regardless of the direction chosen, the source `VertexId` appears first and the
376    /// terminal `VertexId` appears in the third slot.
377    ///
378    /// # Arguments
379    ///
380    /// * `vertex_id` - id of the vertex to lookup incident triplets
381    /// * `direction` - direction to traverse to/from the `vertex_id`
382    ///
383    /// # Returns
384    ///
385    /// For each edge connected to this `vertex_id` traversable via the provided `direction`,
386    /// a triplet of the `EdgeId` and it's connecting `VertexId`s.
387    pub fn incident_triplet_ids(
388        &self,
389        vertex_id: &VertexId,
390        direction: &Direction,
391    ) -> Result<Vec<(VertexId, EdgeListId, EdgeId, VertexId)>, NetworkError> {
392        self.incident_edges_iter(vertex_id, direction)
393            .map(|(edge_list_id, edge_id)| {
394                let terminal_vid = self.incident_vertex(edge_list_id, edge_id, direction)?;
395                Ok((*vertex_id, *edge_list_id, *edge_id, terminal_vid))
396            })
397            .collect()
398    }
399
400    /// creates `Vertex` -> `Edge` -> `Vertex` triplets based on
401    /// a `Vertex` and a traversal `Direction`.
402    ///
403    /// Regardless of the direction chosen, the source `Vertex` appears first and the
404    /// terminal `Vertex` appears in the third slot.
405    ///
406    /// # Arguments
407    ///
408    /// * `vertex_id` - id of the vertex to lookup incident triplets
409    /// * `direction` - direction to traverse to/from the `vertex_id`
410    ///
411    /// # Returns
412    ///
413    /// For each edge connected to this `vertex_id` traversable via the provided `direction`,
414    /// a triplet of the `Edge` and it's connecting `Vertex`s.
415    pub fn incident_triplet_attributes(
416        &self,
417        vertex_id: &VertexId,
418        direction: &Direction,
419    ) -> Result<Vec<(&Vertex, &Edge, &Vertex)>, NetworkError> {
420        self.incident_triplet_ids(vertex_id, direction)?
421            .iter()
422            .map(|(src_id, edge_list_id, edge_id, dst_id)| {
423                let src = self.get_vertex(src_id)?;
424                let edge = self.get_edge(edge_list_id, edge_id)?;
425                let dst = self.get_vertex(dst_id)?;
426                Ok((src, edge, dst))
427            })
428            .collect()
429    }
430}
431
432/// Appends an edge to an adjacency list.
433///
434/// # Arguments
435///
436/// * `edge` - The edge to append to the adjacency list
437/// * `adj` - The adjacency list to modify
438/// * `forward` - If `true`, appends using the source vertex id (forward-oriented adjacency). If `false`, uses the destination vertex id (reverse-oriented adjacency).
439///
440/// # Returns
441///
442/// Returns `Ok(())` if the edge was successfully appended, or an error message if the
443/// required vertex is not found in the adjacency list.
444fn append_to_adjacency(
445    edge: &Edge,
446    adj: &mut [IndexMap<(EdgeListId, EdgeId), VertexId>],
447    forward: bool,
448) -> Result<(), String> {
449    let vertex_idx = if forward {
450        edge.src_vertex_id.0
451    } else {
452        edge.dst_vertex_id.0
453    };
454    match adj.get_mut(vertex_idx) {
455        None => {
456            let direction = if forward { "forward" } else { "reverse" };
457            Err(format!(
458                "vertex {} not found in {} adjacencies for edge list, edge: {}, {}",
459                vertex_idx, direction, edge.edge_list_id.0, edge.edge_id.0
460            ))
461        }
462        Some(out_links) => {
463            let target_vertex = if forward {
464                edge.dst_vertex_id
465            } else {
466                edge.src_vertex_id
467            };
468            out_links.insert((edge.edge_list_id, edge.edge_id), target_vertex);
469            Ok(())
470        }
471    }
472}
473
474#[cfg(test)]
475mod tests {
476    use super::*;
477    use uom::si::{f64::Length, length::meter};
478
479    fn create_test_edge(
480        edge_list_id: usize,
481        edge_id: usize,
482        src_vertex_id: usize,
483        dst_vertex_id: usize,
484    ) -> Edge {
485        Edge::new(
486            edge_list_id,
487            edge_id,
488            src_vertex_id,
489            dst_vertex_id,
490            Length::new::<meter>(1.0),
491        )
492    }
493
494    #[test]
495    fn test_append_to_adjacency_forward_success() {
496        // Create an adjacency list with 3 vertices
497        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
498            vec![IndexMap::new(), IndexMap::new(), IndexMap::new()];
499
500        // Create an edge from vertex 0 to vertex 2
501        let edge = create_test_edge(0, 0, 0, 2);
502
503        // Test forward adjacency (should use src_vertex_id = 0 as index)
504        let result = append_to_adjacency(&edge, &mut adj, true);
505
506        assert!(result.is_ok());
507
508        // Check that the edge was added to the correct adjacency list entry
509        let expected_key = (EdgeListId(0), EdgeId(0));
510        assert!(adj[0].contains_key(&expected_key));
511        assert_eq!(adj[0][&expected_key], VertexId(2)); // Target should be dst_vertex_id
512
513        // Other adjacency lists should remain empty
514        assert!(adj[1].is_empty());
515        assert!(adj[2].is_empty());
516    }
517
518    #[test]
519    fn test_append_to_adjacency_reverse_success() {
520        // Create an adjacency list with 3 vertices
521        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
522            vec![IndexMap::new(), IndexMap::new(), IndexMap::new()];
523
524        // Create an edge from vertex 0 to vertex 2
525        let edge = create_test_edge(0, 0, 0, 2);
526
527        // Test reverse adjacency (should use dst_vertex_id = 2 as index)
528        let result = append_to_adjacency(&edge, &mut adj, false);
529
530        assert!(result.is_ok());
531
532        // Check that the edge was added to the correct adjacency list entry
533        let expected_key = (EdgeListId(0), EdgeId(0));
534        assert!(adj[2].contains_key(&expected_key));
535        assert_eq!(adj[2][&expected_key], VertexId(0)); // Target should be src_vertex_id
536
537        // Other adjacency lists should remain empty
538        assert!(adj[0].is_empty());
539        assert!(adj[1].is_empty());
540    }
541
542    #[test]
543    fn test_append_to_adjacency_forward_invalid_vertex() {
544        // Create an adjacency list with only 2 vertices (indices 0 and 1)
545        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
546            vec![IndexMap::new(), IndexMap::new()];
547
548        // Create an edge with src_vertex_id = 3 (out of bounds)
549        let edge = create_test_edge(0, 5, 3, 1);
550
551        // Test forward adjacency - should fail because vertex 3 doesn't exist
552        let result = append_to_adjacency(&edge, &mut adj, true);
553
554        assert!(result.is_err());
555        let error_msg = result.unwrap_err();
556        assert!(error_msg.contains("vertex 3 not found in forward adjacencies"));
557        assert!(error_msg.contains("edge list, edge: 0, 5"));
558    }
559
560    #[test]
561    fn test_append_to_adjacency_reverse_invalid_vertex() {
562        // Create an adjacency list with only 2 vertices (indices 0 and 1)
563        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
564            vec![IndexMap::new(), IndexMap::new()];
565
566        // Create an edge with dst_vertex_id = 5 (out of bounds)
567        let edge = create_test_edge(1, 10, 0, 5);
568
569        // Test reverse adjacency - should fail because vertex 5 doesn't exist
570        let result = append_to_adjacency(&edge, &mut adj, false);
571
572        assert!(result.is_err());
573        let error_msg = result.unwrap_err();
574        assert!(error_msg.contains("vertex 5 not found in reverse adjacencies"));
575        assert!(error_msg.contains("edge list, edge: 1, 10"));
576    }
577
578    #[test]
579    fn test_append_to_adjacency_multiple_edges_same_vertex() {
580        // Create an adjacency list with 3 vertices
581        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
582            vec![IndexMap::new(), IndexMap::new(), IndexMap::new()];
583
584        // Create multiple edges from vertex 0
585        let edge1 = create_test_edge(0, 0, 0, 1);
586        let edge2 = create_test_edge(0, 1, 0, 2);
587        let edge3 = create_test_edge(1, 0, 0, 2); // Different edge list
588
589        // Add all edges in forward direction
590        assert!(append_to_adjacency(&edge1, &mut adj, true).is_ok());
591        assert!(append_to_adjacency(&edge2, &mut adj, true).is_ok());
592        assert!(append_to_adjacency(&edge3, &mut adj, true).is_ok());
593
594        // Check that all edges were added to vertex 0's adjacency list
595        assert_eq!(adj[0].len(), 3);
596
597        // Verify each edge maps to the correct target vertex
598        assert_eq!(adj[0][&(EdgeListId(0), EdgeId(0))], VertexId(1));
599        assert_eq!(adj[0][&(EdgeListId(0), EdgeId(1))], VertexId(2));
600        assert_eq!(adj[0][&(EdgeListId(1), EdgeId(0))], VertexId(2));
601    }
602
603    #[test]
604    fn test_append_to_adjacency_edge_overwrite() {
605        // Create an adjacency list with 3 vertices
606        let mut adj: Vec<IndexMap<(EdgeListId, EdgeId), VertexId>> =
607            vec![IndexMap::new(), IndexMap::new(), IndexMap::new()];
608
609        // Create two edges with the same EdgeListId and EdgeId but different targets
610        let edge1 = create_test_edge(0, 0, 0, 1);
611        let edge2 = create_test_edge(0, 0, 0, 2); // Same edge list and edge id
612
613        // Add first edge
614        assert!(append_to_adjacency(&edge1, &mut adj, true).is_ok());
615        assert_eq!(adj[0][&(EdgeListId(0), EdgeId(0))], VertexId(1));
616
617        // Add second edge - should overwrite the first one
618        assert!(append_to_adjacency(&edge2, &mut adj, true).is_ok());
619        assert_eq!(adj[0].len(), 1); // Still only one entry
620        assert_eq!(adj[0][&(EdgeListId(0), EdgeId(0))], VertexId(2)); // Updated target
621    }
622}
routee_compass_core/model/network/graph.rs

routee_compass_core/model/network/
graph.rs
