scipy.sparse.csgraph.

maximum_bipartite_matching#

scipy.sparse.csgraph.maximum_bipartite_matching(graph, perm_type='row')#

Gibt eine Zuordnung eines bipartiten Graphen zurück, deren Kardinalität mindestens so groß ist wie die einer beliebigen gegebenen Zuordnung des Graphen.

Parameter:

graphspärliches Array oder spärliche Matrix: Eingabe sparse im CSR-Format, dessen Zeilen eine Partition des Graphen darstellen und dessen Spalten die andere Partition darstellen. Eine Kante zwischen zwei Knoten wird durch das Vorhandensein des entsprechenden Eintrags in der Matrix in ihrer sparsen Darstellung angezeigt.
perm_typestr, {‘row’, ‘column’}: In Bezug auf welche Partition die Zuordnung zurückgegeben werden soll: Wenn 'row', erzeugt die Funktion ein Array, dessen Länge der Anzahl der Spalten in der Eingabe entspricht und dessen \(j\)-tes Element die Zeile ist, die der \(j\)-ten Spalte zugeordnet ist. Umgekehrt, wenn perm_type 'column' ist, gibt dies die Spalten zurück, die jeder Zeile zugeordnet sind.

Rückgabe:

permndarray: Eine Zuordnung der Knoten in einer der beiden Partitionen. Nicht zugeordnete Knoten werden im Ergebnis durch eine -1 dargestellt.

Hinweise

Diese Funktion implementiert den Hopcroft–Karp-Algorithmus [1]. Seine Zeitkomplexität beträgt \(O(\lvert E \rvert \sqrt{\lvert V \rvert})\) und seine Speicherkomplexität ist linear in der Anzahl der Zeilen. In der Praxis bedeutet diese Asymmetrie zwischen Zeilen und Spalten, dass es effizienter sein kann, die Eingabe zu transponieren, wenn sie mehr Spalten als Zeilen enthält.

Nach dem Satz von Konig ist die Kardinalität der Zuordnung auch die Anzahl der Knoten, die in einer minimalen Knotenüberdeckung des Graphen vorkommen.

Beachten Sie, dass explizite Nullen, die in der sparsen Darstellung enthalten sind, immer noch als Kanten gezählt werden.

Die Implementierung wurde in SciPy 1.4.0 geändert, um die Zuordnung allgemeiner bipartiter Graphen zu ermöglichen. Frühere Versionen gingen davon aus, dass eine perfekte Zuordnung existiert. Daher funktioniert Code, der für 1.4.0 geschrieben wurde, möglicherweise nicht notwendigerweise auf älteren Versionen.

Wenn mehrere gültige Lösungen möglich sind, kann die Ausgabe je nach SciPy- und Python-Version variieren.

Referenzen

[1]

John E. Hopcroft und Richard M. Karp. „An n^{5 / 2} Algorithm for Maximum Matchings in Bipartite Graphs“ In: SIAM Journal of Computing 2.4 (1973), S. 225–231. DOI:10.1137/0202019

Beispiele

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import maximum_bipartite_matching

Als einfaches Beispiel betrachten wir einen bipartiten Graphen, dessen Partitionen 2 bzw. 3 Elemente enthalten. Angenommen, eine Partition enthält die Knoten 0 und 1, und die andere Partition enthält die Knoten A, B und C. Angenommen, es gibt Kanten, die 0 und C, 1 und A sowie 1 und B verbinden. Dieser Graph würde dann durch das folgende sparsen Array dargestellt werden

>>> graph = csr_array([[0, 0, 1], [1, 1, 0]])

Hier können die 1en beliebig sein, solange sie als Elemente im sparsen Array gespeichert werden. Wir können nun maximale Zuordnungen wie folgt berechnen

>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

Die erste Ausgabe besagt, dass 1 und 2 mit C und A übereinstimmen, und die zweite Ausgabe besagt, dass A, B und C mit 1, nichts und 0 übereinstimmen.

Beachten Sie, dass explizite Nullen immer noch in Kanten umgewandelt werden. Das bedeutet, dass eine andere Möglichkeit, den obigen Graphen darzustellen, die direkte Verwendung der CSR-Struktur ist, wie folgt

>>> data = [0, 0, 0]
>>> indices = [2, 0, 1]
>>> indptr = [0, 1, 3]
>>> graph = csr_array((data, indices, indptr))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

Wenn eine oder beide Partitionen leer sind, ist die Zuordnung ebenfalls leer

>>> graph = csr_array((2, 0))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[-1 -1]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[]

Wenn das Eingabearray quadratisch ist und bekannt ist, dass der Graph eine perfekte Zuordnung zulässt, d. h. eine Zuordnung mit der Eigenschaft, dass jeder Knoten im Graphen zu einer Kante in der Zuordnung gehört, dann kann die Ausgabe als Permutation von Zeilen (oder Spalten) betrachtet werden, die das Eingabearray in ein Array verwandelt, bei dem alle Diagonalelemente nicht leer sind.

>>> a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]
>>> graph = csr_array(a)
>>> perm = maximum_bipartite_matching(graph, perm_type='row')
>>> print(graph[perm].toarray())
[[1 0 0 1]
 [0 1 2 0]
 [0 1 3 0]
 [2 0 0 3]]