1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, 13 * software distributed under the License is distributed on an 14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 15 * KIND, either express or implied. See the License for the 16 * specific language governing permissions and limitations 17 * under the License. 18 */ 19 20 use std::cmp; 21 use std::fmt; 22 use std::fs::File; 23 use std::io::{BufRead, BufReader}; 24 25 #[cfg(test)] 26 use rand::rngs::StdRng; 27 #[cfg(test)] 28 use rand::Rng; 29 30 use serde::{Deserialize, Serialize}; 31 32 use crate::constants::NodeId; 33 use crate::constants::Weight; 34 35 #[derive(Serialize, Deserialize)] 36 pub struct InputGraph { 37 edges: Vec<Edge>, 38 num_nodes: usize, 39 frozen: bool, 40 } 41 42 impl InputGraph { new() -> Self43 pub fn new() -> Self { 44 InputGraph { 45 edges: Vec::new(), 46 num_nodes: 0, 47 frozen: false, 48 } 49 } 50 51 #[cfg(test)] random(rng: &mut StdRng, num_nodes: usize, mean_degree: f32) -> Self52 pub fn random(rng: &mut StdRng, num_nodes: usize, mean_degree: f32) -> Self { 53 InputGraph::build_random_graph(rng, num_nodes, mean_degree) 54 } 55 from_file(filename: &str) -> Self56 pub fn from_file(filename: &str) -> Self { 57 InputGraph::read_from_file(filename) 58 } 59 add_edge(&mut self, from: NodeId, to: NodeId, weight: Weight) -> usize60 pub fn add_edge(&mut self, from: NodeId, to: NodeId, weight: Weight) -> usize { 61 self.do_add_edge(from, to, weight, false) 62 } 63 add_edge_bidir(&mut self, from: NodeId, to: NodeId, weight: Weight) -> usize64 pub fn add_edge_bidir(&mut self, from: NodeId, to: NodeId, weight: Weight) -> usize { 65 self.do_add_edge(from, to, weight, true) 66 } 67 get_edges(&self) -> &Vec<Edge>68 pub fn get_edges(&self) -> &Vec<Edge> { 69 self.check_frozen(); 70 &self.edges 71 } 72 get_num_nodes(&self) -> usize73 pub fn get_num_nodes(&self) -> usize { 74 self.check_frozen(); 75 self.num_nodes 76 } 77 get_num_edges(&self) -> usize78 pub fn get_num_edges(&self) -> usize { 79 self.check_frozen(); 80 self.edges.len() 81 } 82 freeze(&mut self)83 pub fn freeze(&mut self) { 84 if self.frozen { 85 panic!("Input graph is already frozen"); 86 } 87 self.sort(); 88 self.remove_duplicate_edges(); 89 self.frozen = true; 90 } 91 thaw(&mut self)92 pub fn thaw(&mut self) { 93 self.frozen = false; 94 } 95 sort(&mut self)96 fn sort(&mut self) { 97 &self.edges.sort_by(|a, b| { 98 a.from 99 .cmp(&b.from) 100 .then(a.to.cmp(&b.to)) 101 .then(a.weight.cmp(&&b.weight)) 102 }); 103 } 104 remove_duplicate_edges(&mut self)105 fn remove_duplicate_edges(&mut self) { 106 // we go through (already sorted!) list of edges and remove duplicates 107 let len_before = self.edges.len(); 108 self.edges.dedup_by(|a, b| a.from == b.from && a.to == b.to); 109 if len_before != self.edges.len() { 110 warn!( 111 "There were {} duplicate edges, only the ones with lowest weight were kept", 112 len_before - self.edges.len() 113 ); 114 } 115 } 116 unit_test_output_string(&self) -> String117 pub fn unit_test_output_string(&self) -> String { 118 return self 119 .edges 120 .iter() 121 .map(|e| e.unit_test_output_string()) 122 .collect::<Vec<String>>() 123 .join("\n") 124 + "\n"; 125 } 126 check_frozen(&self)127 fn check_frozen(&self) { 128 if !self.frozen { 129 panic!("You need to call freeze() before using the input graph") 130 } 131 } 132 do_add_edge(&mut self, from: NodeId, to: NodeId, weight: Weight, bidir: bool) -> usize133 fn do_add_edge(&mut self, from: NodeId, to: NodeId, weight: Weight, bidir: bool) -> usize { 134 if self.frozen { 135 panic!("Graph is frozen already, for further changes first use thaw()"); 136 } 137 if from == to { 138 warn!( 139 "Loop edges are not allowed. Skipped edge! from: {}, to: {}, weight: {}", 140 from, to, weight 141 ); 142 return 0; 143 } 144 if weight < 1 { 145 warn!( 146 "Zero weight edges are not allowed. Skipped edge! from: {}, to: {}, weight: {}", 147 from, to, weight 148 ); 149 return 0; 150 } 151 self.num_nodes = cmp::max(self.num_nodes, cmp::max(from, to) + 1); 152 self.edges.push(Edge::new(from, to, weight)); 153 if bidir { 154 self.edges.push(Edge::new(to, from, weight)); 155 } 156 return if bidir { 2 } else { 1 }; 157 } 158 159 /// Builds a random graph, mostly used for testing purposes 160 #[cfg(test)] build_random_graph(rng: &mut StdRng, num_nodes: usize, mean_degree: f32) -> InputGraph161 fn build_random_graph(rng: &mut StdRng, num_nodes: usize, mean_degree: f32) -> InputGraph { 162 let num_edges = (mean_degree * num_nodes as f32) as usize; 163 let mut result = InputGraph::new(); 164 let mut edge_count = 0; 165 loop { 166 let head = rng.gen_range(0, num_nodes); 167 let tail = rng.gen_range(0, num_nodes); 168 // limit max weight, but otherwise allow duplicates, loops etc. to make sure clean-up 169 // inside InputGraph works correctly 170 let weight = rng.gen_range(1, 100); 171 edge_count += result.add_edge(tail, head, weight); 172 if edge_count == num_edges { 173 break; 174 } 175 } 176 result.freeze(); 177 result 178 } 179 180 /// Reads input graph from a text file, using the following format: 181 /// a <from> <to> <weight> 182 /// Mostly used for performance testing. read_from_file(filename: &str) -> Self183 fn read_from_file(filename: &str) -> Self { 184 let file = File::open(filename).unwrap(); 185 let reader = BufReader::new(file); 186 let mut g = InputGraph::new(); 187 for (_index, line) in reader.lines().enumerate() { 188 let s: String = line.unwrap(); 189 if !s.starts_with("a") { 190 continue; 191 } else { 192 let entries = s.split_whitespace().collect::<Vec<&str>>()[1..4] 193 .iter() 194 .map(|m| m.parse::<usize>().unwrap()) 195 .collect::<Vec<usize>>(); 196 let from = entries[0]; 197 let to = entries[1]; 198 let weight = entries[2]; 199 g.add_edge(from, to, weight); 200 } 201 } 202 g.freeze(); 203 g 204 } 205 } 206 207 impl fmt::Debug for InputGraph { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result208 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 209 write!(f, "{}", self.unit_test_output_string()) 210 } 211 } 212 213 #[derive(Serialize, Deserialize, Debug)] 214 pub struct Edge { 215 pub from: NodeId, 216 pub to: NodeId, 217 pub weight: Weight, 218 } 219 220 impl Edge { new(from: NodeId, to: NodeId, weight: Weight) -> Edge221 pub fn new(from: NodeId, to: NodeId, weight: Weight) -> Edge { 222 Edge { from, to, weight } 223 } 224 unit_test_output_string(&self) -> String225 pub fn unit_test_output_string(&self) -> String { 226 return format!("g.add_edge({}, {}, {});", self.from, self.to, self.weight); 227 } 228 } 229 230 #[cfg(test)] 231 mod tests { 232 use super::*; 233 234 #[test] 235 #[should_panic] panic_if_not_frozen_get_edges()236 fn panic_if_not_frozen_get_edges() { 237 let mut g = InputGraph::new(); 238 g.add_edge(0, 1, 3); 239 g.get_edges(); 240 } 241 242 #[test] 243 #[should_panic] panic_if_not_frozen_get_num_edges()244 fn panic_if_not_frozen_get_num_edges() { 245 let mut g = InputGraph::new(); 246 g.add_edge(0, 1, 3); 247 g.get_num_edges(); 248 } 249 250 #[test] 251 #[should_panic] panic_if_not_frozen_get_num_nodes()252 fn panic_if_not_frozen_get_num_nodes() { 253 let mut g = InputGraph::new(); 254 g.add_edge(0, 1, 3); 255 g.get_num_nodes(); 256 } 257 258 #[test] 259 #[should_panic] panic_if_frozen_add_edge()260 fn panic_if_frozen_add_edge() { 261 let mut g = InputGraph::new(); 262 g.add_edge(0, 1, 3); 263 g.freeze(); 264 g.add_edge(2, 5, 4); 265 } 266 267 #[test] freeze_and_thaw()268 fn freeze_and_thaw() { 269 let mut g = InputGraph::new(); 270 g.add_edge(0, 5, 10); 271 g.add_edge(0, 5, 5); 272 g.freeze(); 273 assert_eq!(1, g.get_num_edges()); 274 g.thaw(); 275 g.add_edge(0, 5, 1); 276 g.freeze(); 277 assert_eq!(1, g.get_num_edges()); 278 assert_eq!(1, g.get_edges()[0].weight); 279 } 280 281 #[test] num_nodes()282 fn num_nodes() { 283 let mut g = InputGraph::new(); 284 g.add_edge(7, 1, 2); 285 g.add_edge(5, 6, 4); 286 g.add_edge(11, 8, 3); 287 g.freeze(); 288 assert_eq!(12, g.get_num_nodes()); 289 } 290 291 #[test] skips_loops()292 fn skips_loops() { 293 let mut g = InputGraph::new(); 294 g.add_edge(0, 1, 3); 295 g.add_edge(4, 4, 2); 296 g.add_edge(2, 5, 4); 297 g.freeze(); 298 assert_eq!(2, g.get_num_edges()); 299 } 300 301 #[test] skips_zero_weight_edges()302 fn skips_zero_weight_edges() { 303 let mut g = InputGraph::new(); 304 g.add_edge(0, 1, 5); 305 g.add_edge(1, 2, 0); 306 g.add_edge(2, 3, 3); 307 g.freeze(); 308 assert_eq!(2, g.get_num_edges()); 309 } 310 311 #[test] skips_duplicate_edges()312 fn skips_duplicate_edges() { 313 let mut g = InputGraph::new(); 314 g.add_edge(0, 1, 7); 315 g.add_edge(2, 3, 5); 316 g.add_edge(0, 2, 3); 317 g.add_edge(0, 1, 2); 318 g.add_edge(4, 6, 9); 319 g.add_edge(0, 1, 4); 320 g.freeze(); 321 assert_eq!(4, g.get_num_edges()); 322 // edges should be sorted and duplicates should be removed keeping only the ones with 323 // lowest weight 324 let weights = g 325 .get_edges() 326 .iter() 327 .map(|e| e.weight) 328 .collect::<Vec<Weight>>(); 329 assert_eq!(vec![2, 3, 5, 9], weights); 330 } 331 332 #[test] skips_duplicate_edges_more()333 fn skips_duplicate_edges_more() { 334 let mut g = InputGraph::new(); 335 g.add_edge(1, 3, 43); 336 g.add_edge(3, 2, 90); 337 g.add_edge(3, 2, 88); 338 g.add_edge(2, 3, 87); 339 g.add_edge(3, 0, 75); 340 g.add_edge(0, 2, 45); 341 g.add_edge(1, 3, 71); 342 g.add_edge(4, 3, 5); 343 g.add_edge(1, 3, 91); 344 g.freeze(); 345 assert_eq!(6, g.get_num_edges()); 346 let weights = g 347 .get_edges() 348 .iter() 349 .map(|e| e.weight) 350 .collect::<Vec<Weight>>(); 351 assert_eq!(vec![45, 43, 87, 75, 88, 5], weights); 352 } 353 } 354