Создание графика производительности алгоритма максимального потока Эдмондса Карпа в Python

Question

Прежде чем я углублюсь в вопрос, вот некоторая справочная информация о том, что у меня уже есть:

- Сначала я создал матрицу ненаправленной матрицы смежности, основанную на городах по всей территории США, где веса ребер были рассчитанным расстоянием (достигнуто это с помощью формулы расстояния).

-Я также реализовал минимальное связующее дерево, используя алгоритм Прима.

Теперь мне нужно реализовать алгоритм максимального потока Эдмондса Карпа, который у меня есть, но я не совсем понимаю, как создать график производительности на основе имеющихся у меня данных, чтобы реализовать алгоритм, использованный в следующем коде:

def edmonds_karp(C, source, sink):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for i in xrange(n)]
    # residual capacity from u to v is C[u][v] - F[u][v]

    while True:
        path = bfs(C, F, source, sink)
        if not path:
            break
        # traverse path to find smallest capacity
        flow = min(C[u][v] - F[u][v] for u,v in path)
        # traverse path to update flow
        for u,v in path:
            F[u][v] += flow
            F[v][u] -= flow
    return sum(F[source][i] for i in xrange(n))

def bfs(C, F, source, sink):
    queue = [source]                 
    paths = {source: []}
    while queue:
        u = queue.pop(0)
        for v in xrange(len(C)):
            if C[u][v] - F[u][v] > 0 and v not in paths:
                paths[v] = paths[u] + [(u,v)]
                if v == sink:
                    return paths[v]
                queue.append(v)
    return None

Любая помощь будет принята с благодарностью, спасибо!

Answer 1

Все, что нужно было сделать для алгоритма Эдмондса-Карпа, - это изменить веса всех ребер на 1, потому что они не нужны для того, чтобы найти связность ребер между городами в этой задаче. И график городов с граничными весами, равными 1, станет моим графиком пропускной способности. Также для алгоритма Эдмондса-Карпа понадобится ориентированный граф.