Please, help us to better know about our user community by answering the following short survey: https://forms.gle/wpyrxWi18ox9Z5ae9
Eigen  3.3.9
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 
14 namespace Eigen {
15 
16 namespace internal {
17 
18 enum PermPermProduct_t {PermPermProduct};
19 
20 } // end namespace internal
21 
45 template<typename Derived>
46 class PermutationBase : public EigenBase<Derived>
47 {
48  typedef internal::traits<Derived> Traits;
49  typedef EigenBase<Derived> Base;
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 Index rows() const { return Index(indices().size()); }
92 
94  inline Index cols() const { return Index(indices().size()); }
95 
97  inline 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 
131  void setIdentity()
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 
271 namespace internal {
272 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex>
273 struct 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 
296 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex>
297 class 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 
391 namespace internal {
392 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int _PacketAccess>
393 struct 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 
403 template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex, int _PacketAccess>
404 class 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
435 
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 
455 template<typename _IndicesType> class TranspositionsWrapper;
456 namespace internal {
457 template<typename _IndicesType>
458 struct 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 
485 template<typename _IndicesType>
486 class 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 
512 template<typename MatrixDerived, typename PermutationDerived>
513 EIGEN_DEVICE_FUNC
514 const Product<MatrixDerived, PermutationDerived, AliasFreeProduct>
516  const PermutationBase<PermutationDerived>& permutation)
517 {
519  (matrix.derived(), permutation.derived());
520 }
521 
524 template<typename PermutationDerived, typename MatrixDerived>
525 EIGEN_DEVICE_FUNC
526 const Product<PermutationDerived, MatrixDerived, AliasFreeProduct>
528  const MatrixBase<MatrixDerived>& matrix)
529 {
531  (permutation.derived(), matrix.derived());
532 }
533 
534 
535 template<typename PermutationType>
536 class 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 
591 template<typename Derived>
592 const PermutationWrapper<const Derived> MatrixBase<Derived>::asPermutation() const
593 {
594  return derived();
595 }
596 
597 namespace internal {
598 
599 template<> struct AssignmentKind<DenseShape,PermutationShape> { typedef EigenBase2EigenBase Kind; };
600 
601 } // end namespace internal
602 
603 } // end namespace Eigen
604 
605 #endif // EIGEN_PERMUTATIONMATRIX_H
Eigen::Inverse
Expression of the inverse of another expression.
Definition: Inverse.h:44
Eigen
Namespace containing all symbols from the Eigen library.
Definition: Core:309
Eigen::PermutationMatrix::indices
IndicesType & indices()
Definition: PermutationMatrix.h:362
Eigen::EigenBase< Map< PermutationMatrix< SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex >, _PacketAccess > >::Index
Eigen::Index Index
The interface type of indices.
Definition: EigenBase.h:38
Eigen::PermutationMatrix::indices
const IndicesType & indices() const
Definition: PermutationMatrix.h:360
Eigen::PermutationBase::transpose
InverseReturnType transpose() const
Definition: PermutationMatrix.h:191
Eigen::EigenBase
Definition: EigenBase.h:30
Eigen::PermutationMatrix::PermutationMatrix
PermutationMatrix(const TranspositionsBase< Other > &tr)
Definition: PermutationMatrix.h:338
Eigen::DenseCoeffsBase< Derived, DirectWriteAccessors >::derived
Derived & derived()
Definition: EigenBase.h:45
Eigen::PermutationBase::cols
Index cols() const
Definition: PermutationMatrix.h:94
Eigen::PermutationBase::resize
void resize(Index newSize)
Definition: PermutationMatrix.h:125
Eigen::PermutationBase::setIdentity
void setIdentity(Index newSize)
Definition: PermutationMatrix.h:140
Eigen::PermutationBase::rows
Index rows() const
Definition: PermutationMatrix.h:91
Eigen::PermutationBase::operator=
Derived & operator=(const PermutationBase< OtherDerived > &other)
Definition: PermutationMatrix.h:74
Eigen::PermutationBase::applyTranspositionOnTheLeft
Derived & applyTranspositionOnTheLeft(Index i, Index j)
Definition: PermutationMatrix.h:155
Eigen::PermutationBase::size
Index size() const
Definition: PermutationMatrix.h:97
Eigen::PermutationWrapper
Class to view a vector of integers as a permutation matrix.
Definition: PermutationMatrix.h:487
Eigen::PermutationBase::indices
const IndicesType & indices() const
Definition: PermutationMatrix.h:119
Eigen::PermutationMatrix::operator=
PermutationMatrix & operator=(const TranspositionsBase< Other > &tr)
Definition: PermutationMatrix.h:354
Eigen::PermutationBase::operator*
PlainPermutationType operator*(const InverseImpl< Other, PermutationStorage > &other) const
Definition: PermutationMatrix.h:227
Eigen::PlainObjectBase< Matrix< _Scalar, _Rows, _Cols, _Options, _MaxRows, _MaxCols > >::coeffRef
Scalar & coeffRef(Index rowId, Index colId)
Definition: PlainObjectBase.h:183
Eigen::Product
Expression of the product of two arbitrary matrices or vectors.
Definition: Product.h:75
Eigen::PermutationBase::inverse
InverseReturnType inverse() const
Definition: PermutationMatrix.h:185
Eigen::PermutationBase::toDenseMatrix
DenseMatrixType toDenseMatrix() const
Definition: PermutationMatrix.h:113
Eigen::Map::Map
Map(PointerArgType dataPtr, const StrideType &stride=StrideType())
Definition: Map.h:129
Eigen::PermutationBase::determinant
Index determinant() const
Definition: PermutationMatrix.h:242
Eigen::PermutationWrapper::indices
const internal::remove_all< typename IndicesType::Nested >::type & indices() const
Definition: PermutationMatrix.h:502
Eigen::EigenBase::derived
Derived & derived()
Definition: EigenBase.h:45
Eigen::PermutationMatrix::PermutationMatrix
PermutationMatrix(Index size)
Definition: PermutationMatrix.h:315
Eigen::PermutationMatrix::operator=
PermutationMatrix & operator=(const PermutationBase< Other > &other)
Definition: PermutationMatrix.h:346
Eigen::PermutationBase
Base class for permutations.
Definition: PermutationMatrix.h:47
Eigen::PermutationBase::operator*
PlainPermutationType operator*(const PermutationBase< Other > &other) const
Definition: PermutationMatrix.h:219
Eigen::PermutationBase::operator*
friend PlainPermutationType operator*(const InverseImpl< Other, PermutationStorage > &other, const PermutationBase &perm)
Definition: PermutationMatrix.h:235
Eigen::PermutationMatrix
Permutation matrix.
Definition: PermutationMatrix.h:298
Eigen::DenseCoeffsBase< Derived, WriteAccessors >::coeffRef
Scalar & coeffRef(Index row, Index col)
Definition: DenseCoeffsBase.h:340
Eigen::Matrix
The matrix class, also used for vectors and row-vectors.
Definition: Matrix.h:180
Eigen::PermutationBase::applyTranspositionOnTheRight
Derived & applyTranspositionOnTheRight(Index i, Index j)
Definition: PermutationMatrix.h:174
Eigen::MatrixBase
Base class for all dense matrices, vectors, and expressions.
Definition: MatrixBase.h:50
Eigen::PermutationBase::indices
IndicesType & indices()
Definition: PermutationMatrix.h:121
Eigen::operator*
const Product< MatrixDerived, PermutationDerived, AliasFreeProduct > operator*(const MatrixBase< MatrixDerived > &matrix, const PermutationBase< PermutationDerived > &permutation)
Definition: PermutationMatrix.h:515
Eigen::DenseBase::setZero
Derived & setZero()
Definition: CwiseNullaryOp.h:499
Eigen::PermutationBase::setIdentity
void setIdentity()
Definition: PermutationMatrix.h:131
Eigen::NumTraits
Holds information about the various numeric (i.e. scalar) types allowed by Eigen.
Definition: NumTraits.h:151
Eigen::PermutationMatrix::PermutationMatrix
PermutationMatrix(const MatrixBase< Other > &indices)
Definition: PermutationMatrix.h:333
Eigen::PermutationBase::operator=
Derived & operator=(const TranspositionsBase< OtherDerived > &tr)
Definition: PermutationMatrix.h:82
Eigen::DenseBase::fill
void fill(const Scalar &value)
Definition: CwiseNullaryOp.h:315
Eigen::PermutationMatrix::PermutationMatrix
PermutationMatrix(const PermutationBase< OtherDerived > &other)
Definition: PermutationMatrix.h:322
Eigen::Index
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
The Index type as used for the API.
Definition: Meta.h:33