7

I have the following sparse matrix that contains O(N) elements

boost::numeric::ublas::compressed_matrix<int> adjacency (N, N);

I could write a brute force double loop to go over all the entries in O(N^2) time like below, but this is going to be too slow. 

for(int i=0; i<N; ++i)
   for(int j=0; j<N; ++j)
       std::cout << adjacency(i,j) std::endl;

How can I loop over only the non-zero entries in O(N) time? For each non-zero element I would like to have access to its value, and the indexes i,j.

D R
  • 21,936
  • 38
  • 112
  • 149

1 Answers1

16

You can find the answer in this FAQ: How to iterate over all non zero elements?

In your case it would be:

typedef boost::numeric::ublas::compressed_matrix<int>::iterator1 it1_t;
typedef boost::numeric::ublas::compressed_matrix<int>::iterator2 it2_t;

for (it1_t it1 = adjacency.begin1(); it1 != adjacency.end1(); it1++)
{
  for (it2_t it2 = it1.begin(); it2 != it1.end(); it2++)
  {
    std::cout << "(" << it2.index1() << "," << it2.index2() << ") = ";
    std::cout << *it2 << std::endl;
  }
}
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
Gert
  • 363
  • 2
  • 7
  • Important note which I forgot to add: the type of storage organization you choose for a compressed matrix matters, because it decides what the fastest way of iterating the compressed matrix will be. If you have row_major as storage type, my example above is the fastest way to iterate. If you choose column_major, you will have to exchange the inner and outer loop, i.e. looping over the columns first will be the fastest. – Gert Dec 07 '09 at 10:18
  • boost will iterate depending on the storage representation (row-major or col-major). So the same loops above will work for either representation. No changes need to be made. – user236215 Sep 20 '10 at 10:43
  • 2
    Sorry for bumping an old post. I'm not sure this code actually works see http://lists.boost.org/MailArchives/ublas/2006/11/1516.php. From my experience it will iterate over every element. – Mikhail Jul 07 '11 at 07:56