Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class DynamicPermutation
Note: 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.
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()).
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.
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.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["The `DynamicPermutation` class in C++ manages a partial permutation of numbers (0 to n-1), allowing incremental building and backtracking."],["It's optimized for use in graph symmetry finding and has a memory footprint of roughly 32.125 \\* (n + 2 \\* support_size) bytes."],["Key functionalities include adding and undoing mappings, identifying loose ends and roots of elements within the permutation, and creating a sparse permutation representation."],["The API provides methods like `AddMappings`, `UndoLastMappings`, `LooseEnds`, `RootOf`, and `CreateSparsePermutation` for manipulating and querying the permutation."],["The class ensures data integrity with checks to prevent mapping conflicts and maintains efficiency with amortized O(src.size()) complexity for adding mappings and O(support size) for creating sparse permutations."]]],["The `DynamicPermutation` class manages a partial permutation of elements \\[0..n-1]. Key actions include `AddMappings`, which maps source elements to destination elements, and `UndoLastMappings`, which reverses the last `AddMappings` operation. `Reset` returns the permutation to its initial state. `ImageOf` returns the image of a given element, `RootOf` returns the start of the path containing a given element, and `LooseEnds` identifies incomplete cycles. The class also allows creating a `SparsePermutation` and provides information on `AllMappingsSrc`.\n"]]
