What is the most efficient way to represent resizable adjacecny matrix

Question

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?

Answer 1

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.