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.

Method
AddEdgeWithCost	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.
Match	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.
Matches	Return type: const std::vector<int>&
MinCostPerfectMatching	TODO(user): For now we ask the number of nodes at construction, but we could automatically infer it from the added edges if needed.
MinCostPerfectMatching	Return type: explicit Arguments: int num_nodes
OptimalCost	Return type: int64_t Returns the cost of the perfect matching. Only valid when the last solve status was OPTIMAL.
Reset	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.
Solve	Return type: ABSL_MUST_USE_RESULT Status