Implementation of the Hopcroft-Karp algorithm.

This is a dedicated algorithm for finding a maximal matching in a
bipartite graph.

Previously I've been solving that problem in this code base using
maxflow.c, modelling the graph matching problem as a restricted case
of the optimal network flow problem and then using a full-strength
algorithm for the latter. That's overkill, and also algorithmically
wasteful - the H-K algorithm is asymptotically better, because it can
find multiple augmenting paths in each pass (hence getting the maximum
benefit out of each expensive breadth-first search), as a consequence
of not having to worry about lower- or higher-value augmenting paths
in this restricted problem.

So I expect this algorithm to be faster, at least in principle or in
large cases, when it takes over the jobs currently being done by
maxflow. But that's not the only benefit. Another is that the data
representation is better suited to the problems actually being solved,
which should simplify all the call sites; a third is that I've
incorporated randomisation of the generated matching into the H-K
module itself, which will further save effort at each call site
because they will no longer have to worry about permuting the
algorithm's input - they just have to pass it a random_state and it
will take care of that internally.

This commit only introduces the new matching.c and builds a test
utility for it. I haven't yet migrated any clients of maxflow.

0 files changed, 0 insertions, 0 deletions