1 // Copyright 2010-2021 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 #include <algorithm>
15 #include <cmath>
16 #include <cstdlib>
17 #include <string>
18 #include <vector>
19
20 #include "absl/container/flat_hash_map.h"
21 #include "absl/flags/parse.h"
22 #include "absl/flags/usage.h"
23 #include "absl/strings/str_format.h"
24 #include "examples/cpp/parse_dimacs_assignment.h"
25 #include "examples/cpp/print_dimacs_assignment.h"
26 #include "ortools/algorithms/hungarian.h"
27 #include "ortools/base/commandlineflags.h"
28 #include "ortools/base/logging.h"
29 #include "ortools/base/timer.h"
30 #include "ortools/graph/ebert_graph.h"
31 #include "ortools/graph/linear_assignment.h"
32
33 ABSL_FLAG(bool, assignment_compare_hungarian, false,
34 "Compare result and speed against Hungarian method.");
35 ABSL_FLAG(std::string, assignment_problem_output_file, "",
36 "Print the problem to this file in DIMACS format (after layout "
37 "is optimized, if applicable).");
38 ABSL_FLAG(bool, assignment_reverse_arcs, false,
39 "Ignored if --assignment_static_graph=true. Use StarGraph "
40 "if true, ForwardStarGraph if false.");
41 ABSL_FLAG(bool, assignment_static_graph, true,
42 "Use the ForwardStarStaticGraph representation, "
43 "otherwise ForwardStarGraph or StarGraph according "
44 "to --assignment_reverse_arcs.");
45
46 namespace operations_research {
47
48 typedef ForwardStarStaticGraph GraphType;
49
50 template <typename GraphType>
BuildAndSolveHungarianInstance(const LinearSumAssignment<GraphType> & assignment)51 CostValue BuildAndSolveHungarianInstance(
52 const LinearSumAssignment<GraphType>& assignment) {
53 const GraphType& graph = assignment.Graph();
54 typedef std::vector<double> HungarianRow;
55 typedef std::vector<HungarianRow> HungarianProblem;
56 HungarianProblem hungarian_cost;
57 hungarian_cost.resize(assignment.NumLeftNodes());
58 // First we have to find the biggest cost magnitude so we can
59 // initialize the arc costs that aren't really there.
60 CostValue largest_cost_magnitude = 0;
61 for (typename GraphType::ArcIterator arc_it(graph); arc_it.Ok();
62 arc_it.Next()) {
63 ArcIndex arc = arc_it.Index();
64 CostValue cost_magnitude = std::abs(assignment.ArcCost(arc));
65 largest_cost_magnitude = std::max(largest_cost_magnitude, cost_magnitude);
66 }
67 double missing_arc_cost = static_cast<double>(
68 (assignment.NumLeftNodes() * largest_cost_magnitude) + 1);
69 for (HungarianProblem::iterator row = hungarian_cost.begin();
70 row != hungarian_cost.end(); ++row) {
71 row->resize(assignment.NumNodes() - assignment.NumLeftNodes(),
72 missing_arc_cost);
73 }
74 // We're using a graph representation without forward arcs, so in
75 // order to use the generic GraphType::ArcIterator we would
76 // need to increase our memory footprint by building the array of
77 // arc tails (since we need tails to build the input to the
78 // hungarian algorithm). We opt for the alternative of iterating
79 // over hte arcs via adjacency lists, which gives us the arc tails
80 // implicitly.
81 for (typename GraphType::NodeIterator node_it(graph); node_it.Ok();
82 node_it.Next()) {
83 NodeIndex node = node_it.Index();
84 NodeIndex tail = (node - GraphType::kFirstNode);
85 for (typename GraphType::OutgoingArcIterator arc_it(graph, node);
86 arc_it.Ok(); arc_it.Next()) {
87 ArcIndex arc = arc_it.Index();
88 NodeIndex head =
89 (graph.Head(arc) - assignment.NumLeftNodes() - GraphType::kFirstNode);
90 double cost = static_cast<double>(assignment.ArcCost(arc));
91 hungarian_cost[tail][head] = cost;
92 }
93 }
94 absl::flat_hash_map<int, int> result;
95 absl::flat_hash_map<int, int> wish_this_could_be_null;
96 WallTimer timer;
97 VLOG(1) << "Beginning Hungarian method.";
98 timer.Start();
99 MinimizeLinearAssignment(hungarian_cost, &result, &wish_this_could_be_null);
100 double elapsed = timer.GetInMs() / 1000.0;
101 LOG(INFO) << "Hungarian result computed in " << elapsed << " seconds.";
102 double result_cost = 0.0;
103 for (int i = 0; i < assignment.NumLeftNodes(); ++i) {
104 int mate = result[i];
105 result_cost += hungarian_cost[i][mate];
106 }
107 return static_cast<CostValue>(result_cost);
108 }
109
110 template <typename GraphType>
DisplayAssignment(const LinearSumAssignment<GraphType> & assignment)111 void DisplayAssignment(const LinearSumAssignment<GraphType>& assignment) {
112 for (typename LinearSumAssignment<GraphType>::BipartiteLeftNodeIterator
113 node_it(assignment);
114 node_it.Ok(); node_it.Next()) {
115 const NodeIndex left_node = node_it.Index();
116 const ArcIndex matching_arc = assignment.GetAssignmentArc(left_node);
117 const NodeIndex right_node = assignment.Head(matching_arc);
118 VLOG(5) << "assigned (" << left_node << ", " << right_node
119 << "): " << assignment.ArcCost(matching_arc);
120 }
121 }
122
123 template <typename GraphType>
SolveDimacsAssignment(int argc,char * argv[])124 int SolveDimacsAssignment(int argc, char* argv[]) {
125 std::string error_message;
126 // Handle on the graph we will need to delete because the
127 // LinearSumAssignment object does not take ownership of it.
128 GraphType* graph = nullptr;
129 DimacsAssignmentParser<GraphType> parser(argv[1]);
130 LinearSumAssignment<GraphType>* assignment =
131 parser.Parse(&error_message, &graph);
132 if (assignment == nullptr) {
133 LOG(FATAL) << error_message;
134 }
135 if (!absl::GetFlag(FLAGS_assignment_problem_output_file).empty()) {
136 // The following tail array management stuff is done in a generic
137 // way so we can plug in different types of graphs for which the
138 // TailArrayManager template can be instantiated, even though we
139 // know the type of the graph explicitly. In this way, the type of
140 // the graph can be switched just by changing the graph type in
141 // this file and making no other changes to the code.
142 TailArrayManager<GraphType> tail_array_manager(graph);
143 PrintDimacsAssignmentProblem<GraphType>(
144 *assignment, tail_array_manager,
145 absl::GetFlag(FLAGS_assignment_problem_output_file));
146 tail_array_manager.ReleaseTailArrayIfForwardGraph();
147 }
148 CostValue hungarian_cost = 0.0;
149 bool hungarian_solved = false;
150 if (absl::GetFlag(FLAGS_assignment_compare_hungarian)) {
151 hungarian_cost = BuildAndSolveHungarianInstance(*assignment);
152 hungarian_solved = true;
153 }
154 WallTimer timer;
155 timer.Start();
156 bool success = assignment->ComputeAssignment();
157 double elapsed = timer.GetInMs() / 1000.0;
158 if (success) {
159 CostValue cost = assignment->GetCost();
160 DisplayAssignment(*assignment);
161 LOG(INFO) << "Cost of optimum assignment: " << cost;
162 LOG(INFO) << "Computed in " << elapsed << " seconds.";
163 LOG(INFO) << assignment->StatsString();
164 if (hungarian_solved && (cost != hungarian_cost)) {
165 LOG(ERROR) << "Optimum cost mismatch: " << cost << " vs. "
166 << hungarian_cost << ".";
167 }
168 } else {
169 LOG(WARNING) << "Given problem is infeasible.";
170 }
171 delete assignment;
172 delete graph;
173 return EXIT_SUCCESS;
174 }
175 } // namespace operations_research
176
177 static const char* const kUsageTemplate = "usage: %s <filename>";
178
179 using ::operations_research::ForwardStarGraph;
180 using ::operations_research::ForwardStarStaticGraph;
181 using ::operations_research::SolveDimacsAssignment;
182 using ::operations_research::StarGraph;
183
main(int argc,char * argv[])184 int main(int argc, char* argv[]) {
185 std::string usage;
186 if (argc < 1) {
187 usage = absl::StrFormat(kUsageTemplate, "solve_dimacs_assignment");
188 } else {
189 usage = absl::StrFormat(kUsageTemplate, argv[0]);
190 }
191 google::InitGoogleLogging(usage.c_str());
192 absl::ParseCommandLine(argc, argv);
193
194 if (argc < 2) {
195 LOG(FATAL) << usage;
196 }
197
198 if (absl::GetFlag(FLAGS_assignment_static_graph)) {
199 return SolveDimacsAssignment<ForwardStarStaticGraph>(argc, argv);
200 } else if (absl::GetFlag(FLAGS_assignment_reverse_arcs)) {
201 return SolveDimacsAssignment<StarGraph>(argc, argv);
202 } else {
203 return SolveDimacsAssignment<ForwardStarGraph>(argc, argv);
204 }
205 }
206