scipy.sparse.csgraph.

min_weight_full_bipartite_matching#

scipy.sparse.csgraph.min_weight_full_bipartite_matching(biadjacency, maximize=False)#

Gibt die minimale vollständige bipartite Zuordnung eines bipartiten Graphen zurück.

Hinzugefügt in Version 1.6.0.

Parameter:
biadjacencySparse Array oder Matrix

Biadjacency-Matrix des bipartiten Graphen: Ein Sparse Array im CSR-, CSC- oder COO-Format, dessen Zeilen die eine Partition des Graphen und dessen Spalten die andere Partition darstellen. Eine Kante zwischen zwei Knoten wird durch den entsprechenden Eintrag in der Matrix angezeigt, und das Gewicht der Kante wird durch den Wert dieses Eintrags bestimmt. Dies darf nicht mit der vollständigen Adjazenzmatrix des Graphen verwechselt werden, da nur die Untermatrix benötigt wird, die die bipartiten Strukturen definiert.

maximizebool (Standard: False)

Berechnet eine Zuordnung mit maximalem Gewicht, wenn wahr.

Rückgabe:
row_ind, col_indArray

Ein Array von Zeilenindizes und eines von entsprechenden Spaltenindizes, die die optimale Zuordnung angeben. Das Gesamtgewicht der Zuordnung kann als graph[row_ind, col_ind].sum() berechnet werden. Die Zeilenindizes werden sortiert sein; im Fall einer quadratischen Matrix sind sie gleich numpy.arange(graph.shape[0]).

Hinweise

Sei \(G = ((U, V), E)\) ein gewichteter bipartiter Graph mit Nicht-Null-Gewichten \(w : E \to \mathbb{R} \setminus \{0\}\). Diese Funktion liefert dann eine Zuordnung \(M \subseteq E\) mit der Kardinalität

\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]

die die Summe der Gewichte der Kanten, die in die Zuordnung einbezogen sind, \(\sum_{e \in M} w(e)\) minimiert, oder löst einen Fehler aus, wenn keine solche Zuordnung existiert.

Wenn \(\lvert U \rvert = \lvert V \rvert\), wird dies üblicherweise als perfekte Zuordnung bezeichnet; hier, da wir zulassen, dass \(\lvert U \rvert\) und \(\lvert V \rvert\) sich unterscheiden, folgen wir Karp [1] und bezeichnen die Zuordnung als vollständig.

Diese Funktion implementiert den LAPJVsp-Algorithmus [2], kurz für „Linear assignment problem, Jonker–Volgenant, sparse“.

Das Problem, das er löst, ist äquivalent zum rechteckigen linearen Zuordnungsproblem. [3] Als solches kann diese Funktion verwendet werden, um dieselben Probleme zu lösen wie scipy.optimize.linear_sum_assignment. Diese Funktion kann besser abschneiden, wenn die Eingabe dicht ist, oder für bestimmte spezielle Eingabetypen, wie z. B. solche, bei denen der \((i, j)\)-te Eintrag der Abstand zwischen zwei Punkten im euklidischen Raum ist.

Wenn keine vollständige Zuordnung existiert, löst diese Funktion einen ValueError aus. Um die Größe der größten Zuordnung im Graphen zu bestimmen, siehe maximum_bipartite_matching.

Wir verlangen, dass die Gewichte nicht Null sind, nur um Probleme bei der Handhabung expliziter Nullen bei der Konvertierung zwischen verschiedenen Sparse-Darstellungen zu vermeiden. Nullgewichte können behandelt werden, indem eine Konstante zu allen Gewichten addiert wird, so dass die resultierende Matrix keine Nullen enthält.

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

Referenzen

[1]

Richard Manning Karp: An algorithm to Solve the m x n Assignment Problem in Expected Time O(mn log n). Networks, 10(2):143-152, 1980.

[2]

Roy Jonker und Anton Volgenant: A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38:325-340, 1987.

Beispiele

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

Betrachten wir zunächst ein Beispiel, in dem alle Gewichte gleich sind

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

Hier erhalten wir lediglich eine perfekte Zuordnung des Graphen

>>> print(min_weight_full_bipartite_matching(biadjacency)[1])
[2 0 1]

Das heißt, die erste, zweite und dritte Zeile sind mit der dritten, ersten bzw. zweiten Spalte abgeglichen. Beachten Sie, dass in diesem Beispiel die 0 in der Eingabematrix *nicht* einem Kanten-Gewicht von 0 entspricht, sondern einem Paar von Knoten, das nicht durch eine Kante verbunden ist.

Beachten Sie auch, dass in diesem Fall die Ausgabe mit dem Ergebnis der Anwendung von maximum_bipartite_matching übereinstimmt

>>> from scipy.sparse.csgraph import maximum_bipartite_matching
>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
>>> print(maximum_bipartite_matching(biadjacency, perm_type='column'))
[2 0 1]

Wenn mehrere Kanten verfügbar sind, werden die mit den niedrigsten Gewichten bevorzugt

>>> biadjacency = csr_array([[3, 3, 6], [4, 3, 5], [10, 1, 8]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(col_ind)
[0 2 1]

Das Gesamtgewicht beträgt in diesem Fall \(3 + 5 + 1 = 9\)

>>> print(biadjacency[row_ind, col_ind].sum())
9

Wenn die Matrix nicht quadratisch ist, d.h. wenn die beiden Partitionen unterschiedliche Kardinalitäten haben, ist die Zuordnung so groß wie die kleinere der beiden Partitionen

>>> biadjacency = csr_array([[0, 1, 1], [0, 2, 3]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 1] [2 1]
>>> biadjacency = csr_array([[0, 1], [3, 1], [1, 4]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 2] [1 0]

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

>>> biadjacency = csr_array((2, 0))
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[] []

Im Allgemeinen erreichen wir immer dieselbe Summe von Gewichten wie bei der Verwendung von scipy.optimize.linear_sum_assignment, aber beachten Sie, dass bei dieser fehlende Kanten durch einen Array-Eintrag von float('inf') dargestellt werden. Generieren wir ein zufälliges Sparse-Array mit ganzzahligen Einträgen zwischen 1 und 10

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from scipy.optimize import linear_sum_assignment
>>> sparse = random_array((10, 10), rng=42, density=.5, format='coo') * 10
>>> sparse.data = np.ceil(sparse.data)
>>> dense = sparse.toarray()
>>> dense = np.full(sparse.shape, np.inf)
>>> dense[sparse.row, sparse.col] = sparse.data
>>> sparse = sparse.tocsr()
>>> row_ind, col_ind = linear_sum_assignment(dense)
>>> print(dense[row_ind, col_ind].sum())
25.0
>>> row_ind, col_ind = min_weight_full_bipartite_matching(sparse)
>>> print(sparse[row_ind, col_ind].sum())
25.0