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

30#ifndef UTIL_GRAPH_TOPOLOGICALSORTER_H__

31#define UTIL_GRAPH_TOPOLOGICALSORTER_H__

33#include <cstddef>

34#include <functional>

35#include <limits>

36#include <queue>

37#include <type_traits>

38#include <utility>

39#include <vector>

41#include "absl/base/attributes.h"

42#include "absl/container/flat_hash_map.h"

43#include "absl/container/inlined_vector.h"

44#include "absl/status/status.h"

45#include "absl/status/statusor.h"

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

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

55namespace util {

90template <class AdjacencyLists>

91absl::StatusOr<

92 std::vector<typename util::GraphTraits<AdjacencyLists>::NodeIndex>>

100

101template <class AdjacencyLists>

102absl::StatusOr<

103 std::vector<typename util::GraphTraits<AdjacencyLists>::NodeIndex>>

105

106}

107

108

109

110

111

112

113

114

115

116

117

118

119template <typename T>

121 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,

122 std::vector<T>* topological_order);

123

124template <typename T>

126 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,

127 std::vector<T>* topological_order, std::vector<T>* cycle);

128

129template <typename T>

131 const std::vector<std::pair<T, T>>& arcs);

132

133

134

135

136template <typename T>

138 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,

139 std::vector<T>* topological_order);

140

141template <typename T>

143 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs,

144 std::vector<T>* topological_order, std::vector<T>* cycle);

145

146template <typename T>

148 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs);

149

150

151

152

154 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

157 .value();

158}

159

160

161

162

163

164

165

166

168 int num_nodes, const std::vector<std::pair<int, int>>& arcs,

169 std::vector<int>* topological_order);

171 int num_nodes, const std::vector<std::pair<int, int>>& arcs);

173 int num_nodes, const std::vector<std::pair<int, int>>& arcs,

174 std::vector<int>* topological_order);

176 int num_nodes, const std::vector<std::pair<int, int>>& arcs);

177

179

180template <typename T, typename Sorter>

182 Sorter* sorter, const std::vector<std::pair<T, T>>& arcs,

183 std::vector<T>* topological_order_or_cycle);

184

185

186

187

188

189

190

191

192

193

194

195

196

197template <bool stable_sort = false>

199 public:

200

202

203

204

206 : traversal_started_(false),

207 num_edges_(0),

208 num_edges_added_since_last_duplicate_removal_(0) {}

209

210

211

212

214 : adjacency_lists_(num_nodes),

215 traversal_started_(false),

216 num_edges_(0),

217 num_edges_added_since_last_duplicate_removal_(0) {}

218

219

222 delete;

223

224

225

226

227

228

230

231

232 void AddEdges(absl::Span<const std::pair<int, int>> edges);

233

234

235

236

237

239

240

241

242

243 bool GetNext(int* next_node_index, bool* cyclic,

244 std::vector<int>* output_cycle_nodes = nullptr);

245

248 return nodes_with_zero_indegree_.size();

249 }

250

252

254

255

256

257

258

259

261 int skip_lists_smaller_than);

262

263

265

266 private:

267

268 std::vector<AdjacencyList> adjacency_lists_;

269

270 bool traversal_started_;

271

272

273 int num_nodes_left_;

274 typename std::conditional<

275 stable_sort,

276

277 std::priority_queue<int, std::vector<int>, std::greater<int>>,

278 std::queue<int>>::type nodes_with_zero_indegree_;

279 std::vector<int> indegree_;

280

281

282

283 int num_edges_;

284 int num_edges_added_since_last_duplicate_removal_;

285};

286

289

290}

291

292

293

295 true>

297

298

299

300

301

302

304 false>

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327template <typename T, bool stable_sort = false,

328 typename Hash = typename absl::flat_hash_map<T, int>::hasher,

329 typename KeyEqual =

330 typename absl::flat_hash_map<T, int, Hash>::key_equal>

