<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Mar 25, 2014 at 6:42 AM, Søren Højsgaard <span dir="ltr"><<a href="mailto:sorenh@math.aau.dk" target="_blank">sorenh@math.aau.dk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear all,<br>
I have a large sparse adjacency matrix X for an undirected graph. For a subset 'idx' of the vertices I want to find out if the subgraph defined by this subset is complete (i.e. has edges between all variables). So in R, one would check if X[idx,idx] has only ones outside the diagonal, but this is slow and I want to do it with Rcpp. Here is one attempt where I simply add up the elements above (or below) the diagonal, and to access the elements of X I use coeff which is relatively slow (because X is a sparse matrix).<br>

<br>
#include <RcppEigen.h><br>
typedef Eigen::MappedSparseMatrix<double> MSpMat;<br>
typedef Eigen::SparseVector<double> SpVec;<br>
typedef SpVec::InnerIterator InIter;<br>
<br>
//[[Rcpp::export]]<br>
double foo (MSpMat X, Eigen::VectorXi idx){<br>
  SpVec sidx = idx.sparseView();<br>
  double out=0;<br>
  int i2, j2;<br>
  for (InIter i_(sidx); i_; ++i_){<br>
    i2 = i_.index();<br>
    for (InIter j_(sidx); j_; ++j_){<br>
      j2 = j_.index();<br>
      if (i2>j2)<br>
        out += X.coeff( i2, j2);<br>
    }<br>
  }<br>
  return out;<br>
}<br>
<br>
/*** R<br>
library(Matrix)<br>
M1 <- new("dgCMatrix"<br>
    , i = c(1L, 2L, 3L, 0L, 2L, 3L, 0L, 1L, 3L, 0L, 1L, 2L, 4L, 5L, 3L, 5L, 3L, 4L)<br>
    , p = c(0L, 3L, 6L, 9L, 14L, 16L, 18L)<br>
    , Dim = c(6L, 6L)<br>
    , Dimnames = list(c("a", "b", "c", "d", "e", "f"), c("a", "b", "c", "d", "e", "f"))<br>
    , x = c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)<br>
    , factors = list()<br>
)<br>
M1<br>
<br>
foo(M1, c(2,3,4))<br>
<br>
*/<br>
Can anyone see a better way of doing this?<br>
<br>
I was thinking about whether the sparse matrix iterators could be a solution, but I can't a hold on it. </blockquote><div><br></div><div>Sparse matrix inner and outer iterators are definitely the way to go.  I'll write a version using them.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I was also thinking about using sparse matrices in RcppArmadillo, but I guess the problem (speed) is the same (haven't tried!).<br>
</blockquote><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Any advice will be greatly appreciated.<br>
Cheers<br>
Søren<br>
<br>
<br>
<br>
_______________________________________________<br>
Rcpp-devel mailing list<br>
<a href="mailto:Rcpp-devel@lists.r-forge.r-project.org">Rcpp-devel@lists.r-forge.r-project.org</a><br>
<a href="https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/rcpp-devel" target="_blank">https://lists.r-forge.r-project.org/cgi-bin/mailman/listinfo/rcpp-devel</a><br>
<br>
</blockquote></div></div></div>