use crate::Graph;

pub fn dirac_theorem(g: &Graph) -> bool {
    for vertex in 0..g.size {
        if (g.degree(vertex) as f64) < g.size as f64 / 2.0 {
            return false;
        }
    }
    return true;
}

pub fn ore_theorem(g: &Graph) -> bool {
    for v1 in 0..g.size {
        for v2 in 0..g.size {
            if v1 == v2 || g.matrix[v1][v2] != 0 {
                continue;
            }
            let d1 = g.degree(v1);
            let d2 = g.degree(v2);
            if d1 + d2 < g.size {
                return false;
            }
        }
    }
    return true;
}

pub fn posa_theorem(g: &Graph) -> bool {
    let mut degrees = Vec::new();
    for v in 0..g.size {
        degrees.push(g.degree(v));
    }

    let end = if g.size % 2 == 0 {
        g.size / 2
    } else {
        (g.size - 1) / 2
    };

    for k in 1..end {
        let mut cnt = 0;
        for d in &degrees {
            if *d <= k {
                cnt += 1;
            }
        }
        if cnt >= k {
            return false;
        }
    }
    if g.size % 2 != 0 {
        let mut cnt = 0;
        for d in &degrees {
            if *d <= end {
                cnt += 1;
            }
        }
        if cnt > end {
            return false;
        }
    }
    return true;
}

pub fn bondy_chvatal_hamiltonian_cycle(graph: &Graph) -> Vec<usize> {
    let closure = graph.get_closure_traced(true);

    let mut cycle = Vec::new();
    for i in 0..graph.size - 1 {
        cycle.push(i + 1);
    }
    cycle.push(0);

    loop {
        let mut start = 0;
        let mut m = 0;

        let mut end = start;
        let mut new_start = start;
        let mut current = start;
        loop {
            let next = cycle[current];
            let val = closure.matrix[current][next];
            if val > m {
                m = val;
                end = current;
                new_start = next;
            }
            current = next;
            if current == start {
                break;
            }
        }
        if m == 1 {
            break;
        }
        start = new_start;

        let mut s = start;
        let mut current = cycle[start];
        while current != end {
            let next = cycle[current];
            let u1 = closure.matrix[start][next];
            let u2 = closure.matrix[end][current];
            if u1 < m && u2 < m {
                s = current;
                break;
            }
            current = next;
        }

        let mut new_cycle = Vec::new();
        new_cycle.push(start);
        let mut current = cycle[s];
        while current != end {
            new_cycle.push(current);
            current = cycle[current];
        }
        new_cycle.push(end);
        {
            let mut tmp = Vec::new();
            let mut current = cycle[start];
            while current != s {
                tmp.push(current);
                current = cycle[current];
            }
            tmp.push(s);
            tmp.reverse();
            for i in tmp {
                new_cycle.push(i);
            }
        }
        for i in 0..graph.size - 1 {
            cycle[new_cycle[i]] = new_cycle[i + 1];
        }
        cycle[new_cycle[graph.size - 1]] = new_cycle[0];
    }

    return cycle;
}