Talk:Hopcroft–Karp algorithm

This needs an explanation of the "run really fast" step (http://www.fysh.org/~katie/computing/methodologies.txt)

Delta

Is $N\Delta P$ the only standard terminology we can use? I would prefer to leave $\Delta$ to the maximum degree of the graph. Adking80 (talk) 22:06, 18 July 2008 (UTC)

I have seen $N\oplus P$ (symmetric difference) used in several papers. It seems a much better notation to me. Also, the meaning of $\Delta$ is not explained on the page. I have updated the page accordingly. —Preceding unsigned comment added by Michael Veksler (talk • contribs) 22:29, 9 October 2008 (UTC)

Shortestest

Is shortestest a word? ;D Ossian Hanning (talk) 20:37, 7 March 2008 (UTC)

Maximum vs. maximal

Changed the incorrect "maximum" to "maximal". — Preceding unsigned comment added by 80.145.225.62 (talk) 22:44, 3 October 2006 (UTC)

I agree. Thanks for persisting after the incorrect revert. —David Eppstein 05:55, 4 October 2006 (UTC)

I am sorry for the incorrect revert. I now think that I was wrong. I started this article because the algorithm was mentioned in the text of another article. The only reference I had was CLRS, where it said maximum. So when I saw this edit from an unregistered user, I checked in CLRS, saw that it said maximum, and assumed that the editor was either in error or mischevious. Sorry about this. Let me check that we agree with terminology:

If we go through a one-dimmensional state-space (x-axis below), where each state has a value (y-axis below),

           B                                                                   
           /\                                                                  
   A      /  \                                                                 
   /\    /    \                                                                
  /  \  /      \                                                               
 /    \/        \                                                              
/                \

then here both A and B are maximal points, while only B is a maximum. This is the terminology used in the article Matching.

The description in CLRS is actually just given as an exercise. I tried to solve it, but could not see how to find "maximum set of vertex-disjoint shortest augmenting paths" in $O(V+E)$, so I just wrote the pseudocode for the algorithm as described, and put it in my ever-growing TODO to figure out the missing part. I now found a description of the pseudo-code which still says maximum in the comments, but the code clearly gives only something maximal. So the problem was simpler than I thought :) Thanks for the correction, and sorry about my error. Klem fra Nils Grimsmo 09:16, 4 October 2006 (UTC)

