Home Original page

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14#ifndef UTIL_GRAPH_FLOW_GRAPH_H_

15#define UTIL_GRAPH_FLOW_GRAPH_H_

16

17#include <cstddef>

18#include <cstdint>

19#include <memory>

20#include <vector>

21

22#include "absl/log/check.h"

23#include "absl/types/span.h"

27

28namespace util {

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51template <typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

53 NodeIndexType, ArcIndexType, false> {

54

55

57 ArcIndexType, false>

58 Base;

64

65 public:

67

71 this->AddNode(num_nodes - 1);

72 }

73

74 NodeIndexType Head(ArcIndexType arc) const {

75 DCHECK(is_built_);

76 DCHECK_GE(arc, 0);

77 DCHECK_LT(arc, num_arcs_);

78 return heads_[arc];

79 }

80

81 NodeIndexType Tail(ArcIndexType arc) const {

82 DCHECK(is_built_);

83 DCHECK_GE(arc, 0);

84 DCHECK_LT(arc, num_arcs_);

85

86

87

88

89

90 return heads_[reverse_[arc]];

91 }

92

93

94

95 ArcIndexType OppositeArc(ArcIndexType arc) const {

96 DCHECK(is_built_);

97 DCHECK_GE(arc, 0);

98 DCHECK_LT(arc, num_arcs_);

99 return reverse_[arc];

100 }

101

102

107 NodeIndexType node, ArcIndexType from) const {

108 DCHECK(is_built_);

109 DCHECK_GE(node, 0);

110 DCHECK_LT(node, num_nodes_);

111 DCHECK_GE(from, start_[node]);

113 }

114

115

116

117

119 NodeIndexType node) const {

121 }

123 NodeIndexType node, ArcIndexType from) const {

125 }

126

127 absl::Span<const NodeIndexType> operator[](NodeIndexType node) const {

128 const int b = start_[node];

129 const size_t size = start_[node + 1] - b;

130 if (size == 0) return {};

131 return {&heads_[b], size};

132 }

133

136 tmp_tails_.reserve(bound);

137 tmp_heads_.reserve(bound);

138 }

139

141 num_nodes_ = std::max(num_nodes_, node + 1);

142 }

143

144 ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head) {

145 AddNode(tail > head ? tail : head);

146 tmp_tails_.push_back(tail);

147 tmp_heads_.push_back(head);

148 return num_arcs_++;

149 }

150

152 void Build(std::vector<ArcIndexType>* permutation) final;

153

154

155

156

157

159

160

161

162

163 void SetSortByHead(bool value) { option_sort_by_head_ = value; }

164

165 private:

166

167

168

169 void FillPermutationAndStart(absl::Span<const NodeIndexType> input,

170 absl::Span<ArcIndexType> perm);

171

172

173

174

175 void FillPermutationAndStart(absl::Span<const NodeIndexType> first_criteria,

176 absl::Span<const NodeIndexType> second_criteria,

177 absl::Span<ArcIndexType> perm);

178 void FillReversePermutationAndStart(

179 absl::Span<const NodeIndexType> first_criteria,

180 absl::Span<const NodeIndexType> second_criteria,

181 absl::Span<ArcIndexType> reverse_perm);

182

183

184 void InitializeStart(absl::Span<const NodeIndexType> input);

185 void RestoreStart();

186

187

188 bool option_detect_reverse_ = true;

189 bool option_sort_by_head_ = false;

190

191

192

193

194 bool is_built_ = false;

195

196

197 std::vector<NodeIndexType> tmp_tails_;

198 std::vector<NodeIndexType> tmp_heads_;

199

200

201

202 std::unique_ptr<ArcIndexType[]> start_;

203

204

205

206 std::unique_ptr<NodeIndexType[]> heads_;

207

208 std::unique_ptr<ArcIndexType[]> reverse_;

209};

210

212

213

214template <class Key, class Value>

216 absl::Span<const Value> input, absl::Span<Value> output) {

217 DCHECK_EQ(permutation.size(), input.size());

218 DCHECK_EQ(permutation.size(), output.size());

219 for (int i = 0; i < permutation.size(); ++i) {

220 output[permutation[i]] = input[i];

221 }

222}

223

224}

225

226template <typename NodeIndexType, typename ArcIndexType>

227void FlowGraph<NodeIndexType, ArcIndexType>::InitializeStart(

228 absl::Span<const NodeIndexType> input) {

229

230 std::fill(start_.get(), start_.get() + num_nodes_, 0);

231 start_[num_nodes_] = input.size();

232

233 for (const NodeIndexType node : input) start_[node]++;

234

235

236 int sum = 0;

237 for (int i = 0; i < num_nodes_; ++i) {

238 int temp = start_[i];

239 start_[i] = sum;

240 sum += temp;

241 }

242 DCHECK_EQ(sum, input.size());

243}

244

245template <typename NodeIndexType, typename ArcIndexType>

