S4-PRG-Rust 05_Data — Organisation des donnéesLoading s4prg_rust_05_data...
S4-PRG-Rust 05_Data — Organisation des donnéesrustup doc --std 'std::boxed::Box') pour représenter le membre gauche de l'opération à réaliser,
pub fn new(expr: &str) -> Result<Self, Box<dyn std::error::Error>> { fn inner<'a>( words: &mut impl Iterator<Item = &'a str> ) -> Result<ExprNode, Box<dyn std::error::Error>> { match words.next() { Some(word) => { if let Ok(value) = word.parse::<i32>() { Ok(ExprNode::Value(value)) } else { match word { "+" | "-" | "*" | "/" => { let operation = char::from(word.as_bytes()[0]); let left = Box::new(inner(words)?); let right = Box::new(inner(words)?); Ok(ExprNode::BinOp { operation, left, right, }) } _ => { Err(format!( "unexpected {:?} in expression", word ))? // Ok(ExprNode::Var(word.to_string())) } } } } None => Err("missing word in expression")?, } } // let mut words = expr.split_whitespace(); let expr = inner(&mut words)?; if words.next().is_some() { Err("remaining words after expression")? } Ok(expr) }
rustup doc --std 'std::collections::HashMap'.
FnMut(usize) -> bool, qui sera invoquée sur chaque nœud visité,
rustup doc --std 'std::collections::VecDeque'.
rustup doc --std 'std::option::Option'.
for org in 0..cities.len() { for dst in 0..cities.len() { s4::bm_call!(t, graph.plan_dfs(org, dst)); // dans un cas s4::bm_call!(t, graph.plan_dijkstra(org, dst)); // dans l'autre } }
visited: Option<&mut [bool]>et complétez l'algorithme de cette façon, juste avant la reconstitution de path :
if let Some(visited) = visited { visited.fill(true); for node in to_visit.into_iter() { visited[node] = false; } }
let mut visited = vec![false; graph.nodes()];
Some(&mut visited).
Some(&visited)pour le paramètre visited de l'appel à roadmap::draw_cities_and_roads().
heuristics: Option<&[f64]>et complétez l'algorithme de cette façon pour constituer le poids qui est susceptible de devenir min_weight :
let h = if let Some(heuristics) = heuristics { heuristics[node] } else { 0.0 }; let w = weights[node] + h;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#[allow(unused_imports)] use std::collections::{HashMap, VecDeque};
#[allow(unused_imports)] use crate::{roadmap, s4};
pub const SECTIONS: &[fn()] = &[section_1, section_2];
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/// A structure made to represent a part of an arithmetic expressions. /// /// Combining many of these structures enables the representation of an /// expression made of several values and opérations. /// /// # Examples /// ``` /// use s4prg::chapter_5::ExprNode; /// use std::collections::HashMap; /// let mut vars = HashMap::new(); /// vars.insert("a".to_owned(), 10); /// let expr = ExprNode::BinOp { /// operation: '*', /// left: Box::new(ExprNode::Var("a".to_owned())), /// right: Box::new(ExprNode::BinOp { /// operation: '+', /// left: Box::new(ExprNode::Value(3)), /// right: Box::new(ExprNode::Value(5)), /// }), /// }; /// assert_eq!(expr.show(), "(a * (3 + 5))"); /// assert_eq!(expr.eval(&vars), 80); /// ``` #[derive(Debug, Clone)] pub enum ExprNode { Value(i32), Var(String), BinOp { operation: char, left: Box<ExprNode>, right: Box<ExprNode>, }, }
impl ExprNode { pub fn new(expr: &str) -> Result<Self, Box<dyn std::error::Error>> { fn inner<'a>( words: &mut impl Iterator<Item = &'a str> ) -> Result<ExprNode, Box<dyn std::error::Error>> { match words.next() { Some(word) => { if let Ok(value) = word.parse::<i32>() { Ok(ExprNode::Value(value)) } else { match word { "+" | "-" | "*" | "/" => { let operation = char::from(word.as_bytes()[0]); let left = Box::new(inner(words)?); let right = Box::new(inner(words)?); Ok(ExprNode::BinOp { operation, left, right, }) } _ => { // Err(format!( // "unexpected {:?} in expression", // word // ))? Ok(ExprNode::Var(word.to_string())) } } } } None => Err("missing word in expression")?, } } // let mut words = expr.split_whitespace(); let expr = inner(&mut words)?; if words.next().is_some() { Err("remaining words after expression")? } Ok(expr) }
pub fn show(&self) -> String { match self { ExprNode::Value(value) => format!("{}", value), ExprNode::Var(name) => name.clone(), ExprNode::BinOp { operation, left, right, } => { format!("({} {} {})", left.show(), operation, right.show()) } } }
pub fn eval( &self, vars: &HashMap<String, i32>, ) -> i32 { match self { ExprNode::Value(value) => *value, ExprNode::Var(name) => *vars.get(name).unwrap_or(&0), ExprNode::BinOp { operation, left, right, } => { let left_value = left.eval(vars); let right_value = right.eval(vars); match operation { '+' => left_value + right_value, '-' => left_value - right_value, '*' => left_value * right_value, '/' => left_value / right_value, _ => unreachable!(), } } } } }
fn section_1() { println!("\n~~~~ chapter 5, section 1 ~~~~"); let mut vars = HashMap::new(); vars.insert("a".to_owned(), 10); vars.insert("t".to_owned(), 20); vars.insert("xy".to_owned(), 30); println!("vars: {:?}", vars); // let expr1 = ExprNode::Value(10); println!("expr1: {:?}", expr1); println!("expr1: {:?} ~~> {}", expr1.show(), expr1.eval(&vars)); let expr2 = ExprNode::BinOp { operation: '+', left: Box::new(ExprNode::Value(3)), right: Box::new(ExprNode::Value(5)), }; println!("expr2: {:?}", expr2); println!("expr2: {:?} ~~> {}", expr2.show(), expr2.eval(&vars)); let expr3 = ExprNode::BinOp { operation: '*', left: Box::new(expr1), right: Box::new(expr2), }; println!("expr3: {:?}", expr3); println!("expr3: {:?} ~~> {}", expr3.show(), expr3.eval(&vars)); let expr4 = ExprNode::BinOp { operation: '*', left: Box::new(ExprNode::Var("a".to_owned())), right: Box::new(ExprNode::BinOp { operation: '+', left: Box::new(ExprNode::Value(3)), right: Box::new(ExprNode::Value(5)), }), }; println!("expr4: {:?}", expr4); println!("expr4: {:?} ~~> {}", expr4.show(), expr4.eval(&vars)); // for expr in [ "- xy + * a 5 / t 3", "- xy + * a 5 / t", "- xy + * a 5 / t 3 8", ] { match ExprNode::new(expr) { Ok(expr) => { println!("{:?} ~~> {}", expr.show(), expr.eval(&vars)); } Err(e) => println!("{:?} ~~> {}", expr, e), } } }
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#[derive(Debug, Clone)] pub struct Graph { edges: Vec<Vec<Option<f64>>>, }
impl Graph { pub fn new(nodes: usize) -> Self { Self { edges: vec![vec![None; nodes]; nodes], } }
pub fn nodes(&self) -> usize { self.edges.len() }
pub fn edge( &self, origin: usize, destination: usize, ) -> Option<f64> { self.edges[origin][destination] }
pub fn set_edge( &mut self, origin: usize, destination: usize, weight: Option<f64>, ) { if let Some(weight) = weight { assert!(weight > 0.0, "invalid weight {:?}", weight); assert!( origin != destination, "self referential edge {}", origin ); } self.edges[origin][destination] = weight; }
pub fn breadth_first<F>( &self, origin: usize, mut fnct: F, ) where F: FnMut(usize) -> bool, { let mut visited = vec![false; self.nodes()]; let mut to_visit = VecDeque::new(); to_visit.push_back(origin); while let Some(node) = to_visit.pop_front() { if !visited[node] { visited[node] = true; if !fnct(node) { break; } let edges = &self.edges[node]; for (edge, weight) in edges.iter().enumerate() { if weight.is_some() { to_visit.push_back(edge); } } } } }
/// Plans a traversal from an origin to a destination. /// /// This version uses a recursive depth-first-search solution. /// It return the successive node indices of the traversal /// as well as its total weight. /// /// #Examples /// ``` /// use s4prg::roadmap; /// use s4prg::chapter_5::Graph; /// let (cities, roads) = /// roadmap::load_cities_and_roads("map_16.csv").unwrap(); /// let mut graph = Graph::new(cities.len()); /// for r in roads.iter() { /// graph.set_edge(r.origin, r.destination, Some(r.length)); /// } /// let org = cities.iter().position(|c| c.name == "Bourges").unwrap(); /// let dst = cities.iter().position(|c| c.name == "Pau").unwrap(); /// let (path, _dist) = graph.plan_dfs(org, dst); /// assert_eq!(cities[path[0]].name, "Bourges"); /// assert_eq!(cities[path[1]].name, "Tulle"); /// assert_eq!(cities[path[2]].name, "Toulouse"); /// assert_eq!(cities[path[3]].name, "Pau"); /// ``` pub fn plan_dfs( &self, origin: usize, destination: usize, ) -> (Vec<usize>, f64) { fn recurse( graph: &Graph, origin: usize, destination: usize, visited: &mut [bool], ) -> (Vec<usize>, f64) { if origin == destination { return (vec![origin], 0.0); } let mut best_path = Vec::new(); let mut best_path_weight = f64::MAX; for (e, edge) in graph.edges[origin].iter().enumerate() { if let Some(w) = edge { if !visited[e] { visited[e] = true; let (path, mut path_weight) = recurse(graph, e, destination, visited); if !path.is_empty() { path_weight += w; if path_weight < best_path_weight { best_path = path; best_path.push(origin); best_path_weight = path_weight; } } visited[e] = false; } } } (best_path, best_path_weight) } let mut visited = vec![false; self.nodes()]; visited[origin] = true; let (mut path, weight) = recurse(self, origin, destination, &mut visited); path.reverse(); (path, weight) }
/// Plans a traversal from an origin to a destination. /// /// This version uses Dijkstra's algorithm. /// Providing heuristics for each node to reach the destination, /// turns this algorithm into A*. /// It return the successive node indices of the traversal /// as well as its total weight. /// /// #Examples /// ``` /// use s4prg::roadmap; /// use s4prg::chapter_5::Graph; /// let (cities, roads) = /// roadmap::load_cities_and_roads("map_16.csv").unwrap(); /// let mut graph = Graph::new(cities.len()); /// for r in roads.iter() { /// graph.set_edge(r.origin, r.destination, Some(r.length)); /// } /// let org = cities.iter().position(|c| c.name == "Bourges").unwrap(); /// let dst = cities.iter().position(|c| c.name == "Pau").unwrap(); /// let (path, _dist) = graph.plan_dijkstra(org, dst, None, None); /// assert_eq!(cities[path[0]].name, "Bourges"); /// assert_eq!(cities[path[1]].name, "Tulle"); /// assert_eq!(cities[path[2]].name, "Toulouse"); /// assert_eq!(cities[path[3]].name, "Pau"); /// ``` pub fn plan_dijkstra( &self, origin: usize, destination: usize, heuristics: Option<&[f64]>, visited: Option<&mut [bool]>, ) -> (Vec<usize>, f64) { if origin == destination { return (vec![origin], 0.0); } let mut previous = vec![None; self.nodes()]; let mut to_visit = Vec::from_iter(0..self.nodes()); let mut weights = vec![f64::MAX; self.nodes()]; weights[origin] = 0.0; let mut visited_idx = Some(origin); while let Some(idx) = visited_idx.take() { let visited_node = to_visit.swap_remove(idx); if visited_node == destination { break; } let visited_weight = weights[visited_node]; let mut min_weight = f64::MAX; for (pos, &node) in to_visit.iter().enumerate() { if let Some(weight) = self.edges[visited_node][node] { if visited_weight + weight < weights[node] { weights[node] = visited_weight + weight; previous[node] = Some(visited_node); } } let h = if let Some(heuristics) = heuristics { heuristics[node] } else { 0.0 }; let w = weights[node] + h; if w < min_weight { min_weight = w; visited_idx = Some(pos); } } } if let Some(visited) = visited { visited.fill(true); for node in to_visit.into_iter() { visited[node] = false; } } let mut path = Vec::with_capacity(self.nodes()); if previous[destination].is_some() { let mut prev = destination; path.push(prev); while prev != origin { prev = previous[prev].unwrap(); path.push(prev); } path.reverse(); } (path, weights[destination]) } }
fn section_2() { println!("\n~~~~ chapter 5, section 2 ~~~~"); for map in ["map_16", "map_96"] { let (cities, roads) = roadmap::load_cities_and_roads(format!("{}.csv", map)).unwrap(); // println!("cities: {:?}", cities); // println!("roads: {:?}", roads); roadmap::draw_cities_and_roads( &cities, &roads, None, None, format!("{}.svg", map), ) .unwrap(); // let mut graph = Graph::new(cities.len()); for r in roads.iter() { graph.set_edge(r.origin, r.destination, Some(r.length)); } for origin in 0..graph.nodes() { for destination in 0..graph.nodes() { if let Some(weight) = graph.edge(origin, destination) { println!( "{:?} ~~~({})~~> {:?}", cities[origin].name, weight, cities[destination].name ); } } } // let org_name = "Bourges"; if let Some(org) = cities.iter().position(|c| c.name == org_name) { let mut names = Vec::new(); graph.breadth_first(org, |c| { names.push(cities[c].name.as_str()); true }); println!("breadth first:\n• {}", names.join(", ")); for dst_name in ["Quimper", "Pau", "Nice"] { if let Some(dst) = cities.iter().position(|c| c.name == dst_name) { if cities.len() <= 20 { let (path, weight) = graph.plan_dfs(org, dst); let names = Vec::from_iter( path.iter().map(|c| cities[*c].name.as_str()), ); println!( "plan_dfs {}:\n• {}", weight, names.join(", ") ); roadmap::draw_cities_and_roads( &cities, &roads, Some(&path), None, format!( "{}_dfs_{}_{}.svg", map, org_name, dst_name ), ) .unwrap(); } // let mut visited = vec![false; graph.nodes()]; let (path, weight) = graph.plan_dijkstra( org, dst, None, Some(&mut visited), ); let names = Vec::from_iter( path.iter().map(|c| cities[*c].name.as_str()), ); println!("Dijkstra {}:\n• {}", weight, names.join(", ")); roadmap::draw_cities_and_roads( &cities, &roads, Some(&path), Some(&visited), format!( "{}_dijkstra_{}_{}.svg", map, org_name, dst_name ), ) .unwrap(); // let heuristics = Vec::from_iter( cities .iter() .map(|c| c.direct_distance(&cities[dst])), ); let (path, weight) = graph.plan_dijkstra( org, dst, Some(&heuristics), Some(&mut visited), ); let names = Vec::from_iter( path.iter().map(|c| cities[*c].name.as_str()), ); println!("A* {}:\n• {}", weight, names.join(", ")); roadmap::draw_cities_and_roads( &cities, &roads, Some(&path), Some(&visited), format!( "{}_astar_{}_{}.svg", map, org_name, dst_name ), ) .unwrap(); } } } // let bm = s4::Benchmark::new(format!("plan {}", map)); if cities.len() <= 20 { bm.record("dfs", 2.0, |t| { for org in 0..cities.len() { for dst in 0..cities.len() { s4::bm_call!(t, graph.plan_dfs(org, dst)); } } }); } bm.record("Dijkstra", 2.0, |t| { for org in 0..graph.nodes() { for dst in 0..graph.nodes() { s4::bm_call!( t, graph.plan_dijkstra(org, dst, None, None) ); } } }); bm.record("A*", 2.0, |t| { for org in 0..graph.nodes() { for dst in 0..graph.nodes() { let heuristics = Vec::from_iter( cities .iter() .map(|c| c.direct_distance(&cities[dst])), ); s4::bm_call!( t, graph.plan_dijkstra( org, dst, Some(&heuristics), None ) ); } } }); println!("{}", bm); } }
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#[allow(unused_imports)] use s4prg::{chapter_5::*, roadmap, s4};
#[test] fn chapter_5_section_2() { for map in ["map_16", "map_96"] { let (cities, roads) = roadmap::load_cities_and_roads(format!("{}.csv", map)).unwrap(); let mut graph = Graph::new(cities.len()); for r in roads.iter() { graph.set_edge(r.origin, r.destination, Some(r.length)); } for org in 0..graph.nodes() { for dst in 0..graph.nodes() { let (path1, weight1) = graph.plan_dijkstra(org, dst, None, None); let heuristics = Vec::from_iter( cities.iter().map(|c| c.direct_distance(&cities[dst])), ); let (path2, weight2) = graph.plan_dijkstra(org, dst, Some(&heuristics), None); assert_eq!(path1, path2); s4::assert_float_eq!(weight1, weight2, 0.001); if cities.len() <= 20 { let (path3, weight3) = graph.plan_dfs(org, dst); assert_eq!(path1, path3); s4::assert_float_eq!(weight1, weight3, 0.001); } } } } }
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~