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
22namespace operations_research {
23namespace 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.
43template <typename IndexType>
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.
103template <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.
109template <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.
115template <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
126template <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
135template <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
144template <typename IndexType>
146 PopulateFromIdentity();
147 std::shuffle(perm_.begin(), perm_.end());
148}
149
150template <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
168template <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
191template <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
206template <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 ApplyColumnPermutationToRowIndexedVector(const Permutation< ColIndex > &col_perm, RowIndexedVector *v)
void ApplyPermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
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