operations_research::sat::DagTopologicalSortIterator Class Reference

#include <util.h>

Classes
class	Iterator

Public Member Functions
	DagTopologicalSortIterator ()=default
	DagTopologicalSortIterator (int size)
	Graph maps indices to their children. Any children must exist.
Iterator	begin () const ABSL_ATTRIBUTE_LIFETIME_BOUND
Iterator	end () const ABSL_ATTRIBUTE_LIFETIME_BOUND
void	Reset (int size)
void	AddArc (int from, int to)
	Must be called before iteration starts or between iterations.

Detailed Description

A class to generate all possible topological sorting of a dag.

If the graph has no edges, it will generate all possible permutations.

If the graph has edges, it will generate all possible permutations of the dag that are a topological sorting of the graph.

Typical usage:

DagTopologicalSortIterator dag_topological_sort(5);

dag_topological_sort.AddArc(0, 1); dag_topological_sort.AddArc(1, 2); dag_topological_sort.AddArc(3, 4);

for (const auto& permutation : dag_topological_sort) { ///< Do something with each permutation. }

Note

to test if there are cycles, it is enough to check if at least one iteration occurred in the above loop.

Note 2: adding an arc during an iteration is not supported and the behavior is undefined.

Definition at line 1011 of file util.h.

Constructor & Destructor Documentation

DagTopologicalSortIterator() [1/2]

operations_research::sat::DagTopologicalSortIterator::DagTopologicalSortIterator ( )

default

DagTopologicalSortIterator() [2/2]

operations_research::sat::DagTopologicalSortIterator::DagTopologicalSortIterator ( int size )

inlineexplicit

Graph maps indices to their children. Any children must exist.

Definition at line 1016 of file util.h.

Member Function Documentation

AddArc()

void operations_research::sat::DagTopologicalSortIterator::AddArc ( int from, int to )

inline

Must be called before iteration starts or between iterations.

Definition at line 1110 of file util.h.

begin()

Iterator operations_research::sat::DagTopologicalSortIterator::begin ( ) const

inline

Definition at line 1100 of file util.h.

end()

Iterator operations_research::sat::DagTopologicalSortIterator::end ( ) const

inline

Definition at line 1103 of file util.h.

Reset()

void operations_research::sat::DagTopologicalSortIterator::Reset ( int size )

inline

Definition at line 1107 of file util.h.

---

The documentation for this class was generated from the following file:

• ortools/sat/util.h