# Hopcroft–Karp algorithm in Python

Filed under:
|
|
|
|
##### bipartite

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

Currently I am as far as this:

``````#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 it does not work. I use 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 does not work, I end up in an endless loop :(. Can someone spot the error, I am out of ideas and I must admit that I have not yet fully understand the algorithm, so it is mostly an implementation of the pseudo code on wikipedia

© Stack Overflow or respective owner

• #### unmet dependencies in Ubuntu 12.04

I tried today to install a dvb-card on my Ubuntu 12.04 (Linux blauhai-linux 3.2.0-25-generic #40-Ubuntu SMP Wed May 23 20:30:51 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux ). The installation failed with an error. After that, i tried to install python (it was already installed but i got this error): linux:~\$… >>> More

• #### How can I get sikuli-ide to work?

I installed sikuli-ide with sudo apt-get install sikuli-ide Everything was fine until I tried to start it from the terminal. I typed sikuli-ide But the only response I got was [info] locale: en_US The application was not started, furthermore there is no desktop file and sikuli-ide does not… >>> More

• #### Getting PATH right for python after MacPorts install

as seen on Super User - Search for 'Super User'
I can't import some python libraries (PIL, psycopg2) that I just installed with MacPorts. I looked through these forums, and tried to adjust my PATH variable in \$HOME/.bash_profile in order to fix this but it did not work. I added the location of PIL and psycopg2 to PATH. I know that Terminal is… >>> More

• #### call python with system() in R to run a python script emulating the python console

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to pass a chunk of Python code to Python in R with something like system('python ...'), and I'm wondering if there is an easy way to emulate the python console in this case. For example, suppose the code is "print 'hello world'", how can I get the output like this in R? >>> print… >>> More

• #### Python - Calling a non python program from python?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am currently struggling to call a non python program from a python script. I have a ~1000 files that when passed through this C++ program will generate ~1000 outputs. Each output file must have a distinct name. The command I wish to run is of the form: program_name -input -output -o1 -o2… >>> More

• #### Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More

• #### word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More

• #### Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More

• #### Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More

• #### collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More