Google OR-Tools: ortools/graph/linear_assignment.h Source File

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193#ifndef ORTOOLS_GRAPH_LINEAR_ASSIGNMENT_H_

194#define ORTOOLS_GRAPH_LINEAR_ASSIGNMENT_H_

195

196#include <algorithm>

197#include <cstdint>

198#include <cstdlib>

199#include <deque>

200#include <limits>

201#include <memory>

202#include <string>

203#include <utility>

204#include <vector>

205

206#include "absl/flags/declare.h"

207#include "absl/flags/flag.h"

208#include "absl/strings/str_format.h"

214

215#ifndef SWIG

219#endif

220

222

223

224template <typename GraphType, typename CostValue = int64_t>

226 public:

227 typedef typename GraphType::NodeIndex NodeIndex;

228 typedef typename GraphType::ArcIndex ArcIndex;

230

231

232

233

235

236

237

238

239

241

242

245

247

248

249

250

252 DCHECK(graph_ == nullptr);

253 graph_ = graph;

254 }

255

256

257

259

260

261

262

263

264

265

268

269

270 inline const GraphType& Graph() const { return *graph_; }

271

272

273

274

275

277

278

279

281 DCHECK_EQ(0, scaled_arc_cost_[arc] % cost_scaling_factor_);

282 return scaled_arc_cost_[arc] / cost_scaling_factor_;

283 }

284

285

287

288

289

290

291

292

293

294

295

296

297

298

299

301

302

303

305

306

307

308

310

311

313 if (graph_ == nullptr) {

314

315

317 } else {

318 return graph_->num_nodes();

319 }

320 }

321

322

323

325

326

328 DCHECK_LT(left_node, num_left_nodes_);

329 return matched_arc_[left_node];

330 }

331

332

333

337

338

340 DCHECK_LT(left_node, num_left_nodes_);

342 DCHECK_NE(GraphType::kNilArc, matching_arc);

343 return Head(matching_arc);

344 }

345

346 std::string StatsString() const { return total_stats_.StatsString(); }

347

348

350 return ::util::IntegerRange<NodeIndex>(0, num_left_nodes_);

351 }

352

353

354

355

356

358

359 private:

360 struct Stats {

361 Stats() : pushes(0), double_pushes(0), relabelings(0), refinements(0) {}

362 void Clear() {

363 pushes = 0;

364 double_pushes = 0;

365 relabelings = 0;

366 refinements = 0;

367 }

368 void Add(const Stats& that) {

369 pushes += that.pushes;

370 double_pushes += that.double_pushes;

371 relabelings += that.relabelings;

372 refinements += that.refinements;

373 }

375 return absl::StrFormat(

376 "%d refinements; %d relabelings; "

377 "%d double pushes; %d pushes",

378 refinements, relabelings, double_pushes, pushes);

379 }

380 int64_t pushes;

381 int64_t double_pushes;

382 int64_t relabelings;

383 int64_t refinements;

384 };

385

386#ifndef SWIG

387 class ActiveNodeContainerInterface {

388 public:

389 virtual ~ActiveNodeContainerInterface() {}

390 virtual bool Empty() const = 0;

391 virtual void Add(NodeIndex node) = 0;

393 };

394

395 class ActiveNodeStack : public ActiveNodeContainerInterface {

396 public:

397 ~ActiveNodeStack() override {}

398

399 bool Empty() const override { return v_.empty(); }

400

401 void Add(NodeIndex node) override { v_.push_back(node); }

402

404 DCHECK(!Empty());

406 v_.pop_back();

407 return result;

408 }

409

410 private:

411 std::vector<NodeIndex> v_;

412 };

413

414 class ActiveNodeQueue : public ActiveNodeContainerInterface {

415 public:

416 ~ActiveNodeQueue() override {}

417

418 bool Empty() const override { return q_.empty(); }

419

420 void Add(NodeIndex node) override { q_.push_front(node); }

421

423 DCHECK(!Empty());

425 q_.pop_back();

426 return result;

427 }

428

429 private:

430 std::deque<NodeIndex> q_;

431 };

432#endif

433

434

435

436

437

438

439

440

441 typedef std::pair<ArcIndex, CostValue> ImplicitPriceSummary;

442

443

444

445 bool AllMatched() const;

446

447

448

450

451

452 inline ImplicitPriceSummary BestArcAndGap(NodeIndex left_node) const;

453

454

455

456 void ReportAndAccumulateStats();

