# What is the most efficient way to represent resizable adjacecny matrix

I'm building a simple app that represents some matrix, where nodes are added quite often. Currently I have following code for adding a new node:

``````let mut new_edges = Array2::default((position + 1, position + 1));
for i in 0..position {
for j in 0..position {
new_edges[[i, j]] = self.edges[[i, j]]
}
}

self.edges = new_edges;
``````

So it basically just copies everything on each node insert.

Much more efficient way were just add new items in the end of single-dimension vector and treat it as 2D matrix. For example, it could be vector of length `9` which represents following matrix:

``````0|1|8|
_| | |
3 2|7|
___  |
4 5 6|
_____
``````

So you see. We hold indices of underlying vector in snake order. When we want to resize it we don't move anything but just add new `2n-1` nodes to the end. Adding 4th column and row would lead to adding 7 nodes in following manner:

``````0 |1 |8 |9 |
__|  |  |  |
3  2 |7 |10|
_____|  |  |
4  5  6 |11|
________|  |
15 14 13 12|
___________|
``````

The problem with this approach that I can't express it mathematically, i.e. in this case `matrix[[2,2]]` is stored in vec on index `6`, `matrix[[2,0]]` is stored on the index `8` and `matrix[[0,1]]` is stored on index `3`.

Am I doing the right thing and if the answer is yes, how could 1d to 2d translation be performed?

• I think it would be easier to store the upper and lower halves of the matrix separately. – D Drmmr Mar 25 '18 at 11:50
• @DDrmmr can you be more detailed? I don't see how it can work. – Alex Zhukovskiy Mar 25 '18 at 13:33
• I mean store the upper half in an array and the lower half in a separate array. Then you can achieve the same property (adding a node only requires appending to the array), but with a simpler lookup scheme. – D Drmmr Mar 25 '18 at 14:29

If you want to "express it mathematically" (your words above)

```  n\m| 0  1  2  3  4  5
----+----------------
0  | 0  2  5  9 14 20
|   /  / /  /  /
1  | 1  4  8 13 19 26
|   / /  /  /  /
2  | 3  7 12 18 25 33
|   / /  /  /  /
3  | 6 11 17 24 32 41
```

Then the mathematical expression is just
(n,m)   -->   1/2*(n+m)*(n+m+1)   +   m
This is the very standard "pair enumeration function", e.g.,
https://en.wikipedia.org/wiki/Pairing_function
(their diagram is "topsy-turvy" relative to this one, but amounts to the same thing).
Pair enumeration is essentially just an embedding NxN-->N.

My understanding of it came from pages 118-120 of Stoy's book
• My need is that I need all numbers below `n^2` to be in square `nxn` from starting left top corner. This algorithm doesn't fit because `3` is outside of `2x2` square. – Alex Zhukovskiy Mar 25 '18 at 9:50