無向グラフ - 二部グラフ判定

概要

与えられた無向グラフが二部グラフであるかどうか判定する.

参考

二部グラフ判定をUnionFindTreeで行う - noshi91のメモ

アルゴリズムの詳細

参考に書いてあるとおりにやる.

すなわち, 頂点 $u$ がグループ $1, 2$ にあることを表す述語 $P^{1} (u), P^{2} (u)$ を用意して, エッジ $e = (u, v)$ を $(P^{1} (u) \land P^{2} (v)) \lor (P^{2} (u) \land P^{1} (v))$ と解釈して論理グラフを組み立てて（頂点が命題で連結なときには同時に成り立つ）, 最後に矛盾 ( $P^{1} (u) \land P^{2} (u)$ ) が無いことを確認する.

実装

論理グラフは同じグラフに所属するかだけが問題なので, これを UnionFind で実装する.

/// Graph - Undirected - is Bipartite Graph?
use crate::set::union_find::*;

pub fn is_bigraph(neigh: &[Vec<usize>]) -> bool {
    let n = neigh.len();
    let mut uf = UnionFind::new(n * 2);
    for u in 0..n {
        for &v in neigh[u].iter() {
            uf.merge(u * 2, v * 2 + 1);
            uf.merge(u * 2 + 1, v * 2);
        }
    }
    for u in 0..n {
        if uf.is_same(u * 2, u * 2 + 1) {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod test_is_bipartite_graph {
    use crate::graph::undirected::is_bigraph::*;

    #[test]
    fn it_works() {
        assert!(is_bigraph(&vec![vec![]]));
        assert!(is_bigraph(&[vec![1], vec![0]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![3], vec![]]));
        assert!(is_bigraph(&[vec![1], vec![2], vec![3], vec![0]]));
        assert!(!is_bigraph(&[vec![1], vec![2], vec![0]]));
        assert!(!is_bigraph(&[vec![1], vec![2], vec![3], vec![4], vec![0]]));
    }
}