Hopcroft–Karp algorithm: Difference between revisions

Revision as of 06:27, 24 April 2008

Revision as of 07:53, 24 April 2008

Line 27:

''Pseudo Code''

Initialization:

M = null;

for u:U

for v:V such that (u,v) belongs to E

Start :

if (v is not in M)

{ add (u,v) to M;

for u:U

break; }

for v:V such that (u,v) belongs to E

end if

if v is not in M

end for

{ add (u,v) to M

end for

break; }

Start;

Start :

for all u:U not in M

if (flag_inserted != true)

{ insert u in Q;

u.flag_inserted = true; }

u.previous_node = null;

end if

end for

Create_path;

end for

Create_path:

for all u:U not in M

if flag_inserted != true

while (Q is not empty)

{ insert u in Q

pop an element q from Q;

u.flag_inserted = true; }

if (q.previous_node = null || (q.previous_node,q) is in M )

end for

for e(q,p): E out of q

if (e is not in M && p.flag_inserted = false)

if (p is a free vertex)

Augmenting_Path(q.previous_node, q , p)

else

add p to Q;

p.flag_inserted = true;

end if

end if

end for

else

for e(q,p): E out of q

if (e is in M && p.flag_inserted = false)

add p to Q;

p.flag_inserted = true;

end if

end for

end if

end while

return M

Augmenting_Path(q.previous_node, q , p) :

Re-create the augmenting path ( p -> q -> q.previous_node ->...) using bfs, till the time you hit a free vertex.

Then alternate by un-matching all the nodes in that path that were matched and matching all the nodes which were

originally un-matched. Update M accordingly.

Empty the queue;

For each node, mark all the flag_inserted false and previous_node = null;

Delete the paths;

Start;