Максимальный вес / минимальная стоимость соответствия кода в Python

Question

Я ищу код Python для сопоставления максимального веса / минимальной стоимости в двудольном графе.Я использовал общий код соответствия максимального веса в NetworkX, но нахожу его слишком медленным для своих нужд.Вероятно, это связано как с тем, что общий алгоритм работает медленнее, так и с тем, что решение NetworkX полностью реализовано на Python.В идеале я хотел бы найти некоторый код на Python для задачи сопоставления двудольных, заключающий в себе некоторый код на C / C ++, но сейчас было бы полезно все, что быстрее, чем реализация NetworkX.

Answer 1

После некоторых дальнейших исследований я обнаружил, что следующие два модуля особенно полезны (http://pypi.python.org/pypi/pyLAPJV/0.3 и http://pypi.python.org/pypi/hungarian).. Оба эти алгоритма реализованы на C ++ с привязками Python и работают намного быстрее, чем NetworkX. реализация соответствия. Реализация pyLAPJV, однако, кажется слишком нестабильной для моих нужд и не может правильно обрабатывать идентично взвешенные ребра. Венгерский модуль (хотя предположительно медленнее, чем алгоритм pyLAPJV) работает примерно на 3 порядка быстрее, чем реализация NetworkX для размеров данных, с которыми я сейчас работаю. Я также собираюсь еще раз взглянуть на код, предложенный kunigami, так как считаю, что он может быть запущен, хотя Шедскин довольно легко даст достаточно быструю реализацию.

Answer 2

Пробовали ли вы скупую реализацию венгерского алгоритма, также известного как алгоритм Мункре или Кун-Мункрес?

scipy.optimize.linear_sum_assignment

Answer 3

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

Hopcroft-Karp Bipartite Matching

Answer 4

Согласование минимального веса двудольных может быть решено с помощью венгерского алгоритма ( wikipedia ). Ссылка в википедии ссылается на реализацию python . Я не уверен, что он быстрее, чем код, который вы упомянули.