Skip to content

Instantly share code, notes, and snippets.

@cocomoff cocomoff/public.rs
Created Sep 24, 2019

Embed
What would you like to do?
tekitou public
use fast_paths::InputGraph;
use fast_paths::PreparationGraph;
use fast_paths::Dijkstra;
use fast_paths::contract_node;
fn main() {
let mut input_graph = InputGraph::new();
// // 01234=ABCDE
// input_graph.add_edge_bidir(0, 2, 1);
// input_graph.add_edge_bidir(1, 2, 4);
// input_graph.add_edge_bidir(1, 3, 1);
// input_graph.add_edge_bidir(2, 4, 1);
// input_graph.add_edge_bidir(3, 4, 1);
// input_graph.freeze();
// // build and compute
// let fast_graph = fast_paths::prepare(&input_graph);
// let shortest_path = fast_paths::calc_path(&fast_graph, 0, 4);
// input_graph.add_edge(0, 2, 2);
// input_graph.add_edge(1, 2, 2);
// input_graph.add_edge(2, 3, 1);
// input_graph.add_edge(3, 4, 1);
// input_graph.add_edge(4, 5, 1);
// input_graph.add_edge(4, 6, 1);
// input_graph.add_edge(5, 4, 1);
// input_graph.add_edge(6, 7, 1);
// input_graph.add_edge(7, 8, 2);
// input_graph.add_edge(7, 9, 2);
// input_graph.freeze();
// input_graph.add_edge(0, 1, 10);
// input_graph.add_edge(1, 2, 1);
// input_graph.add_edge(0, 3, 1);
// input_graph.add_edge(3, 1, 1);
// input_graph.freeze();
// // build and compute
// let fast_graph = fast_paths::prepare(&input_graph);
// let shortest_path = fast_paths::calc_path(&fast_graph, 3, 2);
// fast_graph.get_edges_fwd_bwd();
// match shortest_path {
// Some(p) => {
// let weight = p.get_weight();
// let nodes = p.get_nodes();
// println!("{}", weight);
// println!("{:?}", nodes);
// },
// None => { }
// }
let mut g = PreparationGraph::new(5);
g.add_edge(0, 1, 1);
g.add_edge(1, 2, 1);
g.add_edge(0, 3, 1);
g.add_edge(3, 1, 5);
g.add_edge(1, 4, 4);
g.add_edge(3, 4, 3);
g.add_edge(4, 2, 1);
let mut dijkstra = Dijkstra::new(g.get_num_nodes());
contract_node(&mut g, &mut dijkstra, 1);
// there should be a shortcut 0->2, but no shortcuts 0->4, 3->2
// node 1 should be properly disconnected
// assert_eq!(0, g.get_out_edges(1).len());
// assert_eq!(0, g.get_in_edges(1).len());
// assert_eq!(2, g.get_out_edges(0).len());
// assert_eq!(2, g.get_in_edges(2).len());
/*
pub adj_node: NodeId,
pub weight: Weight,
pub center_node: NodeId,*/
for i in 0..g.get_num_nodes() {
println!("{}", i);
for m in g.get_in_edges(i) {
println!(" i {} {} {}", m.adj_node, m.weight, m.center_node)
}
for m in g.get_out_edges(i) {
println!(" o {} {} {}", m.adj_node, m.weight, m.center_node)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.