Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class MinCostPerfectMatching
Note: This documentation is automatically generated.
Given an undirected graph with costs on each edges, this class allows to
compute a perfect matching with minimum cost. A matching is a set of disjoint
pairs of nodes connected by an edge. The matching is perfect if all nodes are
matched to each others.
Adds an undirected edges between the two given nodes.
For now we only accept non-negative cost.
TODO(user): We can easily shift all costs if negative costs are needed.
Important: The algorithm supports multi-edges, but it will be slower. So it
is better to only add one edge with a minimum cost between two nodes. In
particular, do not add both AddEdge(a, b, cost) and AddEdge(b, a, cost).
TODO(user): We could just presolve them away.
Resets the class for a new graph.
TODO(user): Eventually, we may support incremental Solves(). Or at least
memory reuse if one wants to solve many problems in a row.
[[["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\u003eThe \u003ccode\u003eMinCostPerfectMatching\u003c/code\u003e class in C++ helps find the lowest-cost perfect matching in an undirected graph, where a perfect matching pairs all nodes with disjoint edges.\u003c/p\u003e\n"],["\u003cp\u003eIt utilizes the \u003ccode\u003eAddEdgeWithCost\u003c/code\u003e method to define the graph's edges and their associated costs, preferably avoiding redundant or multi-edges for optimal performance.\u003c/p\u003e\n"],["\u003cp\u003eAfter using \u003ccode\u003eSolve\u003c/code\u003e, you can obtain the optimal cost with \u003ccode\u003eOptimalCost\u003c/code\u003e and the node pairings via \u003ccode\u003eMatch\u003c/code\u003e or \u003ccode\u003eMatches\u003c/code\u003e, given the solution is optimal.\u003c/p\u003e\n"],["\u003cp\u003eThe class requires specifying the number of nodes initially and allows resetting for new graph computations using \u003ccode\u003eReset\u003c/code\u003e.\u003c/p\u003e\n"]]],["The `MinCostPerfectMatching` class computes a minimum-cost perfect matching in an undirected graph. Key actions include adding edges with `AddEdgeWithCost`, specifying a tail, head, and cost. The `Solve` method calculates the matching. After solving, `OptimalCost` retrieves the matching's cost, and `Match` returns the node paired with a given node. `Matches` provides the list of paired nodes. `Reset` prepares the class for a new graph, while the constructor creates an instance given a number of nodes.\n"],null,["# MinCostPerfectMatching\n\nC++ Reference: class MinCostPerfectMatching\n===========================================\n\n\nNote: This documentation is automatically generated.\nGiven an undirected graph with costs on each edges, this class allows to compute a perfect matching with minimum cost. A matching is a set of disjoint pairs of nodes connected by an edge. The matching is perfect if all nodes are matched to each others.\n\n| Method ||\n|---------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddEdgeWithCost`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L77) | Return type: `void ` Arguments: `int tail, int head, int64_t cost` Adds an undirected edges between the two given nodes. For now we only accept non-negative cost. TODO(user): We can easily shift all costs if negative costs are needed. Important: The algorithm supports multi-edges, but it will be slower. So it is better to only add one edge with a minimum cost between two nodes. In particular, do not add both AddEdge(a, b, cost) and AddEdge(b, a, cost). TODO(user): We could just presolve them away. |\n| [`Match`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L114) | Return type: `int ` Arguments: `int node` Returns the node matched to the given node. In a perfect matching all nodes have a match. Only valid when the last solve status was OPTIMAL. |\n| [`Matches`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L118) | Return type: `const std::vector\u003cint\u003e& ` \u003cbr /\u003e |\n| [`MinCostPerfectMatching`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L59) | TODO(user): For now we ask the number of nodes at construction, but we could automatically infer it from the added edges if needed. |\n| [`MinCostPerfectMatching`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L60) | Return type: `explicit ` Arguments: `int num_nodes` \u003cbr /\u003e |\n| [`OptimalCost`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L107) | Return type: `int64_t ` Returns the cost of the perfect matching. Only valid when the last solve status was OPTIMAL. |\n| [`Reset`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L66) | Return type: `void ` Arguments: `int num_nodes` Resets the class for a new graph. TODO(user): Eventually, we may support incremental Solves(). Or at least memory reuse if one wants to solve many problems in a row. |\n| [`Solve`](https://github.com/google/or-tools/blob/v9.4/ortools/graph/perfect_matching.h#L103) | Return type: `ABSL_MUST_USE_RESULT Status ` \u003cbr /\u003e |"]]
