OR-Tools  8.2
lp_data/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_LP_DATA_PERMUTATION_H_
15 #define OR_TOOLS_LP_DATA_PERMUTATION_H_
16 
17 #include "absl/random/random.h"
21 
22 namespace operations_research {
23 namespace glop {
24 
25 // Permutation<IndexType> is a template class for storing and using
26 // row- and column- permutations, when instantiated with RowIndex and ColIndex
27 // respectively.
28 //
29 // By a row permutation we mean a permutation that maps the row 'i' of a matrix
30 // (or column vector) to the row 'permutation[i]' and in a similar fashion by a
31 // column permutation we mean a permutation that maps the column 'j' of a matrix
32 // (or row vector) to the column 'permutation[j]'.
33 //
34 // A permutation can be represented as a matrix P, but it gets a bit tricky
35 // here: P.x permutes the rows of x according to the permutation P but x^T.P
36 // permutes the columns of x^T (a row vector) using the INVERSE permutation.
37 // That is, to permute the columns of x^T using P, one has to compute
38 // x^T.P^{-1} but P^{-1} = P^T so the notation is consistent: If P.x permutes x,
39 // then (P.x)^T = x^T.P^T permutes x^T with the same permutation.
40 //
41 // So to be clear, if P and Q are permutation matrices, the matrix P.A.Q^{-1}
42 // is the image of A through the row permutation P and column permutation Q.
43 template <typename IndexType>
44 class Permutation {
45  public:
46  Permutation() : perm_() {}
47 
48  explicit Permutation(IndexType size) : perm_(size.value(), IndexType(0)) {}
49 
50  IndexType size() const { return IndexType(perm_.size()); }
51  bool empty() const { return perm_.empty(); }
52 
53  void clear() { perm_.clear(); }
54 
55  void resize(IndexType size, IndexType value) {
56  perm_.resize(size.value(), value);
57  }
58 
59  void assign(IndexType size, IndexType value) {
60  perm_.assign(size.value(), value);
61  }
62 
63  IndexType& operator[](IndexType i) { return perm_[i]; }
64 
65  const IndexType operator[](IndexType i) const { return perm_[i]; }
66 
67  // Populates the calling object with the inverse permutation of the parameter
68  // inverse.
69  void PopulateFromInverse(const Permutation& inverse);
70 
71  // Populates the calling object with the identity permutation.
73 
74  // Populates the calling object with a random permutation.
76 
77  // Returns true if the calling object contains a permutation, false otherwise.
78  bool Check() const;
79 
80  // Returns the signature of a permutation in O(n), where n is the permutation
81  // size.
82  // The signature of a permutation is the product of the signature of
83  // the cycles defining the permutation.
84  // The signature of an odd cycle is 1, while the signature of an even cycle
85  // is -1. (Remembering hint: the signature of a swap (a 2-cycle) is -1.)
86  int ComputeSignature() const;
87 
88  private:
90 
91  DISALLOW_COPY_AND_ASSIGN(Permutation);
92 };
93 
96 
97 // Applies the permutation perm to the vector b. Overwrites result to store
98 // the result.
99 // TODO(user): Try to restrict this method to using the same integer type in
100 // the permutation and for the vector indices, i.e.
101 // IndexType == ITIVectorType::IndexType. Some client code will need to be
102 // refactored.
103 template <typename IndexType, typename ITIVectorType>
105  const ITIVectorType& b, ITIVectorType* result);
106 
107 // Applies the inverse of perm to the vector b. Overwrites result to store
108 // the result.
109 template <typename IndexType, typename ITIVectorType>
111  const ITIVectorType& b, ITIVectorType* result);
112 
113 // Specialization of ApplyPermutation(): apply a column permutation to a
114 // row-indexed vector v.
115 template <typename RowIndexedVector>
117  const Permutation<ColIndex>& col_perm, RowIndexedVector* v) {
118  RowIndexedVector temp_v = *v;
119  ApplyPermutation(col_perm, temp_v, v);
120 }
121 
122 // --------------------------------------------------------
123 // Implementation
124 // --------------------------------------------------------
125 
126 template <typename IndexType>
128  const size_t size = inverse.perm_.size();
129  perm_.resize(size);
130  for (IndexType i(0); i < size; ++i) {
131  perm_[inverse[i]] = i;
132  }
133 }
134 
135 template <typename IndexType>
137  const size_t size = perm_.size();
138  perm_.resize(size, IndexType(0));
139  for (IndexType i(0); i < size; ++i) {
140  perm_[i] = i;
141  }
142 }
143 
144 template <typename IndexType>
146  PopulateFromIdentity();
147  std::shuffle(perm_.begin(), perm_.end());
148 }
149 
150 template <typename IndexType>
152  const size_t size = perm_.size();
153  absl::StrongVector<IndexType, bool> visited(size, false);
154  for (IndexType i(0); i < size; ++i) {
155  if (perm_[i] < 0 || perm_[i] >= size) {
156  return false;
157  }
158  visited[perm_[i]] = true;
159  }
160  for (IndexType i(0); i < size; ++i) {
161  if (!visited[i]) {
162  return false;
163  }
164  }
165  return true;
166 }
167 
168 template <typename IndexType>
170  const size_t size = perm_.size();
172  DCHECK(Check());
173  int signature = 1;
174  for (IndexType i(0); i < size; ++i) {
175  if (!visited[i]) {
176  int cycle_size = 0;
177  IndexType j = i;
178  do {
179  j = perm_[j];
180  visited[j] = true;
181  ++cycle_size;
182  } while (j != i);
183  if ((cycle_size & 1) == 0) {
184  signature = -signature;
185  }
186  }
187  }
188  return signature;
189 }
190 
191 template <typename IndexType, typename ITIVectorType>
193  const ITIVectorType& b, ITIVectorType* result) {
194  RETURN_IF_NULL(result);
195  const IndexType size(perm.size());
196  if (size == 0) return;
197  DCHECK_EQ(size.value(), b.size().value());
198  result->resize(b.size(), /*whatever junk value*/ b.back());
199  for (IndexType i(0); i < size; ++i) {
200  const typename ITIVectorType::IndexType ith_index(i.value());
201  const typename ITIVectorType::IndexType permuted(perm[i].value());
202  (*result)[permuted] = b[ith_index];
203  }
204 }
205 
206 template <typename IndexType, typename ITIVectorType>
208  const ITIVectorType& b, ITIVectorType* result) {
209  RETURN_IF_NULL(result);
210  const IndexType size(perm.size().value());
211  if (size == 0) return;
212  DCHECK_EQ(size.value(), b.size().value());
213  result->resize(b.size(), /*whatever junk value*/ b.back());
214  for (IndexType i(0); i < size; ++i) {
215  const typename ITIVectorType::IndexType ith_index(i.value());
216  const typename ITIVectorType::IndexType permuted(perm[i].value());
217  (*result)[ith_index] = b[permuted];
218  }
219 }
220 
221 } // namespace glop
222 } // namespace operations_research
223 
224 #endif // OR_TOOLS_LP_DATA_PERMUTATION_H_
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void assign(size_type n, const value_type &val)
void resize(size_type new_size)
size_type size() const
bool empty() const
void resize(IndexType size, IndexType value)
const IndexType operator[](IndexType i) const
void assign(IndexType size, IndexType value)
void PopulateFromInverse(const Permutation &inverse)
int64 value
void ApplyInversePermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
Permutation< ColIndex > ColumnPermutation
void ApplyPermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
void ApplyColumnPermutationToRowIndexedVector(const Permutation< ColIndex > &col_perm, RowIndexedVector *v)
Permutation< RowIndex > RowPermutation
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define RETURN_IF_NULL(x)
Definition: return_macros.h:20