Mentions légales du service

Skip to content
Snippets Groups Projects
main.rs 4.93 KiB
Newer Older
mod undirected_graph;
use std::collections::HashMap;
use std::env;
Ricardo Buring's avatar
Ricardo Buring committed
use std::fs::File;
use std::io::{Seek, Write};
use undirected_graph::UndirectedGraph;
Ricardo Buring's avatar
Ricardo Buring committed
fn main() -> std::io::Result<()> {
    let args: Vec<String> = env::args().collect();

Ricardo Buring's avatar
Ricardo Buring committed
    if args.len() != 3 {
        eprintln!(
            "Usage: {} <number-of-spokes-in-wheel> <sparse-matrix-filename>",
            args[0]
        );
        process::exit(1);
    }

    let num_spokes_maybe: Result<usize, std::num::ParseIntError> = args[1].parse::<usize>();
    if num_spokes_maybe.is_err() {
Ricardo Buring's avatar
Ricardo Buring committed
        eprintln!("Error parsing the first argument as a natural number.");
        process::exit(1);
    }
    let num_spokes: usize = num_spokes_maybe.unwrap();

    if num_spokes < 2 {
        eprintln!("A wheel graph without tadpoles must have at least two spokes.");
        process::exit(1);
    }

Ricardo Buring's avatar
Ricardo Buring committed
    let sparse_matrix_filename: &String = &args[2];
    let sparse_matrix_file_res: Result<File, std::io::Error> = File::create(sparse_matrix_filename);
    if sparse_matrix_file_res.is_err() {
        eprintln!("Error opening file: {}", sparse_matrix_filename);
        process::exit(1);
    }
    let mut sparse_matrix_file: File = sparse_matrix_file_res.unwrap();

    let mut cocycle_graphs: Vec<UndirectedGraph> = vec![];
    let mut cocycle_graph_index: HashMap<UndirectedGraph, usize> = HashMap::new();
    let mut cocycle_graph_vertex_orbits: Vec<HashMap<usize, usize>> = vec![];

    let mut cocycle_differential_graphs: Vec<UndirectedGraph> = vec![];
    let mut cocycle_differential_graph_index: HashMap<UndirectedGraph, usize> = HashMap::new();
    let mut cocycle_differential_graph_edge_orbits: Vec<Vec<usize>> = vec![];

    // NOTE: Start with the normal form of the wheel graph.
    let wheel_graph: UndirectedGraph = UndirectedGraph::wheel_graph(num_spokes);
    let (wheel_graph_sign, wheel_graph_normal, wheel_graph_vertex_orbits, _) =
        wheel_graph.normal_form(false);
    if wheel_graph_sign == 0 {
        eprintln!("The {}-wheel graph has an automorphism that induces an odd permutation on edges, so it is equal to zero in the graph complex.", num_spokes);
        process::exit(1);
    }
    cocycle_graphs.push(wheel_graph_normal.clone());
    cocycle_graph_index.insert(wheel_graph_normal.clone(), 0);
    cocycle_graph_vertex_orbits.push(wheel_graph_vertex_orbits);

Ricardo Buring's avatar
Ricardo Buring committed
    // Write a placeholder for the header.
    let header_line_length: usize = 64;
    writeln!(sparse_matrix_file, "{}", "x".repeat(header_line_length))?;

    let mut num_nonzeros: usize = 0;
    let mut g_idx: usize = 0;
    loop {
        // dbg!(&g_idx);
        let dg_data: HashMap<UndirectedGraph, (i64, Vec<usize>)> =
            cocycle_graphs[g_idx].expanding_differential(&cocycle_graph_vertex_orbits[g_idx]);

        for (dg, (c, dg_edge_orbits)) in dg_data {
            // eprintln!("{:?}", dg);
            let dg_idx: usize = if let Some(&idx) = cocycle_differential_graph_index.get(&dg) {
                // eprintln!("old graph in differential: {}", idx);
                idx
            } else {
                let idx: usize = cocycle_differential_graphs.len();
                // eprintln!("new graph in differential: {}", idx);
                cocycle_differential_graphs.push(dg.clone());
                cocycle_differential_graph_edge_orbits.push(dg_edge_orbits.clone());
                cocycle_differential_graph_index.insert(dg.clone(), idx);
                idx
            };
            // TODO: Make the output lexicographically ordered? Strictly speaking this is not the SMS format right now.
Ricardo Buring's avatar
Ricardo Buring committed
            writeln!(sparse_matrix_file, "{} {} {}", dg_idx + 1, g_idx + 1, c)?;
            num_nonzeros += 1;

            let cg_data: HashMap<UndirectedGraph, HashMap<usize, usize>> =
                dg.contractions(&dg_edge_orbits);
            for (cg, cg_vertex_orbits) in cg_data {
                // eprintln!("{:?}", cg);
                if !cocycle_graph_index.contains_key(&cg) {
                    let idx: usize = cocycle_graphs.len();
                    // eprintln!("new graph in cocycle: {}", idx);
                    cocycle_graphs.push(cg.clone());
                    cocycle_graph_vertex_orbits.push(cg_vertex_orbits);
                    cocycle_graph_index.insert(cg.clone(), idx);
                }
            }
        }

        g_idx += 1;
        if g_idx >= cocycle_graphs.len() {
            break;
        }
    }
Ricardo Buring's avatar
Ricardo Buring committed
    writeln!(sparse_matrix_file, "0 0 0")?;
    sparse_matrix_file.rewind()?;
    let mut header_line: String = format!(
        "{} {} M",
        cocycle_differential_graphs.len(),
        cocycle_graphs.len()
    );
Ricardo Buring's avatar
Ricardo Buring committed
    header_line += &" ".repeat(header_line_length - header_line.len());
    writeln!(sparse_matrix_file, "{}", header_line)?;
        "Sparse {} x {} matrix with {} non-zero entries",
        cocycle_differential_graphs.len(),
        cocycle_graphs.len(),
        num_nonzeros
    );

    // TODO: Also output the ordered bases of graphs.
Ricardo Buring's avatar
Ricardo Buring committed

    Ok(())
Ricardo Buring's avatar
Ricardo Buring committed
}