246void FlowGraph<NodeIndexType, ArcIndexType>::RestoreStart() {

247

248 for (int i = num_nodes_; --i > 0;) {

249 start_[i] = start_[i - 1];

250 }

251 start_[0] = 0;

252}

253

254template <typename NodeIndexType, typename ArcIndexType>

255void FlowGraph<NodeIndexType, ArcIndexType>::FillPermutationAndStart(

256 absl::Span<const NodeIndexType> input, absl::Span<ArcIndexType> perm) {

257 DCHECK_EQ(input.size(), perm.size());

258 InitializeStart(input);

259

260

261

262 for (int i = 0; i < input.size(); ++i) {

263 perm[i] = start_[input[i]]++;

264 }

265

266 RestoreStart();

267}

268

269template <typename NodeIndexType, typename ArcIndexType>

270void FlowGraph<NodeIndexType, ArcIndexType>::FillPermutationAndStart(

271 absl::Span<const NodeIndexType> first_criteria,

272 absl::Span<const NodeIndexType> second_criteria,

273 absl::Span<ArcIndexType> perm) {

274

275 FillPermutationAndStart(second_criteria, absl::MakeSpan(perm));

276

277

278 const auto tmp_storage = std::make_unique<ArcIndexType[]>(num_arcs_);

279 const auto tmp = absl::MakeSpan(tmp_storage.get(), num_arcs_);

281

282

283 const auto second_perm_storage = std::make_unique<ArcIndexType[]>(num_arcs_);

284 const auto second_perm = absl::MakeSpan(second_perm_storage.get(), num_arcs_);

285 FillPermutationAndStart(tmp, second_perm);

286

287

288

289 for (ArcIndexType& image : perm) {

290 image = second_perm[image];

291 }

292}

293

294template <typename NodeIndexType, typename ArcIndexType>

295void FlowGraph<NodeIndexType, ArcIndexType>::FillReversePermutationAndStart(

296 absl::Span<const NodeIndexType> first_criteria,

297 absl::Span<const NodeIndexType> second_criteria,

298 absl::Span<ArcIndexType> reverse_perm) {

299

300 InitializeStart(second_criteria);

301 const auto r_perm_storage = std::make_unique<ArcIndexType[]>(num_arcs_);

302 const auto r_perm = absl::MakeSpan(r_perm_storage.get(), num_arcs_);

303 auto* start = start_.get();

304 for (int i = 0; i < second_criteria.size(); ++i) {

305 r_perm[start[second_criteria[i]]++] = i;

306 }

307

308

309 InitializeStart(first_criteria);

310 for (const int i : r_perm) {

311 reverse_perm[start[first_criteria[i]]++] = i;

312 }

313 RestoreStart();

314}

315

316template <typename NodeIndexType, typename ArcIndexType>