Difference from Dinic algorithm (Dinits' algorithm)?

What's the difference between this algorithm and Dinic algorithm? To me, it just looks like Dinic algorithm - only run on a specific input, so it has better time complexity than general-case Dinic. --Lukas Mach 22:27, 27 December 2006 (UTC)

It's none... H-K is 1973 algorithm and Dinic is 1976 algorithm. --Lukas Mach 01:55, 26 February 2007 (UTC)

Another estimations

Another estimations are O((V+E)V ^1/2) and O(V ^5/2): Lipski W., Kombinatoryka dla Programistow, [Combinatorics for Programmers], Wydawnictwa Naukowo-Techniczne, Warzawa, 1982.--Tim32 (talk) 10:58, 19 November 2007 (UTC)

Both bounds are worse. We can assume that every vertex is incident to at least one edge, so $V+E=O(E)$. We also know that $E<V^{2}/2$. Adking80 (talk) 22:04, 18 July 2008 (UTC)

Pseudocode

Is it just me, or is the pseudocode rather hard to read? For example, the first loop tripped me a bit, because it is some akward mixture of high-level functions ((u,v) in E) and low-level implementation (for node u, node v). Furthermore, the code checks for nodes being in M. I do not understand this, as M is a matching, and thus, a set of edges? --Tetha (talk) 05:49, 11 June 2008 (UTC)

M is a matching. When the code asks whether a vertex is in M, it means, is it an endpoint of one of the edges in M? I don't think it's any shorter or clearer than what's here, but if it would help you to see actual code for this algorithm, I have some here. (You can ignore the "imperfections" routine in that file; it solves a different and somewhat more complicated problem.) —David Eppstein (talk) 06:32, 11 June 2008 (UTC)

At least for me, the python code helps a lot. My definition of a matching came from graph theory, where a matching was just a set of edges that encode the matching (that is, an edge (u,v) in M means: u is matched with v). Your matching is a mapping that maps a node u to the node v, with u being matched with v. In your world, it makes a lot of sense to ask: node in matching, in mine, it did not (I rather would ask: exist an x with (x, u) in M.). Thank you. --Tetha (talk) 09:39, 11 June 2008 (UTC)

LIFO queue?

Page says:

We also maintain a queue(last in first out datastructure)

Last in, first out is a stack, no? —Preceding unsigned comment added by Talex (talk • contribs) 11:40, 20 July 2008 (UTC)

Queue is FIFO, stack is LIFO...I seem to be strange. 210.122.65.2 (talk) 07:50, 18 August 2008 (UTC)

Incorrect pseudo-code

I am sorry that I was trigger-happy with the main article. Only after I have completed my edit did I realize that it should have been discussed on this forum first. (First time to edit a Wikipedia page).

Did not touch the pseudo-code itself, only the part that explains it. It may take me much longer to write a readable and correct version of the pseudo-code.

The pseudo code is not complicated without a reason, it is incorrect. I realized it after I have implemented the algorithm only to see that in some cases it requires almost |V| iterations (rather than the promised $O({\sqrt {(|V|)}})$).

The main problem with the pseudo code (other than clarity) is that the BFS stops immediately when it discovers an augmenting path. The is against the way the original algorithm works, when it generates a maximal number of augmenting paths each time.

The proof that only $O({\sqrt {(|V|)}})$ iterations are needed is based on the premises that each BFS iteration will return strictly longer augmenting paths. The current pseudo-code does not work this way.

For example, consider a graph with edges (divided into n subsets):

• (u01, v01) (u01, v02) (u02, v01)
• (u11, v11) (u11, v12) (u12, v11)

...

• (u_n1, v_n1) (u_n1, v_n2) (u_n2, v_n1)

With initial matching marked in bold The pseudo-code will require n iterations, when the real algorithm requires only one. Michael Veksler (talk) 23:09, 9 October 2008 (UTC)

Suggested pseudo-code:

for all $q\in U\cup V$
  q.matching= null;
end for
while (true)
  // Find all potential beginnings of shortest augmenting paths
  B := empty;
  for all u:U
    if (u.matching = null)
       insert u in B;
    end if
  end for
  
  // Find all endings of shortest augmenting paths
  E := Find_Augmenting_Path_Endings(B);
  if (E is empty)
    M:= empty;
    for all u:U
       if (u.matching ≠ null)
         insert (u, u.matching) in M;
       end if
    end for
    return M;
  end if
  Augment_Paths(E);
end while

// Perform BFS starting with vertices of B.
// Return: a list of free vertices which potentially 
//         end the shortest 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):
 
Q := B;
// F: The set of free endings (the other side of augmenting paths)
F := empty;
for all $q\in U\cup V$
  q.layer:=-1;
end for
// The potential beginnings of augmenting paths are at layer 0.
for all b:B
  b.layer:=0;
end for

while (Q is not empty)
   Q' := empty;
   for all q: Q
     for all (q,p):E
       if (p.layer = -1)
         p.layer:= q.layer+1;
         if (p.matching = null)
           insert p in F; // Collect the free vertex, continue BFS
         else
           insert p in Q';
         end if
       end if
     end for
   end for
   if (F is not empty)
      return F; // Free vertices found, stop at this layer.
   end if
   Q:= empty;
   for all q:Q'
     // By construction, q is not a free vertex.
     p:= q.matching;
     p.layer:= q.layer+1;
     insert p in Q
   end for
end while
return empty;

Augment_Paths(F): 
  for all $q\in U\cup V$
    q.visited= false;
  end for
  for all q:F
    P:=Get_Augmenting_Path(q);
    // Make sure q ends a non-overlapping augmenting path
    if (P is not empty) 
      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 non-overlapping augmenting path.
  return empty;

Michael Veksler (talk) 01:31, 10 October 2008 (UTC)

Minor fixes to the previous version of the algorithm (also by me) Michael Veksler (talk) 06:39, 10 October 2008 (UTC)

This pseudo-code is huge. Maybe it should be rewritten in python as Tetha (talk) has suggested. Unfortunately, I have never written more than few lines in python at a time.

Log: Using u.matching instead of M throughout the algorithm. This gives the right sense of the O(1) nature of operations on M. Michael Veksler (talk) 08:30, 10 October 2008 (UTC)