README.md

Least Expensive Flight Cost Calculator

A simple flight cost calculator done for an honors conversion with Gregory Johnson in CSE 2500 at UConn.

This was my first venture into Rust. It will be very evident in this code that I fought with the borrow checker. If anyone at UConn knows Rust well and would like to show me how this code could be better, please send me an email. I will give you cookies in return. :)

Setup

Make sure Rust is installed.

$ cargo run

Release

Binaries can be downloaded from the release page. Alternatively, the below can be copied to play.rust-lang.org.

use std::collections::HashMap;
use std::collections::HashSet;

pub struct Graph {
    vertices: HashMap<String, HashMap<String, usize>>
}

impl Graph {
    pub fn new() -> Graph {
        Graph { vertices: HashMap::new() }
    }

    pub fn add_vertex(&mut self, name: &str) {
        let name = name.to_string();
        // This can be improved to allow for generic types rather than using strings as vertex
        // identifiers
        self.vertices.insert(name.to_string(), HashMap::new());
    }

    pub fn add_edge(&mut self, u: &str, v: &str, weight: usize) {
        let u = u.to_string();
        let v = v.to_string();

        self.vertices.get_mut(&u).unwrap().insert(v.clone(), weight);
        self.vertices.get_mut(&v).unwrap().insert(u, weight);
    }

    pub fn display(&self) {
        for (vertex, neighbors) in &self.vertices {
            println!("{}", vertex);
            for (neighbor, weight) in neighbors {
                println!("    {}: {}", neighbor, weight)
            }
        }
    }

    pub fn total_weight_of_path(&self, path: &[&str]) -> usize {
        (0..path.len()-1).fold(0, |sum, i|
            sum + self.vertices.get(path[i]).unwrap().get(path[i+1]).unwrap().clone())
    }

    pub fn shortest_path(&self, a: &str, z: &str) -> Vec<String> {
        let mut tree = HashMap::new();
        let mut dist: HashMap<String, usize> = HashMap::new();
        let mut unvisited: HashSet<String> = HashSet::new();
        for key in self.vertices.keys() {
            unvisited.insert(key.to_string());
        }

        dist.insert(a.to_string(), 0);

        while unvisited.contains(z) {
            // We need to grab the unvisited node with the smallest distance. This is typically
            // done with a priority queue, but we'll do it with a linear time search instead to
            // avoid pulling in another dependency and making this proof of concept more complex.
            let mut to_visit: HashSet<String> = dist.keys().cloned().collect();
            to_visit = to_visit.intersection(&unvisited).cloned().collect();

            let mut u = &"".to_string();
            for v in &to_visit {
                if u == "" {
                    u = v;
                }

                if dist.contains_key(v) && (dist.get(v).unwrap().clone() < dist.get(u).unwrap().clone()) {
                    u = v;
                }
            }

            unvisited.remove(u);

            for (v, weight) in self.vertices.get(u).unwrap() {
                if !unvisited.contains(v) { continue };

                let alt = dist.get(u).unwrap().clone() + weight;
                if !dist.contains_key(v) || (alt < dist.get(v).unwrap().clone()) {
                    dist.insert(v.to_string(), alt);
                    tree.insert(v.to_string(), u.to_string());
                }
            }
        }

        let mut path: Vec<String> = Vec::new();
        let mut current: &str = z;
        while current != a {
            path.push(current.to_string());
            current = tree.get(current).unwrap();
        }
        path.push(a.to_string());
        path.reverse();

        path
    }
}

fn main() {
    let cities = [
        "San Francisco",
        "Denver",
        "Chicago",
        "Los Angeles",
        "Boston",
        "Atlanta",
        "Orlando"
    ];

    let costs = [
        ("San Francisco", "Boston", 350),
        ("San Francisco", "Denver", 140),
        ("San Francisco", "Los Angeles", 100),
        ("Denver", "Chicago", 110),
        ("Denver", "Los Angeles", 85),
        ("Chicago", "Boston", 125),
        ("Chicago", "Atlanta", 200),
        ("Los Angeles", "Boston", 365),
        ("Boston", "Atlanta", 145),
        ("Boston", "Orlando", 220),
        ("Atlanta", "Orlando", 80)
    ];

    let mut flights = Graph::new();

    for city in &cities {
        flights.add_vertex(city);
    }

    for cost in &costs {
        flights.add_edge(cost.0, cost.1, cost.2)
    }

    let path = flights.shortest_path("Los Angeles", "Boston");
    println!("Best path from {} to {}: {}", "Los Angeles", "Boston", path.join(", "));

    let path = flights.shortest_path("San Francisco", "Orlando");
    println!("Best path from {} to {}: {}", "San Francisco", "Orlando", path.join(", "));

    let path = flights.shortest_path("Denver", "Atlanta");
    println!("Best path from {} to {}: {}", "Denver", "Atlanta", path.join(", "));
}