318 std::vector<ArcIndexType>* permutation) {

319 DCHECK(!is_built_);

320 if (is_built_) return;

321 is_built_ = true;

322

323 start_ = std::make_unique<ArcIndexType[]>(num_nodes_ + 1);

324 std::vector<ArcIndexType> perm(num_arcs_);

325

326 const int kNoExplicitReverseArc = -1;

327 std::vector<ArcIndexType> reverse(num_arcs_, kNoExplicitReverseArc);

328

329 bool fix_final_permutation = false;

330 if (option_detect_reverse_) {

331

332

333 std::vector<bool> was_reversed_(num_arcs_, false);

334 for (int arc = 0; arc < num_arcs_; ++arc) {

335 if (tmp_heads_[arc] < tmp_tails_[arc]) {

336 std::swap(tmp_heads_[arc], tmp_tails_[arc]);

337 was_reversed_[arc] = true;

338 }

339 }

340

341

342

343

344 auto reverse_perm = absl::MakeSpan(perm);

345 FillReversePermutationAndStart(tmp_tails_, tmp_heads_,

346 absl::MakeSpan(reverse_perm));

347

348

349

350 int candidate_i = 0;

351 int num_filled = 0;

352 for (int i = 0; i < num_arcs_; ++i) {

353 const int arc = reverse_perm[i];

354 const int candidate_arc = reverse_perm[candidate_i];

355 if (tmp_heads_[arc] != tmp_heads_[candidate_arc] ||

356 tmp_tails_[arc] != tmp_tails_[candidate_arc]) {

357 candidate_i = i;

358 continue;

359 }

360

361 if (was_reversed_[arc] != was_reversed_[candidate_arc]) {

362 DCHECK_EQ(reverse[arc], -1);

363 DCHECK_EQ(reverse[candidate_arc], -1);

364 reverse[arc] = candidate_arc;

365 reverse[candidate_arc] = arc;

366 num_filled += 2;

367

368

369 for (; ++candidate_i < i;) {

370 if (reverse[reverse_perm[candidate_i]] == -1) break;

371 }

372 if (candidate_i == i) {

373 candidate_i = ++i;

374 }

375 }

376 }

377

378

379 {

380 const int extra_size = num_arcs_ - num_filled;

381 tmp_tails_.resize(num_arcs_ + extra_size);

382 tmp_heads_.resize(num_arcs_ + extra_size);

383 reverse.resize(num_arcs_ + extra_size);

384 int new_index = num_arcs_;

385 for (int i = 0; i < num_arcs_; ++i) {

386

387 if (was_reversed_[i]) {

388 std::swap(tmp_tails_[i], tmp_heads_[i]);

389 }

390

391 if (reverse[i] != kNoExplicitReverseArc) continue;

392 reverse[i] = new_index;

393 reverse[new_index] = i;

394 tmp_tails_[new_index] = tmp_heads_[i];

395 tmp_heads_[new_index] = tmp_tails_[i];

396 ++new_index;

397 }

398 CHECK_EQ(new_index, num_arcs_ + extra_size);

399 }

400 } else {

401

402 tmp_tails_.resize(2 * num_arcs_);

403 tmp_heads_.resize(2 * num_arcs_);

404 reverse.resize(2 * num_arcs_);

405 for (int arc = 0; arc < num_arcs_; ++arc) {

406 const int image = num_arcs_ + arc;

407 tmp_heads_[image] = tmp_tails_[arc];

408 tmp_tails_[image] = tmp_heads_[arc];

409 reverse[image] = arc;

410 reverse[arc] = image;

411 }

412

413

414

415

416

417

418

419 fix_final_permutation = true;

420 for (int arc = 0; arc < num_arcs_; ++arc) {

421 const int image = num_arcs_ + arc;

422 std::swap(tmp_heads_[image], tmp_heads_[arc]);

423 std::swap(tmp_tails_[image], tmp_tails_[arc]);

424 }

425 }

426

427 num_arcs_ = tmp_heads_.size();

428 perm.resize(num_arcs_);

429

430

431

432

433

434

435 if (option_sort_by_head_) {

436 FillPermutationAndStart(tmp_tails_, tmp_heads_, absl::MakeSpan(perm));

437 } else {

438 FillPermutationAndStart(tmp_tails_, absl::MakeSpan(perm));

439 }

440

441

442 heads_ = std::make_unique<NodeIndexType[]>(num_arcs_);

444 perm, tmp_heads_, absl::MakeSpan(heads_.get(), num_arcs_));

445

446

449

450

451 reverse_ = std::make_unique<ArcIndexType[]>(num_arcs_);

452 for (int i = 0; i < num_arcs_; ++i) {

453 reverse_[perm[i]] = perm[reverse[i]];

454 }

455

456 if (permutation != nullptr) {

457 if (fix_final_permutation) {

458 for (int i = 0; i < num_arcs_ / 2; ++i) {

459 std::swap(perm[i], perm[num_arcs_ / 2 + i]);

460 }

461 }

462 permutation->swap(perm);

463 }

464

465 node_capacity_ = num_nodes_;

466 arc_capacity_ = num_arcs_;

468}

469

470}

471

472#endif

int32_t num_nodes() const

int32_t arc_capacity() const

void Reserve(int32_t node_capacity, int32_t arc_capacity)

NodeIndexType node_capacity_

virtual void ReserveArcs(ArcIndexType bound)

ArcIndexType arc_capacity_

FlowGraph(NodeIndexType num_nodes, ArcIndexType arc_capacity)

Definition flow_graph.h:68

void SetDetectReverse(bool value)

Definition flow_graph.h:158

void SetSortByHead(bool value)

Definition flow_graph.h:163

util::IntegerRange< ArcIndexType > OutgoingOrOppositeIncomingArcs(NodeIndexType node) const

Definition flow_graph.h:118

ArcIndexType OppositeArc(ArcIndexType arc) const

Definition flow_graph.h:95

void AddNode(NodeIndexType node)

Definition flow_graph.h:140

absl::Span< const NodeIndexType > operator[](NodeIndexType node) const

Definition flow_graph.h:127

ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)

Definition flow_graph.h:144

NodeIndexType Head(ArcIndexType arc) const

Definition flow_graph.h:74

util::IntegerRange< ArcIndexType > OutgoingArcs(NodeIndexType node) const

Definition flow_graph.h:103

util::IntegerRange< ArcIndexType > OutgoingOrOppositeIncomingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const

Definition flow_graph.h:122

void Build()

Definition flow_graph.h:151

util::IntegerRange< ArcIndexType > OutgoingArcsStartingFrom(NodeIndexType node, ArcIndexType from) const

Definition flow_graph.h:106

void ReserveArcs(ArcIndexType bound) override

Definition flow_graph.h:134

NodeIndexType Tail(ArcIndexType arc) const

Definition flow_graph.h:81

void STLClearObject(T *obj)

void PermuteInto(absl::Span< const Key > permutation, absl::Span< const Value > input, absl::Span< Value > output)

Definition flow_graph.h:215

static int input(yyscan_t yyscanner)