Hopcroft–Karp algorithm: Difference between revisions

Revision as of 22:15, 9 October 2008

Revision as of 07:17, 11 October 2008

Line 23:

The algorithm is run in phases. Each phase consists of:

* A BFS is run from free U vertices. This BFS stops at depthlayer ''k'' where aone or more free V vertexvertices isare reached. NoteCollect that,''all'' free V vertices at thelayer last''k'' iteration,and put them in the algorithmset collectsF. allA freevertex V''v'' verticesis atput depthin F iff <math> v\in V</math> and ''kv'' ends a shortest augmenting path.

* Find a maximal set of non-overlapping''vertex disjoint'' augmenting paths of length ''k''. AchievedThis is set is computed by DFS from theF free V vertices (computed by BFS) to free U vertices. Every one of this paths is used to enlarge M.

'''Work-in-progress'''. ''The following pseudo code does not describe this algorithm correctly. It has to be rewritten. Even worse, it requires O(n) iterations instead of <math>O(\sqrt{n})</math> as a result its complexity is O(n³) instead of O(n^2.5)''

We also maintain a queue(first in first out data-structure) Q in our pseudo code.

''Pseudo Code''

for all <math>q\in U \cup V</math>

q.matching= null;

end for

while (true)

// Find all potential beginnings of shortest augmenting paths

B := empty;

for all u:U s.t. (u.matching = null)

insert u in B;

end for

// Find all endings of shortest augmenting paths

F := Find_Augmenting_Path_Endings(B);

if (F is empty)

M:= empty;

for all u:U s.t. (u.matching ≠ null)

insert (u, u.matching) in M; // insert edge

end for

return M;

end if

Augment_Paths(F);

end while

// Perform BFS starting with vertices of B.

Initialization:

// '''Return''': a list of free vertices which potentially

// end the shortest vertex-disjoint augmenting paths.

// '''Side effect''': For any vertex v.layer has the index of

// the BFS layer to reach this vertex (or -1)

// '''B''': potential beginning of augmenting paths

Find_Augmenting_Path_Endings(B):

MQ := nullB;

// F: The set of free endings (the other side of augmenting paths)

F := empty;

for u:U

for all <math>q\in U \cup V</math>

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

q.layer:=-1;

if (v is not in M)

end for

add (u,v) to M;

// The potential beginnings of augmenting paths are at layer 0.

break;

for all b:B

end if

b.layer:=0;

end for

end for

Start;

Start :

for all u:U not in M

if (u.flag_inserted != true)

insert u in Q;

u.flag_inserted = true;

u.previous_node = null;

end if

end for

Create_path;

Create_path:

while (Q is not empty)

Q' := empty;

pop an element q from Q;

for all q: Q

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

for eall (q,p): E outs.t. of(p.layer q= -1)

if (e is not in M && p.flag_inserted layer:= false)q.layer+1;

if (p.matching is= a free vertexnull)

insert p in F; // Collect the free vertex, continue BFS

Augmenting_Path(q.previous_node, q , p)

else

addinsert p toin Q';

end p.flag_inserted = true;if

end if for

end if

end for

if (F is not empty)

return F; // Free vertices found, stop at this layer.

else

end if

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

Q:= empty;

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

for all add p to q:Q;'

// By p.flag_insertedconstruction, =q true;matched.

endp:= ifq.matching;

p.layer:= q.layer+1;

insert p in Q;

end for

end if

end while

return Mempty;

Augment_Paths(F):

Augmenting_Path(q.previous_node, q , p) :

for all <math>q\in U \cup V</math>

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

q.visited= false;

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

end for

originally un-matched. Update M accordingly.

Empty thefor queue;all q:F

P:=Get_Augmenting_Path(q);

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

// Make sure q ends a ''vertex-disjoint'' augmenting path

Delete the paths;

if (P is not empty)

Start;

// Perform <math> M := M\oplus P </math>

odd := true;

for all (t,q):P

if (odd)

// Make (t,q) match (first, third, ... edges)

p.matching := q;

q.matching := t;

odd := false;

else

// t.matching has already been updated by the ''odd'' condition

q.matching := null; // This is not strictly required

odd := true;

end if

end for

end if

end for

// DFS from p, avoiding previously visited vertices.

// Start at the last layer of BFS, and go backwards

// to layer 0.

Get_Augmenting_Path(p):

if (p.visited)

return empty;

end if

p.visited:= true;

if (p.layer = 0) // layer 0 has free vertices.

return (p);

end if

// Consider only edges going one layer backwards.

for all (q,p):E such that p.layer+1=q.layer

P= Get_Augmenting_Path(q);

if (P not empty)

return (q, P); // Prepend q to the path found so far.

end if

end for

// Could not find a vertex-disjoint augmenting path ending with p.

return empty;

== References ==