332 public:

334

335

339

340

341

342

343

344

345

346

347

348 void AddNode(const T& node) { int_sorter_.AddNode(LookupOrInsertNode(node)); }

349

350

351 void AddEdges(const std::vector<std::pair<T, T>>& edges) {

352 for (const auto& [from, to] : edges) AddEdge(from, to);

353 }

354

355

356

357

358

360

361

362 const int from_int = LookupOrInsertNode(from);

363 const int to_int = LookupOrInsertNode(to);

364 int_sorter_.AddEdge(from_int, to_int);

365 }

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384 bool GetNext(T* node, bool* cyclic_ptr,

385 std::vector<T>* output_cycle_nodes = nullptr) {

387 int node_index;

388 if (!int_sorter_.GetNext(

389 &node_index, cyclic_ptr,

390 output_cycle_nodes ? &cycle_int_nodes_ : nullptr)) {

391 if (*cyclic_ptr && output_cycle_nodes != nullptr) {

392 output_cycle_nodes->clear();

393 for (const int int_node : cycle_int_nodes_) {

394 output_cycle_nodes->push_back(nodes_[int_node]);

395 }

396 }

397 return false;

398 }

399 *node = nodes_[node_index];

400 return true;

401 }

402

403

404

407 return int_sorter_.GetCurrentFringeSize();

408 }

409

410

411

412

413

416 nodes_.resize(node_to_index_.size());

417

418

419 for (auto& node_and_index : node_to_index_) {

420 nodes_[node_and_index.second] = std::move(node_and_index.first);

421 }

423 int_sorter_.StartTraversal();

424 }

425

426

427

429

430 private:

431

432

433

434 absl::flat_hash_map<T, int, Hash, KeyEqual> node_to_index_;

435

436

437 std::vector<T> nodes_;

438

439

441

442

443

444 std::vector<int> cycle_int_nodes_;

445

446

447

448 int LookupOrInsertNode(const T& node) {

449 return gtl::LookupOrInsert(&node_to_index_, node, node_to_index_.size());

450 }

451};

452

454

455

456template <typename T, typename Sorter>

458 Sorter* sorter, const std::vector<std::pair<T, T>>& arcs,

459 std::vector<T>* topological_order, std::vector<T>* cycle) {

460 topological_order->clear();

461 sorter->AddEdges(arcs);

462 bool cyclic = false;

463 sorter->StartTraversal();

464 T next;

465 while (sorter->GetNext(&next, &cyclic, cycle)) {

466 topological_order->push_back(next);

467 }

468 return !cyclic;

469}

470

471template <bool stable_sort = false>

473 int num_nodes, const std::vector<std::pair<int, int>>& arcs,

474 std::vector<int>* topological_order) {

476 topological_order->reserve(num_nodes);

478 &sorter, arcs, topological_order, nullptr);

479}

480

481template <typename T, bool stable_sort = false>

483 absl::Span<const T> nodes, const std::vector<std::pair<T, T>>& arcs,

484 std::vector<T>* topological_order, std::vector<T>* cycle) {

486 for (const T& node : nodes) {

488 }

490 topological_order, cycle);

491}

492

493

494template <typename T, typename Sorter>

496 Sorter* sorter, int num_nodes, const std::vector<std::pair<T, T>>& arcs) {

497 std::vector<T> topo_order;

498 topo_order.reserve(num_nodes);

501 return topo_order;

502}

503

504template <bool stable_sort = false>

506 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

509}

510

511template <typename T, bool stable_sort = false>

513 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {

515 for (const T& node : nodes) {

517 }

519}

520}

521

522

524 int num_nodes, const std::vector<std::pair<int, int>>& arcs,

525 std::vector<int>* topological_order) {

527 topological_order);

528}

529

531 int num_nodes, const std::vector<std::pair<int, int>>& arcs,

532 std::vector<int>* topological_order) {

534 topological_order);

535}

536

