Play with graph representations and Rust reference models.

graphs.rs

use std::fs::File;
use std::io::Read;
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
use std::default::Default;
use std::string::String;
use std::fmt;

#[derive(Debug)]
enum Color {
    White,
    Grey,
    Black,
}

impl Default for Color {
    fn default() -> Color {
        Color::White
    }
}

#[derive(Debug)]
struct Node {
    id: char,
    color: Color
}

impl Node {
    fn new(id: char) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node{
            id: id,
            color: Default::default(),
        }))
    }
}

// GRAPH BUILDER //////////////////////////////////////////////////////////////
trait GraphBuilder {
    fn add_node(&mut self, id: char);
    fn add_edge(&mut self, id_from: char, id_to: char);
    fn add_edge_with_path(&mut self, left_id: char, right_id: char, conn: char) {
        if conn == '|' || conn == '-' || conn == '>' || conn == 'v' {
            self.add_edge(left_id, right_id);
        }
        if conn == '|' || conn == '-' || conn == '<' || conn == '^' {
            self.add_edge(right_id, left_id);
        }
    }
}

// GRAPH //////////////////////////////////////////////////////////////////////
#[derive(Debug)]
struct Graph {
    nodes: HashMap<char, Rc<RefCell<Node>>>,
    edges: HashMap<char, Vec<Rc<RefCell<Node>>>>,
}

impl Graph {
    fn new() -> Graph {
        Graph {
            nodes: HashMap::new(),
            edges: HashMap::new(),
        }
    }

    fn get_node(&self, id: char) -> Rc<RefCell<Node>> {
        self.nodes.get(&id).unwrap().clone()
    }
}

impl GraphBuilder for Graph {
    fn add_node(&mut self, id: char) {
        self.nodes.insert(id, Node::new(id));
        self.edges.insert(id, Vec::new());
    }

    fn add_edge(&mut self, id_from: char, id_to: char) {
        let node_from_rc = self.nodes.get(&id_to).unwrap();
        let mut node_edges = self.edges.get_mut(&id_from).unwrap();
        node_edges.push(node_from_rc.clone());
    }
}

// EDGE LIST NODE /////////////////////////////////////////////////////////////
struct EdgeListNode {
    id: char,
    color: Color,
    edges: Vec<Edge>,
}

impl EdgeListNode {
    fn new(id: char) -> EdgeListNode {
        EdgeListNode {
            id: id,
            color: Default::default(),
            edges: Vec::new(),
        }
    }
}

impl fmt::Debug for EdgeListNode {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Node: {} Connections: {:?}", self.id, self.edges)
    }
}

// // EDGE ///////////////////////////////////////////////////////////////////////
struct Edge {
    visited: bool,
    parent: Option<char>,
    left: Rc<RefCell<EdgeListNode>>,
    right: Rc<RefCell<EdgeListNode>>,
}

impl Edge {
    fn new(left: Rc<RefCell<EdgeListNode>>, right: Rc<RefCell<EdgeListNode>>) -> Edge {
        Edge {
            visited: false,
            parent: None,
            left: left,
            right: right,
        }
    }
}

impl fmt::Debug for Edge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.right.borrow().id)
    }
}

// EDGE LIST GRAPH ////////////////////////////////////////////////////////////
#[derive(Debug)]
struct EdgeListGraph {
    nodes: HashMap<char, Rc<RefCell<EdgeListNode>>>,
}

impl EdgeListGraph {
    fn new() -> EdgeListGraph {
        EdgeListGraph {
            nodes: HashMap::new(),
        }
    }
}

impl GraphBuilder for EdgeListGraph {
    fn add_node(&mut self, id: char) {
        self.nodes.insert(id, Rc::new(RefCell::new(EdgeListNode::new(id))));
    }

    fn add_edge(&mut self, id_from: char, id_to: char) {
        let edge = Edge::new(
            self.nodes.get(&id_from).unwrap().clone(),
            self.nodes.get(&id_to).unwrap().clone()
        );
        self.nodes.get(&id_from).unwrap().borrow_mut().edges.push(edge);
    }
}

impl EdgeListGraph {
    fn min_spanning_tree(&mut self, from: char) {
        let mut stack: Vec<Rc<RefCell<EdgeListNode>>> = Vec::new();
        let mut node = self.nodes.get_mut(&from).unwrap();

        stack.push(node.clone());
        while stack.len() > 0 {
            let rc_node = stack.pop().unwrap();
            let mut node = rc_node.borrow_mut();
            node.color = Color::Grey;
            println!("Mapped: {:?}", node.id);

            for edge in node.edges.iter_mut() {
                let edge_node = edge.right.borrow();
                match edge_node.color {
                    Color::White => {
                        stack.insert(0, edge.right.clone());
                    },
                    _ => (),
                }
            }
        }
    }

    fn path(&mut self, from: char) {
        let mut node = self.nodes.get_mut(&from).unwrap().borrow_mut();
        for edge in node.edges.iter_mut() {
            println!("Edge: {:?}", edge.visited);
        }
    }
}

fn build_graph(builder: &mut GraphBuilder) -> char {
    println!("Read input...");
    let mut file = File::open("/Users/itarato/Documents/Rust/243hard.in").unwrap();
    let mut content = String::new();
    file.read_to_string(&mut content);

    let lines: Vec<&str> = content.split_terminator('\n').collect();
    let sizes_raw: Vec<&str> = lines[0].split_terminator(' ').collect();
    let w = sizes_raw[0].parse::<usize>().unwrap();
    let h = sizes_raw[1].parse::<usize>().unwrap();
    let start = lines[1].chars().collect::<Vec<char>>()[0];
    println!("W: {} H: {} Start: {}", w, h, start);

    // Add nodes.
    for y in 0..h as usize {
        let line_chars = lines[2 + y * 2].chars().collect::<Vec<char>>();
        for x in 0..w as usize {
            let id = line_chars[x * 4];
            builder.add_node(id);
        }
    }

    // Add edges.
    for i in 0..h as usize {
        for j in 0..w as usize {
            if j < w - 1 {
                let line_chars = lines[2 + i * 2].chars().collect::<Vec<char>>();
                let left_id = line_chars[j * 4];
                let right_id = line_chars[(j + 1) * 4];
                let conn = line_chars[j * 4 + 2];
                builder.add_edge_with_path(left_id, right_id, conn);
                println!("Read: {} {} {}", left_id, conn, right_id);
            }

            if i < h - 1 {
                let left_id = lines[2 + i * 2].chars().collect::<Vec<char>>()[j * 4];
                let right_id = lines[2 + (i + 1) * 2].chars().collect::<Vec<char>>()[j * 4];
                let conn = lines[2 + (i + 1) * 2 - 1].chars().collect::<Vec<char>>()[j * 4];
                builder.add_edge_with_path(left_id, right_id, conn);
                println!("Read: {} {} {}", left_id, conn, right_id);
            }
        }
    }

    start
}

fn main() {
    // let mut builder = Graph::new();
    let mut builder = EdgeListGraph::new();
    let start = build_graph(&mut builder);
    println!("{:?}", builder);

    builder.min_spanning_tree(start);
}