VLSIの配置配線アルゴリズムMincut (Kernighan–Linのアルゴリズム)について復習

ちょっと諸事情で過去に勉強したアルゴリズムを復習したくて、Mincutアルゴリズムを再度勉強していた。

VLSIにおいて配置配線をする際に使用されるアルゴリズムとして有名なものに、Quadratic Placement & Mincutというものがある。そのうちのMincutは、1つのグラフを、なるべく同じ大きさで、交差する辺を最小にしつつ分割するアルゴリズムだ。

以下のWikipediaが参考になる。

en.wikipedia.org

function Kernighan-Lin(G(V, E)) is
    determine a balanced initial partition of the nodes into sets A and B
    
    do
        compute D values for all a in A and b in B
        let gv, av, and bv be empty lists
        for n := 1 to |V| / 2 do
            find a from A and b from B, such that g = D[a] + D[b] − 2×c(a, b) is maximal
            remove a and b from further consideration in this pass
            add g to gv, a to av, and b to bv
            update D values for the elements of A = A \ a and B = B \ b
        end for
        find k which maximizes g_max, the sum of gv[1], ..., gv[k]
        if g_max > 0 then
            Exchange av[1], av[2], ..., av[k] with bv[1], bv[2], ..., bv[k]
    until (g_max ≤ 0)

    return G(V, E)

あるノード $a$ に着目し、グループの中でまとまっている辺を $I_a$ とし、グループから外に出る辺を $E_a$ とする。この時の差分を $D_a=I_a-E_a$ と計算する。また、 $c(a, b)$ はノードaからbのコストを示す。

コメントにあるように、 $D_a+D_b-2\times c(a, b)$ が最大となる $a$ と $b$ を見つける。この式の意味は、内部に接続が多い方が $D$ が大きくなるため、内部へのパスが多い $a$ と $b$ を選択し、かつ $a$ から $b$ への接続のコストを引いたものなり、 $a$ と $b$ を直接つなぐコスト以外の、内部の辺への寄与率を示したものになる。