Graphs puzzle

graphs_puzzle.rs

use petgraph::{algo::is_isomorphic, graph::NodeIndex, graph::UnGraph};

fn add_possible_edges<T: Clone>(g: UnGraph<T, ()>, num_nodes: usize) -> Vec<UnGraph<T, ()>> {
    let mut res = Vec::new();
    for i in 0..num_nodes - 1 {
        for j in (i + 1)..num_nodes {
            if !g.contains_edge(NodeIndex::new(i), NodeIndex::new(j)) {
                let mut new_g = g.clone();
                new_g.add_edge(NodeIndex::new(i), NodeIndex::new(j), ());
                res.push(new_g)
            }
        }
    }
    res
}

fn reduce_isomorphic_graph<T>(gs: Vec<UnGraph<T, ()>>) -> Vec<UnGraph<T, ()>> {
    let mut iso_gs = Vec::new();
    for g in gs {
        let mut exist_iso_graph = false;
        for checked_g in iso_gs.iter() {
            if is_isomorphic(&g, checked_g) {
                exist_iso_graph = true;
                break;
            }
        }
        if !exist_iso_graph {
            iso_gs.push(g);
        }
    }
    iso_gs
}

fn grow_graphs<T: Clone>(gs: Vec<UnGraph<T, ()>>, num_nodes: usize) -> Vec<UnGraph<T, ()>> {
    let new_gs = gs
        .into_iter()
        .flat_map(|g| add_possible_edges(g, num_nodes))
        .collect();

    reduce_isomorphic_graph(new_gs)
}

fn max_independent_set<T>(g: &UnGraph<T, ()>) -> Vec<usize> {
    let mut best_set = vec![];

    // Brute-force solution.
    // List all possible subsets of nodes and find independent ones.
    for bitset in 0..(1 << g.node_count()) {
        let mut set = vec![];
        for i in 0..g.node_count() {
            if (bitset >> i) & 1 != 0 {
                set.push(i);
            }
        }

        let mut is_independent = true;
        for i in 0..set.len() {
            for j in i + 1..set.len() {
                if g.contains_edge(NodeIndex::new(set[i]), NodeIndex::new(set[j])) {
                    is_independent = false;
                    break;
                }
            }
            if !is_independent {
                break;
            }
        }
        if is_independent && set.len() > best_set.len() {
            best_set = set;
        }
    }
    best_set
}

fn main() {
    let num_nodes = 8;

    let mut g = UnGraph::<usize, ()>::default();
    for _ in 0..num_nodes {
        g.add_node(1);
    }

    let mut gs = vec![g];
    for num_edges in 1..=7 {
        gs = grow_graphs(gs, num_nodes);
        let len_mex_indep_set = gs
            .iter()
            .map(max_independent_set)
            .map(|v| v.len())
            .min()
            .unwrap();
        // maximum independent set のサイズが3以下になるようなグラフを一つでも作れればよい
        println!(
            "Number of edges = {}: minimum size of maximum independent set = {}",
            num_edges, len_mex_indep_set
        );
    }
}