26#ifndef OR_TOOLS_GRAPH_PERFECT_MATCHING_H_
27#define OR_TOOLS_GRAPH_PERFECT_MATCHING_H_
32#include "absl/strings/str_cat.h"
33#include "absl/strings/str_join.h"
61 void Reset(
int num_nodes);
103 DCHECK(optimal_solution_found_);
104 return optimal_cost_;
110 DCHECK(optimal_solution_found_);
111 return matches_[node];
114 DCHECK(optimal_solution_found_);
119 std::unique_ptr<BlossomGraph> graph_;
125 bool optimal_solution_found_ =
false;
126 int64 optimal_cost_ = 0;
127 int64 maximum_edge_cost_ = 0;
128 std::vector<int> matches_;
352 int NumMatched()
const {
return nodes_.size() - unmatched_nodes_.size(); }
408 void AppendNodePathToRoot(
NodeIndex n, std::vector<NodeIndex>* path)
const;
421 return root_blossom_node_[edge.tail];
424 return root_blossom_node_[edge.head];
431 return root_blossom_node_[edge.OtherEnd(node)];
448 const std::vector<NodeIndex>& SubNodes(
NodeIndex n);
451 bool is_initialized_ =
false;
466 std::vector<NodeIndex> subnodes_;
472 std::vector<NodeIndex> unmatched_nodes_;
475 std::vector<EdgeIndex> primal_update_edge_queue_;
476 std::vector<EdgeIndex> possible_shrink_;
481 std::vector<Edge*> tmp_all_tops_;
488 int64 num_grows_ = 0;
489 int64 num_augments_ = 0;
490 int64 num_shrinks_ = 0;
491 int64 num_expands_ = 0;
492 int64 num_dual_updates_ = 0;
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
bool DebugDualsAreFeasible() const
ABSL_MUST_USE_RESULT bool Initialize()
const Node & GetNode(int n) const
DEFINE_INT_TYPE(CostValue, int64)
CostValue DualObjective() const
void Grow(EdgeIndex e, NodeIndex tail, NodeIndex head)
CostValue ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()
bool DebugEdgeIsTightAndExternal(const Edge &edge) const
static const CostValue kMaxCostValue
NodeIndex Match(NodeIndex n) const
void AddEdge(NodeIndex tail, NodeIndex head, CostValue cost)
const Edge & GetEdge(int e) const
bool NodeIsMatched(NodeIndex n) const
CostValue Slack(const Edge &edge) const
std::string NodeDebugString(NodeIndex n) const
std::string EdgeDebugString(EdgeIndex e) const
void DebugCheckNoPossiblePrimalUpdates()
std::string DebugString() const
void Augment(EdgeIndex e)
CostValue Dual(const Node &node) const
static const EdgeIndex kNoEdgeIndex
DEFINE_INT_TYPE(NodeIndex, int)
static const NodeIndex kNoNodeIndex
DEFINE_INT_TYPE(EdgeIndex, int)
void Expand(NodeIndex to_expand)
void UpdateAllTrees(CostValue delta)
void DisplayStats() const
void DebugUpdateNodeDual(NodeIndex n, CostValue delta)
BlossomGraph(int num_nodes)
ABSL_MUST_USE_RESULT Status Solve()
int Match(int node) const
void Reset(int num_nodes)
int64 OptimalCost() const
const std::vector< int > & Matches() const
void AddEdgeWithCost(int tail, int head, int64 cost)
MinCostPerfectMatching(int num_nodes)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Edge(NodeIndex t, NodeIndex h, CostValue c)
bool operator>(const Edge &other) const
void SetHeapIndex(int index)
NodeIndex OtherEnd(NodeIndex n) const
CostValue tree_dual_delta
std::vector< NodeIndex > blossom
CostValue saved_pseudo_dual
std::vector< NodeIndex > saved_blossom