C++ Reference: class DynamicPermutation

This documentation is automatically generated.

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.
Method
AddMappings

Return type: void

Arguments: const std::vector<int>& src, const std::vector<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()).

AllMappingsSrc

Return type: const std::vector<int>&

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

CreateSparsePermutation

Return type: std::unique_ptr<SparsePermutation>

Creates a SparsePermutation representing the current permutation. Requirements: the permutation must only have cycles. Complexity: O(support size).

DebugString

Return type: std::string

DynamicPermutation

Return type: explicit

Arguments: int n

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

ImageOf

Return type: int

Arguments: int i

LooseEnds

Return type: const std::set<int>&

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.

Reset

Return type: void

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

RootOf

Return type: int

Arguments: int i

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.

Size

Return type: int

UndoLastMappings

Return type: void

Arguments: 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.