457

458

459

460

461

463

464

465

466

467 bool UpdateEpsilon();

468

469

470

471 inline bool IsActive(NodeIndex left_node) const;

472

473

474

475

476

477

478 inline bool IsActiveForDebugging(NodeIndex node) const;

479

480

481 bool Refine();

482

483

484

485 void InitializeActiveNodeContainer();

486

487

488

489

490

491

492

493 void SaturateNegativeArcs();

494

495

496

497

498 bool DoublePush(NodeIndex source);

499

500

502 return scaled_arc_cost_[arc] - price_[Head(arc)];

503 }

504

505

506

507 const GraphType* graph_;

508

509

511

512

513

514

515

516 bool incidence_precondition_satisfied_;

517

518

519 bool success_;

520

521

522

523

524

525

526 const CostValue cost_scaling_factor_;

527

528

530

531

532

533 static constexpr CostValue kMinEpsilon = 1;

534

535

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830 CostValue slack_relabeling_price_;

831

832

833

834

835

836

837

838

839

840

843 bool* in_range) const {

844 const CostValue n = graph_->num_nodes();

845

846

847

848

849

850

851

852

853

854

855

856 const double result =

857 static_cast<double>(std::max<CostValue>(1, n / 2 - 1)) *

858 (static_cast<double>(old_epsilon) + static_cast<double>(new_epsilon));

859 const double limit =

860 static_cast<double>(std::numeric_limits<CostValue>::max());

861 if (result > limit) {

862

863 if (in_range != nullptr) *in_range = false;

864 return std::numeric_limits<CostValue>::max();

865 } else {

866

867

868 return static_cast<CostValue>(result);

869 }

870 }

871

872

873

874

875

876

877

878

879

880

881

882

883

884 CostValue largest_scaled_cost_magnitude_;

885

886

887

888

890

891

892

893

894

895

896

897 ZVector<CostValue> price_;

898

899

900

901

902 std::vector<ArcIndex> matched_arc_;

903

904

905

906

907

908

909

910 ZVector<NodeIndex> matched_node_;

911

912

913

914

915 std::vector<CostValue> scaled_arc_cost_;

916

917

918

919

920 std::unique_ptr<ActiveNodeContainerInterface> active_nodes_;

921

922

923

924 Stats total_stats_;

925

926

927

928 Stats iteration_stats_;

929};

930

931

932

933

934template <typename GraphType, typename CostValue>

936 const GraphType& graph, const NodeIndex num_left_nodes)

937 : graph_(&graph),

938 num_left_nodes_(num_left_nodes),

939 success_(false),

940 cost_scaling_factor_(1 + num_left_nodes),

941 alpha_(absl::GetFlag(FLAGS_assignment_alpha)),

942 epsilon_(0),

943 price_lower_bound_(0),

944 slack_relabeling_price_(0),

945 largest_scaled_cost_magnitude_(0),

946 total_excess_(0),

947 price_(num_left_nodes, 2 * num_left_nodes - 1),

948 matched_arc_(num_left_nodes, 0),

949 matched_node_(num_left_nodes, 2 * num_left_nodes - 1),

950 scaled_arc_cost_(graph.arc_capacity(), 0),

951 active_nodes_(absl::GetFlag(FLAGS_assignment_stack_order)

952 ? static_cast<ActiveNodeContainerInterface*>(

953 new ActiveNodeStack())

954 : static_cast<ActiveNodeContainerInterface*>(

955 new ActiveNodeQueue())) {}

956

957template <typename GraphType, typename CostValue>

960 : graph_(nullptr),

961 num_left_nodes_(num_left_nodes),

962 success_(false),

963 cost_scaling_factor_(1 + num_left_nodes),

964 alpha_(absl::GetFlag(FLAGS_assignment_alpha)),

965 epsilon_(0),

966 price_lower_bound_(0),

967 slack_relabeling_price_(0),

968 largest_scaled_cost_magnitude_(0),

969 total_excess_(0),

970 price_(num_left_nodes, 2 * num_left_nodes - 1),

971 matched_arc_(num_left_nodes, 0),

972 matched_node_(num_left_nodes, 2 * num_left_nodes - 1),

973 scaled_arc_cost_(num_arcs, 0),

974 active_nodes_(absl::GetFlag(FLAGS_assignment_stack_order)

975 ? static_cast<ActiveNodeContainerInterface*>(

976 new ActiveNodeStack())

977 : static_cast<ActiveNodeContainerInterface*>(

978 new ActiveNodeQueue())) {}