537template <typename T>

539 const std::vector<std::pair<T, T>>& arcs,

540 std::vector<T>* topological_order) {

542 nullptr);

543}

544

545template <typename T>

547 const std::vector<std::pair<T, T>>& arcs,

548 std::vector<T>* topological_order, std::vector<T>* cycle) {

550 cycle);

551}

552

553template <typename T>

555 const std::vector<std::pair<T, T>>& arcs,

556 std::vector<T>* topological_order) {

558 nullptr);

559}

560

561template <typename T>

563 const std::vector<std::pair<T, T>>& arcs,

564 std::vector<T>* topological_order,

565 std::vector<T>* cycle) {

567 cycle);

568}

569

571 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

573}

574

576 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

578}

579

580template <typename T>

582 const std::vector<std::pair<T, T>>& arcs) {

584}

585

586template <typename T>

588 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {

590}

591

592}

593

594

595

596

597

600template <typename T, bool stable_sort = false,

601 typename Hash = typename absl::flat_hash_map<T, int>::hasher,

602 typename KeyEqual =

603 typename absl::flat_hash_map<T, int, Hash>::key_equal>

606

607namespace util {

608namespace graph {

610 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

611 return ::util::DenseIntTopologicalSortOrDie(num_nodes, arcs);

612}

614 int num_nodes, const std::vector<std::pair<int, int>>& arcs) {

615 return ::util::DenseIntStableTopologicalSortOrDie(num_nodes, arcs);

616}

617template <typename T>

619 const std::vector<T>& nodes, const std::vector<std::pair<T, T>>& arcs) {

620 return ::util::StableTopologicalSortOrDie<T>(nodes, arcs);

621}

622

623template <class AdjacencyLists>

624absl::StatusOr<std::vector<typename GraphTraits<AdjacencyLists>::NodeIndex>>

627 if (adj.size() > std::numeric_limits<NodeIndex>::max()) {

628 return absl::InvalidArgumentError(

629 absl::StrFormat("Too many nodes: adj.size()=%v", adj.size()));

630 }

631 const NodeIndex num_nodes(adj.size());

632 std::vector<NodeIndex> indegree(static_cast<size_t>(num_nodes), NodeIndex(0));

633 std::vector<NodeIndex> topo_order;

634 topo_order.reserve(static_cast<size_t>(num_nodes));

635 for (NodeIndex from(0); from < num_nodes; ++from) {

636 for (const NodeIndex head : adj[from]) {

637 if (!(NodeIndex(0) <= head && head < num_nodes)) {

638 return absl::InvalidArgumentError(

639 absl::StrFormat("Invalid arc in adj[%v]: %v (num_nodes=%v)", from,

640 head, num_nodes));

641 }

642

643

644

645 ++indegree[static_cast<size_t>(head)];

646 }

647 }

648 for (NodeIndex i(0); i < num_nodes; ++i) {

649 if (!indegree[static_cast<size_t>(i)]) topo_order.push_back(i);

650 }

651 size_t num_visited = 0;

652 while (num_visited < topo_order.size()) {

653 const NodeIndex from = topo_order[num_visited++];

654 for (const NodeIndex head : adj[from]) {

655 if (!--indegree[static_cast<size_t>(head)]) topo_order.push_back(head);

656 }

657 }

658 if (topo_order.size() < static_cast<size_t>(num_nodes)) {

659 return absl::InvalidArgumentError("The graph has a cycle");

660 }

661 return topo_order;

662}

663

664template <class AdjacencyLists>

665absl::StatusOr<

666 std::vector<typename util::GraphTraits<AdjacencyLists>::NodeIndex>>

669 if (adj.size() > std::numeric_limits<NodeIndex>::max()) {

670 return absl::InvalidArgumentError(

671 absl::StrFormat("Too many nodes: adj.size()=%v", adj.size()));

672 }

673 const NodeIndex num_nodes(adj.size());

674

675

