Algoritmo di Hopcroft-Karp in Python

Question

Sto cercando di implementare lo Hopcroft Karp algorithm in Python usando networkx come rappresentazione grafica.

Attualmente sto fino a questo:

#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'algoritmo è tratto da http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm Tuttavia non funziona. Io uso il seguente codice di prova

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 

Purtroppo questo non funziona, finisco in un ciclo infinito :(. Qualcuno può individuare l'errore, io sono a corto di idee e devo ammettere che non ho ancora pienamente capire l'algoritmo, quindi è principalmente un'implementazione del codice pseudo su wikipedia

Answer 1

la linea

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

dovrebbe essere

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

come da pseudo-codice sulla pagina di Wikipedia. L'unico altro problema che vedo è che stai usando il deque come stack e vuoi usarlo come coda. Per rimediare a questo, è sufficiente popleft piuttosto che pop (che si apre a destra). Così la linea

v = self.q.pop() 

dovrebbe essere

v = self.q.popleft() 

Speriamo che tutto il resto funziona. Stavo solo controllando che il tuo codice Python funzioni allo stesso modo dello pseudocodice su Wikipedia, quindi spero che lo pseudocodice sia corretto.

Answer 2

In python esiste un pacchetto per questo algoritmo. HopcroftKarp, è possibile utilizzare direttamente tale pacchetto per la propria implementazione.