use crate::graph::Graph;

pub async fn dominating_numbers(
    g: Graph,
) -> (String, usize, 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;

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

        if cs.cardinality > min_size {
            continue;
        }

        let mut visited = vec![0; g.size];
        'outer: 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 {
                    break 'outer;
                }
            }
        }
        if visited.iter().sum::<usize>() == g.size {
            geodesic_sets.push(cs.vertices.clone());
            if cs.cardinality < min_size {
                min_size = cs.cardinality;
            }
        }
    }

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

    let mut fg = None;
    if geodesic_sets.len() == 1 {
        fg = Some(0)
    } else {
        for (i, check) in geodesic_sets.iter().enumerate() {
            let mut verts = check.clone();
            for (j, set) in geodesic_sets.iter().enumerate() {
                if i == j {
                    continue;
                }
                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 && new_fg < fg.unwrap_or(g.size as u32) {
                fg = Some(new_fg);
            }

            if let Some(fg) = fg {
                if fg == 1 {
                    break;
                }
            }
        }
    }

    (line, g.size, independent_dominating, fg)
}