Hopcroft–Karp algorithm: Difference between revisions

Revision as of 13:45, 21 December 2008

Revision as of 20:59, 5 March 2009

Line 102:

if (P is not empty)

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

oddfor :=all true;(t,u):P

// Make (t,qu) match (first,all third,edges ...starting edges)from the last layer

for all (t,q):P

ift.matching (odd):= u;

qu.matching := t;

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

t.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 since it will be updated in the next iteration when odd is true

odd := true;

end if

end for

end if

Line 121 ⟶ 113:

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

// to layer 0.

// '''Return''': List of edges on augmenting path. Returns only edges from

// p: Is at the end of a non-matching edge (an odd layer)

// even to odd layers.

// '''p''': IsVertex at the end of a non-matching edge (an odd layer)

Get_Augmenting_Path(p):

if (p.visited OR p.layer = 0)

Line 128 ⟶ 122:

p.visited:= true;

// Consider only edges going one layer backwards.

for all (q,p):E s.t. (p.layer+-1=q.layer AND NOT q.matching.visited)

// q is at an even layer

if (q.layer = 0)

// q is free vertex on the first layer

return (q, p);

for allreturn (t,(q, p)):P;

end if

// Note that q.matching must be defined, and point to

Line 138 ⟶ 133:

if (P not empty)

// Append (q, p) to the path found so far.

return (P, (q, p));

end if

end for