Hopcroft-Karp Algorithm in Python

Question

I am trying to implement the Hopcroft Karp algorithm in Python using networkx as a graph representation.

Currently, I still:

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

The algorithm is taken from http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm However, this will not work. I am using the following test code

 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 

Unfortunately, this will not work, I ended up in an endless loop :( Maybe someone will notice an error, I have no ideas, and I must admit that I have not completely understood the algorithm, so this is basically an implementation of pseudocode on wikipedia

Answer 1

Line

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

it should be

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

in accordance with the pseudocode on the Wikipedia page. The only problem I see is that you are using deque as a stack and you want to use it as a queue. To fix this, you just need to heal, not pop (which appears on the right). So the line

 v = self.q.pop() 

it should be

 v = self.q.popleft() 

Hope everything else will work. I just checked that your Python code works the same as the Wikipedia pseudocode, so I hope the pseudocode is correct.

Answer 2

There is a package in python for this algorithm. HopcroftKarp , you can directly use this package for your implementation.