979

980template <typename GraphType, typename CostValue>

983 if (graph_ != nullptr) {

984 DCHECK_GE(arc, 0);

985 DCHECK_LT(arc, graph_->num_arcs());

987 DCHECK_LE(num_left_nodes_, head);

988 }

989 cost *= cost_scaling_factor_;

990 const CostValue cost_magnitude = std::abs(cost);

991 largest_scaled_cost_magnitude_ =

992 std::max(largest_scaled_cost_magnitude_, cost_magnitude);

993 scaled_arc_cost_[arc] = cost;

994}

995

996template <typename ArcIndexType, typename CostValue>

998 public:

1000 : temp_(0), cost_(cost) {}

1001

1002

1005

1007 temp_ = (*cost_)[source];

1008 }

1009

1011 ArcIndexType destination) const override {

1012 (*cost_)[destination] = (*cost_)[source];

1013 }

1014

1016 (*cost_)[destination] = temp_;

1017 }

1018

1020

1021 private:

1023 std::vector<CostValue>* const cost_;

1024};

1025

1026

1027

1028

1029

1030

1031template <typename GraphType>

1033 public:

1035

1036

1037

1038

1040 typename GraphType::ArcIndex b) const {

1041 return ((graph_.Tail(a) < graph_.Tail(b)) ||

1042 ((graph_.Tail(a) == graph_.Tail(b)) &&

1043 (graph_.Head(a) < graph_.Head(b))));

1044 }

1045

1046 private:

1047 const GraphType& graph_;

1048

1049

1050

1051

1052};

1053

1054

1055template <typename GraphType, typename CostValue>

1056PermutationCycleHandler<typename GraphType::ArcIndex>*

1059 &scaled_arc_cost_);

1060}

1061

1062template <typename GraphType, typename CostValue>

1063CostValue LinearSumAssignment<GraphType, CostValue>::NewEpsilon(

1064 const CostValue current_epsilon) const {

1065 return std::max(current_epsilon / alpha_, kMinEpsilon);

1066}

1067

1068template <typename GraphType, typename CostValue>

1069bool LinearSumAssignment<GraphType, CostValue>::UpdateEpsilon() {

1070 CostValue new_epsilon = NewEpsilon(epsilon_);

1071 slack_relabeling_price_ = PriceChangeBound(epsilon_, new_epsilon, nullptr);

1072 epsilon_ = new_epsilon;

1073 VLOG(3) << "Updated: epsilon_ == " << epsilon_;

1074 VLOG(4) << "slack_relabeling_price_ == " << slack_relabeling_price_;

1075 DCHECK_GT(slack_relabeling_price_, 0);

1076

1077

1078

1079 return true;

1080}

1081

1082

1083template <typename GraphType, typename CostValue>

1084inline bool LinearSumAssignment<GraphType, CostValue>::IsActive(

1086 DCHECK_LT(left_node, num_left_nodes_);

1087 return matched_arc_[left_node] == GraphType::kNilArc;

1088}

1089

1090

1091

1092

1093template <typename GraphType, typename CostValue>

1094inline bool LinearSumAssignment<GraphType, CostValue>::IsActiveForDebugging(

1096 if (node < num_left_nodes_) {

1097 return IsActive(node);

1098 } else {

1099 return matched_node_[node] == GraphType::kNilNode;

1100 }

1101}

1102

1103template <typename GraphType, typename CostValue>

1105 CostValue>::InitializeActiveNodeContainer() {

1106 DCHECK(active_nodes_->Empty());

1107 for (const NodeIndex node : BipartiteLeftNodes()) {

1108 if (IsActive(node)) {

1109 active_nodes_->Add(node);

1110 }

1111 }

1112}

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124template <typename GraphType, typename CostValue>

1125void LinearSumAssignment<GraphType, CostValue>::SaturateNegativeArcs() {

1126 total_excess_ = 0;

1127 for (const NodeIndex node : BipartiteLeftNodes()) {

1128 if (IsActive(node)) {

1129

1130

1131 total_excess_ += 1;

1132 } else {

1133

1134 total_excess_ += 1;

1135 const NodeIndex mate = GetMate(node);

1136 matched_arc_[node] = GraphType::kNilArc;

1137 matched_node_[mate] = GraphType::kNilNode;

1138 }

1139 }

1140}

1141

1142

