algoritmo Hopcroft-Karp en Python
-
11-10-2019 - |
Pregunta
Estoy tratando de poner en práctica el Hopcroft Karp algoritmo 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 toma 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
Por desgracia esto no funciona, que terminan en un bucle sin fin :(. ¿Alguien puede detectar el error, estoy fuera de ideas y debo admitir que todavía no he entender completamente el algoritmo, por lo que es en su mayoría una implementación de la pseudo código en wikipedia
Solución
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 de la página de Wikipedia. El único otro problema que veo es que está utilizando el deque como una pila y desea utilizarlo como una cola. Para remediar esto, sólo tiene que popleft en lugar de pop (que aparece a la derecha). Así, la línea
v = self.q.pop()
debería ser
v = self.q.popleft()
Con suerte todo lo demás funciona. Estaba comprobando que su código Python funciona de la misma manera que el pseudocódigo en Wikipedia, así que espero que pseudocódigo es correcta.
Otros consejos
En Python hay un paquete para este algoritmo. HopcroftKarp , puede utilizar directamente la oferta para su aplicación.