1

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?

Alex Zhukovskiy
  • 111
  • 5
  • 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

1 Answers1

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.

John Forkosh
  • 821
  • 5
  • 11
  • 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 09:50
  • It seems that [this algorithm is working as expected](https://play.rust-lang.org/?gist=89f28777fd52bd9e6211be29eb644586&version=stable). However, seems to be complicated. – Alex Zhukovskiy Mar 25 '18 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? – Erik Eidt Mar 26 '18 at 00: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 – John Forkosh Mar 26 '18 at 04: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. – John Forkosh Mar 26 '18 at 08:30
  • @JohnForkosh yep, it's broken a bit. [here](https://play.rust-lang.org/?gist=1202068318122823fdc30e19d0ae3313&version=stable) is the right solution. It works as expected, [here](https://play.rust-lang.org/?gist=e6ed757986f9b7c331478c4f0fa2efd6&version=stable) it's used as part of adjacency matrix representation algorithm, you can check `index_linear` and test in the end of the example. – Alex Zhukovskiy Mar 27 '18 at 08:16