# 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. Commented Mar 25, 2018 at 11:50
• @DDrmmr can you be more detailed? I don't see how it can work. Commented Mar 25, 2018 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. Commented Mar 25, 2018 at 14:29

## 1 Answer

If you want to "express it mathematically" (your words above)
try arranging your (n,m) indices this very similar way instead...

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
https://books.google.com/books?id=jM0mAAAAMAAJ
But, sorry, I can't seem to get books.google to display full pages for it.

• 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. Commented Mar 25, 2018 at 9:50
• It seems that this algorithm is working as expected. However, seems to be complicated. Commented Mar 25, 2018 at 13:31
• @AlexZhukovskiy, encapsulate the complexity within an abstraction, so you don't see it for the most part; one that offers x,y lookup plus expansion? Commented Mar 26, 2018 at 0:45
• @AlexZhukovskiy Yeah, this standard pair enumeration isn't as space-efficient, in that the embedding maps "corner" index (n,n) to 2(n^2+n) rather than the best case n^2. And its inverse projections (as per that wikipedia link) are kind of "goofy", although as EE pointed out, easy to hide. I only pointed it out as the standard NxN-->N procedure. Yours would require only half the space, and if that's crucial, EE's suggestion is perhaps best. That is, there may be no easy algebraic expression for your procedure, but you can encapsulate the embedding/projection pair in pretty straightforward code Commented Mar 26, 2018 at 4:09
• @AlexZhukovskiy I briefly glanced at your rust-lang.org pseudocode. I'm not familiar with that, but its first statement let (i,j) = if i>j {(j,i)} else {(i,j)}; looks to me like it swaps (i,j) when i>j. If that's what's happening, it'll only work for you if your matrix is symmetric. Commented Mar 26, 2018 at 8:30