zad2.py

# Spójność krawędziowa

# (Tw. Mengera) Minimalna ilość krawędzi które należy usunąć by zadane wierzchołki s, t znalazły się w
# różnych komponentach spójnych jest równa ilości krawędziowo rozłącznych ścieżek pomiędzy s i t
# Wskazówka: jak można zinterpretować ilość krawędziowo rozłącznych ścieżek jako problem maksymalnego przepływu?

from collections import deque
from checker import check2

def gen_list_from_edges(E):
    n = 0
    for u, v, _ in E:
        u -= 1 # korekcja indeksowania wierzchołków
        v -= 1
        if u > n:
            n = u
        if v > n:
            n = v

    n += 1

    G = [[] for _ in range(n)]

    for u, v, _ in E:
        u -= 1
        v -= 1
        G[v].append(u)
        G[u].append(v)

    return G, n

def bfs(G, M, s, t, parents, n):
    visited = [False] * n
    Q = deque()

    Q.append(s)
    visited[s] = True

    while len(Q) > 0:
        u = Q.popleft()

        for v in G[u]:
            if M[u][v] and not visited[v]: # jak waga 0 to nie mogę przejść
                Q.append(v)
                visited[v] = True
                parents[v] = u

    return visited[t] # zwraca czy dotarł do t

# nie można scalić obu pętli bo wtedy byśmy aktualizowali macierz o path_flow, które nie zostało jeszcze wtedy
# zminimalizowane
def edmonds_karp(G, n, s, t):
    M = [[1] * n for _ in range(n)] # wagi krawędzi ustalone na 1 aby sposób zadziałał
    parents = [None] * n
    inf = float('inf')

    max_flow = 0

    while bfs(G, M, s, t, parents, n): # dopóki da się dotrzeć do t
        bottleneck = inf
        u = t
        while u != s: # przejście od tyłu i wyzanczenie wąskiego gardła ścieżki
            val = M[parents[u]][u]
            if val < bottleneck: bottleneck = val
            u = parents[u]

        max_flow += bottleneck # dla jednej ze ścieżek

        u = t
        while u != s: # powiększenie sieci residentialnej (co uwzględnia też "wycofanie strumienia i przelanie inną krawędzią")
            # znalezienie ścieżki powiększającej
            v = parents[u]
            M[u][v] += bottleneck # sieć residentialna ma wagi dodatnie
            M[v][u] -= bottleneck
            u = parents[u]

    return max_flow


def menger(E):
    G, n = gen_list_from_edges(E)

    min_amount = n ** 2

    for t in range(1, n):
        max_flow = edmonds_karp(G, n, 0, t)
        if max_flow < min_amount: min_amount = max_flow

    return min_amount


# check2(menger, 'grid100x100')
check2(menger)