Алгоритм Hopcroft-Karp в Python

Question

Я пытаюсь реализовать Hopcroft Karp algorithm в 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 

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

Answer 1

линия

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 работает так же, как псевдокод в Википедии, поэтому надеюсь, что псевдокод правильный.

Answer 2

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