Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: perfect_matching
Note: This documentation is automatically generated.
Implementation of the Blossom V min-cost perfect matching algorithm. The main source for the algo is the paper: "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Vladimir Kolmogorov.
The Algorithm is a primal-dual algorithm. It always maintains a dual-feasible solution. We recall some notations here, but see the paper for more details as it is well written.
TODO(user): This is a work in progress. The algo is not fully implemented yet. The initial version is closer to Blossom IV since we update the dual values for all trees at once with the same delta.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["This documentation details the implementation of the Blossom V algorithm for finding minimum cost perfect matching in graphs."],["The implementation is based on Kolmogorov's paper \"Blossom V: A new implementation of a minimum cost perfect matching algorithm\" and utilizes a primal-dual approach."],["The current implementation is a work in progress and resembles Blossom IV in its approach to updating dual values."],["Key classes provided include `BlossomGraph` for representing the graph and `MinCostPerfectMatching` for executing the algorithm."]]],["The core content details the implementation of the Blossom V min-cost perfect matching algorithm, based on Vladimir Kolmogorov's paper. It's a primal-dual algorithm maintaining a dual-feasible solution. The current implementation, however, is still a work in progress and resembles Blossom IV more closely, updating dual values for all trees simultaneously. Key elements are represented by the `BlossomGraph` and `MinCostPerfectMatching` classes.\n"]]
