path: root/graph-checker/src/graph.rs

use std::collections::{HashMap, HashSet};
use std::fmt;

#[derive(Clone, PartialEq, Eq)]
pub struct Graph {
    pub size: usize,
    pub matrix: Vec<Vec<u32>>,
}

#[derive(Debug)]
pub struct GraphProfile {
    g6: String,
    stats: HashMap<String, bool>,
}

impl GraphProfile {
    pub fn new(g6: &String) -> Self {
        Self {
            g6: g6.clone(),
            stats: HashMap::new(),
        }
    }

    pub fn insert(&mut self, key: String, value: bool) {
        self.stats.insert(key, value);
    }
}

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Cutset {
    pub cardinality: usize,
    pub vertices: Vec<u32>,
    pub graph: Graph,
}

impl fmt::Display for Graph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for row in 0..self.size {
            for col in 0..self.size {
                write!(f, "{}", self.matrix[row][col])?;
                if col < self.size - 1 {
                    write!(f, " ")?;
                }
            }
            if row < self.size - 1 {
                write!(f, "\n")?;
            }
        }
        return Ok(());
    }
}

impl fmt::Debug for Graph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "\n")?;
        for row in 0..self.size {
            for col in 0..self.size {
                write!(f, "{}", self.matrix[row][col])?;
                if col < self.size - 1 {
                    write!(f, " ")?;
                }
            }
            if row < self.size - 1 {
                write!(f, "\n")?;
            }
        }
        return Ok(());
    }
}

fn trim_cutset(cutset: &Cutset) -> Graph {
    let mut mat = vec![vec![0; cutset.cardinality]; cutset.cardinality];

    let mut i = 0;
    for vi in 0..cutset.graph.size {
        if cutset.vertices[vi] == 0 {
            continue;
        }
        let mut j = 0;
        for vj in 0..cutset.graph.size {
            if cutset.vertices[vj] == 0 {
                continue;
            }
            mat[i][j] = cutset.graph.matrix[vi][vj];
            j += 1;
        }
        i += 1;
    }
    return Graph {
        size: cutset.cardinality,
        matrix: mat,
    };
}

fn iterate(n: usize) -> Vec<Vec<u32>> {
    let mut components = Vec::new();

    let mut v: Vec<u32> = vec![0; n];
    loop {
        let mut sum: usize = 0;
        for i in &v {
            sum += *i as usize;
        }

        if sum == v.len() {
            break;
        }

        let mut k = 0;
        for i in 0..v.len() {
            if v[i] == 1 {
                v[i] = 0;
            } else {
                k = i;
                break;
            }
        }
        v[k] = 1;
        components.push(v.clone());
    }

    return components;
}

impl Graph {
    pub fn to_g6(&self) -> String {
        let mut g = vec![0; self.size];
        for i in 0..self.size {
            let mut row: u32 = 0;
            for j in 0..self.size {
                row |= self.matrix[i][j] << (31 - j);
            }
            g[i] = row;
        }

        crate::geng::get_g6(g, self.size)
    }

    pub fn from_g6(line: &String) -> Graph {
        let mut chars: Vec<u8> = Vec::new();
        for character in line.chars() {
            chars.push((character as i32 - 63) as u8);
        }
        let size = chars[0] as usize;
        let bytes = &chars[1..];

        let mut matrix: Vec<Vec<u32>> = vec![vec![0; size]; size];
        let mut i = 0;
        for col in 1..size {
            for row in 0..col {
                let bit: u32 = (bytes[i / 6] >> (5 - i % 6) & 1) as u32;
                matrix[row][col] = bit;
                matrix[col][row] = bit;
                i += 1;
            }
        }
        return Graph { size, matrix };
    }

    pub fn degree(&self, vertex: usize) -> usize {
        let mut sum: usize = 0;
        for i in &self.matrix[vertex] {
            sum += if *i == 0 { 0 } else { 1 } as usize;
        }
        return sum;
    }

    pub fn min_degree(&self) -> usize {
        let mut min = self.size + 1;
        for i in 0..self.size {
            let d = self.degree(i);
            if d < min {
                min = d;
            }
        }
        return min;
    }

