New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 1104 - Add ability to iterate (non-nested) over values in sparse matrix
Summary: Add ability to iterate (non-nested) over values in sparse matrix
Status: DECISIONNEEDED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Sparse (show other bugs)
Version: 3.4 (development)
Hardware: All All
: Normal Feature Request
Assignee: Nobody
URL:
Whiteboard:
Keywords:
: 1165 (view as bug list)
Depends on: 1271 231
Blocks: 1179 3.x
  Show dependency treegraph
 
Reported: 2015-11-04 15:48 UTC by Matthew Woehlke
Modified: 2019-02-18 15:55 UTC (History)
3 users (show)



Attachments

Description Matthew Woehlke 2015-11-04 15:48:41 UTC
In modern C++, especially with range-based for, and considering that SparseMatrix::InnerIterator knows the row and column, it would be useful to have an iterator that allowed visiting every non-zero cell without a nested loop. For example:

  for (auto iter : /*adapt*/(sparse_matrix))
  {
    static_assert(decltype(iter) == decltype(sparse_matrix)::InnerIterator);
    // do stuff with iter
  }

It's debatable if direct iteration should be permitted (and whether such should include zero cells also), or if construction of an adaptor would be required (different adaptors could provide sparse or dense iteration).
Comment 1 Gael Guennebaud 2015-11-04 17:16:37 UTC
One might also expect to iterate over the columns or rows... see bug 231.

A related idea would be to add a read/write linear view to the list of non-zero coefficients. Might be useful to do our own cooking, and explicitly iterate over all non zero coefficients. E.g.:

  mat.nonZerosView() += 1;

  for(auto iter : mat.nonZerosView()) { ... }
Comment 2 Matthew Woehlke 2015-11-09 20:57:58 UTC
> One might also expect to iterate over the columns or rows

Yes, that's what I meant by "It's debatable if direct iteration should be permitted". Indirect iteration, such as calling a helper function that returns a suitable adaptor, or having a member that does so (as in your suggestion), may indeed be preferable. (Note that by "adaptor" I mean something with begin() and end() that return suitable iterators; it needn't do more than that. That may be what you mean by "view", or you may imply additional functionality. I have no objection to additional functionality, but I'd be happy with or without such.)
Comment 3 Matthew Woehlke 2016-04-05 17:52:10 UTC
FYI: We have implemented such an adaptor: https://github.com/Kitware/vital/blob/master/vital/util/enumerate_matrix.h

IIUC, this will naïvely iterate over the outer and inner indices without regard to whether that is row-major or column-major. That seems likely to be more efficient and is probably sufficient for many use cases. This could be provided for either "direct" or "indirect" iteration (see previous comments for explanation). Neither option would block providing other adaptors that ensure row-major or column-major iteration via an "indirect" method.
Comment 4 Matthew Woehlke 2016-04-05 17:54:30 UTC
*** Bug 1165 has been marked as a duplicate of this bug. ***
Comment 5 Gael Guennebaud 2016-08-30 07:40:23 UTC
See also bug 1271. In compressed mode you can now do:

SparseMatrix<double> A;

std::vector<double> vec(A.coeffs().data(), A.coeffs().data()+A.nonZeros());
Comment 6 Christoph Hertzberg 2016-08-30 16:09:40 UTC
(In reply to Gael Guennebaud from comment #5)
> std::vector<double> vec(A.coeffs().data(), A.coeffs().data()+A.nonZeros());

This was actually already possible with A.valuePtr() instead of A.coeffs().data()

As I wrote in Bug 1165 comment 1, I think a full-functional Sparse iterator should support accessing row() and col() as well. I.e., (*it) should be API compatible to Eigen::Triplet.
Comment 7 citibeth 2016-12-01 15:01:51 UTC
> I.e., (*it) should be API compatible to Eigen::Triplet.

I absolutely agree.
Comment 8 Gael Guennebaud 2019-02-18 15:55:01 UTC
Some updates:

- meanwhile, we've implemented STL iterators for dense matrices, see:
  https://eigen.tuxfamily.org/dox-devel/group__TutorialSTL.html

 To iterate over all entries of a 2D matrix, you need to reshape:
 
  for(auto x : A.reshaped())
   cout << x << " ";

- This also means you can already do:

  for(auto& x : sparse_mat.coeffs()) { x = ...; }

- If you need row/column indices, then, to be consistent we probably want something like:

  for(auto& t : sparse_mat.triplets()) {
     t.row(); // read-only
     t.col(); // read-only
     t.value(); // read-write because we used auto&
  }


Some comments on Matthew's implementation:

- the new link is: https://github.com/Kitware/kwiver/blob/master/vital/util/enumerate_matrix.h

- I don't think iterator should dereference to InnerIterator because InnerIterator also exposes operator++ and other stuff you want.

- It should more likely dereference to a Triplet (or some variant to support writable value).

- This implementation allocate an InnerIterator on the heap -> this should be avoid by using placement new (or by not relying on InnerIterator, which is not harder if we want to support compressed-storage only, and not arbitrary expression)

- If relying on InnerIterator, then no need to store m_outer, InnerIterator already has it.

Note You need to log in before you can comment on or make changes to this bug.