Eigen - Sort matrix diagonal

Question

What I have is diagonal matrix of type Eigen::MatrixXi. I need elements on the diagonal to be sorted in ascending order. For example like this:

2 0 0      1 0 0
0 7 0  >>> 0 2 0
0 0 1      0 0 7

I thought I would simply do:

std::sort(matrix.diagonal().begin(), matrix.diagonal().end());

But apparently Eigen::Diagonal does not have begin nor end function. So the question is, is there any way of sorting elements on diagonal using internal std::sort or anything similarly elegant?

I went through official documentation but did not find anything useful.

Metencephalon

it looks that there is no such function eigen.tuxfamily.org/bz/show_bug.cgi?id=299 maybe your best bet woul be to create you own algorithm. – Phira

you can extract the diagonal to new array sort it then re-copy it to the matrix, or you can create new function to sort array its elements array[i][i] { elements on the diagonal } . – Glomma

You could create an iterator that traverses only diagonal elements, and define your own free functions diagonal_iterator begin(Eigen::Diagonal& d) and diagonal_iterator end(Eigen::Diagonal& d). Then call std::sort(begin(matrix.diagonal()), end(matrix.diagonal()) – Biauriculate

If you extend this to an full answer, I will accept it since this seems to be most elegant solution. I have already written sort algorithm that works directly with original matrix, but iterator would be much cleaner solution. – Metencephalon

Answer 1

There is no native support for sorting matrices as of today. There are two long-pending feature requests relevant to this functionality:

• Bug 231 - STL compatible iterators
• Bug 299 - Sort function for matrices and vectors returning indices as well

As suggested by @NicolasM in the comments, currently, the most elegant solution is to provide custom iterators yourself, e.g.:

namespace Eigen {
  template<typename Scalar>
  class iterator {
    Scalar* ptr;
    int stride;
  public: 
    iterator(Scalar* ptr_, int stride_) : ptr(ptr_), stride(stride_) {}
    Scalar& operator*() const { return *ptr;}
    iterator& operator++() { ptr += stride; return *this;}
    bool operator<(const iterator& other) { return ptr < other.ptr; }
    // implement further operations, required for random access iterators ...
  }

  template<class Derived>
  iterator begin(MatrixBase<Derived>&& mat)
  { return iterator(mat.data(), mat.innerStride()); }
  template<class Derivde>
  iterator end(MatrixBase<Derived>&& mat)
  { return iterator(mat.data() + mat.size()*mat.innerStride(), mat.innerStride()); }

} // namespace Eigen

Darnley

Answer 2

What I tried to say is something like this.

void insertion_sort(int arr[3][3], int length) {

int i, j, tmp;
for (i = 1; i < length; i++) {
    j = i;
    while (j > 0 && arr[j - 1][j- 1] > arr[j][j]) {
        tmp = arr[j][j];
        arr[j][j] = arr[j - 1][j - 1];
        arr[j - 1][j - 1] = tmp;
        j--;
    }       
}
}

int main() {    

int a[3][3] = { { 2, 0, 0 }, { 0, 7, 0 }, { 0, 0, 1 } };
insertion_sort(a, 3);

for (int i = 0; i < 3; ++i)
{
    for (int j = 0; j < 3; ++j)
        cout << a[i][j] << " ";
    cout << endl;
}

I used insertion sort because it's easy to implement.

Glomma