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 
20 namespace operations_research {
21 
23 
25  NodeIndex right_node,
26  CostValue cost) {
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 
36 NodeIndex SimpleLinearSumAssignment::NumNodes() const { return num_nodes_; }
37 
38 ArcIndex 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