operations_research::DynamicPermutation Class Reference

#include <dynamic_permutation.h>

Public Member Functions
	DynamicPermutation (int n)
	Upon construction, every element i in [0..n-1] maps to itself.
int	Size () const
void	AddMappings (absl::Span< const int > src, absl::Span< const int > dst)
void	UndoLastMappings (std::vector< int > *undone_mapping_src)
void	Reset ()
int	ImageOf (int i) const
	Forced-inline for the speed.
const std::vector< int > &	AllMappingsSrc () const
	Returns the union of all "src" ever given to AddMappings().
int	RootOf (int i) const
	Forced-inline for the speed.
const std::set< int > &	LooseEnds () const
std::unique_ptr< SparsePermutation >	CreateSparsePermutation () const
std::string	DebugString () const

Detailed Description

Maintains a 'partial' permutation of [0..n-1] onto itself, with a dynamic API allowing it to be built incrementally, and allowing some backtracking. This is tuned for a specific usage by ./find_graph_symmetries.cc.

RAM usage: as of 2014-04, this class needs less than: 32.125 * (n + 2 * support_size) bytes.

Definition at line 35 of file dynamic_permutation.h.

Constructor & Destructor Documentation

DynamicPermutation()

operations_research::DynamicPermutation::DynamicPermutation ( int n )

explicit

Upon construction, every element i in [0..n-1] maps to itself.

Definition at line 26 of file dynamic_permutation.cc.

Member Function Documentation

AddMappings()

void operations_research::DynamicPermutation::AddMappings	(	absl::Span< const int >	src,
		absl::Span< const int >	dst )

Declares a set of mappings for this permutation: src[i] will map to dst[i]. Requirements that are DCHECKed:

• "src" and "dst" must have the same size.
• For all i, src[i] must not already be mapped to something.
• For all i, dst[i] must not already be the image of something.

Complexity: amortized O(src.size()).

Remember the sources for the undo stack.

Definition at line 31 of file dynamic_permutation.cc.

AllMappingsSrc()

const std::vector< int > & operations_research::DynamicPermutation::AllMappingsSrc ( ) const

inline

Returns the union of all "src" ever given to AddMappings().

Definition at line 69 of file dynamic_permutation.h.

CreateSparsePermutation()

std::unique_ptr< SparsePermutation > operations_research::DynamicPermutation::CreateSparsePermutation

(

)

const

Creates a SparsePermutation representing the current permutation. Requirements: the permutation must only have cycles.

Complexity: O(support size).

Deal with the special case of a trivial x->x cycle, which we do not want to add to the sparse permutation.

Definition at line 93 of file dynamic_permutation.cc.

DebugString()

std::string operations_research::DynamicPermutation::DebugString

(

)

const

That's wasteful, but we don't care, DebugString() may be slow.

Definition at line 123 of file dynamic_permutation.cc.

ImageOf()

int operations_research::DynamicPermutation::ImageOf ( int i ) const

inline

Forced-inline for the speed.

Definition at line 116 of file dynamic_permutation.h.

LooseEnds()

const std::set< int > & operations_research::DynamicPermutation::LooseEnds ( ) const

inline

The exhaustive set of the 'loose end' of the incomplete cycles (e.g., paths) built so far.

Todo

(user): use a faster underlying container like SparseBitSet, and tweak this API accordingly.

Definition at line 85 of file dynamic_permutation.h.

Reset()

void operations_research::DynamicPermutation::Reset

(

)

Makes the permutation back to the identity (i.e. like right after construction). Complexity: O(support size).

Definition at line 82 of file dynamic_permutation.cc.

RootOf()

int operations_research::DynamicPermutation::RootOf ( int i ) const

inline

Forced-inline for the speed.

While the permutation is partially being built, the orbit of elements will either form unclosed paths, or closed cycles. In the former case, RootOf(i) returns the start of the path where i lies. If i is on a cycle, RootOf(i) will return some element of its cycle (meaning that if i maps to itself, RootOf(i) = i).

Complexity: O(log(orbit size)) in average, assuming that the mappings are added in a random order. O(orbit size) in the worst case.

Definition at line 123 of file dynamic_permutation.h.

Size()

int operations_research::DynamicPermutation::Size ( ) const

inline

Definition at line 40 of file dynamic_permutation.h.

UndoLastMappings()

void operations_research::DynamicPermutation::UndoLastMappings

(

std::vector< int > *

undone_mapping_src

)

Undoes the last AddMappings() operation, and fills the "undone_mapping_src" vector with the src of that last operation. This works like an undo stack. For example, applying the sequence (Add, Add, Add, Undo, Add, Undo, Undo) has exactly the same effect as applying the first Add() alone. If you call this too may times (i.e. there is nothing left to undo), it is simply a no-op.

Complexity: same as the AddMappings() operation being undone.

Dump the undone mappings.

Note(user): the mappings should be undone in reverse order, because the code that keeps "tails" up to date depends on it.

Definition at line 53 of file dynamic_permutation.cc.

---

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

• ortools/algorithms/dynamic_permutation.h
• ortools/algorithms/dynamic_permutation.cc