676 for (NodeIndex node(0); node < NodeIndex(node); ++node) {

677 for (const NodeIndex head : adj[node]) {

678 if (head >= num_nodes) {

679 return absl::InvalidArgumentError(

680 absl::StrFormat("Invalid child %v in adj[%v]", head, node));

681 }

682 }

683 }

684

685

686

687

688

689 std::vector<bool> no_cycle_reachable_from(static_cast<size_t>(num_nodes),

690 false);

691

692

693 struct DfsState {

694 NodeIndex node;

695

696 decltype(adj[NodeIndex(0)].begin()) children;

697 decltype(adj[NodeIndex(0)].end()) children_end;

698

699 explicit DfsState(NodeIndex _node,

700 const decltype(adj[NodeIndex(0)])& neighbours)

701 : node(_node),

702 children(neighbours.begin()),

703 children_end(neighbours.end()) {}

704 };

705 std::vector<DfsState> dfs_stack;

706 std::vector<bool> visited(static_cast<size_t>(num_nodes), false);

707 for (NodeIndex start_node(0); start_node < NodeIndex(num_nodes);

708 ++start_node) {

709 if (no_cycle_reachable_from[static_cast<size_t>(start_node)]) continue;

710

711

712 visited[static_cast<size_t>(start_node)] = true;

713 dfs_stack.push_back(DfsState(start_node, adj[start_node]));

714 while (!dfs_stack.empty()) {

715 DfsState* const cur_state = &dfs_stack.back();

716 while (

717 cur_state->children != cur_state->children_end &&

718 no_cycle_reachable_from[static_cast<size_t>(*cur_state->children)]) {

719 ++cur_state->children;

720 }

721 if (cur_state->children == cur_state->children_end) {

722 no_cycle_reachable_from[static_cast<size_t>(cur_state->node)] = true;

723 dfs_stack.pop_back();

724 continue;

725 }

726

727 const NodeIndex child = *cur_state->children;

728

729

730

731

732

733

734

735

736 if (no_cycle_reachable_from[static_cast<size_t>(child)]) continue;

737 if (visited[static_cast<size_t>(child)]) {

738

739

740 size_t cycle_start = dfs_stack.size() - 1;

741 while (dfs_stack[cycle_start].node != child) --cycle_start;

742 const size_t cycle_size = dfs_stack.size() - cycle_start;

743 std::vector<NodeIndex> cycle(cycle_size);

744 for (size_t c = 0; c < cycle_size; ++c) {

745 cycle[c] = dfs_stack[cycle_start + c].node;

746 }

747 return cycle;

748 }

749

750

751 dfs_stack.push_back(DfsState(child, adj[child]));

752 visited[static_cast<size_t>(child)] = true;

753 }

754 }

755

756

757 return std::vector<NodeIndex>{};

758}

759

760}

761}

762

763#endif

static StaticGraph FromArcs(NodeIndexType num_nodes, const ArcContainer &arcs)

void AddEdges(const std::vector< std::pair< T, T > > &edges)

Definition topologicalsorter.h:351

TopologicalSorter & operator=(const TopologicalSorter &)=delete

TopologicalSorter()=default

~TopologicalSorter()=default

void StartTraversal()

Definition topologicalsorter.h:414

int GetCurrentFringeSize()

Definition topologicalsorter.h:405

bool TraversalStarted() const

Definition topologicalsorter.h:428

void AddNode(const T &node)

Definition topologicalsorter.h:348

TopologicalSorter(const TopologicalSorter &)=delete

bool GetNext(T *node, bool *cyclic_ptr, std::vector< T > *output_cycle_nodes=nullptr)

Definition topologicalsorter.h:384

void AddEdge(const T &from, const T &to)

Definition topologicalsorter.h:359

DenseIntTopologicalSorterTpl(int num_nodes)

Definition topologicalsorter.h:213

static int RemoveDuplicates(std::vector< AdjacencyList > *lists, int skip_lists_smaller_than)

