// This file is part of Eigen, a lightweight C++ template library // for linear algebra. // // Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com> // Copyright (C) 2009-2015 Gael Guennebaud <gael.guennebaud@inria.fr> // // This Source Code Form is subject to the terms of the Mozilla // Public License v. 2.0. If a copy of the MPL was not distributed // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
/** \class PermutationBase * \ingroup Core_Module * * \brief Base class for permutations * * \tparam Derived the derived class * * This class is the base class for all expressions representing a permutation matrix, * internally stored as a vector of integers. * The convention followed here is that if \f$ \sigma \f$ is a permutation, the corresponding permutation matrix * \f$ P_\sigma \f$ is such that if \f$ (e_1,\ldots,e_p) \f$ is the canonical basis, we have: * \f[ P_\sigma(e_i) = e_{\sigma(i)}. \f] * This convention ensures that for any two permutations \f$ \sigma, \tau \f$, we have: * \f[ P_{\sigma\circ\tau} = P_\sigma P_\tau. \f] * * Permutation matrices are square and invertible. * * Notice that in addition to the member functions and operators listed here, there also are non-member * operator* to multiply any kind of permutation object with any kind of matrix expression (MatrixBase) * on either side. * * \sa class PermutationMatrix, class PermutationWrapper
*/ template<typename Derived> class PermutationBase : public EigenBase<Derived>
{ typedef internal::traits<Derived> Traits; typedef EigenBase<Derived> Base; public:
/** \returns the number of rows */ inline EIGEN_DEVICE_FUNC Index rows() const { return Index(indices().size()); }
/** \returns the number of columns */ inline EIGEN_DEVICE_FUNC Index cols() const { return Index(indices().size()); }
/** \returns the size of a side of the respective square matrix, i.e., the number of indices */ inline EIGEN_DEVICE_FUNC Index size() const { return Index(indices().size()); }
/** \returns a Matrix object initialized from this permutation matrix. Notice that it * is inefficient to return this Matrix object by value. For efficiency, favor using * the Matrix constructor taking EigenBase objects.
*/
DenseMatrixType toDenseMatrix() const
{ return derived();
}
/** const version of indices(). */ const IndicesType& indices() const { return derived().indices(); } /** \returns a reference to the stored array representing the permutation. */
IndicesType& indices() { return derived().indices(); }
/** Resizes to given size.
*/ inlinevoid resize(Index newSize)
{
indices().resize(newSize);
}
/** Sets *this to be the identity permutation matrix */ void setIdentity()
{
StorageIndex n = StorageIndex(size()); for(StorageIndex i = 0; i < n; ++i)
indices().coeffRef(i) = i;
}
/** Sets *this to be the identity permutation matrix of given size.
*/ void setIdentity(Index newSize)
{
resize(newSize);
setIdentity();
}
/** Multiplies *this by the transposition \f$(ij)\f$ on the left. * * \returns a reference to *this. * * \warning This is much slower than applyTranspositionOnTheRight(Index,Index): * this has linear complexity and requires a lot of branching. * * \sa applyTranspositionOnTheRight(Index,Index)
*/
Derived& applyTranspositionOnTheLeft(Index i, Index j)
{
eigen_assert(i>=0 && j>=0 && i<size() && j<size()); for(Index k = 0; k < size(); ++k)
{ if(indices().coeff(k) == i) indices().coeffRef(k) = StorageIndex(j); elseif(indices().coeff(k) == j) indices().coeffRef(k) = StorageIndex(i);
} return derived();
}
/** Multiplies *this by the transposition \f$(ij)\f$ on the right. * * \returns a reference to *this. * * This is a fast operation, it only consists in swapping two indices. * * \sa applyTranspositionOnTheLeft(Index,Index)
*/
Derived& applyTranspositionOnTheRight(Index i, Index j)
{
eigen_assert(i>=0 && j>=0 && i<size() && j<size());
std::swap(indices().coeffRef(i), indices().coeffRef(j)); return derived();
}
/** \returns the product of a permutation with another inverse permutation. * * \note \blank \note_try_to_help_rvo
*/ template<typename Other> inline PlainPermutationType operator*(const InverseImpl<Other,PermutationStorage>& ;other) const
{ return PlainPermutationType(internal::PermPermProduct, *this, other.eval()); }
/** \returns the product of an inverse permutation with another permutation. * * \note \blank \note_try_to_help_rvo
*/ template<typename Other> friend inline PlainPermutationType operator*(const InverseImpl<Other, PermutationStorage>& ;other, const PermutationBase& perm)
{ return PlainPermutationType(internal::PermPermProduct, other.eval(), perm); }
/** \returns the determinant of the permutation matrix, which is either 1 or -1 depending on the parity of the permutation. * * This function is O(\c n) procedure allocating a buffer of \c n booleans.
*/
Index determinant() const
{
Index res = 1;
Index n = size();
Matrix<bool,RowsAtCompileTime,1,0,MaxRowsAtCompileTime> mask(n);
mask.fill(false);
Index r = 0; while(r < n)
{ // search for the next seed while(r<n && mask[r]) r++; if(r>=n) break; // we got one, let's follow it until we are back to the seed
Index k0 = r++;
mask.coeffRef(k0) = true; for(Index k=indices().coeff(k0); k!=k0; k=indices().coeff(k))
{
mask.coeffRef(k) = true;
res = -res;
}
} return res;
}
/** \class PermutationMatrix * \ingroup Core_Module * * \brief Permutation matrix * * \tparam SizeAtCompileTime the number of rows/cols, or Dynamic * \tparam MaxSizeAtCompileTime the maximum number of rows/cols, or Dynamic. This optional parameter defaults to SizeAtCompileTime. Most of the time, you should not have to specify it. * \tparam _StorageIndex the integer type of the indices * * This class represents a permutation matrix, internally stored as a vector of integers. * * \sa class PermutationBase, class PermutationWrapper, class DiagonalMatrix
*/ template<int SizeAtCompileTime, int MaxSizeAtCompileTime, typename _StorageIndex> class PermutationMatrix : public PermutationBase<PermutationMatrix<SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex> >
{ typedef PermutationBase<PermutationMatrix> Base; typedef internal::traits<PermutationMatrix> Traits; public:
/** Generic constructor from expression of the indices. The indices * array has the meaning that the permutations sends each integer i to indices[i]. * * \warning It is your responsibility to check that the indices array that you passes actually * describes a permutation, i.e., each value between 0 and n-1 occurs exactly once, where n is the * array's size.
*/ template<typename Other> explicitinline PermutationMatrix(const MatrixBase<Other>& indices) : m_indices(indices)
{}
/** Convert the Transpositions \a tr to a permutation matrix */ template<typename Other> explicit PermutationMatrix(const TranspositionsBase<Other>& tr)
: m_indices(tr.size())
{
*this = tr;
}
/** Copies the other permutation into *this */ template<typename Other>
PermutationMatrix& operator=(const PermutationBase<Other>& other)
{
m_indices = other.indices(); return *this;
}
/** Assignment from the Transpositions \a tr */ template<typename Other>
PermutationMatrix& operator=(const TranspositionsBase<Other>& tr)
{ return Base::operator=(tr.derived());
}
/** const version of indices(). */ const IndicesType& indices() const { return m_indices; } /** \returns a reference to the stored array representing the permutation. */
IndicesType& indices() { return m_indices; }
/**** multiplication helpers to hopefully get RVO ****/
inline Map(const StorageIndex* indicesPtr, Index size)
: m_indices(indicesPtr,size)
{}
/** Copies the other permutation into *this */ template<typename Other>
Map& operator=(const PermutationBase<Other>& other)
{ return Base::operator=(other.derived()); }
/** Assignment from the Transpositions \a tr */ template<typename Other>
Map& operator=(const TranspositionsBase<Other>& tr)
{ return Base::operator=(tr.derived()); }
#ifndef EIGEN_PARSED_BY_DOXYGEN /** This is a special case of the templated operator=. Its purpose is to * prevent a default operator= from hiding the templated operator=.
*/
Map& operator=(const Map& other)
{
m_indices = other.m_indices; return *this;
} #endif
/** const version of indices(). */ const IndicesType& indices() const { return m_indices; } /** \returns a reference to the stored array representing the permutation. */
IndicesType& indices() { return m_indices; }
/** \class PermutationWrapper * \ingroup Core_Module * * \brief Class to view a vector of integers as a permutation matrix * * \tparam _IndicesType the type of the vector of integer (can be any compatible expression) * * This class allows to view any vector expression of integers as a permutation matrix. * * \sa class PermutationBase, class PermutationMatrix
*/ template<typename _IndicesType> class PermutationWrapper : public PermutationBase<PermutationWrapper<_IndicesType> >
{ typedef PermutationBase<PermutationWrapper> Base; typedef internal::traits<PermutationWrapper> Traits; public:
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
