DEV Community

loading...

Discussion on: Write better code: Day 8 - Shortest route

Collapse
idanarye profile image
Idan Arye

Isn't this just a simple BFS?

play.rust-lang.org/?version=stable...

The function(+data type used for search) is:

#[derive(Debug)]
struct NoRoute;

#[derive(Debug)]
struct NodePath<'a> {
    node: &'a str,
    prev: Option<Rc<NodePath<'a>>>,
}

impl<'a> NodePath<'a> {
    fn new(node: &str) -> NodePath {
        NodePath { node, prev: None }
    }

    fn resolve(&self) -> Vec<&'a str> {
        let mut result = vec![self.node];
        let mut path_node = &self.prev;
        loop {
            path_node = if let Some(path_node) = path_node {
                result.insert(0, path_node.node);
                &path_node.prev
            } else {
                return result;
            }
        }
    }
}

fn send_a_message<'a>(
    network: &'a HashMap<String, HashSet<String>>,
    sender: &'a str,
    receiver: &'a str,
) -> Result<Vec<&'a str>, NoRoute> {
    let _ = (network, sender, receiver);
    let mut tried = HashSet::new();
    let mut to_try = VecDeque::new();
    to_try.push_back(Rc::new(NodePath::new(sender)));

    while let Some(path_node) = to_try.pop_front() {
        if path_node.node == receiver {
            return Ok(path_node.resolve());
        }
        let routes = if let Some(routes) = network.get(path_node.node) {
            routes
        } else {
            continue;
        };
        for next_node in routes.iter() {
            if tried.contains(next_node) {
                continue;
            }
            tried.insert(next_node);
            to_try.push_back(Rc::new(NodePath {
                node: next_node,
                prev: Some(path_node.clone()),
            }));
        }
    }
    Err(NoRoute)
}
Collapse
arjunrajkumar profile image
Arjun Rajkumar Author

Nice. Yes it is.