New feature: maximum matching of general graph - #2550
Conversation
| /** | ||
| * \function igraph_maximum_matching | ||
| * \brief Calculates a maximum matching in a graph. | ||
| * |
There was a problem hiding this comment.
| * | |
| * | |
| * \experimental | |
| * |
Just so we don't forget.
|
The algorithm itself uses the I'm really fine with either, and will get started implementing it once we decided this. |
|
We didn't forget this PR, just need to find the time to go over it. It's a non-trivial amount of work. The Changing the interface is relatively easy. The first step of the review should be verifying correctness and performance. |
There was a problem hiding this comment.
Pull Request Overview
This pull request introduces a new maximum matching feature for general graphs along with corresponding unit tests, example code, and build system updates.
- Adds new unit tests (trivial, path, bipartite, general, and Petersen graphs) for the maximum matching functionality.
- Implements the new maximum matching algorithm in src/misc/matching.c, including blossom contraction, with proper memory management using IGRAPH_FINALLY macros.
- Updates CMakeLists.txt, header declarations, and example files to support the new functionality.
Reviewed Changes
Copilot reviewed 5 out of 5 changed files in this pull request and generated 2 comments.
Show a summary per file
| File | Description |
|---|---|
| tests/unit/igraph_maximum_matching.c | Adds comprehensive tests for maximum matching on various graph types. |
| tests/CMakeLists.txt | Updates test targets to include igraph_maximum_matching. |
| src/misc/matching.c | Implements the new maximum matching algorithm with blossom contraction. |
| include/igraph_matching.h | Updates header to export the igraph_maximum_matching function. |
| examples/simple/igraph_maximum_matching.c | Provides an example usage of the maximum matching function. |
| while (igraph_vector_int_size(&path) != 0) { | ||
| //augment | ||
| for (igraph_integer_t i = 0; i + 2 < igraph_vector_int_size(&path); i = i + 2) { |
There was a problem hiding this comment.
[nitpick] Cache the result of igraph_vector_int_size(&path) in a local variable within the loop condition to avoid repeated calls, which can improve performance in cases where the vector size is invariant during the loop.
| while (igraph_vector_int_size(&path) != 0) { | |
| //augment | |
| for (igraph_integer_t i = 0; i + 2 < igraph_vector_int_size(&path); i = i + 2) { | |
| igraph_integer_t path_size = igraph_vector_int_size(&path); | |
| while (path_size != 0) { | |
| //augment | |
| for (igraph_integer_t i = 0; i + 2 < path_size; i = i + 2) { |
There was a problem hiding this comment.
Well, this is almost correct. It is indeed good to save the vector length and avoid repeated igraph_vector_int_size() calls in the for loop. But of course the same shouldn't be done for the while loop, as the vector size keep changing there.
Co-authored-by: Copilot <175728472+Copilot@users.noreply.github.com>
| return IGRAPH_SUCCESS; | ||
| } | ||
|
|
||
| void igraph_i_maximum_matching_get_tree_path(igraph_integer_t *current, igraph_vector_bool_t *f_is_root, igraph_vector_int_t *contraction, |
There was a problem hiding this comment.
This function is void instead of returning igraph_error_t and the push_back() calls within are not checked for errors. Are we certain that these push_back() calls cannot fail, i.e. are they acting on a vector with guaranteed sufficient reserved storage? If yes, this should be explained in a comment. If not, error checks are necessary.
| current = VECTOR(f_parent)[current]; | ||
| } | ||
| current = w; | ||
| igraph_vector_int_resize(&temp_list, 0); |
There was a problem hiding this comment.
Generally, all functions that return an error code must be protected using IGRAPH_CHECK.
| IGRAPH_CHECK(igraph_vector_bool_init(&b_mark, n)); | ||
| IGRAPH_FINALLY(igraph_vector_bool_destroy, &b_mark); |
There was a problem hiding this comment.
Such pairs can be replaced with the more concise:
| IGRAPH_CHECK(igraph_vector_bool_init(&b_mark, n)); | |
| IGRAPH_FINALLY(igraph_vector_bool_destroy, &b_mark); | |
| IGRAPH_VECTOR_BOOL_INIT_FINALLY(&b_mark, n); |
Boolean vector that are not resized can be replaced with a more space-efficient igraph_bitset_t. This is a minor nitpick that is better fixed only when everything else is addressed.
|
I had a quick look while testing Copilot, but unfortunately I still don't have the capacity to review this PR in full at this moment. I hope that you are interested in coming back to it eventually, but there is no need to address the comments just yet. |
|
This is not API-breaking so we do not need to merge this before the release of 1.0. Unscheduling from the milestone to keep things tidy. |
The new pull request after the issues with #2530
Fixes #2403