Алгоритм Хопкрофта-Карпа в Python

Я пытаюсь реализовать алгоритм Hopcroft Karp в Python, используя networkx как представление графика.

В настоящее время я до сих пор:

#Algorithms for bipartite graphs import networkx as nx import collections class HopcroftKarp(object): INFINITY = -1 def __init__(self, G): self.G = G def match(self): self.N1, self.N2 = self.partition() self.pair = {} self.dist = {} self.q = collections.deque() #init for v in self.G: self.pair[v] = None self.dist[v] = HopcroftKarp.INFINITY matching = 0 while self.bfs(): for v in self.N1: if self.pair[v] and self.dfs(v): matching = matching + 1 return matching def dfs(self, v): if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == self.dist[v] + 1 and self.dfs(self.pair[u]): self.pair[u] = v self.pair[v] = u return True self.dist[v] = HopcroftKarp.INFINITY return False return True def bfs(self): for v in self.N1: if self.pair[v] == None: self.dist[v] = 0 self.q.append(v) else: self.dist[v] = HopcroftKarp.INFINITY self.dist[None] = HopcroftKarp.INFINITY while len(self.q) > 0: v = self.q.pop() if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == HopcroftKarp.INFINITY: self.dist[ self.pair[u] ] = self.dist[v] + 1 self.q.append(self.pair[u]) return self.dist[None] != HopcroftKarp.INFINITY def partition(self): return nx.bipartite_sets(self.G) 

Алгоритм взят из http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Однако это не сработает. Я использую следующий тестовый код

 G = nx.Graph([ (1,"a"), (1,"c"), (2,"a"), (2,"b"), (3,"a"), (3,"c"), (4,"d"), (4,"e"),(4,"f"),(4,"g"), (5,"b"), (5,"c"), (6,"c"), (6,"d") ]) matching = HopcroftKarp(G).match() print matching 

К сожалению, это не работает, я заканчиваю бесконечный цикл 🙁 Может кто-то заметить ошибку, у меня нет идей, и я должен признать, что я еще не полностью понял алгоритм, так что это в основном реализация псевдо код на wikipedia

  • Преобразование кадра данных pandas в ряд
  • Использовать код учебника LSTM для предсказания следующего слова в предложении?
  • pypi UserWarning: Неизвестный параметр распространения: 'install_requires'
  • Классы словаря Python. «В» сложности
  • Связанный, вложенный dict () получает вызовы в python
  • есть ли пул для ThreadingMixIn и ForkingMixIn для SocketServer?
  • Установите глобальную горячую клавишу с помощью Python 2.6
  • Закрываются ли файлы во время выхода из исключения?
  • 2 Solutions collect form web for “Алгоритм Хопкрофта-Карпа в Python”

    Линия

     if self.pair[v] and self.dfs(v): 

    должно быть

     if self.pair[v] is None and self.dfs(v): 

    в соответствии с псевдокодом на странице Википедии. Единственная проблема, которую я вижу, это то, что вы используете deque как стек, и вы хотите использовать его как очередь. Чтобы исправить это, вам просто нужно поплечить, а не поп (который появляется справа). Таким образом, линия

     v = self.q.pop() 

    должно быть

     v = self.q.popleft() 

    Надеюсь, все остальное работает. Я просто проверял, что ваш код Python работает так же, как псевдокод в Википедии, поэтому надеюсь, что псевдокод правильный.

    В python есть пакет для этого алгоритма. HopcroftKarp , вы можете напрямую использовать этот пакет для своей реализации.

    Python - лучший язык программирования в мире.