CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12
  1. #1
    Join Date
    May 2010
    Posts
    33

    Boost library: sort a matrix by a column

    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

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Boost library: sort a matrix by a column

    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:
    Code:
    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).

  3. #3
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

    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?

  4. #4
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

    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?

  5. #5
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Boost library: sort a matrix by a column

    Well, here's a simple example using strings....you can generalize it to your case.
    Code:
    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).

  6. #6
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

    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

  7. #7
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Boost library: sort a matrix by a column

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

  8. #8
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

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

    matrix <double> m_name;

    Swapping rows would be a great success

  9. #9
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Boost library: sort a matrix by a column

    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:
    Code:
    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.

  10. #10
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

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

  11. #11
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Boost library: sort a matrix by a column

    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:
    Code:
    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.

  12. #12
    Join Date
    May 2010
    Posts
    33

    Re: Boost library: sort a matrix by a column

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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured