## Using iterators for sparse vectors and matrices

Soren Hojsgaard and Doug Bates — written Apr 1, 2014 — source

## Iterating over a sparse vector

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
```

## Iterating over a sparse matrix

```Loading required package: methods
```
```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
```

# Example from graph theory

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.

tags: eigen  sparse  modeling