graph_parser.rs

use std::fs::File;
use std::io::Read;
use std::str::FromStr;

use nom::Parser;

#[repr(C)]
#[derive(Clone, Default)]
pub struct Node {
    pub edge_start: u32,
    pub num_edges: u32,
}

pub fn parse_graph(file: String) -> Result<(Vec<Node>, u32, Vec<u32>), String> {
    let mut file = File::open(file).map_err(|err| format!("Error opening input file: {}", err))?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)
        .map_err(|err| format!("Error reading input file: {}", err))?;

    let mut parser = nom::combinator::all_consuming(graph_parser);
    let (_, result) = parser
        .parse(&contents)
        .map_err(|err| format!("Parsing error: {}", err))?;

    Ok(result)
}

fn graph_parser<'a>(text: &'a str) -> nom::IResult<&'a str, (Vec<Node>, u32, Vec<u32>)> {
    // First, we find the number of nodes
    let text = nom::character::complete::multispace0(text)?.0;
    let (text, num_nodes) = nom::character::complete::digit1(text)?;

    let num_nodes = u32::from_str(num_nodes).unwrap();

    // Then, for each node there are two numbers: the index of that node's first edge and the
    // number of edges that node has
    let mut nodes = vec![];
    let mut text = text;
    for _ in 0..num_nodes {
        let ntext = nom::character::complete::multispace0(text)?.0;
        let (ntext, edge_start) = nom::character::complete::digit1(ntext)?;
        let ntext = nom::character::complete::multispace0(ntext)?.0;
        let (ntext, num_edges) = nom::character::complete::digit1(ntext)?;

        let edge_start = u32::from_str(edge_start).unwrap();
        let num_edges = u32::from_str(num_edges).unwrap();

        nodes.push(Node {
            edge_start,
            num_edges,
        });
        text = ntext;
    }

    // Next, we find the source node
    let text = nom::character::complete::multispace0(text)?.0;
    let (text, source) = nom::character::complete::digit1(text)?;

    let source = u32::from_str(source).unwrap();

    // Next, the number of edges
    let text = nom::character::complete::multispace0(text)?.0;
    let (text, num_edges) = nom::character::complete::digit1(text)?;

    let num_edges = u32::from_str(num_edges).unwrap();

    // Finally, for each edge there are two numbers: the id (i.e. what the edge goes to) and the
    // weight which is ignored (weighted BFS can't be parallelized in the same way, it would
    // require synchronization)
    let mut edges = vec![];
    let mut text = text;
    for _ in 0..num_edges {
        let ntext = nom::character::complete::multispace0(text)?.0;
        let (ntext, id) = nom::character::complete::digit1(ntext)?;
        let ntext = nom::character::complete::multispace0(ntext)?.0;
        let (ntext, _) = nom::character::complete::digit1(ntext)?;

        let id = u32::from_str(id).unwrap();

        edges.push(id);
        text = ntext;
    }

    // Consume any remaining whitespace
    let text = nom::character::complete::multispace0(text)?.0;

    Ok((text, (nodes, source, edges)))
}