    pub fn degree_vector(&self) -> Vec<usize> {
        let mut set = HashSet::new();
        for i in 0..self.size {
            let d = self.degree(i);
            set.insert(d);
        }
        let mut vec = Vec::from_iter(set.into_iter());
        vec.sort_by(|a, b| b.cmp(a));
        return vec;
    }

    pub fn get_closure_traced(&self, trace_steps: bool) -> Graph {
        let mut step = if trace_steps { 2 } else { 1 };

        let mut closure = self.clone();
        for _ in 0..(closure.size * closure.size) {
            let mut changed = false;
            for row in 0..closure.size {
                for col in 0..closure.size {
                    if row == col || closure.matrix[row][col] != 0 {
                        continue;
                    }
                    let sum = closure.degree(row) + closure.degree(col);
                    if sum >= closure.size {
                        closure.matrix[row][col] = step;
                        if trace_steps {
                            step += 1;
                        }
                        changed = true;
                    }
                }
            }
            if !changed {
                break;
            }
        }
        return closure;
    }

    pub fn cutsets(&self) -> Vec<Cutset> {
        let mut cs = Vec::new();
        for vertices in iterate(self.size) {
            let mut g = self.clone();
            for vertex in 0..g.size {
                for i in 0..g.size {
                    if vertices[vertex] == 0 {
                        g.matrix[vertex as usize][i as usize] = 0;
                        g.matrix[i as usize][vertex as usize] = 0;
                    }
                }
            }
            let cardinality = vertices.iter().sum::<u32>() as usize;
            cs.push(Cutset {
                cardinality,
                vertices: vertices.clone(),
                graph: g,
            });
        }
        return cs;
    }

    pub fn max_independent_cutset(&self) -> Cutset {
        let mut max_cutset = None;
        for cutset in self.cutsets() {
            if cutset.graph.is_independent() {
                match &max_cutset {
                    None => max_cutset = Some(cutset),
                    Some(m_cutset) => {
                        if cutset.cardinality > m_cutset.cardinality {
                            max_cutset = Some(cutset);
                        }
                    }
                };
            }
        }
        return max_cutset.unwrap();
    }

    fn dfs(&self, vertex: &usize, visited: &mut Vec<usize>) {
        visited[*vertex] = 1;
        for i in 0..self.size {
            if visited[i] == 0 && self.matrix[*vertex][i] != 0 {
                self.dfs(&i, visited);
            }
        }
    }

    fn count_components_partial(&self, included_vertices: &Vec<u32>) -> usize {
        let mut visited = vec![0; self.size];
        for i in 0..included_vertices.len() {
            if included_vertices[i] == 0 {
                visited[i] = 1;
            }
        }
        let mut count = 0;
        while visited.iter().sum::<usize>() != visited.len() {
            let mut next = 0;
            for i in 0..self.size {
                if visited[i] == 0 {
                    next = i;
                    break;
                }
            }
            self.dfs(&next, &mut visited);
            count += 1;
        }
        return count;
    }

    pub fn count_components(&self) -> usize {
        self.count_components_partial(&vec![1; self.size])
    }

    pub fn is_connected(&self) -> bool {
        self.count_components() == 1
    }

    pub fn is_2_connected(&self) -> bool {
        let mut vertices = vec![1; self.size];
        for i in 0..self.size {
            vertices[i] = 0;
            let c = self.count_components_partial(&vertices);
            vertices[i] = 1;

            if c != 1 {
                return false;
            }
        }
        return true;
    }

    pub fn is_3_connected(&self) -> bool {
        let mut vertices = vec![1; self.size];
        for i in 0..self.size {
            for j in 0..self.size {
                if i == j {
                    continue;
                }
                vertices[i] = 0;
                vertices[j] = 0;
                let c = self.count_components_partial(&vertices);
                vertices[i] = 1;
                vertices[j] = 1;

                if c != 1 {
                    return false;
                }
            }
        }
        return true;
    }

