Hopcroft-Karp algorithme en Python

Question

J'essaie d'implémenter le Hopcroft Karp algorithm en Python en utilisant networkx comme représentation graphique.

Actuellement, je suis aussi loin que cela:

#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) 

L'algorithme est tiré de http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Toutefois, il ne fonctionne pas. J'utilise le code de test suivant

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 

Malheureusement, cela ne fonctionne pas, je me retrouve dans une boucle sans fin :(. Quelqu'un peut-il repérer l'erreur, je suis d'idées et je dois admettre que je n'ai pas encore pleinement comprendre l'algorithme, il est donc la plupart du temps une mise en œuvre du code de pseudo sur wikipedia

Answer 1

la ligne

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

devrait être

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

selon le pseudo-code sur la page Wikipedia. Le seul autre problème que je vois est que vous utilisez le deque comme une pile et que vous voulez l'utiliser comme une file d'attente. Pour remédier à cela, il suffit de popleft plutôt que pop (qui apparaît à droite). Ainsi, la ligne

v = self.q.pop() 

devrait être

v = self.q.popleft() 

Espérons que tout le reste fonctionne. Je vérifiais juste que votre code Python fonctionne de la même manière que le pseudo-code de Wikipédia donc j'espère que ce pseudo-code est correct.

Answer 2

En python, il existe un package pour cet algorithme. HopcroftKarp, vous pouvez directement utiliser ce package pour votre implémentation.