Please, help us to better know about our user community by answering the following short survey: https://forms.gle/wpyrxWi18ox9Z5ae9
Eigen  3.4.0
 
Loading...
Searching...
No Matches
PermutationMatrix.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com>
5// Copyright (C) 2009-2015 Gael Guennebaud <gael.guennebaud@inria.fr>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10
11#ifndef EIGEN_PERMUTATIONMATRIX_H
12#define EIGEN_PERMUTATIONMATRIX_H
13
14namespace Eigen {
15
16namespace internal {
17
18enum PermPermProduct_t {PermPermProduct};
19
20} // end namespace internal
21
45template<typename Derived>
46class PermutationBase : public EigenBase<Derived>
47{
48 typedef internal::traits<Derived> Traits;
50 public:
51
52 #ifndef EIGEN_PARSED_BY_DOXYGEN
53 typedef typename Traits::IndicesType IndicesType;
54 enum {
55 Flags = Traits::Flags,
56 RowsAtCompileTime = Traits::RowsAtCompileTime,
57 ColsAtCompileTime = Traits::ColsAtCompileTime,
58 MaxRowsAtCompileTime = Traits::MaxRowsAtCompileTime,
59 MaxColsAtCompileTime = Traits::MaxColsAtCompileTime
60 };
61 typedef typename Traits::StorageIndex StorageIndex;
63 DenseMatrixType;
65 PlainPermutationType;
66 typedef PlainPermutationType PlainObject;
67 using Base::derived;
68 typedef Inverse<Derived> InverseReturnType;
69 typedef void Scalar;
70 #endif
71
73 template<typename OtherDerived>
75 {
76 indices() = other.indices();
77 return derived();
78 }
79
81 template<typename OtherDerived>
82 Derived& operator=(const TranspositionsBase<OtherDerived>& tr)
83 {
84 setIdentity(tr.size());
85 for(Index k=size()-1; k>=0; --k)
86 applyTranspositionOnTheRight(k,tr.coeff(k));
87 return derived();
88 }
89
91 inline EIGEN_DEVICE_FUNC Index rows() const { return Index(indices().size()); }
92
94 inline EIGEN_DEVICE_FUNC Index cols() const { return Index(indices().size()); }
95
97 inline EIGEN_DEVICE_FUNC Index size() const { return Index(indices().size()); }
98
99 #ifndef EIGEN_PARSED_BY_DOXYGEN
100 template<typename DenseDerived>
101 void evalTo(MatrixBase<DenseDerived>& other) const
102 {
103 other.setZero();
104 for (Index i=0; i<rows(); ++i)
105 other.coeffRef(indices().coeff(i),i) = typename DenseDerived::Scalar(1);
106 }
107 #endif
108
113 DenseMatrixType toDenseMatrix() const
114 {
115 return derived();
116 }
117
119 const IndicesType& indices() const { return derived().indices(); }
121 IndicesType& indices() { return derived().indices(); }
122
125 inline void resize(Index newSize)
126 {
127 indices().resize(newSize);
128 }
129
132 {
133 StorageIndex n = StorageIndex(size());
134 for(StorageIndex i = 0; i < n; ++i)
135 indices().coeffRef(i) = i;
136 }
137
140 void setIdentity(Index newSize)
141 {
142 resize(newSize);
143 setIdentity();
144 }
145
156 {
157 eigen_assert(i>=0 && j>=0 && i<size() && j<size());
158 for(Index k = 0; k < size(); ++k)
159 {
160 if(indices().coeff(k) == i) indices().coeffRef(k) = StorageIndex(j);
161 else if(indices().coeff(k) == j) indices().coeffRef(k) = StorageIndex(i);
162 }
163 return derived();
164 }
165
175 {
176 eigen_assert(i>=0 && j>=0 && i<size() && j<size());
177 std::swap(indices().coeffRef(i), indices().coeffRef(j));
178 return derived();
179 }
180
185 inline InverseReturnType inverse() const
186 { return InverseReturnType(derived()); }
191 inline InverseReturnType transpose() const
192 { return InverseReturnType(derived()); }
193
194 /**** multiplication helpers to hopefully get RVO ****/
195
196
197#ifndef EIGEN_PARSED_BY_DOXYGEN
198 protected:
199 template<typename OtherDerived>
200 void assignTranspose(const PermutationBase<OtherDerived>& other)
201 {
202 for (Index i=0; i<rows();++i) indices().coeffRef(other.indices().coeff(i)) = i;
203 }
204 template<typename Lhs,typename Rhs>
205 void assignProduct(const Lhs& lhs, const Rhs& rhs)
206 {
207 eigen_assert(lhs.cols() == rhs.rows());
208 for (Index i=0; i<rows();++i) indices().coeffRef(i) = lhs.indices().coeff(rhs.indices().coeff(i));
209 }
210#endif
211
212 public:
213
218 template<typename Other>
219 inline PlainPermutationType operator*(const PermutationBase<Other>& other) const
220 { return PlainPermutationType(internal::PermPermProduct, derived(), other.derived()); }
221
226 template<typename Other>
227 inline PlainPermutationType operator*(const InverseImpl<Other,PermutationStorage>& other) const
228 { return PlainPermutationType(internal::PermPermProduct, *this, other.eval()); }
229
234 template<typename Other> friend
235 inline PlainPermutationType operator*(const InverseImpl<Other, PermutationStorage>& other, const PermutationBase& perm)
236 { return PlainPermutationType(internal::PermPermProduct, other.eval(), perm); }
237
243 {
244 Index res = 1;
245 Index n = size();
247 mask.fill(false);
248 Index r = 0;
249 while(r < n)
250 {
251 // search for the next seed
252 while(r<n && mask[r]) r++;
253 if(r>=n)
254 break;
255 // we got one, let's follow it until we are back to the seed
256 Index k0 = r++;
257 mask.coeffRef(k0) = true;
258 for(Index k=indices().coeff(k0); k!=k0; k=indices().coeff(k))
259 {
260 mask.coeffRef(k) = true;
261 res = -res;
262 }
263 }
264 return res;
265 }
266
267 protected:
268
269};
270
271namespace internal {
272template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex>
273struct traits<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex> >
274 : traits<Matrix<_StorageIndex,SizeAtCompileTime,SizeAtCompileTime,0,MaxSizeAtCompileTime,MaxSizeAtCompileTime> >
275{
276 typedef PermutationStorage StorageKind;
277 typedef Matrix<_StorageIndex, SizeAtCompileTime, 1, 0, MaxSizeAtCompileTime, 1> IndicesType;
278 typedef _StorageIndex StorageIndex;
279 typedef void Scalar;
280};
281}
282
296template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex>
297class PermutationMatrix : public PermutationBase<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex> >
298{
300 typedef internal::traits<PermutationMatrix> Traits;
301 public:
302
303 typedef const PermutationMatrix& Nested;
304
305 #ifndef EIGEN_PARSED_BY_DOXYGEN
306 typedef typename Traits::IndicesType IndicesType;
307 typedef typename Traits::StorageIndex StorageIndex;
308 #endif
309
310 inline PermutationMatrix()
311 {}
312
315 explicit inline PermutationMatrix(Index size) : m_indices(size)
316 {
317 eigen_internal_assert(size <= NumTraits<StorageIndex>::highest());
318 }
319
321 template<typename OtherDerived>
323 : m_indices(other.indices()) {}
324
332 template<typename Other>
333 explicit inline PermutationMatrix(const MatrixBase<Other>& indices) : m_indices(indices)
334 {}
335
337 template<typename Other>
338 explicit PermutationMatrix(const TranspositionsBase<Other>& tr)
339 : m_indices(tr.size())
340 {
341 *this = tr;
342 }
343
345 template<typename Other>
347 {
348 m_indices = other.indices();
349 return *this;
350 }
351
353 template<typename Other>
354 PermutationMatrix& operator=(const TranspositionsBase<Other>& tr)
355 {
356 return Base::operator=(tr.derived());
357 }
358
360 const IndicesType& indices() const { return m_indices; }
362 IndicesType& indices() { return m_indices; }
363
364
365 /**** multiplication helpers to hopefully get RVO ****/
366
367#ifndef EIGEN_PARSED_BY_DOXYGEN
368 template<typename Other>
369 PermutationMatrix(const InverseImpl<Other,PermutationStorage>& other)
370 : m_indices(other.derived().nestedExpression().size())
371 {
372 eigen_internal_assert(m_indices.size() <= NumTraits<StorageIndex>::highest());
373 StorageIndex end = StorageIndex(m_indices.size());
374 for (StorageIndex i=0; i<end;++i)
375 m_indices.coeffRef(other.derived().nestedExpression().indices().coeff(i)) = i;
376 }
377 template<typename Lhs,typename Rhs>
378 PermutationMatrix(internal::PermPermProduct_t, const Lhs& lhs, const Rhs& rhs)
379 : m_indices(lhs.indices().size())
380 {
381 Base::assignProduct(lhs,rhs);
382 }
383#endif
384
385 protected:
386
387 IndicesType m_indices;
388};
389
390
391namespace internal {
392template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int _PacketAccess>
393struct traits<Map<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex>,_PacketAccess> >
394 : traits<Matrix<_StorageIndex,SizeAtCompileTime,SizeAtCompileTime,0,MaxSizeAtCompileTime,MaxSizeAtCompileTime> >
395{
396 typedef PermutationStorage StorageKind;
397 typedef Map<const Matrix<_StorageIndex, SizeAtCompileTime, 1, 0, MaxSizeAtCompileTime, 1>, _PacketAccess> IndicesType;
398 typedef _StorageIndex StorageIndex;
399 typedef void Scalar;
400};
401}
402
403template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int _PacketAccess>
404class Map<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex>,_PacketAccess>
405 : public PermutationBase<Map<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex>,_PacketAccess> >
406{
407 typedef PermutationBase<Map> Base;
408 typedef internal::traits<Map> Traits;
409 public:
410
411 #ifndef EIGEN_PARSED_BY_DOXYGEN
412 typedef typename Traits::IndicesType IndicesType;
413 typedef typename IndicesType::Scalar StorageIndex;
414 #endif
415
416 inline Map(const StorageIndex* indicesPtr)
417 : m_indices(indicesPtr)
418 {}
419
420 inline Map(const StorageIndex* indicesPtr, Index size)
421 : m_indices(indicesPtr,size)
422 {}
423
425 template<typename Other>
426 Map& operator=(const PermutationBase<Other>& other)
427 { return Base::operator=(other.derived()); }
428
430 template<typename Other>
431 Map& operator=(const TranspositionsBase<Other>& tr)
432 { return Base::operator=(tr.derived()); }
433
434 #ifndef EIGEN_PARSED_BY_DOXYGEN
438 Map& operator=(const Map& other)
439 {
440 m_indices = other.m_indices;
441 return *this;
442 }
443 #endif
444
446 const IndicesType& indices() const { return m_indices; }
448 IndicesType& indices() { return m_indices; }
449
450 protected:
451
452 IndicesType m_indices;
453};
454
455template<typename _IndicesType> class TranspositionsWrapper;
456namespace internal {
457template<typename _IndicesType>
458struct traits<PermutationWrapper<_IndicesType> >
459{
460 typedef PermutationStorage StorageKind;
461 typedef void Scalar;
462 typedef typename _IndicesType::Scalar StorageIndex;
463 typedef _IndicesType IndicesType;
464 enum {
465 RowsAtCompileTime = _IndicesType::SizeAtCompileTime,
466 ColsAtCompileTime = _IndicesType::SizeAtCompileTime,
467 MaxRowsAtCompileTime = IndicesType::MaxSizeAtCompileTime,
468 MaxColsAtCompileTime = IndicesType::MaxSizeAtCompileTime,
469 Flags = 0
470 };
471};
472}
473
485template<typename _IndicesType>
486class PermutationWrapper : public PermutationBase<PermutationWrapper<_IndicesType> >
487{
489 typedef internal::traits<PermutationWrapper> Traits;
490 public:
491
492 #ifndef EIGEN_PARSED_BY_DOXYGEN
493 typedef typename Traits::IndicesType IndicesType;
494 #endif
495
496 inline PermutationWrapper(const IndicesType& indices)
497 : m_indices(indices)
498 {}
499
501 const typename internal::remove_all<typename IndicesType::Nested>::type&
502 indices() const { return m_indices; }
503
504 protected:
505
506 typename IndicesType::Nested m_indices;
507};
508
509
512template<typename MatrixDerived, typename PermutationDerived>
513EIGEN_DEVICE_FUNC
514const Product<MatrixDerived, PermutationDerived, AliasFreeProduct>
515operator*(const MatrixBase<MatrixDerived> &matrix,
516 const PermutationBase<PermutationDerived>& permutation)
517{
519 (matrix.derived(), permutation.derived());
520}
521
524template<typename PermutationDerived, typename MatrixDerived>
525EIGEN_DEVICE_FUNC
526const Product<PermutationDerived, MatrixDerived, AliasFreeProduct>
527operator*(const PermutationBase<PermutationDerived> &permutation,
528 const MatrixBase<MatrixDerived>& matrix)
529{
531 (permutation.derived(), matrix.derived());
532}
533
534
535template<typename PermutationType>
536class InverseImpl<PermutationType, PermutationStorage>
537 : public EigenBase<Inverse<PermutationType> >
538{
539 typedef typename PermutationType::PlainPermutationType PlainPermutationType;
540 typedef internal::traits<PermutationType> PermTraits;
541 protected:
542 InverseImpl() {}
543 public:
544 typedef Inverse<PermutationType> InverseType;
545 using EigenBase<Inverse<PermutationType> >::derived;
546
547 #ifndef EIGEN_PARSED_BY_DOXYGEN
548 typedef typename PermutationType::DenseMatrixType DenseMatrixType;
549 enum {
550 RowsAtCompileTime = PermTraits::RowsAtCompileTime,
551 ColsAtCompileTime = PermTraits::ColsAtCompileTime,
552 MaxRowsAtCompileTime = PermTraits::MaxRowsAtCompileTime,
553 MaxColsAtCompileTime = PermTraits::MaxColsAtCompileTime
554 };
555 #endif
556
557 #ifndef EIGEN_PARSED_BY_DOXYGEN
558 template<typename DenseDerived>
559 void evalTo(MatrixBase<DenseDerived>& other) const
560 {
561 other.setZero();
562 for (Index i=0; i<derived().rows();++i)
563 other.coeffRef(i, derived().nestedExpression().indices().coeff(i)) = typename DenseDerived::Scalar(1);
564 }
565 #endif
566
568 PlainPermutationType eval() const { return derived(); }
569
570 DenseMatrixType toDenseMatrix() const { return derived(); }
571
574 template<typename OtherDerived> friend
575 const Product<OtherDerived, InverseType, AliasFreeProduct>
576 operator*(const MatrixBase<OtherDerived>& matrix, const InverseType& trPerm)
577 {
578 return Product<OtherDerived, InverseType, AliasFreeProduct>(matrix.derived(), trPerm.derived());
579 }
580
583 template<typename OtherDerived>
584 const Product<InverseType, OtherDerived, AliasFreeProduct>
585 operator*(const MatrixBase<OtherDerived>& matrix) const
586 {
587 return Product<InverseType, OtherDerived, AliasFreeProduct>(derived(), matrix.derived());
588 }
589};
590
591template<typename Derived>
592const PermutationWrapper<const Derived> MatrixBase<Derived>::asPermutation() const
593{
594 return derived();
595}
596
597namespace internal {
598
599template<> struct AssignmentKind<DenseShape,PermutationShape> { typedef EigenBase2EigenBase Kind; };
600
601} // end namespace internal
602
603} // end namespace Eigen
604
605#endif // EIGEN_PERMUTATIONMATRIX_H
Derived & setZero()
Definition: CwiseNullaryOp.h:546
Derived & derived()
Definition: EigenBase.h:46
Scalar & coeffRef(Index row, Index col)
Definition: DenseCoeffsBase.h:342
Expression of the inverse of another expression.
Definition: Inverse.h:44
Map(PointerArgType dataPtr, const StrideType &stride=StrideType())
Definition: Map.h:129
Base class for all dense matrices, vectors, and expressions.
Definition: MatrixBase.h:50
The matrix class, also used for vectors and row-vectors.
Definition: Matrix.h:180
Scalar & coeffRef(Index rowId, Index colId)
Definition: PlainObjectBase.h:175
Base class for permutations.
Definition: PermutationMatrix.h:47
InverseReturnType transpose() const
Definition: PermutationMatrix.h:191
Derived & applyTranspositionOnTheLeft(Index i, Index j)
Definition: PermutationMatrix.h:155
void resize(Index newSize)
Definition: PermutationMatrix.h:125
Index determinant() const
Definition: PermutationMatrix.h:242
Index size() const
Definition: PermutationMatrix.h:97
Index cols() const
Definition: PermutationMatrix.h:94
Derived & applyTranspositionOnTheRight(Index i, Index j)
Definition: PermutationMatrix.h:174
friend PlainPermutationType operator*(const InverseImpl< Other, PermutationStorage > &other, const PermutationBase &perm)
Definition: PermutationMatrix.h:235
void setIdentity()
Definition: PermutationMatrix.h:131
Derived & operator=(const PermutationBase< OtherDerived > &other)
Definition: PermutationMatrix.h:74
IndicesType & indices()
Definition: PermutationMatrix.h:121
void setIdentity(Index newSize)
Definition: PermutationMatrix.h:140
PlainPermutationType operator*(const InverseImpl< Other, PermutationStorage > &other) const
Definition: PermutationMatrix.h:227
const IndicesType & indices() const
Definition: PermutationMatrix.h:119
Index rows() const
Definition: PermutationMatrix.h:91
InverseReturnType inverse() const
Definition: PermutationMatrix.h:185
DenseMatrixType toDenseMatrix() const
Definition: PermutationMatrix.h:113
Derived & operator=(const TranspositionsBase< OtherDerived > &tr)
Definition: PermutationMatrix.h:82
PlainPermutationType operator*(const PermutationBase< Other > &other) const
Definition: PermutationMatrix.h:219
Permutation matrix.
Definition: PermutationMatrix.h:298
PermutationMatrix(const TranspositionsBase< Other > &tr)
Definition: PermutationMatrix.h:338
PermutationMatrix(const MatrixBase< Other > &indices)
Definition: PermutationMatrix.h:333
PermutationMatrix(const PermutationBase< OtherDerived > &other)
Definition: PermutationMatrix.h:322
PermutationMatrix & operator=(const PermutationBase< Other > &other)
Definition: PermutationMatrix.h:346
const IndicesType & indices() const
Definition: PermutationMatrix.h:360
IndicesType & indices()
Definition: PermutationMatrix.h:362
PermutationMatrix & operator=(const TranspositionsBase< Other > &tr)
Definition: PermutationMatrix.h:354
PermutationMatrix(Index size)
Definition: PermutationMatrix.h:315
Class to view a vector of integers as a permutation matrix.
Definition: PermutationMatrix.h:487
const internal::remove_all< typenameIndicesType::Nested >::type & indices() const
Definition: PermutationMatrix.h:502
Expression of the product of two arbitrary matrices or vectors.
Definition: Product.h:75
Namespace containing all symbols from the Eigen library.
Definition: Core:141
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
The Index type as used for the API.
Definition: Meta.h:74
const Product< MatrixDerived, PermutationDerived, AliasFreeProduct > operator*(const MatrixBase< MatrixDerived > &matrix, const PermutationBase< PermutationDerived > &permutation)
Definition: PermutationMatrix.h:515
Definition: EigenBase.h:30
Eigen::Index Index
The interface type of indices.
Definition: EigenBase.h:39
Derived & derived()
Definition: EigenBase.h:46
Holds information about the various numeric (i.e. scalar) types allowed by Eigen.
Definition: NumTraits.h:233