Cycles - Gerwin Dox

chooser.rs

use std::collections::HashSet;
use std::iter::FromIterator;

pub fn reduce(cycles : &Vec<Vec<usize>>, node_size : usize) -> Vec<usize> {
    let mut set : Vec<HashSet<usize>> = cycles.iter().map(|v| HashSet::from_iter(v.iter().map(|&a| a))).collect();
    let mut importance : Vec<usize> = set.iter().map(|v| v.len()).collect();
    let mut counter = node_size;
    let mut res = Vec::new();
    while counter > 0 {
        let max_index = importance.iter().enumerate().map(|(n, &s)| (s, n)).max().unwrap().1;
        counter -= set[max_index].len();
        res.push(max_index);
        for (n, mut s) in set.iter_mut().enumerate() {
            for i in &cycles[max_index] {
                if s.remove(i) {
                    importance[n] -= 1;
                }
            }
        }
    }
    res
}

cycle.rs

use super::matrix::Matrix;
use super::matrix::hm;
use std::collections::HashSet;
use std::thread;
use super::cyclefinder::CycleFinder;
use super::chooser::reduce;
pub const MAX_LENGTH : hm = 750;


pub fn test_cycle() -> Result<(), ::std::io::Error> {
    //let matrix = Matrix::from_vector(Some(0).into_iter().cycle().enumerate().map(|(n, _)| n).map(|n| if n % 10 == 1 || n==72 {Some(1)} else {None}).take(81).collect());
    let matrix = Matrix::from_csv("../Case-5-Cycling-Nodes-instance-2.csv")?;
    //println!("{:?}", matrix);
    let q = matrix.into_connection_list();
    //let q = vec![vec![1,4],vec![0,2],vec![1,3], vec![2,4], vec![3, 0]];
    let mut res = CycleFinder::yield_circuits(&q, &matrix);
    let res2 = reduce(&res, matrix.get_size());
    println!("{}", res2.len());
    let out : Vec<Vec<_>> = res2.into_iter().map(|v| res[v].iter().map(|&x| x + 1).collect()).collect();
    use std::fs;
    use std::io::Write;
    let mut file = fs::File::create("output.txt").unwrap();
    for i in out {
        for j in i {
            write!(file, "{} ", j);
        }
        write!(file, "\n");

    }

    Ok(())
}

cyclefinder.rs

use std::collections::HashSet;
use super::matrix::hm;
use super::matrix::Matrix;
use super::cycle::MAX_LENGTH;

pub struct CycleFinder<'a>  {
    stack : Vec<usize>,
    B : Vec<HashSet<usize>>,
    blocked : Vec<bool>,
    s : usize,
    res : Vec<Vec<Vec<usize>>>,
    matrix : &'a Matrix,
    max_length : usize,
    counter : usize,
}

pub const MAX_STEPS : usize = 1000000;

impl<'a> CycleFinder<'a> {
    fn add_to_res(&mut self, path : Vec<usize>) {
        if path.len() > self.max_length {
            self.res[self.s].clear();
            self.max_length = path.len();
        }
        if path.len() == self.max_length {
            self.res[self.s].push(path);
        }
    }

    pub fn yield_circuits(adjacency_list : &Vec<Vec<usize>>, matrix : &Matrix) -> Vec<Vec<usize>> {
        let size = adjacency_list.len();
        let mut cyclefinder = CycleFinder {
            stack : Vec::new(),
            B : (0..size).map(|_| HashSet::new()).collect(),
            blocked : vec![false; size],
            s : 0,
            res : (0..size).map(|_| Vec::new()).collect(),
            matrix : matrix,
            max_length : 0,
            counter : 0,
        };
        cyclefinder.algorithm(&adjacency_list.clone());
        cyclefinder.res.into_iter().flat_map(|k| k.into_iter()).collect()
    }

