OR-Tools  8.2
assignment.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Simple interface to solve the linear sum assignment problem. It
15// uses about twice as much memory as directly using the
16// LinearSumAssignment class template, but it is as fast and presents
17// a simpler interface. This is the class you should use in most
18// situations.
19//
20// The assignment problem: Given N "left" nodes and N "right" nodes,
21// and a set of left->right arcs with integer costs, find a perfect
22// matching (i.e., each "left" node is assigned to one "right" node)
23// that minimizes the overall cost.
24//
25// Example usage:
26//
27// #include "ortools/graph/assignment.h"
28//
29// SimpleLinearSumAssignment assignment;
30// for (int arc = 0; arc < num_arcs; ++arc) {
31// assignment.AddArcWithCost(head(arc), tail(arc), cost(arc));
32// }
33// if (assignment.Solve() == SimpleLinearSumAssignment::OPTIMAL) {
34// printf("A perfect matching exists.\n");
35// printf("The best possible cost is %d.\n", assignment.OptimalCost());
36// printf("An optimal assignment is:\n");
37// for (int node = 0; node < assignment.NumNodes(); ++node) {
38// printf("left node %d assigned to right node %d with cost %d.\n",
39// node,
40// assignment.RightMate(node),
41// assignment.AssignmentCost(node));
42// }
43// printf("Note that it may not be the unique optimal assignment.");
44// } else {
45// printf("There is an issue with the input or no perfect matching exists.");
46// }
47
48#ifndef OR_TOOLS_GRAPH_ASSIGNMENT_H_
49#define OR_TOOLS_GRAPH_ASSIGNMENT_H_
50
51#include <vector>
52
54
55namespace operations_research {
56
58 public:
59 // The constructor takes no size.
60 // New node indices will be created lazily by AddArcWithCost().
62
63 // Adds an arc from a left node to a right node with a given cost.
64 // * Node indices must be non-negative (>= 0). For a perfect
65 // matching to exist on n nodes, the values taken by "left_node"
66 // must cover [0, n), same for "right_node".
67 // * The arc cost can be any integer, negative, positive or zero.
68 // * After the method finishes, NumArcs() == the returned ArcIndex + 1.
69 ArcIndex AddArcWithCost(NodeIndex left_node, NodeIndex right_node,
71
72 // Returns the current number of left nodes which is the same as the
73 // number of right nodes. This is one greater than the largest node
74 // index seen so far in AddArcWithCost().
75 NodeIndex NumNodes() const;
76
77 // Returns the current number of arcs in the graph.
78 ArcIndex NumArcs() const;
79
80 // Returns user-provided data.
81 // The implementation will crash if "arc" is not in [0, NumArcs()).
82 NodeIndex LeftNode(ArcIndex arc) const;
83 NodeIndex RightNode(ArcIndex arc) const;
84 CostValue Cost(ArcIndex arc) const;
85
86 // Solves the problem (finds the perfect matching that minimizes the
87 // cost) and returns the solver status.
88 enum Status {
89 OPTIMAL, // The algorithm found a minimum-cost perfect matching.
90 INFEASIBLE, // The given problem admits no perfect matching.
91 POSSIBLE_OVERFLOW, // Some cost magnitude is too large.
92 };
93 Status Solve();
94
95 // Returns the cost of an assignment with minimal cost.
96 // This is 0 if the last Solve() didn't return OPTIMAL.
97 CostValue OptimalCost() const { return optimal_cost_; }
98
99 // Returns the right node assigned to the given left node in the
100 // last solution computed by Solve(). This works only if Solve()
101 // returned OPTIMAL.
102 //
103 // Note: It is possible that there is more than one optimal
104 // solution. The algorithm is deterministic so it will always return
105 // the same solution for a given problem. There is no such guarantee
106 // from one code version to the next, but the code does not change
107 // often.
108 NodeIndex RightMate(NodeIndex left_node) const {
109 return arc_head_[assignment_arcs_[left_node]];
110 }
111
112 // Returns the cost of the arc used for "left_node"'s assignment.
113 // This works only if Solve() returned OPTIMAL.
115 return arc_cost_[assignment_arcs_[left_node]];
116 }
117
118 private:
119 NodeIndex num_nodes_;
120 std::vector<NodeIndex> arc_tail_;
121 std::vector<NodeIndex> arc_head_;
122 std::vector<CostValue> arc_cost_;
123 std::vector<ArcIndex> assignment_arcs_;
124 CostValue optimal_cost_;
125 DISALLOW_COPY_AND_ASSIGN(SimpleLinearSumAssignment);
126};
127
128} // namespace operations_research
129
130#endif // OR_TOOLS_GRAPH_ASSIGNMENT_H_
NodeIndex RightMate(NodeIndex left_node) const
Definition: assignment.h:108
ArcIndex AddArcWithCost(NodeIndex left_node, NodeIndex right_node, CostValue cost)
CostValue AssignmentCost(NodeIndex left_node) const
Definition: assignment.h:114
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 cost