OR-Tools  8.1
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
operations_research::SimpleLinearSumAssignment::Solve
Status Solve()
Definition: graph/assignment.cc:52
operations_research::LinearSumAssignment::GetAssignmentArc
ArcIndex GetAssignmentArc(NodeIndex left_node) const
Definition: linear_assignment.h:338
operations_research::ForwardEbertGraph
Definition: ebert_graph.h:1564
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::LinearSumAssignment::SetArcCost
void SetArcCost(ArcIndex arc, CostValue cost)
Definition: linear_assignment.h:1009
operations_research::SimpleLinearSumAssignment::LeftNode
NodeIndex LeftNode(ArcIndex arc) const
Definition: graph/assignment.cc:40
operations_research::LinearSumAssignment
Definition: linear_assignment.h:226
operations_research::NodeIndex
int32 NodeIndex
Definition: ebert_graph.h:192
operations_research::SimpleLinearSumAssignment::RightNode
NodeIndex RightNode(ArcIndex arc) const
Definition: graph/assignment.cc:44
operations_research::LinearSumAssignment::FinalizeSetup
bool FinalizeSetup()
Definition: linear_assignment.h:1388
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::SimpleLinearSumAssignment::NumArcs
ArcIndex NumArcs() const
Definition: graph/assignment.cc:38
cost
int64 cost
Definition: routing_flow.cc:130
assignment.h
operations_research::SimpleLinearSumAssignment::AddArcWithCost
ArcIndex AddArcWithCost(NodeIndex left_node, NodeIndex right_node, CostValue cost)
Definition: graph/assignment.cc:24
operations_research::CostValue
int64 CostValue
Definition: ebert_graph.h:203
operations_research::LinearSumAssignment::GetCost
CostValue GetCost() const
Definition: linear_assignment.h:1473
operations_research::SimpleLinearSumAssignment::OPTIMAL
@ OPTIMAL
Definition: assignment.h:89
operations_research::SimpleLinearSumAssignment::INFEASIBLE
@ INFEASIBLE
Definition: assignment.h:90
operations_research::ArcIndex
int32 ArcIndex
Definition: ebert_graph.h:201
operations_research::SimpleLinearSumAssignment::SimpleLinearSumAssignment
SimpleLinearSumAssignment()
Definition: graph/assignment.cc:22
operations_research::SimpleLinearSumAssignment::Status
Status
Definition: assignment.h:88
operations_research::SimpleLinearSumAssignment::NumNodes
NodeIndex NumNodes() const
Definition: graph/assignment.cc:36
ebert_graph.h
operations_research::SimpleLinearSumAssignment::Cost
CostValue Cost(ArcIndex arc) const
Definition: graph/assignment.cc:48
operations_research::SimpleLinearSumAssignment::POSSIBLE_OVERFLOW
@ POSSIBLE_OVERFLOW
Definition: assignment.h:91
linear_assignment.h
commandlineflags.h
operations_research::LinearSumAssignment::ComputeAssignment
bool ComputeAssignment()
Definition: linear_assignment.h:1448