7.2 最小切割佈局#

import random
from collections import defaultdict

def fm_partition(nodes, adj, balance=0.45):
    """
    Fiduccia-Mattheyses 二分割。
    adj: node -> set of neighbors；回傳 (A, B, cut_size)
    """
    rng = random.Random(7)
    half = int(len(nodes) * balance)
    A = set(rng.sample(sorted(nodes), half))
    B = set(nodes) - A

    def gain(v):
        return sum(1 for u in adj[v] if u in B) - \
               sum(1 for u in adj[v] if u in A) if v in A else \
               sum(1 for u in adj[v] if u in A) - \
               sum(1 for u in adj[v] if u in B)

    best_cut, best_A = None, None
    locked = set()
    for _ in range(30):                       # 多輪 pass
        gains = {v: gain(v) for v in nodes - locked}
        if not gains:
            break
        # 貪心：挑最大增益且保持平衡的移動（簡化版 FM）
        cand = sorted(gains.items(), key=lambda kv: -kv[1])
        improved = False
        for v, g in cand:
            src, dst = (A, B) if v in A else (B, A)
            if len(A) - (v in A) < balance * len(nodes) and v in A:
                continue
            if len(B) - (v in B) < balance * len(nodes) and v in B:
                continue
            (A if v in A else B).remove(v)
            dst.add(v)
            locked.add(v)
            improved = True
            break
        if not improved:
            break
        cut = sum(1 for v in A for u in adj[v] if u in B) // 1
        if best_cut is None or cut < best_cut:
            best_cut, best_A = cut, set(A)
    cut = sum(1 for v in best_A for u in adj[v] if u not in best_A)
    return best_A, set(nodes) - best_A, cut

def min_cut_place(netlist, cell_sizes=None):
    """遞迴對半切：交替 V/H 切線，回傳 cell -> (x, y) 槽位"""
    # 建相鄰關係（超邊展開成團）
    adj = defaultdict(set)
    nodes = set()
    for net in netlist:
        for u in net:
            nodes.add(u)
            for v in net:
                if v != u:
                    adj[u].add(v)

    slots = []                                 # 遞迴展開槽位
    def assign(group, depth, x0, y0, w, h):
        if len(group) <= 1 or depth > 4:
            for c in group:
                slots.append((c, x0, y0))
            return
        A, B, _ = fm_partition(group, adj)
        if not A or not B:                     # 分不動：直接均分
            gl = sorted(group)
            A, B = set(gl[:len(gl)//2]), set(gl[len(gl)//2:])
        if depth % 2 == 0:                     # 偶數層垂直切（左右）
            assign(A, depth+1, x0, y0, w/2, h)
            assign(B, depth+1, x0+w/2, y0, w/2, h)
        else:                                  # 奇數層水平切（上下）
            assign(A, depth+1, x0, y0, w, h/2)
            assign(B, depth+1, x0, y0+h/2, w, h/2)

    assign(nodes, 0, 0, 0, 8, 8)
    return dict(slots)

def hpwl(nets, pos):
    t = 0
    for net in nets:
        xs = [pos[n][0] for n in net]; ys = [pos[n][1] for n in net]
        t += (max(xs)-min(xs)) + (max(ys)-min(ys))
    return t

netlist = [["a","b","c"], ["b","c","d"], ["c","d","e"],
           ["e","f","g"], ["f","g","h"], ["g","h","a"], ["a","e"]]
pos = min_cut_place(netlist)
print("單元槽位:", dict(sorted(pos.items())))
print("HPWL =", hpwl(netlist, pos))

單元槽位: {'a': (0, 0), 'b': (0, 0), 'c': (4, 0), 'd': (4, 4), 'e': (0, 4), 'f': (8, 0), 'g': (8, 4), 'h': (8, 8)}
HPWL = 34