transit_grid/graphs/topology/
repair.rs

1use crate::core::NodeId;
2
3use super::TopologyGraph;
4
5/// `TopologyGraphRepairer` provides functionality to manipulate and repair edges in a topological graph.
6///
7/// It provides methods for reversing dual edges and cross-linking dual edges.
8pub trait TopologyGraphRepairer {
9    /// Repairs the direction of edges in a graph if they are incorrectly directed.
10    ///
11    /// This function repairs edges between two nodes in the graph by examining their direction.
12    /// If the edges have the same direction (either both outgoing or both incoming), the direction
13    /// of the edges will be switched to ensure a consistent direction from `node1` to `node2`.
14    ///
15    /// # Examples
16    /// Correct scenarios:
17    /// a -> node1_indices.0 -> node2_indices.0 -> b
18    /// a -> node1_indices.0 -> node2_indices.1 -> b
19    /// a -> node1_indices.1 -> node2_indices.0 -> b
20    ///
21    /// Incorrect scenarios:
22    /// a -> node1_indices.0 <- node2_indices.0 -> b
23    /// a -> node1_indices.1 <- node2_indices.0 -> b
24    /// a -> node1_indices.0 <- node2_indices.1 -> b
25    ///
26    /// In the incorrect scenarios, the function will correct the edge directions as:
27    /// a -> node1_indices.0 -> node2_indices.0 -> b
28    /// a -> node1_indices.1 -> node2_indices.0 -> b
29    /// a -> node1_indices.0 -> node2_indices.1 -> b
30    ///
31    /// # Arguments
32    /// * `node1`: The first node of the edge pair.
33    /// * `node2`: The second node of the edge pair.
34    ///
35    /// # Panics
36    /// This function will panic if either of the node indices is not present in the graph.
37    ///
38    /// # Note
39    /// This function is mainly intended to be used for directed graphs. Using it for undirected graphs
40    /// may not have the intended effect.
41    ///
42    /// This function should be used when a graph's edge directions are set manually and may be incorrect,
43    /// and when it's important that the edges have a specific direction for the logic of the application.
44    fn repair_edge(&mut self, node1: NodeId, node2: NodeId);
45
46    /// Reverse the dual edge defined by the two given node IDs.
47    ///
48    /// Implementations should ensure that after this operation, the direction of the dual edge between the two nodes is reversed. This implies that if the edge was directed from `node1` to `node2`, it should be directed from `node2` to `node1` after this operation, and vice versa.
49    ///
50    /// # Arguments
51    ///
52    /// * `node1` - The ID of the first node defining the dual edge to be reversed.
53    /// * `node2` - The ID of the second node defining the dual edge to be reversed.
54    fn reverse_dual_edge(&mut self, node1: NodeId, node2: NodeId);
55
56    /// Cross-link the dual edge defined by the two given node IDs.
57    ///
58    /// Implementations should ensure that after this operation, the dual edge between the two nodes is cross-linked. This implies that if there was a direct edge from `node1` to `node2`, there should now also be a direct edge from `node2` to `node1` after this operation, and vice versa.
59    ///
60    /// # Arguments
61    ///
62    /// * `node1` - The ID of the first node defining the dual edge to be cross-linked.
63    /// * `node2` - The ID of the second node defining the dual edge to be cross-linked.
64    fn cross_link_dual_edge(&mut self, node1: NodeId, node2: NodeId);
65}
66
67impl TopologyGraphRepairer for TopologyGraph {
68    fn repair_edge(&mut self, node1: NodeId, node2: NodeId) {
69        if let Some((edge_index1, edge_index2)) = self.find_edge_indices(node1, node2)
70            && !self.edge_is_in_neighbors_direction(edge_index1)
71                && !self.edge_is_in_neighbors_direction(edge_index2)
72            {
73                self.reverse_dual_edge(node1, node2);
74            }
75        if let Some((edge_index1, edge_index2)) = self.find_edge_indices(node1, node2)
76            && !self.edge_is_in_neighbors_direction(edge_index1)
77                && !self.edge_is_in_neighbors_direction(edge_index2)
78            {
79                self.cross_link_dual_edge(node1, node2);
80            }
81    }
82
83    fn reverse_dual_edge(&mut self, node1: NodeId, node2: NodeId) {
84        if let Some(edges) = self.find_edge_indices(node1, node2) {
85            self.reverse_edge(edges.0);
86            self.reverse_edge(edges.1);
87        }
88    }
89
90    fn cross_link_dual_edge(&mut self, node1: NodeId, node2: NodeId) {
91        if let Some(edges) = self.find_edge_indices(node1, node2) {
92            let (source1, target1) = self.graph.edge_endpoints(edges.0).unwrap();
93            let (source2, target2) = self.graph.edge_endpoints(edges.1).unwrap();
94
95            let weight1 = self.graph.edge_weight(edges.0).unwrap().clone();
96            let weight2 = self.graph.edge_weight(edges.1).unwrap().clone();
97
98            self.graph.remove_edge(edges.0);
99            self.graph.remove_edge(edges.1);
100
101            self.graph.add_edge(source1, source2, weight1);
102            self.graph.add_edge(target1, target2, weight2);
103        }
104    }
105}
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110    use crate::prelude::TopoEdge;
111    use petgraph::{dot::Dot, stable_graph::EdgeIndex};
112
113    #[test]
114    fn test_repair_edge() {
115        let mut topo_graph = TopologyGraph::new();
116
117        let node_id_a = 1;
118        let node_id_b = 2;
119        let node_id_c = 3;
120        let node_id_d = 4;
121
122        topo_graph.add_node(node_id_a);
123        topo_graph.add_node(node_id_b);
124        topo_graph.add_node(node_id_c);
125        topo_graph.add_node(node_id_d);
126
127        let _edge31 = topo_graph.add_edge(31, 1, 2);
128        let edge32 = topo_graph.add_edge(32, 2, 3);
129        let _edge33 = topo_graph.add_edge(33, 3, 4);
130
131        println!("{:?}", Dot::new(&topo_graph.graph));
132
133        assert!(!topo_graph.edge_is_in_neighbors_direction(edge32.0));
134        assert!(!topo_graph.edge_is_in_neighbors_direction(edge32.1));
135
136        topo_graph.repair_edge(node_id_b, node_id_c);
137
138        println!("{:?}", Dot::new(&topo_graph.graph));
139
140        assert!(topo_graph.edge_is_in_neighbors_direction(edge32.0));
141        assert!(topo_graph.edge_is_in_neighbors_direction(edge32.1));
142    }
143
144    #[test]
145    fn test_reverse_dual_edge() {
146        let mut topo_graph = TopologyGraph::new();
147
148        let node_id1 = 1;
149        let node_id2 = 2;
150
151        let (added_node_id1_1, added_node_id1_2) = topo_graph.add_node(node_id1);
152        let (added_node_id2_1, added_node_id2_2) = topo_graph.add_node(node_id2);
153
154        assert_eq!(topo_graph.graph.node_count(), 4);
155
156        let edge_id1 = 1;
157
158        let topo_edge = TopoEdge {
159            id: EdgeIndex::new(0),
160            from: node_id1,
161            to: node_id2,
162            edge_id: edge_id1,
163        };
164
165        topo_graph
166            .graph
167            .add_edge(added_node_id1_1, added_node_id2_1, topo_edge.clone());
168        topo_graph
169            .graph
170            .add_edge(added_node_id2_2, added_node_id1_2, topo_edge.clone());
171
172        assert_eq!(topo_graph.graph.edge_count(), 2);
173
174        assert!(topo_graph.has_incoming(added_node_id2_1));
175        assert!(!topo_graph.has_incoming(added_node_id1_1));
176
177        assert!(topo_graph.has_incoming(added_node_id1_2));
178        assert!(!topo_graph.has_incoming(added_node_id2_2));
179
180        topo_graph.reverse_dual_edge(node_id1, node_id2);
181
182        assert!(topo_graph.has_incoming(added_node_id1_1));
183        assert!(!topo_graph.has_incoming(added_node_id2_1));
184
185        assert!(topo_graph.has_incoming(added_node_id2_2));
186        assert!(!topo_graph.has_incoming(added_node_id1_2));
187    }
188
189    #[test]
190    fn test_cross_link_dual_edge() {
191        let mut topo_graph = TopologyGraph::new();
192
193        let node_id1 = 1;
194        let node_id2 = 2;
195
196        let (added_node_id1_1, added_node_id1_2) = topo_graph.add_node(node_id1);
197        let (added_node_id2_1, added_node_id2_2) = topo_graph.add_node(node_id2);
198
199        assert_eq!(topo_graph.graph.node_count(), 4);
200
201        let edge_id1 = 1;
202
203        topo_graph.add_edge(edge_id1, node_id1, node_id2);
204
205        assert_eq!(topo_graph.graph.edge_count(), 2);
206
207        assert!(!topo_graph.has_incoming(added_node_id1_1));
208        assert!(topo_graph.has_incoming(added_node_id2_1));
209
210        assert!(topo_graph.has_incoming(added_node_id1_2));
211        assert!(!topo_graph.has_incoming(added_node_id2_2));
212
213        assert!(topo_graph
214            .graph
215            .find_edge(added_node_id1_1, added_node_id2_1)
216            .is_some());
217
218        topo_graph.cross_link_dual_edge(node_id1, node_id2);
219
220        assert!(!topo_graph.has_incoming(added_node_id1_1));
221        assert!(!topo_graph.has_incoming(added_node_id2_1));
222
223        assert!(topo_graph.has_incoming(added_node_id1_2));
224        assert!(topo_graph.has_incoming(added_node_id2_2));
225
226        assert!(topo_graph
227            .graph
228            .find_edge(added_node_id1_1, added_node_id2_1)
229            .is_none());
230        assert!(topo_graph
231            .graph
232            .find_edge(added_node_id2_1, added_node_id1_2)
233            .is_some());
234        assert!(topo_graph
235            .graph
236            .find_edge(added_node_id1_1, added_node_id2_2)
237            .is_some());
238    }
239}
transit_grid/graphs/topology/repair.rs

transit_grid/graphs/topology/
repair.rs