1143template <typename GraphType, typename CostValue>

1144bool LinearSumAssignment<GraphType, CostValue>::DoublePush(NodeIndex source) {

1145 DCHECK_GT(num_left_nodes_, source);

1146 DCHECK(IsActive(source)) << "Node " << source

1147 << "must be active (unmatched)!";

1148 ImplicitPriceSummary summary = BestArcAndGap(source);

1149 const ArcIndex best_arc = summary.first;

1150 const CostValue gap = summary.second;

1151

1152

1153

1154 if (best_arc == GraphType::kNilArc) {

1155 return false;

1156 }

1157 const NodeIndex new_mate = Head(best_arc);

1158 const NodeIndex to_unmatch = matched_node_[new_mate];

1159 if (to_unmatch != GraphType::kNilNode) {

1160

1161

1162 matched_arc_[to_unmatch] = GraphType::kNilArc;

1163 active_nodes_->Add(to_unmatch);

1164

1165 iteration_stats_.double_pushes += 1;

1166 } else {

1167

1168 total_excess_ -= 1;

1169

1170 iteration_stats_.pushes += 1;

1171 }

1172 matched_arc_[source] = best_arc;

1173 matched_node_[new_mate] = source;

1174

1175 iteration_stats_.relabelings += 1;

1176 const CostValue new_price = price_[new_mate] - gap - epsilon_;

1177 price_[new_mate] = new_price;

1178 return new_price >= price_lower_bound_;

1179}

1180

1181template <typename GraphType, typename CostValue>

1182bool LinearSumAssignment<GraphType, CostValue>::Refine() {

1183 SaturateNegativeArcs();

1184 InitializeActiveNodeContainer();

1185 while (total_excess_ > 0) {

1186

1187

1188 const NodeIndex node = active_nodes_->Get();

1189 if (!DoublePush(node)) {

1190

1191

1192

1193

1194

1195

1196

1197 LOG_IF(DFATAL, total_stats_.refinements > 0)

1198 << "Infeasibility detection triggered after first iteration found "

1199 << "a feasible assignment!";

1200 return false;

1201 }

1202 }

1203 DCHECK(active_nodes_->Empty());

1204 iteration_stats_.refinements += 1;

1205 return true;

1206}

1207

1208

1209

1210

1211

1212

1213

1214

1215

1216

1217

1218

1219

1220

1221

1222template <typename GraphType, typename CostValue>

1223inline typename LinearSumAssignment<GraphType, CostValue>::ImplicitPriceSummary

1224LinearSumAssignment<GraphType, CostValue>::BestArcAndGap(

1226 DCHECK(IsActive(left_node))

1227 << "Node " << left_node << " must be active (unmatched)!";

1228 DCHECK_GT(epsilon_, 0);

1229 const auto arcs = graph_->OutgoingArcs(left_node);

1230 auto arc_it = arcs.begin();

1231 DCHECK(!arcs.empty());

1232 ArcIndex best_arc = *arc_it;

1233 CostValue min_partial_reduced_cost = PartialReducedCost(best_arc);

1234

1235

1236

1237

1238

1239 const CostValue max_gap = slack_relabeling_price_ - epsilon_;

1240 CostValue second_min_partial_reduced_cost =

1241 min_partial_reduced_cost + max_gap;

1242 for (++arc_it; arc_it != arcs.end(); ++arc_it) {

1243 const ArcIndex arc = *arc_it;

1244 const CostValue partial_reduced_cost = PartialReducedCost(arc);

1245 if (partial_reduced_cost < second_min_partial_reduced_cost) {

1246 if (partial_reduced_cost < min_partial_reduced_cost) {

1247 best_arc = arc;

1248 second_min_partial_reduced_cost = min_partial_reduced_cost;

1249 min_partial_reduced_cost = partial_reduced_cost;

1250 } else {

1251 second_min_partial_reduced_cost = partial_reduced_cost;

1252 }

1253 }

1254 }

1255 const CostValue gap = std::min<CostValue>(

1256 second_min_partial_reduced_cost - min_partial_reduced_cost, max_gap);

1257 DCHECK_GE(gap, 0);

1258 return std::make_pair(best_arc, gap);

1259}

1260

1261

1262

1263

1264

1265template <typename GraphType, typename CostValue>

