scipy.sparse.csgraph.

maximum_flow#

scipy.sparse.csgraph.maximum_flow(csgraph, source, sink)#

Maximiert den Fluss zwischen zwei Knoten in einem Graphen.

Hinzugefügt in Version 1.4.0.

Parameter:
csgraphcsr_array

Die quadratische Matrix, die einen gerichteten Graphen darstellt, wobei der Eintrag (i, j) eine Ganzzahl ist, die die Kapazität der Kante zwischen den Knoten i und j darstellt.

sourceint

Der Quellknoten, aus dem der Fluss fließt.

sinkint

Der Senkenknoten, zu dem der Fluss fließt.

method: {‘edmonds_karp’, ‘dinic’}, optional

Die Methode/der Algorithmus, der zur Berechnung des maximalen Flusses verwendet wird. Folgende Methoden werden unterstützt:

  • ‘edmonds_karp’: Edmonds-Karp-Algorithmus in [1].

  • ‘dinic’: Dinics Algorithmus in [4].

Standard ist ‘dinic’.

Hinzugefügt in Version 1.8.0.

Rückgabe:
resMaximumFlowResult

Ein maximaler Fluss, dargestellt durch ein MaximumFlowResult, das den Wert des Flusses in flow_value und den Flussgraphen in flow enthält.

Löst aus:
TypeError

wenn der Eingabegraph nicht im CSR-Format vorliegt.

ValueError

wenn die Kapazitätswerte keine Ganzzahlen sind oder die Quelle oder Senke außerhalb der Grenzen liegen.

Hinweise

Dies löst das Problem des maximalen Flusses auf einem gegebenen gerichteten gewichteten Graphen: Ein Fluss ordnet jeder Kante einen Wert, auch Fluss genannt, zu, der kleiner ist als die Kapazität der Kante, sodass für jeden Knoten (außer der Quell- und der Senkenknoten) der gesamte eingehende Fluss gleich dem gesamten ausgehenden Fluss ist. Der Wert eines Flusses ist die Summe des Flusses aller Kanten, die vom Quellknoten ausgehen, und das Problem des maximalen Flusses besteht darin, einen Fluss zu finden, dessen Wert maximal ist.

Nach dem Max-Flow-Min-Cut-Theorem ist der maximale Wert des Flusses auch das Gesamtgewicht der Kanten in einem minimalen Schnitt.

Zur Lösung des Problems stellen wir den Edmonds–Karp-Algorithmus [1] und den Dinic-Algorithmus [4] bereit. Die Implementierung beider Algorithmen versucht, die Sparsamkeit auszunutzen. Die Zeitkomplexität des ersteren beträgt \(O(|V|\,|E|^2)\) und die Speicherkomplexität ist \(O(|E|)\). Letzterer erreicht seine Leistung, indem er Level-Graphen aufbaut und darin blockierende Flüsse findet. Seine Zeitkomplexität beträgt \(O(|V|^2\,|E|)\) und seine Speicherkomplexität ist \(O(|E|)\).

Das Problem des maximalen Flusses wird normalerweise mit reellwertigen Kapazitäten definiert, aber wir verlangen, dass alle Kapazitäten ganzzahlig sind, um die Konvergenz zu gewährleisten. Bei rationalen Kapazitäten oder Kapazitäten, die zu \(x\mathbb{Q}\) für ein festes \(x \in \mathbb{R}\) gehören, ist es möglich, das Problem auf den ganzzahligen Fall zu reduzieren, indem alle Kapazitäten entsprechend skaliert werden.

Die Lösung eines Problems des maximalen Flusses kann beispielsweise für die Optimierung von Graphenschnitten in der Computer Vision verwendet werden [3].

Referenzen

[1] (1,2)

Edmonds, J. und Karp, R. M. Theoretical improvements in algorithmic efficiency for network flow problems. 1972. Journal of the ACM. 19 (2): S. 248-264

[2]

Cormen, T. H. und Leiserson, C. E. und Rivest, R. L. und Stein C. Introduction to Algorithms. Zweite Auflage. 2001. MIT Press.

[4] (1,2)

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

Beispiele

Vielleicht das einfachste Fluss-Problem ist das eines Graphen mit nur zwei Knoten und einer Kante von der Quelle (0) zur Senke (1).

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

Hier ist der maximale Fluss einfach die Kapazität der Kante.

>>> 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

Wenn es hingegen einen Engpass zwischen Quelle und Senke gibt, kann dies den maximalen Fluss reduzieren.

(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

Ein weniger triviales Beispiel wird in [2], Kapitel 26.1, gegeben.

>>> 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

Es ist möglich, das Problem der maximalen Übereinstimmung in einem bipartiten Graphen auf ein Problem des maximalen Flusses zu reduzieren: Sei \(G = ((U, V), E)\) ein bipartiter Graph. Dann fügen Sie dem Graphen einen Quellknoten mit Kanten zu jedem Knoten in \(U\) und einen Senkenknoten mit Kanten von jedem Knoten in \(V\) hinzu. Geben Sie schließlich jeder Kante im resultierenden Graphen eine Kapazität von 1. Ein maximaler Fluss im neuen Graphen liefert dann eine maximale Übereinstimmung im ursprünglichen Graphen, bestehend aus den Kanten in \(E\), deren Fluss positiv ist.

Angenommen, die Kanten werden durch eine \(\lvert U \rvert \times \lvert V \rvert\) Matrix im CSR-Format dargestellt, deren \((i, j)\)-ter Eintrag 1 ist, wenn es eine Kante von \(i \in U\) nach \(j \in V\) gibt, und sonst 0; das heißt, die Eingabe hat das Format, das von maximum_bipartite_matching benötigt wird. Dann enthält die CSR-Darstellung des oben konstruierten Graphen diese Matrix als Block. Hier ist ein Beispiel

>>> 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]]

An diesem Punkt können wir den maximalen Fluss zwischen der hinzugefügten Senke und der hinzugefügten Quelle finden, und die gewünschte Übereinstimmung kann durch Einschränkung der Flussfunktion auf den Block erhalten werden, der dem ursprünglichen Graphen entspricht.

>>> 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]]

Dies sagt uns, dass der erste, zweite und dritte Knoten in \(U\) mit dem zweiten, ersten bzw. dritten Knoten in \(V\) übereinstimmen.

Während dies das Problem der maximalen bipartiten Übereinstimmung im Allgemeinen löst, beachten Sie, dass für dieses Problem spezialisierte Algorithmen wie maximum_bipartite_matching im Allgemeinen besser funktionieren.

Dieser Ansatz kann auch verwendet werden, um verschiedene gängige Verallgemeinerungen des Problems der maximalen bipartiten Übereinstimmung zu lösen. Wenn beispielsweise einige Knoten mit mehr als einem anderen Knoten übereinstimmen können, kann dies durch entsprechende Anpassung der Kapazitäten des neuen Graphen gehandhabt werden.

Auf dieser Seite