transit_grid/graphs/physical/
mod.rs

1use std::collections::HashMap;
2
3use crate::core::{EdgeId, NodeId, TransitEdge, TransitNode};
4use geo::{Coord, CoordNum, Distance, Euclidean};
5use petgraph::{
6    graph::EdgeIndex,
7    graph::{NodeIndex, UnGraph},
8};
9
10/// Represents the physical layout of the transit network.
11///
12/// `PhysicalGraph` is an undirected graph where each node represents a transit node (a point in the transit network where a vehicle can stop) and each edge represents a transit edge (a path between two transit nodes).
13/// The `PhysicalGraph` uses the `UnGraph` structure from the `petgraph` crate to internally represent this data. The `PhysicalGraph` maintains mappings between `NodeId`s and `NodeIndex`es (from `petgraph`), allowing for efficient conversion between the two.
14///
15/// # Examples
16///
17/// Creating a new `PhysicalGraph` and adding a `TransitNode`:
18/// ```
19/// use transit_grid::core::TransitNode;
20/// use transit_grid::prelude::PhysicalGraph;
21/// use geo::{coord, Coord};
22///
23/// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
24/// let node = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
25/// graph.add_transit_node(node);
26/// ```
27///
28/// Adding a `TransitEdge` to the `PhysicalGraph`:
29/// ```
30/// use transit_grid::core::{TransitNode, TransitEdge};
31/// use transit_grid::prelude::PhysicalGraph;
32/// use geo::{coord, Coord, LineString};
33///
34/// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
35/// let node1 = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
36/// let node2 = TransitNode { id: 2, location: coord! { x:1.0, y:1.0 } };
37/// let node1_id = graph.add_transit_node(node1);
38/// let node2_id = graph.add_transit_node(node2);
39/// let edge = TransitEdge {
40///     id: 1,
41///     source: 1,
42///     target: 2,
43///     length: 1.0,
44///     path: LineString(vec![coord! { x:0.0, y:0.0 }, coord! { x:1.0, y:1.0 }]),
45/// };
46/// graph.add_transit_edge(edge);
47/// ```
48#[derive(Debug, Clone)]
49pub struct PhysicalGraph<R, T: CoordNum> {
50    /// Underlying undirected graph.
51    pub graph: UnGraph<TransitNode<R>, TransitEdge<T>, u32>,
52
53    /// Mapping of NodeId to petgraph's NodeIndex.
54    id_to_index: HashMap<NodeId, NodeIndex>,
55
56    /// Mapping of petgraph's NodeIndex to NodeId.
57    index_to_id: HashMap<NodeIndex, NodeId>,
58}
59
60impl<R: Copy, T: CoordNum> PhysicalGraph<R, T> {
61    /// Creates a new, empty `PhysicalGraph`.
62    pub fn new() -> Self {
63        PhysicalGraph {
64            graph: UnGraph::<TransitNode<R>, TransitEdge<T>, u32>::new_undirected(),
65            id_to_index: HashMap::new(),
66            index_to_id: HashMap::new(),
67        }
68    }
69
70    /// Converts a `NodeIndex` to a `NodeId`.
71    ///
72    /// This method provides a way to map from the petgraph's `NodeIndex` to
73    /// the `NodeId` used in the `TransitNode`.
74    ///
75    /// # Arguments
76    ///
77    /// * `index` - The `NodeIndex` to be converted.
78    ///
79    /// # Returns
80    ///
81    /// * `NodeId` - The corresponding `NodeId` of the provided `NodeIndex`.
82    ///
83    /// # Example
84    ///
85    /// ```
86    /// use transit_grid::prelude::PhysicalGraph;
87    /// use transit_grid::core::TransitNode;
88    /// use geo::{coord, Coord};
89    ///
90    /// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
91    /// let node = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
92    /// let node_index = graph.add_transit_node(node);
93    /// let node_id = graph.index_to_id(node_index);
94    /// assert_eq!(node_id, Some(&1));
95    /// ```
96    pub fn index_to_id(&self, index: NodeIndex) -> Option<&NodeId> {
97        self.index_to_id.get(&index)
98    }
99
100    /// Converts a `NodeId` to a `NodeIndex`.
101    ///
102    /// This method provides a way to map from a `NodeId` used in the `TransitNode` to
103    /// the petgraph's `NodeIndex`.
104    ///
105    /// # Arguments
106    ///
107    /// * `id` - The `NodeId` to be converted.
108    ///
109    /// # Returns
110    ///
111    /// * `NodeIndex` - The corresponding `NodeIndex` of the provided `NodeId`.
112    ///
113    /// # Example
114    ///
115    /// ```
116    /// use transit_grid::prelude::PhysicalGraph;
117    /// use transit_grid::core::TransitNode;
118    /// use geo::{coord, Coord};
119    ///
120    /// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
121    /// let node = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
122    /// let node_index = graph.add_transit_node(node);
123    /// let queried_index = graph.id_to_index(1);
124    /// assert_eq!(Some(&node_index), queried_index);
125    /// ```
126    pub fn id_to_index(&self, id: NodeId) -> Option<&NodeIndex> {
127        self.id_to_index.get(&id)
128    }
129
130    /// Adds a `TransitNode` to the `PhysicalGraph`.
131    ///
132    /// # Example
133    /// ```
134    /// use transit_grid::prelude::PhysicalGraph;
135    /// use transit_grid::core::TransitNode;
136    /// use geo::{coord, Coord};
137    ///
138    /// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
139    /// let node = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
140    /// graph.add_transit_node(node);
141    /// ```
142    pub fn add_transit_node(&mut self, node: TransitNode<R>) -> NodeIndex {
143        let index = self.graph.add_node(node);
144        self.id_to_index.insert(node.id, index);
145        self.index_to_id.insert(index, node.id);
146        index
147    }
148
149    /// Adds a `TransitEdge` to the `PhysicalGraph`.
150    ///
151    /// # Example
152    /// ```
153    /// use transit_grid::prelude::PhysicalGraph;
154    /// use transit_grid::core::{TransitNode, TransitEdge};
155    /// use geo::{coord, Coord, LineString};
156    /// use petgraph::csr::IndexType;
157    ///
158    /// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
159    /// let node1 = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
160    /// let node2 = TransitNode { id: 2, location: coord! { x:1.0, y:1.0 } };
161    ///
162    /// let node1_id = graph.add_transit_node(node1);
163    /// let node2_id = graph.add_transit_node(node2);
164    ///
165    /// let edge = TransitEdge {
166    ///     id: 1,
167    ///     source: 1,
168    ///     target: 2,
169    ///     length: 1.0,
170    ///     path: LineString(vec![coord! { x:0.0, y:0.0 }, coord! { x:1.0, y:1.0 }]),
171    /// };
172    ///
173    /// graph.add_transit_edge(edge);
174    /// ```
175    pub fn add_transit_edge(&mut self, edge: TransitEdge<T>) -> EdgeIndex {
176        let from = self.id_to_index(edge.source);
177        let to = self.id_to_index(edge.target);
178        if let (Some(from), Some(to)) = (from, to) {
179            self.graph.add_edge(*from, *to, edge)
180        } else {
181            panic!("Invalid node ID")
182        }
183    }
184
185    /// Returns a reference to the `TransitEdge` connecting the two nodes specified by `node1` and `node2`.
186    ///
187    /// # Arguments
188    ///
189    /// * `node1` - The `NodeId` of the first node.
190    /// * `node2` - The `NodeId` of the second node.
191    ///
192    /// # Returns
193    ///
194    /// A reference to the `TransitEdge` connecting `node1` and `node2`. This function will panic if there is no edge between the nodes.
195    ///
196    /// # Panics
197    ///
198    /// This function will panic in the following cases:
199    ///
200    /// * If `node1` or `node2` are not valid node IDs in the graph.
201    /// * If there is no edge between `node1` and `node2`.
202    pub fn get_transit_edge(&self, node1: NodeId, node2: NodeId) -> Option<&TransitEdge<T>> {
203        let node1_index = self.id_to_index(node1);
204        let node2_index = self.id_to_index(node2);
205        if let (Some(node1_index), Some(node2_index)) = (node1_index, node2_index) {
206            if let Some(edge_index) = self.graph.find_edge(*node1_index, *node2_index) {
207                self.graph.edge_weight(edge_index)
208            } else {
209                None
210            }
211        } else {
212            None
213        }
214    }
215
216    /// Returns a reference to the `TransitEdge` with the specified `EdgeId`.
217    pub fn get_transit_edge_by_id(&self, edge_id: EdgeId) -> Option<&TransitEdge<T>> {
218        self.graph
219            .edge_references()
220            .find(|edge| edge.weight().id == edge_id)
221            .map(|edge| edge.weight())
222    }
223
224    /// Repairs a physical edge in the `PhysicalGraph` based on its nodes' locations.
225    ///
226    /// # Arguments
227    ///
228    /// * `edge` - The `TransitEdge` to be repaired.
229    ///
230    /// # Example
231    ///
232    /// ```
233    /// use transit_grid::prelude::PhysicalGraph;
234    /// use transit_grid::core::{TransitNode, TransitEdge};
235    /// use geo::{coord, Coord, LineString};
236    ///
237    /// let mut graph: PhysicalGraph<Coord, f64> = PhysicalGraph::new();
238    /// let node1 = TransitNode { id: 1, location: coord! { x:0.0, y:0.0 } };
239    /// let node2 = TransitNode { id: 2, location: coord! { x:1.0, y:1.0 } };
240    ///
241    /// let node1_id = graph.add_transit_node(node1);
242    /// let node2_id = graph.add_transit_node(node2);
243    ///
244    /// let mut edge = TransitEdge {
245    ///     id: 1,
246    ///     source: 1,
247    ///     target: 2,
248    ///     length: 1.0,
249    ///     path: LineString(vec![coord! { x:1.0, y:1.0 }, coord! { x:0.0, y:0.0 }]),  // Note that the direction is initially reversed
250    /// };
251    ///
252    /// graph.add_transit_edge(edge.clone());
253    /// graph.repair_edge(1, 2);
254    /// let edge = graph.get_transit_edge(1, 2).unwrap();
255    /// assert_eq!(
256    ///    edge.path,
257    ///    LineString(vec![Coord { x: 0.0, y: 0.0 }, Coord { x: 1.0, y: 1.0 }])
258    /// );
259    ///
260    /// // After repair, the edge path should be from 0,0 to 1,1
261    /// //assert_eq!(edge.path.0.first().unwrap(), &coord! { x:0.0, y:0.0 });
262    /// //assert_eq!(edge.path.0.last().unwrap(), &coord! { x:1.0, y:1.0 });
263    /// ```
264    pub fn repair_edge(&mut self, node1: NodeId, node2: NodeId)
265    where
266        Euclidean: Distance<T, R, Coord<T>>,
267    {
268        let node1_index = self.id_to_index(node1);
269        let node2_index = self.id_to_index(node2);
270        if let (Some(node1_index), Some(node2_index)) = (node1_index, node2_index) {
271            let from_node_location = {
272                let from_node: &TransitNode<R> = self.graph.node_weight(*node1_index).unwrap();
273                from_node.location
274            };
275
276            let edge_index = self.graph.find_edge(*node1_index, *node2_index).unwrap();
277            let edge = self.graph.edge_weight_mut(edge_index).unwrap();
278
279            let first_point = *edge.path.0.first().unwrap();
280            let last_point = *edge.path.0.last().unwrap();
281
282            let dist_to_first = Euclidean.distance(from_node_location, first_point);
283            let dist_to_last = Euclidean.distance(from_node_location, last_point);
284
285            if dist_to_first > dist_to_last {
286                edge.path.0.reverse();
287            }
288        }
289    }
290}
291
292impl<R: Copy, T: CoordNum> Default for PhysicalGraph<R, T> {
293    fn default() -> Self {
294        Self::new()
295    }
296}
297
298#[cfg(test)]
299mod tests {
300    use super::*;
301    use geo::{coord, Coord, LineString};
302
303    #[test]
304    fn test_graph() {
305        let mut graph = PhysicalGraph::new();
306
307        let node1 = TransitNode {
308            id: 1,
309            location: coord! { x:0.0, y:0.0 },
310        };
311
312        let node2 = TransitNode {
313            id: 2,
314            location: coord! { x:1.0, y:1.0 },
315        };
316
317        let node3 = TransitNode {
318            id: 3,
319            location: coord! { x:1.0, y:1.0 },
320        };
321
322        let _node1_id = graph.add_transit_node(node1);
323        let _node2_id = graph.add_transit_node(node2);
324        let _node3_id = graph.add_transit_node(node3);
325
326        let edge = TransitEdge {
327            id: 1,
328            source: 1,
329            target: 2,
330            length: 1.0,
331            path: LineString(vec![coord! { x:0.0, y:0.0 }, coord! { x:1.0, y:1.0 }]),
332        };
333
334        let _ = graph.add_transit_edge(edge);
335
336        assert_eq!(graph.graph.node_count(), 3);
337        assert_eq!(graph.graph.edge_count(), 1);
338
339        assert!(graph.get_transit_edge(1, 2).is_some());
340        assert!(graph.get_transit_edge(1, 3).is_none());
341    }
342
343    #[test]
344    fn test_index_to_id() {
345        let mut graph = PhysicalGraph::<Coord, f64>::new();
346
347        let node1 = TransitNode {
348            id: 1,
349            location: coord! { x:0.0, y:0.0 },
350        };
351
352        let node2 = TransitNode {
353            id: 2,
354            location: coord! { x:1.0, y:1.0 },
355        };
356
357        let node1_index = graph.add_transit_node(node1);
358        let node2_index = graph.add_transit_node(node2);
359
360        let node1_id = graph.index_to_id(node1_index);
361        let node2_id = graph.index_to_id(node2_index);
362
363        assert_eq!(node1_id, Some(&1));
364        assert_eq!(node2_id, Some(&2));
365    }
366
367    #[test]
368    fn test_id_to_index() {
369        let mut graph = PhysicalGraph::<Coord, f64>::new();
370
371        let node1 = TransitNode {
372            id: 1,
373            location: coord! { x:0.0, y:0.0 },
374        };
375
376        let node2 = TransitNode {
377            id: 2,
378            location: coord! { x:1.0, y:1.0 },
379        };
380
381        let node1_index = graph.add_transit_node(node1);
382        let node2_index = graph.add_transit_node(node2);
383
384        let queried_node1_index = graph.id_to_index(1);
385        let queried_node2_index = graph.id_to_index(2);
386
387        assert_eq!(Some(&node1_index), queried_node1_index);
388        assert_eq!(Some(&node2_index), queried_node2_index);
389    }
390
391    #[test]
392    fn test_default() {
393        let graph: PhysicalGraph<u32, f64> = PhysicalGraph::default();
394
395        assert_eq!(graph.graph.node_count(), 0);
396        assert_eq!(graph.graph.edge_count(), 0);
397    }
398
399    #[test]
400    fn test_repair_physical() {
401        let mut graph = PhysicalGraph::<Coord, f64>::new();
402        let node1 = TransitNode {
403            id: 1,
404            location: Coord { x: 0.0, y: 0.0 },
405        };
406        let node2 = TransitNode {
407            id: 2,
408            location: Coord { x: 1.0, y: 1.0 },
409        };
410
411        graph.add_transit_node(node1);
412        graph.add_transit_node(node2);
413
414        let edge = TransitEdge {
415            id: 1,
416            source: 1,
417            target: 2,
418            length: 1.0,
419            path: LineString(vec![Coord { x: 1.0, y: 1.0 }, Coord { x: 0.0, y: 0.0 }]),
420        };
421
422        graph.add_transit_edge(edge.clone());
423
424        graph.repair_edge(1, 2);
425
426        let edge = graph.get_transit_edge(1, 2).unwrap();
427
428        assert_eq!(
429            edge.path,
430            LineString(vec![Coord { x: 0.0, y: 0.0 }, Coord { x: 1.0, y: 1.0 }])
431        );
432    }
433}
transit_grid/graphs/physical/mod.rs

transit_grid/graphs/physical/
mod.rs
