use crate::graph::Graph;

pub async fn dominating_numbers(
    g: Graph,
) -> (String, Option<u32>, Option<u32>) {
    let line = g.to_g6();
    let mut independent_dominating = None;

    let mut geodesic_sets = Vec::new();
    let mut min_size = g.size as u32;

    for cs in g.cutsets() {
        let dom = cs.is_dominating_in(&g);
        let idp = cs.graph.is_independent();
        if independent_dominating.is_none() && dom && idp {
            independent_dominating = Some(cs.cardinality as u32);
        }

        let mut visited = vec![0; g.size];
        for a in 0..cs.graph.size {
            if cs.vertices[a] == 0 {
                continue;
            }
            for b in a..cs.graph.size {
                if cs.vertices[b] == 0 {
                    continue;
                }
                if a != b {
                    for geod in g.get_geodesics(a, b) {
                        for i in geod {
                            visited[i] = 1;
                        }
                    }
                }
            }
        }
        if visited.iter().sum::<usize>() == g.size {
            geodesic_sets.push(cs.vertices.clone());
            let tmp = cs.vertices.into_iter().sum::<u32>();
            if tmp < min_size {
                min_size = tmp;
            }
        }
    }

    let geodesic_sets: Vec<_> = geodesic_sets
        .into_iter()
        .filter(|s| s.iter().sum::<u32>() == min_size)
        .collect();

    let mut fg = None;
    if geodesic_sets.len() == 1 {
        fg = Some(0)
    } else {
        for i in 0..geodesic_sets.len() {
            let check = &geodesic_sets[i];
            let mut verts = check.clone();
            for j in 0..geodesic_sets.len() {
                if i == j {
                    continue;
                }
                let set = &geodesic_sets[j];
                for v in 0..g.size {
                    if check[v] == set[v] {
                        verts[v] = 0;
                    }
                }
            }
            let new_fg = verts.iter().sum::<u32>();
            if new_fg > 0 {
                if new_fg < fg.unwrap_or(g.size as u32) {
                    fg = Some(new_fg);
                }
            }
        }
    }

    // println!("{line} {independent_dominating:?} {fg:?}");

    (line, independent_dominating, fg)
}