C++ Reference: class MinCostPerfectMatching

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 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

Returns the cost of the perfect macthing. 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