Looping over the non-zero elements of a uBlas sparse matrix.

Question

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.

Answer 1

I scanned through the uBLAS library (interesting stuff btw), and it doesn't seem like they have something for that. Might I suggest using a different or parallel data structure? Your implementation will depend mostly on what usage you make of a sparse matrix. Looping through it O(N^2) style is not what a sparse matrix is meant for in the first place (unless you can access the underlying structure which, in the case of uBLAS, doesn't seem possible), you might as well use a chained list or plain array of small structs like so:

struct sparseMatrixElement {
   int value;
   int row;
   int col;
};

Answer 2

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 << "(" << i2.index1() << "," << i2.index2() << ") = ";
    std::cout << *it2 << std::endl;
  }
}