find-stoer-wagner-problems.py

from typing import List

WEIGHT_RANGE = 3


class Graph4:
    edge_weights = ...  # type: List[int]

    def __init__(self):
        self.edge_weights = [-WEIGHT_RANGE, -WEIGHT_RANGE, -WEIGHT_RANGE, -WEIGHT_RANGE, -WEIGHT_RANGE, -WEIGHT_RANGE]

    def next_weights(self):
        for i in range(len(self.edge_weights) - 1, -1, -1):
            self.edge_weights[i] += 1
            if self.edge_weights[i] <= WEIGHT_RANGE:
                return True
            self.edge_weights[i] = -WEIGHT_RANGE
        return False

    def weight(self, a, b):
        if a > b:
            [a, b] = [b, a]
        if a == 0:
            return self.edge_weights[b - 1]
        elif a == 1:
            return self.edge_weights[b + 1]
        else:
            return self.edge_weights[5]

    def cut(self, bits):
        sum = 0
        for i in range(3):
            for j in range(i + 1, 4):
                i_i = (bits & (1 << i)) >> i
                j_j = (bits & (1 << j)) >> j
                if i_i != j_j:
                    sum += self.weight(i, j)
        return sum

    def min_cut(self):
        minc = 10000
        for i in range(1, 8):
            c = self.cut(i)
            if c < minc:
                minc = c
        return minc

    def count_min_cut(self):
        minc = self.min_cut()
        count = 0
        for i in range(1, 8):
            c = self.cut(i)
            if c == minc:
                count += 1
        return count

    def order_ok(self):
        first_ok = self.weight(0, 1) > self.weight(0, 2) and self.weight(0, 1) > self.weight(0, 3)
        second_ok = self.weight(0, 2) + self.weight(1, 2) > self.weight(1, 2) + self.weight(1, 3)
        return first_ok and second_ok


g = Graph4()
while g.next_weights():
    if not g.order_ok():
        continue
    min_cut = g.min_cut()
    c7 = g.cut(7)
    c5 = g.cut(5)
    c3 = g.cut(3)
    min_cut_count = g.count_min_cut()
    if c3 != min_cut and c5 == min_cut and c7 > c5 and min_cut_count == 1:
        print(g.edge_weights)
        print(min_cut, c3, c5, c7, min_cut_count)