Algoritmo Hopcroft-Karp in Python
-
11-10-2019 - |
Domanda
Sto cercando di implementare la Hopcroft Karp algoritmo in Python utilizzando NetworkX come rappresentazione grafica.
Al momento io sono per quanto riguarda 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 Comunque, 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 lavoro, mi finire in un ciclo infinito :(. Qualcuno può individuare l'errore, io sono a corto di idee e devo ammettere che non ho ancora comprendere appieno l'algoritmo, quindi è in gran parte un'implementazione del codice pseudo su wikipedia
Soluzione
La linea
if self.pair[v] and self.dfs(v):
dovrebbe essere
if self.pair[v] is None and self.dfs(v):
come per la pseudo-codice sulla pagina di Wikipedia. L'unico altro problema che vedo è che si sta utilizzando la coda doppia come una pila e si desidera utilizzarlo come una coda. Per ovviare a questo, non vi resta che 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 codice Python funziona nello stesso modo come il pseudocodice su Wikipedia quindi speriamo che pseudocodice è corretta.
Altri suggerimenti
In Python esiste un pacchetto per questo algoritmo. HopcroftKarp , è possibile utilizzare direttamente il pacchetto per l'implementazione.