    fn unblock(&mut self, u : usize) {
        self.blocked[u] = false;
        let mut future = Vec::new();
        for &w in &self.B[u] {
            if self.blocked[w] {
                future.push((w, true));
            }
            else
            {
                future.push((w, false));
            }
        }
        for (w, b) in future {
            self.B[u].remove(&w);
            if b {
                self.unblock(w);
            }
        }
    }

    fn circuit(&mut self, Ak : &Vec<Vec<usize>>, v : usize, length : hm) -> bool {
        self.counter += 1;
        let mut f = false;
        let new_length = if let Some((&last, _)) = self.stack.split_last() {
            length + self.matrix.get_distance(last, v).unwrap()
        } else {
            length
        };
        if new_length > MAX_LENGTH {return false};
        self.stack.push(v);

        self.blocked[v] = true;
        for &w in &Ak[v] {
            if w == self.s {
                if new_length + self.matrix.get_distance(v, w).unwrap() <= MAX_LENGTH
                {
                    let x = self.stack.clone();
                    self.add_to_res(x);
                    f = true;
                }
            }
            else if !self.blocked[w] {
                if self.counter < MAX_STEPS && self.circuit(Ak, w, new_length) {
                    f = true;
                }
            }
        }
        if f {self.unblock(v);}
        else {
            for &w in &Ak[v] {
                self.B[w].insert(v);
            }
        }
        assert!(self.stack.pop() == Some(v));
        f
    }

    pub fn algorithm(&mut self, Ak : &Vec<Vec<usize>>) {
        while self.s < Ak.len() {
            self.max_length = 0;
            self.counter = 0;
            let local_s = self.s;
            self.circuit(Ak, local_s, 0);
            println!("{} -> {}", self.s, self.max_length);
            self.s+=1;
        }
    }

}

main.rs

mod matrix;
mod cycle;
mod cyclefinder;
mod chooser;

fn main() {
    println!("Hello, world!");
    cycle::test_cycle();
}

matrix.rs

use std::io;

pub type hm = i64;

#[derive(Debug)]
pub struct Matrix {
    data : Vec<Option<hm>>,
    size : usize,
}

impl Matrix{
    pub fn new() -> Matrix {
        Matrix {
            data : Vec::new(),
            size : 0,
        }
    }
    pub fn from_vector(vector : Vec<Option<hm>>) -> Matrix {
        let mut res = Matrix {
            size : (vector.len() as f64).sqrt() as usize,
            data : vector,
        };
        for i in 0..res.size {
            *res.get_mut_distance(i, i) = None;
        }
        res

    }

    pub fn from_csv(filename : &str) -> Result<Matrix, io::Error> {
        use std::fs;
        use std::io::Read;
        use std::io::Write;
        let mut file = fs::File::open(filename).unwrap();
        let mut contents = Vec::new();
        file.read_to_end(&mut contents);
        let contents_str : String= contents.into_iter().map(|a| a as char).collect();
        let per_array = contents_str.split('\n').into_iter().skip(1);
        let per_number : Vec<Option<hm>> = per_array.flat_map(|a| a.split(',').into_iter().skip(1)).map(|a| a.parse::<hm>().ok()).collect();
        Ok(Matrix::from_vector(per_number))
    }
    pub fn get_distance(&self, x : usize, y : usize) -> Option<hm> {
        if x >= self.size {
            None
        }
        else if y >= self.size {
            None
        }
        else {
            //unsafe{self.data.get_unsafe(x * self.size + y)}
            self.data[x * self.size + y]
        }
    }

    fn get_mut_distance(&mut self, x : usize, y : usize) -> &mut Option<hm> {
        &mut self.data[x*self.size + y]
    }

    pub fn into_connection_list(&self) -> Vec<Vec<usize>> {
        let mut res = Vec::new();
        for i in 0..self.size {
            let mut q = Vec::new();
            for j in 0..self.size {
                if self.get_distance(i, (i + j)%self.get_size()).is_some() {
                    q.push((i + j)%self.get_size());
                }
            }
            res.push(q);
        }
        res
    }
    pub fn get_size(&self) -> usize {
        self.size
    }
}