toolbox_rs/
ddsg.rs

1use itertools::Itertools;
2use log::info;
3
4use crate::{edge::InputEdge, geometry::primitives::FPCoordinate, graph::NodeID, io::read_lines};
5
6pub enum WeightType {
7    Unit,
8    Original,
9}
10
11#[derive(Debug, PartialEq)]
12pub enum Direction {
13    Both = 0,
14    Forward = 1,
15    Reverse = 2,
16    Closed = 3,
17}
18
19impl TryFrom<i32> for Direction {
20    type Error = ();
21
22    fn try_from(v: i32) -> Result<Self, Self::Error> {
23        match v {
24            x if x == Direction::Both as i32 => Ok(Direction::Both),
25            x if x == Direction::Forward as i32 => Ok(Direction::Forward),
26            x if x == Direction::Reverse as i32 => Ok(Direction::Reverse),
27            x if x == Direction::Closed as i32 => Ok(Direction::Closed),
28            _ => Err(()),
29        }
30    }
31}
32
33pub fn read_graph<T: std::fmt::Debug + std::cmp::Eq + From<usize>>(
34    filename: &str,
35    weight_type: WeightType,
36) -> Vec<InputEdge<T>> {
37    let mut edges = Vec::new();
38
39    let mut lines = read_lines(filename).expect("could not load graph file");
40
41    let first_line = lines.next().unwrap().unwrap();
42    if first_line != "d" {
43        return edges;
44    }
45
46    let second_line = lines.next().unwrap().unwrap();
47    let sizes = second_line
48        .get(..)
49        .unwrap_or("")
50        .split_ascii_whitespace()
51        .collect_vec();
52    info!("expecting {} nodes and {} edges", sizes[0], sizes[1]);
53
54    let mut input_edge_counter = 0;
55
56    // load dimacs graph and coordinates
57    for line in lines {
58        let line = line.unwrap();
59        // IDSTARTNODE IDDESTNODE WEIGHT BLOCKEDDIR DISTANCE TIME
60        let tokens = line.get(..).unwrap_or("").split_whitespace().collect_vec();
61        if tokens.len() != 4 {
62            continue;
63        }
64        let u = tokens[0].parse::<NodeID>().unwrap();
65        let v = tokens[1].parse::<NodeID>().unwrap();
66
67        // avoid eigenloops
68        if u == v {
69            continue;
70        }
71
72        let data = tokens[2].parse::<usize>().unwrap();
73        let direction = Direction::try_from(tokens[3].parse::<i32>().unwrap()).unwrap();
74        input_edge_counter += 1;
75
76        match direction {
77            Direction::Both => {
78                edges.push(InputEdge::<T> {
79                    source: u,
80                    target: v,
81                    data: match &weight_type {
82                        WeightType::Unit => T::from(1),
83                        WeightType::Original => T::from(data),
84                    },
85                });
86                edges.push(InputEdge::<T> {
87                    source: v,
88                    target: u,
89                    data: match &weight_type {
90                        WeightType::Unit => T::from(1),
91                        WeightType::Original => T::from(data),
92                    },
93                });
94            }
95            Direction::Forward => {
96                edges.push(InputEdge::<T> {
97                    source: u,
98                    target: v,
99                    data: match &weight_type {
100                        WeightType::Unit => T::from(1),
101                        WeightType::Original => T::from(data),
102                    },
103                });
104            }
105            Direction::Reverse => {
106                edges.push(InputEdge::<T> {
107                    source: v,
108                    target: u,
109                    data: match &weight_type {
110                        WeightType::Unit => T::from(1),
111                        WeightType::Original => T::from(data),
112                    },
113                });
114            }
115            Direction::Closed => {
116                // closed in both directions, thus ignore
117            }
118        }
119    }
120    info!(
121        "exploded {input_edge_counter} input edges into {} directed edges",
122        edges.len()
123    );
124    edges
125}
126
127pub fn read_coordinates(filename: &str) -> Vec<FPCoordinate> {
128    let mut lines = read_lines(filename).expect("could not load coordinates file");
129    let first_line = lines.next().unwrap().unwrap();
130    let coordinate_count = first_line.parse::<usize>().unwrap();
131    info!("expecting {coordinate_count} coordinates");
132    let mut coordinates = Vec::with_capacity(coordinate_count);
133    for line in lines {
134        let line = line.unwrap();
135        let tokens = line.get(..).unwrap_or("").split_whitespace().collect_vec();
136        let count = tokens[0].parse::<usize>().unwrap();
137        assert_eq!(count, coordinates.len());
138
139        let lon = tokens[1].parse::<f64>().unwrap() / 100_000.;
140        let lat = tokens[2].parse::<f64>().unwrap() / 100_000.;
141        coordinates.push(FPCoordinate::new_from_lat_lon(lat, lon));
142    }
143    assert_eq!(coordinate_count, coordinates.len());
144    info!("loaded {coordinate_count} coordinates");
145
146    coordinates
147}
148
149#[cfg(test)]
150mod tests {
151    use std::io::Write;
152    use tempfile::NamedTempFile;
153
154    use crate::ddsg::{read_coordinates, Direction, WeightType};
155
156    #[test]
157    fn direction_try_from() {
158        assert_eq!(Direction::try_from(0), Ok(Direction::Both));
159        assert_eq!(Direction::try_from(1), Ok(Direction::Forward));
160        assert_eq!(Direction::try_from(2), Ok(Direction::Reverse));
161        assert_eq!(Direction::try_from(3), Ok(Direction::Closed));
162        assert_eq!(Direction::try_from(4), Err(()));
163    }
164
165    #[test]
166    fn read_graph_undirected() {
167        let filename = create_temp_file_with_content("d\n2 1\n0 1 10 0\n");
168        let edges = crate::ddsg::read_graph::<usize>(
169            filename.path().to_str().unwrap(),
170            WeightType::Original,
171        );
172        assert_eq!(edges.len(), 2);
173        assert_eq!(edges[0].source, 0);
174        assert_eq!(edges[0].target, 1);
175        assert_eq!(edges[0].data, 10);
176        assert_eq!(edges[1].source, 1);
177        assert_eq!(edges[1].target, 0);
178        assert_eq!(edges[1].data, 10);
179    }
180
181    #[test]
182    fn read_graph_with_invalid_data() {
183        let filename = create_temp_file_with_content("t\n2 1\n0 1 10 0\n");
184        let edges = crate::ddsg::read_graph::<usize>(
185            filename.path().to_str().unwrap(),
186            WeightType::Original,
187        );
188        assert_eq!(edges.len(), 0);
189    }
190
191    #[test]
192    fn read_graph_with_different_directions() {
193        let filename = create_temp_file_with_content("d\n3 3\n0 1 10 1\n1 2 20 2\n2 0 30 3\n");
194        let edges = crate::ddsg::read_graph::<usize>(
195            filename.path().to_str().unwrap(),
196            WeightType::Original,
197        );
198        assert_eq!(edges.len(), 2);
199        assert_eq!(edges[0].source, 0);
200        assert_eq!(edges[0].target, 1);
201        assert_eq!(edges[0].data, 10);
202        assert_eq!(edges[1].source, 2);
203        assert_eq!(edges[1].target, 1);
204        assert_eq!(edges[1].data, 20);
205    }
206
207    #[test]
208    fn read_ddsg_coordinates() {
209        let filename = create_temp_file_with_content("2\n0 1000000 2000000\n1 3000000 4000000\n");
210        let coordinates = crate::ddsg::read_coordinates(filename.path().to_str().unwrap());
211        assert_eq!(coordinates.len(), 2);
212        assert_eq!(coordinates[0].to_lon_lat_pair(), (10., 20.));
213        assert_eq!(coordinates[1].to_lon_lat_pair(), (30., 40.));
214    }
215
216    #[test]
217    fn read_coordinates_with_invalid_data() {
218        let filename =
219            create_temp_file_with_content("2\n0 1000000 2000000\n1 invalid_data 4000000\n");
220        let result =
221            std::panic::catch_unwind(|| read_coordinates(filename.path().to_str().unwrap()));
222        assert!(result.is_err());
223    }
224
225    fn create_temp_file_with_content(content: &str) -> NamedTempFile {
226        let mut file = NamedTempFile::new().unwrap();
227        write!(file, "{}", content).unwrap();
228        file
229    }
230}
toolbox_rs/ddsg.rs

toolbox_rs/
ddsg.rs
