#[macro_use]
extern crate log;
use serde::{Deserialize, Deserializer, Serialize, Serializer};
pub use crate::constants::*;
pub use crate::fast_graph::FastGraph;
pub use crate::fast_graph32::FastGraph32;
pub use crate::fast_graph_builder::FastGraphBuilder;
pub use crate::fast_graph_builder::Params;
pub use crate::fast_graph_builder::ParamsWithOrder;
pub use crate::input_graph::Edge;
pub use crate::input_graph::InputGraph;
pub use crate::path_calculator::PathCalculator;
pub use crate::shortest_path::ShortestPath;
mod constants;
#[cfg(test)]
mod dijkstra;
mod fast_graph;
mod fast_graph32;
mod fast_graph_builder;
#[cfg(test)]
mod floyd_warshall;
mod heap_item;
mod input_graph;
mod node_contractor;
mod path_calculator;
mod preparation_graph;
mod shortest_path;
mod valid_flags;
mod witness_search;
pub fn prepare(input_graph: &InputGraph) -> FastGraph {
FastGraphBuilder::build(input_graph)
}
pub fn prepare_with_params(input_graph: &InputGraph, params: &Params) -> FastGraph {
FastGraphBuilder::build_with_params(input_graph, params)
}
pub fn prepare_with_order(input_graph: &InputGraph, order: &[NodeId]) -> Result<FastGraph, String> {
FastGraphBuilder::build_with_order(input_graph, order)
}
pub fn prepare_with_order_with_params(
input_graph: &InputGraph,
order: &[NodeId],
params: &ParamsWithOrder,
) -> Result<FastGraph, String> {
FastGraphBuilder::build_with_order_with_params(input_graph, order, params)
}
pub fn calc_path(fast_graph: &FastGraph, source: NodeId, target: NodeId) -> Option<ShortestPath> {
let mut calc = PathCalculator::new(fast_graph.get_num_nodes());
calc.calc_path(fast_graph, source, target)
}
pub fn calc_path_multiple_sources_and_targets(
fast_graph: &FastGraph,
sources: Vec<(NodeId, Weight)>,
target: Vec<(NodeId, Weight)>,
) -> Option<ShortestPath> {
let mut calc = PathCalculator::new(fast_graph.get_num_nodes());
calc.calc_path_multiple_sources_and_targets(fast_graph, sources, target)
}
pub fn create_calculator(fast_graph: &FastGraph) -> PathCalculator {
PathCalculator::new(fast_graph.get_num_nodes())
}
pub fn get_node_ordering(fast_graph: &FastGraph) -> Vec<NodeId> {
fast_graph.get_node_ordering()
}
pub fn serialize_32<S: Serializer>(fg: &FastGraph, s: S) -> Result<S::Ok, S::Error> {
FastGraph32::new(fg).serialize(s)
}
pub fn deserialize_32<'de, D: Deserializer<'de>>(d: D) -> Result<FastGraph, D::Error> {
let fg32 = <FastGraph32>::deserialize(d)?;
Ok(fg32.convert_to_usize())
}
#[cfg(test)]
mod tests {
use std::error::Error;
use std::fs::{remove_file, File};
use std::time::SystemTime;
use rand::rngs::StdRng;
use rand::Rng;
use stopwatch::Stopwatch;
use crate::constants::NodeId;
use crate::dijkstra::Dijkstra;
use crate::fast_graph::FastGraph;
use crate::floyd_warshall::FloydWarshall;
use crate::path_calculator::PathCalculator;
use crate::preparation_graph::PreparationGraph;
use super::*;
use crate::fast_graph_builder::ParamsWithOrder;
#[test]
fn routing_on_random_graph() {
const REPEATS: usize = 100;
for _i in 0..REPEATS {
run_test_on_random_graph();
}
}
fn run_test_on_random_graph() {
const NUM_NODES: usize = 50;
const NUM_QUERIES: usize = 1_000;
const MEAN_DEGREE: f32 = 2.0;
let mut rng = create_rng();
let input_graph = InputGraph::random(&mut rng, NUM_NODES, MEAN_DEGREE);
debug!("random graph: \n {:?}", input_graph);
let fast_graph = prepare(&input_graph);
let mut path_calculator = create_calculator(&fast_graph);
let dijkstra_graph = PreparationGraph::from_input_graph(&input_graph);
let mut dijkstra = Dijkstra::new(input_graph.get_num_nodes());
let mut fw = FloydWarshall::new(input_graph.get_num_nodes());
fw.prepare(&input_graph);
let mut num_different_paths = 0;
for _i in 0..NUM_QUERIES {
let source = rng.gen_range(0, input_graph.get_num_nodes());
let target = rng.gen_range(0, input_graph.get_num_nodes());
let path_fast = path_calculator
.calc_path(&fast_graph, source, target)
.unwrap_or(ShortestPath::none(source, target));
let path_dijkstra = dijkstra
.calc_path(&dijkstra_graph, source, target)
.unwrap_or(ShortestPath::none(source, target));
let weight_fast = path_fast.get_weight();
let weight_dijkstra = path_dijkstra.get_weight();
let weight_fw = fw.calc_weight(source, target);
assert_eq!(
weight_fw, weight_fast,
"\nNo agreement for routing query from: {} to: {}\nFloyd-Warshall: {}\nCH: {}\
\n Failing graph:\n{:?}",
source, target, weight_fw, weight_fast, input_graph
);
assert_eq!(
path_dijkstra, path_fast,
"\nNo agreement for routing query from: {} to: {}\nDijkstra: {}\nCH: {}\
\n Failing graph:\n{:?}",
source, target, weight_dijkstra, weight_fast, input_graph
);
if path_dijkstra.get_nodes() != path_fast.get_nodes() {
num_different_paths += 1;
}
}
if num_different_paths as f32 > 0.1 * NUM_QUERIES as f32 {
panic!(
"too many different paths: {}, out of {}, a few different paths can be expected \
because of unambiguous shortest paths, but if there are too many something is \
wrong",
num_different_paths, NUM_QUERIES
);
}
}
#[test]
fn routing_with_multiple_sources_and_targets_on_random_graph() {
const REPEATS: usize = 20;
for _ in 0..REPEATS {
const NUM_NODES: usize = 50;
const NUM_QUERIES: usize = 1_000;
const MEAN_DEGREE: f32 = 2.0;
const NUM_SOURCES: usize = 3;
const NUM_TARGETS: usize = 3;
let mut rng = create_rng();
let input_graph = InputGraph::random(&mut rng, NUM_NODES, MEAN_DEGREE);
debug!("random graph: \n {:?}", input_graph);
let fast_graph = prepare(&input_graph);
let mut path_calculator = create_calculator(&fast_graph);
let dijkstra_graph = PreparationGraph::from_input_graph(&input_graph);
let mut dijkstra = Dijkstra::new(input_graph.get_num_nodes());
let mut num_different_paths = 0;
let mut num_paths_not_found = 0;
for _ in 0..NUM_QUERIES {
let sources =
gen_weighted_nodes(&mut rng, input_graph.get_num_nodes(), NUM_SOURCES);
let targets =
gen_weighted_nodes(&mut rng, input_graph.get_num_nodes(), NUM_TARGETS);
let fast_path = path_calculator.calc_path_multiple_sources_and_targets(
&fast_graph,
sources.clone(),
targets.clone(),
);
let mut dijkstra_paths: Vec<(Option<ShortestPath>, Weight, Weight)> = vec![];
for (source, source_weight) in &sources {
for (target, target_weight) in &targets {
dijkstra_paths.push((
dijkstra.calc_path(&dijkstra_graph, *source, *target),
*source_weight,
*target_weight,
))
}
}
let found_dijkstras: Vec<(ShortestPath, Weight, Weight)> = dijkstra_paths
.into_iter()
.filter(|(p, source_weight, target_weight)| {
p.is_some() && *source_weight < WEIGHT_MAX && *target_weight < WEIGHT_MAX
})
.map(|(p, source_weight, target_weight)| {
(p.unwrap(), source_weight, target_weight)
})
.collect();
let shortest_dijkstra_weight = found_dijkstras
.iter()
.map(|(p, source_weight, target_weight)| {
p.get_weight() + source_weight + target_weight
})
.min();
if shortest_dijkstra_weight.is_none() {
assert!(fast_path.is_none());
num_paths_not_found += 1;
continue;
}
assert!(fast_path.is_some());
let f = fast_path.unwrap();
let w = shortest_dijkstra_weight.unwrap();
assert_eq!(w, f.get_weight(),
"\nfast_path's weight {} does not match the weight of the shortest Dijkstra path {}.\
\nsources: {:?}\
\ntargets: {:?}\
\nFailing graph:\n{:?}",
f.get_weight(), w, sources, targets, input_graph);
let matching_dijkstras: Vec<(ShortestPath, Weight, Weight)> = found_dijkstras
.into_iter()
.filter(|(p, source_weight, target_weight)| {
p.get_weight() + source_weight + target_weight == f.get_weight()
&& p.get_source() == f.get_source()
&& p.get_target() == f.get_target()
})
.collect();
assert!(
matching_dijkstras.len() > 0,
"There has to be at least one Dijkstra path with source,target and weight equal to fast_path"
);
if !matching_dijkstras
.into_iter()
.any(|(p, _, _)| p.get_nodes() == f.get_nodes())
{
num_different_paths += 1;
}
}
if num_paths_not_found as f32 > 0.5 * NUM_QUERIES as f32 {
panic!(
"too many paths not found: {}, out of {}",
num_paths_not_found, NUM_QUERIES
)
}
if num_different_paths as f32 > 0.1 * NUM_QUERIES as f32 {
panic!(
"too many different paths: {}, out of {}, a few different paths can be expected \
because of unambiguous shortest paths, but if there are too many something is \
wrong",
num_different_paths, NUM_QUERIES
);
}
}
}
fn gen_weighted_nodes(rng: &mut StdRng, max_node: usize, num: usize) -> Vec<(NodeId, Weight)> {
(0..num)
.map(|_| {
(
rng.gen_range(0, max_node),
if rng.gen_range(0, 100) < 3 {
WEIGHT_MAX
} else {
rng.gen_range(0, 100)
},
)
})
.collect()
}
#[test]
fn save_to_and_load_from_disk() {
let mut g = InputGraph::new();
g.add_edge(0, 5, 6);
g.add_edge(5, 2, 1);
g.add_edge(2, 3, 4);
g.freeze();
let fast_graph = prepare(&g);
save_to_disk(&fast_graph, "example.fp").expect("writing to disk failed");
let loaded = load_from_disk("example.fp").unwrap();
remove_file("example.fp").expect("deleting file failed");
assert_eq!(fast_graph.get_num_nodes(), loaded.get_num_nodes());
assert_eq!(fast_graph.get_num_in_edges(), loaded.get_num_in_edges());
assert_eq!(fast_graph.get_num_out_edges(), loaded.get_num_out_edges());
}
#[test]
fn save_to_and_load_from_disk_32() {
let mut g = InputGraph::new();
g.add_edge(0, 5, 6);
g.add_edge(5, 2, 1);
g.add_edge(2, 3, 4);
g.freeze();
let fast_graph = prepare(&g);
save_to_disk32(&fast_graph, "example32.fp").expect("writing to disk failed");
let loaded = load_from_disk32("example32.fp").unwrap();
remove_file("example32.fp").expect("deleting file failed");
assert_eq!(fast_graph.get_num_nodes(), loaded.get_num_nodes());
assert_eq!(fast_graph.get_num_in_edges(), loaded.get_num_in_edges());
assert_eq!(fast_graph.get_num_out_edges(), loaded.get_num_out_edges());
}
#[test]
fn deterministic_result() {
const NUM_NODES: usize = 50;
const MEAN_DEGREE: f32 = 2.0;
for _ in 0..10 {
let mut rng = create_rng();
let input_graph = InputGraph::random(&mut rng, NUM_NODES, MEAN_DEGREE);
let serialized1 = bincode::serialize(&prepare(&input_graph)).unwrap();
let serialized2 = bincode::serialize(&prepare(&input_graph)).unwrap();
if serialized1 != serialized2 {
panic!("Preparing and serializing the same graph twice produced different results");
}
}
}
#[ignore]
#[test]
fn run_performance_test_dist() {
println!("Running performance test for Bremen dist");
run_performance_test(
&InputGraph::from_file("meta/test_maps/bremen_dist.gr"),
&Params::new(0.1, 500, 2, 50),
845493338,
30265,
)
}
#[ignore]
#[test]
fn run_performance_test_time() {
println!("Running performance test for Bremen time");
run_performance_test(
&InputGraph::from_file("meta/test_maps/bremen_time.gr"),
&Params::new(0.1, 100, 2, 100),
88104267255,
30265,
);
}
#[ignore]
#[test]
fn run_performance_test_ballard() {
println!("Running performance test for ballard");
run_performance_test(
&InputGraph::from_file("meta/test_maps/graph_ballard.gr"),
&Params::new(0.1, 100, 3, 100),
28409159409,
14992,
);
}
#[ignore]
#[test]
fn run_performance_test_23rd() {
println!("Running performance test for 23rd");
run_performance_test(
&InputGraph::from_file("meta/test_maps/graph_23rd.gr"),
&Params::new(0.1, 100, 3, 100),
19438403873,
20421,
);
}
#[ignore]
#[test]
fn run_performance_test_south_seattle_car() {
println!("Running performance test for South Seattle car");
run_performance_test(
&InputGraph::from_file("meta/test_maps/south_seattle_car.gr"),
&Params::new(0.1, 100, 10, 100),
77479396,
30805,
);
}
#[ignore]
#[test]
fn run_performance_test_bremen_dist_fixed_ordering() {
println!("Running performance test for Bremen dist (fixed node ordering)");
run_performance_test_fixed_ordering(
&InputGraph::from_file("meta/test_maps/bremen_dist.gr"),
&Params::default(),
&ParamsWithOrder::default(),
845493338,
30265,
);
}
#[ignore]
#[test]
fn run_performance_test_south_seattle_fixed_ordering() {
println!("Running performance test for South Seattle car (fixed node ordering)");
run_performance_test_fixed_ordering(
&InputGraph::from_file("meta/test_maps/south_seattle_car.gr"),
&Params::new(0.1, 100, 10, 100),
&ParamsWithOrder::new(100),
77479396,
30805,
);
}
fn run_performance_test(
input_graph: &InputGraph,
params: &Params,
expected_checksum: usize,
expected_num_not_found: usize,
) {
let mut fast_graph = FastGraph::new(1);
prepare_algo(
&mut |input_graph| fast_graph = prepare_with_params(input_graph, params),
&input_graph,
);
print_fast_graph_stats(&fast_graph);
let mut path_calculator = PathCalculator::new(fast_graph.get_num_nodes());
do_run_performance_test(
&mut |s, t| path_calculator.calc_path(&fast_graph, s, t),
input_graph.get_num_nodes(),
expected_checksum,
expected_num_not_found,
);
}
fn run_performance_test_fixed_ordering(
input_graph: &InputGraph,
params: &Params,
params_with_order: &ParamsWithOrder,
expected_checksum: usize,
expected_num_not_found: usize,
) {
let mut time = Stopwatch::start_new();
let mut fast_graph = prepare_with_params(input_graph, params);
time.stop();
println!(
"preparation time (heuristic order). {} ms",
time.elapsed_ms()
);
let order = get_node_ordering(&fast_graph);
prepare_algo(
&mut |input_graph| {
fast_graph =
prepare_with_order_with_params(input_graph, &order, params_with_order).unwrap()
},
&input_graph,
);
print_fast_graph_stats(&fast_graph);
let mut path_calculator = PathCalculator::new(fast_graph.get_num_nodes());
do_run_performance_test(
&mut |s, t| path_calculator.calc_path(&fast_graph, s, t),
input_graph.get_num_nodes(),
expected_checksum,
expected_num_not_found,
);
}
fn print_fast_graph_stats(fast_graph: &FastGraph) {
println!(
"number of nodes (fast graph) ...... {}",
fast_graph.get_num_nodes()
);
println!(
"number of out-edges (fast graph) .. {}",
fast_graph.get_num_out_edges()
);
println!(
"number of in-edges (fast graph) .. {}",
fast_graph.get_num_in_edges()
);
}
pub fn prepare_algo<F>(preparation: &mut F, input_graph: &InputGraph)
where
F: FnMut(&InputGraph),
{
let mut time = Stopwatch::new();
time.start();
preparation(&input_graph);
time.stop();
println!(
"number of nodes (input graph) ..... {}",
input_graph.get_num_nodes()
);
println!(
"number of edges (input graph) ..... {}",
input_graph.get_num_edges()
);
println!(
"preparation time .................. {} ms",
time.elapsed_ms()
);
}
fn do_run_performance_test<F>(
calc_path: &mut F,
num_nodes: usize,
expected_checksum: usize,
expected_num_not_found: usize,
) where
F: FnMut(NodeId, NodeId) -> Option<ShortestPath>,
{
let num_queries = 100_000;
let seed = 123;
let mut rng = create_rng_with_seed(seed);
let mut checksum = 0;
let mut num_not_found = 0;
let mut time = Stopwatch::new();
for _i in 0..num_queries {
let source = rng.gen_range(0, num_nodes);
let target = rng.gen_range(0, num_nodes);
time.start();
let path = calc_path(source, target);
time.stop();
match path {
Some(path) => checksum += path.get_weight(),
None => num_not_found += 1,
}
}
println!(
"total query time .................. {} ms",
time.elapsed_ms()
);
println!(
"query time on average ............. {} μs",
time.elapsed().as_micros() / (num_queries as u128)
);
assert_eq!(expected_checksum, checksum, "invalid checksum");
assert_eq!(
expected_num_not_found, num_not_found,
"invalid number of paths not found"
);
}
fn create_rng() -> StdRng {
let seed = create_seed();
create_rng_with_seed(seed)
}
fn create_rng_with_seed(seed: u64) -> StdRng {
debug!("creating random number generator with seed: {}", seed);
rand::SeedableRng::seed_from_u64(seed)
}
fn create_seed() -> u64 {
SystemTime::now()
.duration_since(SystemTime::UNIX_EPOCH)
.unwrap()
.as_nanos() as u64
}
fn save_to_disk(fast_graph: &FastGraph, file_name: &str) -> Result<(), Box<dyn Error>> {
let file = File::create(file_name)?;
Ok(bincode::serialize_into(file, fast_graph)?)
}
fn load_from_disk(file_name: &str) -> Result<FastGraph, Box<dyn Error>> {
let file = File::open(file_name)?;
Ok(bincode::deserialize_from(file)?)
}
fn save_to_disk32(fast_graph: &FastGraph, file_name: &str) -> Result<(), Box<dyn Error>> {
let fast_graph32 = &FastGraph32::new(fast_graph);
let file = File::create(file_name)?;
Ok(bincode::serialize_into(file, fast_graph32)?)
}
fn load_from_disk32(file_name: &str) -> Result<FastGraph, Box<dyn Error>> {
let file = File::open(file_name)?;
let r: Result<FastGraph32, Box<dyn Error>> = Ok(bincode::deserialize_from(file)?);
r.map(|g| g.convert_to_usize())
}
}