Søren Højsgaard and Doug Bates — written Apr 1, 2014 — source

Consider the following vector:

A sparse representation of this vector will tell that at entries 1,3,5 (or at entries 0,2,4 if we are 0-based) we will find the values 2,4,7.

Using Eigen via
RcppEigen we
can obtain the coercion with `.sparseView()`

.
We can iterate over all elements (including the zeros) in a sparse
vector as follows:

Standard looping over a sparse vector i=0 value=2 i=1 value=0 i=2 value=4 i=3 value=0 i=4 value=7

To iterate only over the non-zero elements we can do:

Looping over a sparse vector using iterators i=0 value=2 i=2 value=4 i=4 value=7

6 x 6 sparse Matrix of class "dgCMatrix" a b c d e f a . 4 2 5 . . b 1 . 3 1 . . c 2 5 . 2 . . d 3 1 4 . 5 2 e . . . 3 . 3 f . . . 4 1 .

To iterate over all values in a column of this matrix we can do:

Standard looping over a sparse matrix i,j=0,1 value=4 i,j=1,1 value=0 i,j=2,1 value=5 i,j=3,1 value=1 i,j=4,1 value=0 i,j=5,1 value=0

To iterate over only the non-zero elements in a column we can do:

Standard looping over a sparse matrix i,j=0,2 value=2 i,j=1,2 value=3 i,j=3,2 value=4

A graph with nodes V={1,2,…n} can be reprsented by an adjacency matrix, say A, with the following semantics: A is n x n. The entry A(i,j) is non-zero if and only if there is an edge from node i to node j. If also A(j,i) is non-zero then the edge between i and j is undirected. Hence if A is symmetric then all edges are undirected, and the corresponding graph is undirected. In the following we focus on undirected graphs. If there is an edge between i and j we say that i and j are neighbours. A subset U of the nodes is complete if all pairs of nodes in U are neighbours. Here we shall implement a function which for a sparse matrix representation of and undirected graph will determine if a given set of nodes is complete.

6 x 6 sparse Matrix of class "dgCMatrix" a b c d e f a . 1 1 1 . . b 1 . 1 1 . . c 1 1 . 1 . . d 1 1 1 . 1 1 e . . . 1 . 1 f . . . 1 1 .

Define two subsets of nodes

With an extensive use of sparse matrix and vector iterators we can solve the task as follows:

[1] TRUE FALSE

For comparison we implement the same function using the .coeff() method for looking up values in the adjacency matrix directly:

[1] TRUE FALSE

NOTICE: For large sets U (and hence for large graphs) the first implementation is considerably faster than the second.

Tweet- Performance considerations with sparse matrices in Armadillo — Hong Ooi
- Suppressing Call Stack Info in Rcpp-Generated Errors and Warnings — Michael Weylandt
- Introducing RcppArrayFire — Ralf Stubner