Codice di corrispondenza bipartito di costo massimo/minimo in Python

Question

Sto cercando il codice Python per la corrispondenza di peso/minimo costo massimo in un grafico bipartito. Ho utilizzato il codice di corrispondenza del peso massimo del caso generale in NetworkX, ma lo trovo troppo lento per le mie esigenze. Ciò è probabilmente dovuto sia al fatto che l'algoritmo generale è più lento, sia al fatto che la soluzione NetworkX è implementata interamente in Python. Idealmente, mi piacerebbe trovare un codice Python per il problema di corrispondenza bipartito che avvolge un po 'di codice C/C++, ma al momento, qualsiasi cosa più veloce dell'implementazione di NetworkX sarebbe utile.

Answer 1

Dopo ulteriori indagini, ho trovato particolarmente utili i seguenti due moduli (http://pypi.python.org/pypi/pyLAPJV/0.3 e http://pypi.python.org/pypi/hungarian). Sono entrambi algoritmi implementati in C++ con collegamenti Python ed eseguiti molto più velocemente rispetto all'implementazione di corrispondenza di NetworkX. L'implementazione di pyLAPJV, tuttavia, sembra essere un po 'troppo volubile per le mie esigenze e non gestisce correttamente i bordi con pesi identici. Il modulo ungherese (anche se apparentemente più lento dell'algoritmo pyLAPJV) esegue circa 3 ordini di grandezza più velocemente dell'implementazione di NetworkX sulle dimensioni dei dati con cui attualmente mi occupo. Darò anche un'altra occhiata al codice suggerito da kunigami, poiché ritengo che possa essere eseguito con Shedskin abbastanza facilmente per dare un'implementazione ragionevolmente veloce.

Answer 2

Non troppo sicuro se questo è ciò che si sta cercando, ma è un'implementazione python dell'algoritmo di corrispondenza del grafico bipartito Hopcroft-Karp. In caso contrario, probabilmente può essere un buon punto di partenza per te.

Hopcroft-Karp Bipartite Matching

Answer 3

Il peso corrispondente minimo bipartito può essere risolto dall'algoritmo ungherese (wikipedia). Il collegamento nei collegamenti di Wikipedia ad un'implementazione python. Non sono sicuro se sia più veloce del codice che hai citato, però.

Answer 4

Hai provato l'implementazione scipy dell'algoritmo ungherese, noto anche come algoritmo Munkres o Kuhn-Munkres?

scipy.optimize.linear_sum_assignment