scipy.sparse.csgraph.

maximum_flow#

scipy.sparse.csgraph.maximum_flow(csgraph, источник, сток)#

Максимизировать поток между двумя вершинами в графе.

Добавлено в версии 1.4.0.

Параметры:

csgraphcsr_array

Квадратная матрица, представляющая ориентированный граф, чей (i, j)-й элемент является целым числом, представляющим пропускную способность ребра между вершинами i и j.

источникint

Исходная вершина, из которой течет поток.

стокint

Вершина-сток, в которую течёт поток.

method: {‘edmonds_karp’, ‘dinic’}, опционально

Метод/алгоритм, используемый для вычисления максимального потока. Поддерживаются следующие методы:

'edmonds_karp': алгоритм Эдмондса-Карпа в [1].

'dinic': алгоритм Диница в [4].

По умолчанию 'dinic'.

Добавлено в версии 1.8.0.

Возвращает:

resMaximumFlowResult: Максимальный поток, представленный MaximumFlowResult который включает значение потока в flow_value, и граф потока в flow.

Вызывает:

TypeError:: если входной граф не в формате CSR.
ValueError:: если значения емкости не являются целыми числами, или источник или сток выходят за пределы.

Примечания

Это решает задачу о максимальном потоке в заданном ориентированном взвешенном графе: поток сопоставляет каждому ребру значение, также называемое потоком, меньшее, чем пропускная способность ребра, так что для каждой вершины (кроме исходной и стоковой вершин) общий входящий поток равен общему исходящему потоку. Значение потока — это сумма потоков всех рёбер, выходящих из исходной вершины, и задача о максимальном потоке состоит в нахождении потока с максимальным значением.

По теореме о максимальном потоке и минимальном разрезе, максимальное значение потока также является суммарным весом ребер в минимальном разрезе.

Для решения проблемы мы предоставляем алгоритм Эдмондса–Карпа [1] и алгоритм Диница [4]. Реализация обоих алгоритмов стремится использовать разреженность. Временная сложность первого \(O(|V|\,|E|^2)\) и её пространственная сложность составляет \(O(|E|)\). Последний достигает своей производительности за счёт построения уровневых графов и нахождения блокирующих потоков в них. Его временная сложность составляет \(O(|V|^2\,|E|)\) и его пространственная сложность составляет \(O(|E|)\).

Задача о максимальном потоке обычно определяется с вещественными пропускными способностями, но мы требуем, чтобы все пропускные способности были целыми для обеспечения сходимости. При работе с рациональными пропускными способностями или пропускными способностями, принадлежащими \(x\mathbb{Q}\) для некоторого фиксированного \(x \in \mathbb{R}\), возможно свести задачу к интегральному случаю, масштабируя все мощности соответствующим образом.

Решение задачи о максимальном потоке может использоваться, например, для оптимизации разрезов графа в компьютерном зрении [3].

Ссылки

[1] (1,2)

Эдмондс, Дж. и Карп, Р. М. Теоретические улучшения алгоритмической эффективности для задач сетевого потока. 1972. Journal of the ACM. 19 (2): стр. 248-264

[2]

Кормен, Т. Х. и Лейзерсон, Ч. Э. и Ривест, Р. Л. и Штайн К. Алгоритмы: построение и анализ. Второе издание. 2001. MIT Press.

[3]

https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision

[4] (1,2)

Dinic, Efim A. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, vol. 11, pp. 1277-1280. 1970.

Примеры

Возможно, простейшая задача потока — это граф только из двух вершин с ребром от источника (0) к стоку (1):

(0) --5--> (1)

Здесь максимальный поток — это просто пропускная способность ребра:

>>> import numpy as np
>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import maximum_flow
>>> graph = csr_array([[0, 5], [0, 0]])
>>> maximum_flow(graph, 0, 1).flow_value
5
>>> maximum_flow(graph, 0, 1, method='edmonds_karp').flow_value
5

Если, с другой стороны, существует узкое место между источником и стоком, это может уменьшить максимальный поток:

(0) --5--> (1) --3--> (2)

>>> graph = csr_array([[0, 5, 0], [0, 0, 3], [0, 0, 0]])
>>> maximum_flow(graph, 0, 2).flow_value
3

Менее тривиальный пример приведён в [2], Глава 26.1:

>>> graph = csr_array([[0, 16, 13,  0,  0,  0],
...                    [0,  0, 10, 12,  0,  0],
...                    [0,  4,  0,  0, 14,  0],
...                    [0,  0,  9,  0,  0, 20],
...                    [0,  0,  0,  7,  0,  4],
...                    [0,  0,  0,  0,  0,  0]])
>>> maximum_flow(graph, 0, 5).flow_value
23

Можно свести задачу поиска максимального паросочетания в двудольном графе к задаче максимального потока: Пусть \(G = ((U, V), E)\) быть двудольным графом. Затем добавьте в граф исходную вершину с ребрами к каждой вершине в \(U\) и стоковая вершина с рёбрами от каждой вершины в \(V\). Наконец, присвойте каждому ребру в результирующем графе пропускную способность 1. Тогда максимальный поток в новом графе дает максимальное паросочетание в исходном графе, состоящее из ребер в \(E\) , чей поток положителен.

Предположим, что рёбра представлены \(\lvert U \rvert \times \lvert V \rvert\) матрица в формате CSR, чья \((i, j)\)-я запись равна 1, если есть ребро из \(i \in U\) to \(j \in V\) и 0 в противном случае; то есть входные данные имеют форму, требуемую maximum_bipartite_matching. Затем CSR-представление графа, построенного выше, содержит эту матрицу как блок. Вот пример:

>>> graph = csr_array([[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 1, 0]])
>>> print(graph.toarray())
[[0 1 0 1]
 [1 0 1 0]
 [0 1 1 0]]
>>> i, j = graph.shape
>>> n = graph.nnz
>>> indptr = np.concatenate([[0],
...                          graph.indptr + i,
...                          np.arange(n + i + 1, n + i + j + 1),
...                          [n + i + j]])
>>> indices = np.concatenate([np.arange(1, i + 1),
...                           graph.indices + i + 1,
...                           np.repeat(i + j + 1, j)])
>>> data = np.ones(n + i + j, dtype=int)
>>>
>>> graph_flow = csr_array((data, indices, indptr))
>>> print(graph_flow.toarray())
[[0 1 1 1 0 0 0 0 0]
 [0 0 0 0 0 1 0 1 0]
 [0 0 0 0 1 0 1 0 0]
 [0 0 0 0 0 1 1 0 0]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0]]

На этом этапе мы можем найти максимальный поток между добавленным стоком и добавленным источником, и желаемое сопоставление может быть получено путём ограничения функции потока блоком, соответствующим исходному графу:

>>> result = maximum_flow(graph_flow, 0, i+j+1, method='dinic')
>>> matching = result.flow[1:i+1, i+1:i+j+1]
>>> print(matching.toarray())
[[0 1 0 0]
 [1 0 0 0]
 [0 0 1 0]]

Это говорит нам, что первая, вторая и третья вершины в \(U\) сопоставляются со второй, первой и третьей вершиной в \(V\) соответственно.

Хотя это решает задачу максимального паросочетания в двудольном графе в общем случае, обратите внимание, что алгоритмы, специализированные для этой задачи, такие как maximum_bipartite_matching, как правило, будет работать лучше.

Этот подход также может использоваться для решения различных обобщений задачи о максимальном паросочетании в двудольном графе. Если, например, некоторые вершины могут быть сопоставлены более чем с одной другой вершиной, это может быть обработано путем соответствующей модификации пропускных способностей нового графа.