Algoritmo Hopcroft-Karp en Python

Question

Estoy tratando de implementar el Hopcroft Karp algorithm en Python usando networkx como representación gráfica.

Actualmente estoy en lo siguiente:

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

El algoritmo se ha tomado de http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Sin embargo, no funciona. Yo uso el siguiente código de prueba

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 

Desafortunadamente esto no funciona, termino en un bucle sin fin :(. Alguien puede detectar el error, estoy fuera de ideas y debo admitir que no tengo todavía completamente entender el algoritmo, por lo que es en su mayoría una implementación de la pseudo código en la wikipedia

Answer 1

la línea

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

debería ser

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

según el pseudo-código en la página de Wikipedia. El único otro problema que veo es que estás usando la deque como una pila y quieres usarla como una cola. Para remediar eso, solo necesitas usar popleft en lugar de pop (que sale bien). Por lo que la línea de

v = self.q.pop() 

debe ser

v = self.q.popleft() 

todo lo demás funciona con esperanza. Estaba comprobando que tu código de Python funciona de la misma manera que el pseudocódigo en Wikipedia, así que con suerte ese pseudocódigo es correcto.

Answer 2

En python hay un paquete para este algoritmo. HopcroftKarp, puede usar directamente ese paquete para su implementación.