    pub fn is_4_connected(&self) -> bool {
        let mut vertices = vec![1; self.size];
        for i in 0..self.size {
            for j in 0..self.size {
                for k in 0..self.size {
                    if i == j || j == k || i == k {
                        continue;
                    }
                    vertices[i] = 0;
                    vertices[j] = 0;
                    vertices[k] = 0;
                    let c = self.count_components_partial(&vertices);
                    vertices[i] = 1;
                    vertices[j] = 1;
                    vertices[k] = 1;

                    if c != 1 {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    pub fn neighbors(&self, vert: i32) -> Vec<i32> {
        let mut res = Vec::new();

        for i in 0..self.size as i32 {
            if i != vert && self.matrix[i as usize][vert as usize] != 0 {
                res.push(i);
            }
        }

        return res;
    }

    pub fn is_locally_connected(&self) -> bool {
        for i in 0..self.size {
            let neighbors = self.neighbors(i as i32);
            let mut part = vec![0; self.size];
            for neighbor in &neighbors {
                part[*neighbor as usize] = 1;
            }
            if self.count_components_partial(&part) != 1 {
                return false;
            }
        }
        return true;
    }

    pub fn get_closure(&self) -> Graph {
        self.get_closure_traced(false)
    }

    pub fn check_toughness(&self, t: f64) -> bool {
        for cutset in self.cutsets() {
            let components_count =
                cutset.graph.count_components_partial(&cutset.vertices) as f64;
            let cut_cardinality = (self.size - cutset.cardinality) as f64;
            if components_count > 1.0 && cut_cardinality < t * components_count
            {
                return false;
            }
        }
        return true;
    }

    pub fn get_toughness(&self) -> f64 {
        let mut left: f64 = 0.0;
        let mut right: f64 = 1024.0;
        let eps: f64 = 1e-9;

        while (right - left).abs() > eps {
            let mid = (left + right) / 2.0;

            if self.check_toughness(mid) == false {
                right = mid;
            } else {
                left = mid;
            }
        }

        return (left * 1e7).round() / 1e7;
    }

    pub fn is_complete(&self) -> bool {
        for row in 0..self.size {
            for col in 0..self.size {
                if row != col && self.matrix[row][col] == 0 {
                    return false;
                }
            }
        }
        return true;
    }

    pub fn is_independent(&self) -> bool {
        for row in 0..self.size {
            for col in 0..self.size {
                if row != col && self.matrix[row][col] != 0 {
                    return false;
                }
            }
        }
        return true;
    }

    fn swap_vertices(&mut self, a: usize, b: usize) {
        let n = self.size;
        let ab = self.matrix[a][b];
        for i in 0..n {
            let ai = self.matrix[a][i];
            let bi = self.matrix[b][i];
            self.matrix[a][i] = bi;
            self.matrix[i][a] = bi;
            self.matrix[b][i] = ai;
            self.matrix[i][b] = ai;
        }
        self.matrix[b][b] = 0;
        self.matrix[a][a] = 0;
        self.matrix[a][b] = ab;
        self.matrix[b][a] = ab;
    }

    pub fn is_isomorphic(&self, other: &Graph) -> bool {
        if self.size != other.size {
            return false;
        }

        let mut g2 = other.clone();
        if self == &g2 {
            return true;
        }

        if self.degree_vector() != other.degree_vector() {
            return false;
        }

        let n = self.size;
        let mut c = vec![0; n];

        let mut i = 0;
        while i < n {
            if c[i] < i {
                if i % 2 == 0 {
                    g2.swap_vertices(0, i);
                } else {
                    g2.swap_vertices(c[i], i);
                }

                if self == &g2 {
                    return true;
                }

                c[i] += 1;
                i = 1;
            } else {
                c[i] = 0;
                i += 1;
            }
        }
        return false;
    }

    pub fn is_free_of(&self, graphs: &Vec<Graph>) -> bool {
        for cutset in self.cutsets() {
            let subg = trim_cutset(&cutset);
            for g in graphs {
                if cutset.cardinality != g.size {
                    continue;
                }
                if subg.is_isomorphic(g) {
                    return false;
                }
            }
        }
        return true;
    }
}