Maximum matching algorithms in igraph

Maximum unweighted matching in bipartite graphs: Hopcroft-Karp algorithm (O(|E| * sqrt(|V|) worst case), or push-relabel. Python implementation of the Hopcroft-Karp algorithm: [3]. Some papers suggest that push-relabel is better [4,5]

Maximum unweighted/weighted matching in general graphs: Edmonds' matching algorithm (O(|V|^4)) or the Micali-Vazirani algorithm (O(|E| * sqrt(|V|)) [1]. Kolmogorov's implementation [2].

[1] Micali, Silvio; Vazirani, Vijay (1980), "An O(V1/2E) algorithm for finding maximum matching in general graphs", 21st Annual Symposium on Foundations of Computer Science, (IEEE Computer Society Press, New York): 17–27

[2] Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Mathematical Programming Computation 1 (1): 43–67

[3] http://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/

[4] http://www.cerfacs.fr/algor/reports/2011/TR_PA_11_33.pdf

[5] http://www.avglab.com/andrew/pub/neci-tr-97-127.ps

Proposed interface in the C layer:

    int igraph_maximum_bipartite_matching(const igraph_t* graph, const igraph_vector_bool_t* types, igraph_integer_t* matching_size, igraph_vector_t* matching, const igraph_vector_t* weights);
    int igraph_maximum_matching(const igraph_t* graph, igraph_integer_t* matching_size, igraph_vector_t* matching, const igraph_vector_t* weights);