void AddNode(int node_index)

void AddEdge(int from, int to)

int GetCurrentFringeSize()

Definition topologicalsorter.h:246

void AddEdges(absl::Span< const std::pair< int, int > > edges)

bool TraversalStarted() const

Definition topologicalsorter.h:253

DenseIntTopologicalSorterTpl & operator=(const DenseIntTopologicalSorterTpl &)=delete

bool GetNext(int *next_node_index, bool *cyclic, std::vector< int > *output_cycle_nodes=nullptr)

DenseIntTopologicalSorterTpl(const DenseIntTopologicalSorterTpl &)=delete

absl::InlinedVector< int, 4 > AdjacencyList

Definition topologicalsorter.h:201

void ExtractCycle(std::vector< int > *cycle_nodes) const

DenseIntTopologicalSorterTpl()

Definition topologicalsorter.h:205

auto LogContainer(const ContainerT &container, const PolicyT &policy) -> decltype(gtl::LogRange(container.begin(), container.end(), policy))

Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)

void STLClearHashIfBig(T *obj, size_t limit)

absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > > FastTopologicalSort(const AdjacencyLists &adj)

Definition topologicalsorter.h:625

std::vector< int > DenseIntStableTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:613

std::vector< T > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)

Definition topologicalsorter.h:618

std::vector< int > DenseIntTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:609

absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > > FindCycleInGraph(const AdjacencyLists &adj)

Definition topologicalsorter.h:667

std::vector< T > TopologicalSortOrDieImpl(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)

Definition topologicalsorter.h:512

ABSL_MUST_USE_RESULT bool DenseIntTopologicalSortImpl(int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)

Definition topologicalsorter.h:472

std::vector< int > DenseIntTopologicalSortOrDieImpl(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:505

ABSL_MUST_USE_RESULT bool TopologicalSortImpl(absl::Span< const T > nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order, std::vector< T > *cycle)

Definition topologicalsorter.h:482

std::vector< T > RunTopologicalSorterOrDie(Sorter *sorter, int num_nodes, const std::vector< std::pair< T, T > > &arcs)

Definition topologicalsorter.h:495

ABSL_MUST_USE_RESULT bool RunTopologicalSorter(Sorter *sorter, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order_or_cycle)

std::vector< int > DenseIntTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:570

::util::internal::DenseIntTopologicalSorterTpl< false > DenseIntTopologicalSorter

Definition topologicalsorter.h:305

ABSL_MUST_USE_RESULT bool DenseIntStableTopologicalSort(int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)

Definition topologicalsorter.h:530

ABSL_MUST_USE_RESULT bool TopologicalSort(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

Definition topologicalsorter.h:538

std::vector< int > DenseIntStableTopologicalSortOrDie(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:575

ABSL_MUST_USE_RESULT bool StableTopologicalSort(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

Definition topologicalsorter.h:554

std::vector< T > TopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)

Definition topologicalsorter.h:581

::util::internal::DenseIntTopologicalSorterTpl< true > DenseIntStableTopologicalSorter

Definition topologicalsorter.h:296

std::vector< T > StableTopologicalSortOrDie(const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)

Definition topologicalsorter.h:587

ABSL_MUST_USE_RESULT bool DenseIntTopologicalSort(int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)

Definition topologicalsorter.h:523

ABSL_MUST_USE_RESULT std::vector< int > FindCycleInDenseIntGraph(int num_nodes, const std::vector< std::pair< int, int > > &arcs)

Definition topologicalsorter.h:153

trees with all degrees equal to

std::decay_t< decltype(*(std::declval< NeighborRangeType >().begin()))> NodeIndex

::util::DenseIntStableTopologicalSorter DenseIntStableTopologicalSorter

Definition topologicalsorter.h:598

::util::DenseIntTopologicalSorter DenseIntTopologicalSorter

Definition topologicalsorter.h:599