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."],[[["\u003cp\u003eThis documentation details the implementation of the Blossom V algorithm for finding minimum cost perfect matching in graphs.\u003c/p\u003e\n"],["\u003cp\u003eThe 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.\u003c/p\u003e\n"],["\u003cp\u003eThe current implementation is a work in progress and resembles Blossom IV in its approach to updating dual values.\u003c/p\u003e\n"],["\u003cp\u003eKey classes provided include \u003ccode\u003eBlossomGraph\u003c/code\u003e for representing the graph and \u003ccode\u003eMinCostPerfectMatching\u003c/code\u003e for executing the algorithm.\u003c/p\u003e\n"]]],["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"],null,[]]