1266inline CostValue LinearSumAssignment<GraphType, CostValue>::ImplicitPrice(

1268 DCHECK_GT(num_left_nodes_, left_node);

1269 DCHECK_GT(epsilon_, 0);

1270 const auto arcs = graph_->OutgoingArcs(left_node);

1271

1272 DCHECK(!arcs.empty());

1273 auto arc_it = arcs.begin();

1274 ArcIndex best_arc = *arc_it;

1275 if (best_arc == matched_arc_[left_node]) {

1276 ++arc_it;

1277 if (arc_it != arcs.end()) {

1278 best_arc = *arc_it;

1279 }

1280 }

1281 CostValue min_partial_reduced_cost = PartialReducedCost(best_arc);

1282 if (arc_it == arcs.end()) {

1283

1284

1285

1286

1287 return -(min_partial_reduced_cost + slack_relabeling_price_);

1288 }

1289 for (++arc_it; arc_it != arcs.end(); ++arc_it) {

1290 const ArcIndex arc = *arc_it;

1291 if (arc != matched_arc_[left_node]) {

1292 const CostValue partial_reduced_cost = PartialReducedCost(arc);

1293 if (partial_reduced_cost < min_partial_reduced_cost) {

1294 min_partial_reduced_cost = partial_reduced_cost;

1295 }

1296 }

1297 }

1298 return -min_partial_reduced_cost;

1299}

1300

1301

1302template <typename GraphType, typename CostValue>

1303bool LinearSumAssignment<GraphType, CostValue>::AllMatched() const {

1304 for (NodeIndex node = 0; node < graph_->num_nodes(); ++node) {

1305 if (IsActiveForDebugging(node)) {

1306 return false;

1307 }

1308 }

1309 return true;

1310}

1311

1312

1313template <typename GraphType, typename CostValue>

1316

1317

1318 CostValue left_node_price = ImplicitPrice(left_node);

1319 for (const ArcIndex arc : graph_->OutgoingArcs(left_node)) {

1320 const CostValue reduced_cost = left_node_price + PartialReducedCost(arc);

1321

1322

1323

1324

1325 if (matched_arc_[left_node] == arc) {

1326

1327

1328

1329 if (reduced_cost > epsilon_) {

1330 return false;

1331 }

1332 } else {

1333

1334

1335 if (reduced_cost < 0) {

1336 return false;

1337 }

1338 }

1339 }

1340 }

1341 return true;

1342}

1343

1344template <typename GraphType, typename CostValue>

1346 incidence_precondition_satisfied_ = true;

1347

1348

1349

1350 epsilon_ = std::max(largest_scaled_cost_magnitude_, kMinEpsilon + 1);

1351 VLOG(2) << "Largest given cost magnitude: "

1352 << largest_scaled_cost_magnitude_ / cost_scaling_factor_;

1353

1354

1355 for (NodeIndex node = 0; node < num_left_nodes_; ++node) {

1356 matched_arc_[node] = GraphType::kNilArc;

1357 if (graph_->OutgoingArcs(node).empty()) {

1358 incidence_precondition_satisfied_ = false;

1359 }

1360 }

1361

1362

1363 for (NodeIndex node = num_left_nodes_; node < graph_->num_nodes(); ++node) {

1364 price_[node] = 0;

1365 matched_node_[node] = GraphType::kNilNode;

1366 }

1367 bool in_range = true;

1368 double double_price_lower_bound = 0.0;

1370 CostValue old_error_parameter = epsilon_;

1371 do {

1372 new_error_parameter = NewEpsilon(old_error_parameter);

1373 double_price_lower_bound -=

1374 2.0 * static_cast<double>(PriceChangeBound(

1375 old_error_parameter, new_error_parameter, &in_range));

1376 old_error_parameter = new_error_parameter;

1377 } while (new_error_parameter != kMinEpsilon);

1378 const double limit =

1379 -static_cast<double>(std::numeric_limits<CostValue>::max());

1380 if (double_price_lower_bound < limit) {

1381 in_range = false;

1382 price_lower_bound_ = -std::numeric_limits<CostValue>::max();

1383 } else {

1384 price_lower_bound_ = static_cast<CostValue>(double_price_lower_bound);

1385 }

1386 VLOG(4) << "price_lower_bound_ == " << price_lower_bound_;

1387 DCHECK_LE(price_lower_bound_, 0);

1388 if (!in_range) {

1389 LOG(WARNING) << "Price change bound exceeds range of representable "

1390 << "costs; arithmetic overflow is not ruled out and "

1391 << "infeasibility might go undetected.";

1392 }

