CODEWITHSUNDEEP
c++sortingmatrix
user1420
user1420

Reputation: 143

Sort Eigen matrix column values by ascending order of column 1 values

I have a n x 3 matrix in Eigen. I would like to rearrange the values of the 2nd and 3rd columns by sorting the values in the 1st column in ascending order. E.g before sorting:

  1  4  6
 -2  5  2
  3  1  0

After sorting according to ascending order of column 1 values:

 -2 5 2
  1 4 6
  3 1 0

I am at a loss at how to approach this. I could read each column into a vector and sort the column 1 vector using std::sort but I fail to see how I can retain the corresponding values in columns 2 and 3 for the sorted values in column 1. The value of n is known and is fixed, if that helps in any way.

Upvotes: 7

Views: 9580

Answers (5)

chtz
chtz

Reputation: 18807

With Eigen 3.4 and C++14 (or later), you can directly use the iterator interface of Eigen. Unfortunately it is missing a forward of the swap functionality, so write this once:

#include <Eigen/Core>

namespace Eigen {
    template<class T>
    void swap(T&& a, T&& b){
        a.swap(b);
    }
}

But afterwards, you can directly write this one-liner:

std::sort(A.rowwise().begin(), A.rowwise().end(),
     [](auto const& r1, auto const& r2){return r1(0)<r2(0);});

Working example on godbolt: https://godbolt.org/z/h9nEGvz4e

Upvotes: 2

telmozufi
telmozufi

Reputation: 11

I've implemented this function, you'll need:

#include <Eigen/Dense>
#include <Eigen/Core>

The function is:

Eigen::MatrixXd sortMatrix(const Eigen::MatrixXd &original_matrix) {

  Eigen::MatrixXd sorted_matrix(original_matrix.rows(), original_matrix.cols());
  Eigen::VectorXd sorted_rows = original_matrix.col(0);
  Eigen::VectorXd::Index min_row;

  for ( int i = 0; i < original_matrix.rows(); i++) {
    sorted_rows.minCoeff(&min_row);
    sorted_matrix.row(i) = original_matrix.row(min_row);
    sorted_rows(min_row) = std::numeric_limits<double>::max();
  }

   return sorted_matrix;
}

The function creates a copy of the first column of the matrix to be sorted in a new vector. It copies the minimum value in another matrix. Once copied, that value is destroyed (maximum value assigned in the vector, so that it isn't recognized again as a minimum), so it will keep on finding and ordering minimum values until all the auxiliar vector is empty of original values and the new matrix is ordered. If there are two exact same values theres no warranty that second column will be ordered, it just focuses on the first one. It is an O(n^2) algortihm so it becomes less efficient as the matrix size grows. Some information about the used commands:

Block operations in Eigen ( col(), row() )

Matrix and vector arithmetic in Eigen, ( minCoeff() )

Upvotes: 1

xjcl
xjcl

Reputation: 15309

The best solution I came up with was to copy the rows into a std::vector and then go on to sort that:

#include <Eigen/Core>
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool compare_head(const Eigen::VectorXd& lhs, const Eigen::VectorXd& rhs)
{
    return lhs(0) < rhs(0);
}

Eigen::MatrixXd sorted_rows_by_head(Eigen::MatrixXd A)
{
    std::vector<Eigen::VectorXd> vec;
    for (int64_t i = 0; i < A.rows(); ++i)
        vec.push_back(A.row(i));

    std::sort(vec.begin(), vec.end(), &compare_head);

    for (int64_t i = 0; i < A.rows(); ++i)
        A.row(i) = vec[i];

    return A;
}

Upvotes: 2

Frederik
Frederik

Reputation: 385

Based on the second Option by xjcl, I created a lambda based option that can easily be included in a header file:

#include <Eigen>
#include <algorithm>
#include <vector>

void eigen_sort_rows_by_head(Eigen::MatrixXd& A_nx3)
{
    std::vector<Eigen::VectorXd> vec;
    for (int64_t i = 0; i < A_nx3.rows(); ++i)
        vec.push_back(A_nx3.row(i));

    std::sort(vec.begin(), vec.end(), [](Eigen::VectorXd const& t1, Eigen::VectorXd const& t2){ return t1(0) < t2(0); } );

    for (int64_t i = 0; i < A_nx3.rows(); ++i)
        A_nx3.row(i) = vec[i];
};

This option also takes the target matrix by reference. How ever, I guess it can be improved and I hope for help:

  • Make it in place (using Eigen SWAP)
  • Allow to specify a variable number of columns ( 0 to n ) that shall be used in the comparison in given order. Remaining columns are used in lexicographic order to break ties.
  • Allow to pass (optional) a function / PRNG to break ties, if any remain.

Furthermore, could we not use auto for automatic template deduction despite the warnings in Eigen?

Upvotes: 2

Sebastian Lenartowicz
Sebastian Lenartowicz

Reputation: 4864

This isn't pretty, and relies on picking apart the matrix using its template parameters - but it works.

#include <Eigen/Core>
#include <algorithm>
#include <vector>

// Simple little templated comparison functor
template <typename MatrixT>
bool compareRows(MatrixT a, MatrixT b) {
    return a(0,0) < b(0,0);
}

// These are the 6 template arguments to every Eigen matrix
template <typename Scalar, int rows, int cols, int options, int maxRows, int maxCols> 
Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> sortMatrix(
    Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> target
) {
    // Manually construct a vector of correctly-typed matrix rows
    std::vector<Eigen::Matrix<Scalar, 1, cols>> matrixRows;
    for (unsigned int i = 0; i < target.rows(); i++) 
            matrixRows.push_back(target.row(i));
    std::sort(
            matrixRows.begin(),
            matrixRows.end(),
            compareRows<Eigen::Matrix<Scalar, 1, cols>>
    );

    Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> sorted;
    for (unsigned int i = 0; i < matrixRows.size(); i++)
            sorted.row(i) = matrixRows[i];
    return sorted;
}

Thankfully, due to template argument deduction, you can simply call this mess like this:

Eigen::Matrix3f myMatrix;
// Fill in contents here
Eigen::Matrix3f sorted = sortMatrix(myMatrix);

I'm almost positive there's a more elegant way to do this, but I can't think of it right now. And, because it uses std::vector, you'll need to compile with -std=c++11 or better.

Upvotes: 1

Related Questions