Boost library: sort a matrix by a column

[pm44xl22]

Hi all, don't know whether this is the right section but I have a big problem:

I am using boost C++ libraries to work with matrix data... I now need to sort a matrix by the data in a column

For example:

1 3
0 2

sorting increasingly by the second column:

0 2
1 3



std::sort can not do the job because it would sort ALL the matrix elements.. how can I solve this?

Please help

[Lindley]

First, define a vector<int> which is as large as the number of rows, and populate it with the values 0...r-1. You can use Boost.Assign to do this, or just use a loop.

Next, define a comparator something like this:

struct CompareColumn
{
    const matrix *mat;
    int colnum;
    CompareColumn(const matrix &m, int keycol)
        : mat(&m), colnum(keycol)
    {}
    bool operator()(const int &lhs, const int &rhs) const
    {    return (*mat)[lhs][colnum] < (*mat)[rhs][colnum];   }
};

If you're using one of the newest generation of compilers, you could write this as a lambda expression instead.

Third, use std::sort() with this comparator to sort the index vector.

Fourth, use the index vector to rearrange the rows in the matrix (this may require copying values to a second matrix).

[pm44xl22]

Uhm, what do you mean with the fourth step?

I have in the end a sorted vector (which is the key column of my matrix sorted) and the matrix, how to combine the two things?

[pm44xl22]

Maybe I got it... a cycle where I am going to do something like

for(int i=0;i<rows_number;i++)
for(int q=0; q<columns_number;q++)
sorted_matrix.insert_element(i, q, unsorted_matrix[index_vector[i]][q]);


right?

[Lindley]

Well, here's a simple example using strings....you can generalize it to your case.

string s = "Hello, world!";// 13 characters, indexes 0..12 are valid
vector<int> inds = boost::list_of(0,2,4,6,8,10,12,1,3,5,7,9,11};
string s2(s.size());
for (unsigned i = 0; i < inds.size(); i++)
    s2[i] = s[inds[i]];
cout << s2;// Output will be "Hlo ol!el,wrd"

EDIT: The above is moving in the right direction. If the interface allows it, you'll find it much more efficient to copy entire rows at a time (assuming the matrix is stored row-contiguous).

[pm44xl22]

Is it possible with boost library to swap two rows of a matrix? (copy a row at a time)

I searched the documentation but found nothing

[Lindley]

I don't know which boost library you're specifically referring to. multi_array? uBLAS? Is there another one?

[pm44xl22]

I am currently using uBLAS (i suppose.. the namespace has that name).

matrix <double> m_name;

Swapping rows would be a great success

[Lindley]

Okay, uBLAS matrices are row-major by default. That means, if nothing else, that you can default to memcpy() safely if you want. For instance:

matrix<double> m1(4,5);
matrix<double> m2(4,5);
memcpy(&m2(1,0),&m1(3,0),5*sizeof(double));

The idea being that if you take the address of the first element in any row, then the next cols*sizeof(type) bytes will be the elements of that row.

This isn't ideal. memcpy() should be combined with C++ only with care. However, it should work in this case.

[pm44xl22]

Sounds dangerous to me but if there is not another solution, that should do the trick

[Lindley]

There might be a safer way. The uBLAS documentation isn't too specific on the type returned by begin1() and end1(). If that type is a proxy object for a row, and if it's assignable, then you could use boost:ermutation_iterator to do it:

matrix<double> srcmat(4,7), dstmat(4, 7);
vector<int> indicies;// fill + sort this as described

typedef boost::permutation_iterator< matrix<double>::iterator1, std::vector<int>::iterator > permutation_type;
permutation_type it = make_permutation_iterator( srcmat.begin1(), indices.begin() );
permutation_type it_end = make_permutation_iterator( srcmat.begin1(), indices.end() );

std::copy(it, it_end, dstmat.begin1());

Not positive that will work though.

[pm44xl22]

I'll give it a try, thank you so much for helping me!