OR-Tools  8.2
dynamic_permutation.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_ALGORITHMS_DYNAMIC_PERMUTATION_H_
15#define OR_TOOLS_ALGORITHMS_DYNAMIC_PERMUTATION_H_
16
17#include <memory>
18#include <set> // TODO(user): remove when no longer used.
19#include <vector>
20
22
23namespace operations_research {
24
25class SparsePermutation;
26
27// Maintains a 'partial' permutation of [0..n-1] onto itself, with a dynamic
28// API allowing it to be built incrementally, and allowing some backtracking.
29// This is tuned for a specific usage by ./find_graph_symmetries.cc.
30//
31// RAM usage: as of 2014-04, this class needs less than:
32// 32.125 * (n + 2 * support_size) bytes.
34 public:
35 // Upon construction, every element i in [0..n-1] maps to itself.
36 explicit DynamicPermutation(int n);
37
38 int Size() const { return image_.size(); } // Return the original "n".
39
40 // Declares a set of mappings for this permutation: src[i] will map to dst[i].
41 // Requirements that are DCHECKed:
42 // - "src" and "dst" must have the same size.
43 // - For all i, src[i] must not already be mapped to something.
44 // - For all i, dst[i] must not already be the image of something.
45 //
46 // Complexity: amortized O(src.size()).
47 void AddMappings(const std::vector<int>& src, const std::vector<int>& dst);
48
49 // Undoes the last AddMappings() operation, and fills the "undone_mapping_src"
50 // vector with the src of that last operation. This works like an undo stack.
51 // For example, applying the sequence (Add, Add, Add, Undo, Add, Undo, Undo)
52 // has exactly the same effect as applying the first Add() alone.
53 // If you call this too may times (i.e. there is nothing left to undo), it is
54 // simply a no-op.
55 //
56 // Complexity: same as the AddMappings() operation being undone.
57 void UndoLastMappings(std::vector<int>* undone_mapping_src);
58
59 // Makes the permutation back to the identity (i.e. like right after
60 // construction).
61 // Complexity: O(support size).
62 void Reset();
63
64 int ImageOf(int i) const; // Complexity: one vector lookup.
65
66 // Returns the union of all "src" ever given to AddMappings().
67 const std::vector<int>& AllMappingsSrc() const { return mapping_src_stack_; }
68
69 // While the permutation is partially being built, the orbit of elements will
70 // either form unclosed paths, or closed cycles. In the former case,
71 // RootOf(i) returns the start of the path where i lies. If i is on a cycle,
72 // RootOf(i) will return some element of its cycle (meaning that if i maps to
73 // itself, RootOf(i) = i).
74 //
75 // Complexity: O(log(orbit size)) in average, assuming that the mappings are
76 // added in a random order. O(orbit size) in the worst case.
77 int RootOf(int i) const;
78
79 // The exhaustive set of the 'loose end' of the incomplete cycles
80 // (e.g., paths) built so far.
81 // TODO(user): use a faster underlying container like SparseBitSet, and
82 // tweak this API accordingly.
83 const std::set<int>& LooseEnds() const { return loose_ends_; }
84
85 // Creates a SparsePermutation representing the current permutation.
86 // Requirements: the permutation must only have cycles.
87 //
88 // Complexity: O(support size).
89 std::unique_ptr<SparsePermutation> CreateSparsePermutation() const;
90
91 std::string DebugString() const;
92
93 private:
94 std::vector<int> image_;
95 // ancestor_[i] isn't exactly RootOf(i): it might itself have an ancestor, and
96 // so on.
97 std::vector<int> ancestor_;
98
99 // The concatenation of all "src" ever given to AddMappings(), and their
100 // sizes, to implement the undo stack. Note that "mapping_src_stack_" contains
101 // exactly the support of the permutation.
102 std::vector<int> mapping_src_stack_;
103 std::vector<int> mapping_src_size_stack_;
104
105 // See the homonymous accessor, above.
106 std::set<int> loose_ends_;
107
108 // Used transiently by CreateSparsePermutation(). Its resting state is:
109 // size=Size(), all elements are false.
110 mutable std::vector<bool> tmp_mask_;
111};
112
113// Forced-inline for the speed.
114inline int DynamicPermutation::ImageOf(int i) const {
115 DCHECK_GE(i, 0);
116 DCHECK_LT(i, Size());
117 return image_[i];
118}
119
120// Forced-inline for the speed.
121inline int DynamicPermutation::RootOf(int i) const {
122 DCHECK_GE(i, 0);
123 DCHECK_LT(i, Size());
124 while (true) {
125 const int j = ancestor_[i];
126 if (j == i) return i;
127 i = j;
128 }
129}
130
131} // namespace operations_research
132
133#endif // OR_TOOLS_ALGORITHMS_DYNAMIC_PERMUTATION_H_
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
std::unique_ptr< SparsePermutation > CreateSparsePermutation() const
void UndoLastMappings(std::vector< int > *undone_mapping_src)
void AddMappings(const std::vector< int > &src, const std::vector< int > &dst)
const std::set< int > & LooseEnds() const
const std::vector< int > & AllMappingsSrc() const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...