1393 return in_range;

1394}

1395

1396template <typename GraphType, typename CostValue>

1397void LinearSumAssignment<GraphType, CostValue>::ReportAndAccumulateStats() {

1398 total_stats_.Add(iteration_stats_);

1399 VLOG(3) << "Iteration stats: " << iteration_stats_.StatsString();

1400 iteration_stats_.Clear();

1401}

1402

1403template <typename GraphType, typename CostValue>

1405 CHECK(graph_ != nullptr);

1406 bool ok = graph_->num_nodes() == 2 * num_left_nodes_;

1407 if (!ok) return false;

1408

1409

1410

1411

1412

1414 ok = ok && incidence_precondition_satisfied_;

1416 while (ok && epsilon_ > kMinEpsilon) {

1417 ok = ok && UpdateEpsilon();

1418 ok = ok && Refine();

1419 ReportAndAccumulateStats();

1421 DCHECK(!ok || AllMatched());

1422 }

1423 success_ = ok;

1424 VLOG(1) << "Overall stats: " << total_stats_.StatsString();

1425 return ok;

1426}

1427

1428template <typename GraphType, typename CostValue>

1430

1431

1432 DCHECK(success_);

1436 }

1437 return cost;

1438}

1439

1440}

1441

1442#endif

bool operator()(typename GraphType::ArcIndex a, typename GraphType::ArcIndex b) const

Definition linear_assignment.h:1039

ArcIndexOrderingByTailNode(const GraphType &graph)

Definition linear_assignment.h:1034

CostValueCycleHandler(const CostValueCycleHandler &)=delete

CostValueCycleHandler & operator=(const CostValueCycleHandler &)=delete

void SetTempFromIndex(ArcIndexType source) override

Definition linear_assignment.h:1006

void SetIndexFromTemp(ArcIndexType destination) const override

Definition linear_assignment.h:1015

~CostValueCycleHandler() override

Definition linear_assignment.h:1019

CostValueCycleHandler(std::vector< CostValue > *cost)

Definition linear_assignment.h:999

void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override

Definition linear_assignment.h:1010

void SetArcCost(ArcIndex arc, CostValue cost)

Definition linear_assignment.h:981

CostValue GetAssignmentCost(NodeIndex node) const

Definition linear_assignment.h:334

operations_research::PermutationCycleHandler< typename GraphType::ArcIndex > * ArcAnnotationCycleHandler()

Definition linear_assignment.h:1057

std::string StatsString() const

Definition linear_assignment.h:346

NodeIndex NumLeftNodes() const

Definition linear_assignment.h:324

NodeIndex NumNodes() const

Definition linear_assignment.h:312

NodeIndex Head(ArcIndex arc) const

Definition linear_assignment.h:276

ArcIndex GetAssignmentArc(NodeIndex left_node) const

Definition linear_assignment.h:327

bool ComputeAssignment()

Definition linear_assignment.h:1404

~LinearSumAssignment()

Definition linear_assignment.h:246

CostValue CostValueT

Definition linear_assignment.h:229

const GraphType & Graph() const

Definition linear_assignment.h:270

NodeIndex GetMate(NodeIndex left_node) const

Definition linear_assignment.h:339

GraphType::NodeIndex NodeIndex

Definition linear_assignment.h:227

bool FinalizeSetup()

Definition linear_assignment.h:1345

bool EpsilonOptimal() const

Definition linear_assignment.h:1314

CostValue GetCost() const

Definition linear_assignment.h:1429

::util::IntegerRange< NodeIndex > BipartiteLeftNodes() const

Definition linear_assignment.h:349

LinearSumAssignment(const LinearSumAssignment &)=delete

void SetGraph(const GraphType *graph)

Definition linear_assignment.h:251

CostValue ArcCost(ArcIndex arc) const

Definition linear_assignment.h:280

LinearSumAssignment(const GraphType &graph, NodeIndex num_left_nodes)

Definition linear_assignment.h:935

LinearSumAssignment & operator=(const LinearSumAssignment &)=delete

void SetCostScalingDivisor(CostValue factor)

Definition linear_assignment.h:258

GraphType::ArcIndex ArcIndex

Definition linear_assignment.h:228

PermutationCycleHandler(const PermutationCycleHandler &)=delete

OR_DLL ABSL_DECLARE_FLAG(int64_t, assignment_alpha)

BlossomGraph::CostValue CostValue

BlossomGraph::NodeIndex NodeIndex