存储在单个向量中的三角形邻接矩阵的正向和反向索引 [英] Forward and inverse indexing of a triangular adjacency matrix stored in a single vector
问题描述
Index＃，City1<> ; City2
=========================
Index＃0，1<> 2
索引＃1，1> 3
索引＃2，1> 4
索引＃3，2> 3
索引＃4，2> 4
索引＃5，3> 4
索引总数= 6
城市= 4
（1-2）（1-3）（1-4）
（2-3） ）（2-4）
（3-4）
- 所有的道路都是双向的）。如果我有260个城市，我需要33670个指数，而不是260x260或67600个指数。例如：对于4个城市，索引号4是从2到4的距离（或翻转为4到2）。
注：以上是一个示例，其中每个城市为1，然后是2到除了1，...，城市倒数第二个城市（n-1到n）的每个城市。其他'形状'是开放的讨论（如反向秩序，甚至另一个计划）。
如果我有260个城市，我怎么能告诉哪些城市从零开始索引#i是指？有没有2个公式可以用来从索引中获取city1和city2？ （例如：索引号33333从234到249）。
$ b $ pre $ getIndex（city1，city2）//返回索引
getCities（索引）//返回city1，city2
用高中代数来推导这些并不难。但是计算它们是非常昂贵的。
设 j> i 并让 p> = 0 为表示线性三角矩阵的向量中的对应索引。然后
p = j *（j - 3）/ 2 + i
使用此公式，线性布局为：
（i，j）=（1,2）（1,3）（2,3）（1,4）（2,4）（3,4）...
p = 0 1 2 3 4 5 ...
例如对于（1,2）我们有 2 *（2-3）/ 2 + 1 == 0 期待。对于（2,4）它是 4 *（4 - 3）/ 2 + 2 == 4 。
换一种方式，
j = floor（（3 + sqrt（8 * p + 1））/ 2）
i = p - j *（j - 3）/ 2
对于 p == 0 ， j = floor（（3 + sqrt（1））/ 2）== 2 。然后 i = 0-2 *（2-3）/ 2 == 1 。对于 p == 4 ，它是 j = floor（（3 + sqrt（33））/ 2）= 4 ，那么 i = 4 - 4 *（4 - 3）/ 2 = 2 。
平方根是可能为什么你不经常看到使用这种技术。注意整数平方根可以正常工作，在某些情况下，它可能比浮点更快。总而言之，它可能更快，更简单，并且几乎和存储效率一样高使用指向数组的指针数组来增加长度。
加法
它毕竟，有是消除平方根的一种方法。我们将三角形阵列切成两半，并将这些部分拼成一个矩形。对于 n = 5 顶点的图：
jp = 0 1 2 3 4
= --- -------------------
2 | a | |一个$ j |我| h | g |
------- ---- === ------------
3 | b | c |排列：| b | c $ f | e | d |
----------- -------------------
4 | d | e | f | 5 6 7 8 9
---------------
5 | g | h |我| j |
---------------
i = 1 2 3 4
右侧是写入两行的向量。
现在对于单数n，
{n * j + i - k，如果j < （其中k = 2 * n + 1
p = {
{kk - （n * j + i）否则
{其中kk =（floor（ n / 2）+4）* n
常量 k 和 kk 可以在数组创建时计算一次。
，让 j'= floor（p / n）和 i'= p mod n 。那么如果j'<= i'
i，那么
i = i'+ 1，j = j'+ 2 = n - i'，j = n - j'othewise
我会让你算出偶数 n case。
这些只比普通二维数组索引要贵一些，这是由于2路在每种情况下都是分支。
I have a map with points, I would like to know the distance between each point. (This is possibly known as Undirected Cyclic Graph). As there are a lot of points, with my storage being limited, the array needs to be dense. For 4 cities (n = 4), I need 6 indexes to map these 4 cities:
Index #, City1 <> City2
=========================
Index #0, 1 <> 2
Index #1, 1 <> 3
Index #2, 1 <> 4
Index #3, 2 <> 3
Index #4, 2 <> 4
Index #5, 3 <> 4
Index total = 6
Cities = 4
Or viewed triangularly:
(1-2)(1-3)(1-4)
(2-3)(2-4)
(3-4)
This (either direction/edge -- all roads are two-way). If I have 260 cities, I need 33670 indexes instead of 260x260 or 67600 indexes. Ex: With 4 cities, Index #4 is the distance from 2 to 4 (or 'flipped' as 4 to 2).
Note: The above is an example with 1 to each other city, then 2 to each city except 1, ... , the 2nd-to-last city to last city (n-1 to n). Other 'shapes' are open for discussion (such as reverse order or even another scheme).
If I have 260 cities, how can I tell what cities zero-based index #i refers to? are there 2 formulas I can use to get city1 and city2 from the index and back again? (Ex: Index #33333 is 234 to/from 249).
getIndex(city1, city2) // returns index
getCities(Index) // returns city1, city2
It's not hard to derive these with some high school algebra. But computing them is pretty expensive.
Let (i,j) be the edge from city i >= 1 to city j > i and let p >= 0 be the corresponding index in the vector representing the linearized triangular matrix. Then
p = j * (j - 3) / 2 + i
With this formula, the linear layout is:
(i,j) = (1,2)(1,3)(2,3)(1,4)(2,4)(3,4)...
p = 0 1 2 3 4 5 ...
E.g. for (1,2) we have 2 * (2 - 3) / 2 + 1 == 0 as you'd expect. And for (2,4) it's 4 * (4 - 3) / 2 + 2 == 4.
To go the other way,
j = floor((3 + sqrt(8 * p + 1)) / 2)
i = p - j * (j - 3) / 2
For p == 0, j = floor((3 + sqrt(1)) / 2) == 2. Then i = 0 - 2 * (2 - 3) / 2 == 1. For p == 4, it's j = floor((3 + sqrt(33)) / 2) = 4, then i = 4 - 4 * (4 - 3) / 2 = 2.
The square root is probably why you don't often see this technique used. Note integer square root will work fine, which can be faster than floating point in some circumstances.
All in all, it's probably faster, simpler, and almost as storage efficient to use an array of pointers to rows of increasing length.
Addition
It turns out after all that there is a way to eliminate the square root. We cut the triangular array in half and fit the pieces to make a rectangle. For a graph with n = 5 vertices:
j p = 0 1 2 3 4
= --- -------------------
2 | a | | a $ j | i | h | g |
------- ----===------------
3 | b | c | is arranged: | b | c $ f | e | d |
----------- -------------------
4 | d | e | f | 5 6 7 8 9
---------------
5 | g | h | i | j |
---------------
i = 1 2 3 4
where the right hand side is a vector written in two rows.
Now for odd n,
{ n*j + i - k, if j < n/2 + 2
{ where k = 2*n+1
p = {
{ kk - (n*j + i) otherwise
{ where kk = (floor(n/2)+4)*n
The constants k and kk can be computed one time when the array is created.
To go the other way, let j' = floor(p/n) and i' = p mod n. Then
i = i' + 1, j = j' + 2 if j' <= i'
i = n - i', j = n - j' othewise
I will let you work out the even n case.
These are only a bit more expensive than normal 2d array indexing, due to the 2-way branch in each case.
这篇关于存储在单个向量中的三角形邻接矩阵的正向和反向索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
