OR-Tools  8.2
graph/assignment.cc
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
15
19
20namespace operations_research {
21
23
25 NodeIndex right_node,
27 const ArcIndex num_arcs = arc_cost_.size();
28 num_nodes_ = std::max(num_nodes_, left_node + 1);
29 num_nodes_ = std::max(num_nodes_, right_node + 1);
30 arc_tail_.push_back(left_node);
31 arc_head_.push_back(right_node);
32 arc_cost_.push_back(cost);
33 return num_arcs;
34}
35
36NodeIndex SimpleLinearSumAssignment::NumNodes() const { return num_nodes_; }
37
38ArcIndex SimpleLinearSumAssignment::NumArcs() const { return arc_cost_.size(); }
39
41 return arc_tail_[arc];
42}
43
45 return arc_head_[arc];
46}
47
49 return arc_cost_[arc];
50}
51
53 optimal_cost_ = 0;
54 assignment_arcs_.clear();
55 if (NumNodes() == 0) return OPTIMAL;
56 // HACK(user): Detect overflows early. In ./linear_assignment.h, the cost of
57 // each arc is internally multiplied by cost_scaling_factor_ (which is equal
58 // to (num_nodes + 1)) without overflow checking.
59 const CostValue max_supported_arc_cost =
61 for (const CostValue unscaled_arc_cost : arc_cost_) {
62 if (unscaled_arc_cost > max_supported_arc_cost) return POSSIBLE_OVERFLOW;
63 }
64
65 const ArcIndex num_arcs = arc_cost_.size();
66 ForwardStarGraph graph(2 * num_nodes_, num_arcs);
67 LinearSumAssignment<ForwardStarGraph> assignment(graph, num_nodes_);
68 for (ArcIndex arc = 0; arc < num_arcs; ++arc) {
69 graph.AddArc(arc_tail_[arc], num_nodes_ + arc_head_[arc]);
70 assignment.SetArcCost(arc, arc_cost_[arc]);
71 }
72 // TODO(user): Improve the LinearSumAssignment api to clearly define
73 // the error cases.
74 if (!assignment.FinalizeSetup()) return POSSIBLE_OVERFLOW;
75 if (!assignment.ComputeAssignment()) return INFEASIBLE;
76 optimal_cost_ = assignment.GetCost();
77 for (NodeIndex node = 0; node < num_nodes_; ++node) {
78 assignment_arcs_.push_back(assignment.GetAssignmentArc(node));
79 }
80 return OPTIMAL;
81}
82
83} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: ebert_graph.h:1001
ArcIndex GetAssignmentArc(NodeIndex left_node) const
void SetArcCost(ArcIndex arc, CostValue cost)
ArcIndex AddArcWithCost(NodeIndex left_node, NodeIndex right_node, CostValue cost)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 cost