単一ベクトルに格納された三角形隣接行列の順方向および逆方向のインデックス付け

Question

私は点を持つ地図を持っています。私は各点の間の距離を知りたいと思います。 （これは、Undirected Cyclic Graphとも呼ばれます）。多くの点があり、ストレージが限られているため、アレイは密集している必要があります。

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 

または三角形見：4つの都市（N = 4）、Iは、これらの4都市をマッピングするために6つのインデックスを必要とするため

(1-2)(1-3)(1-4) 
(2-3)(2-4) 
(3-4) 

この（いずれかの方向/エッジ - すべての道路は、2であります方法）。 260都市ある場合は、260x260や67600のインデックスではなく、33670のインデックスが必要です。例：4つの都市では、インデックス＃4は2から4までの距離です（または4から2に「反転」されます）。
注：上の例は、都市を1つずつ、次に都市を1、...、最後の都市から最後の都市（n-1〜n）を除いて2つの都市にそれぞれ2つずつの例です。他の「形」は議論のために開いています（逆順や別の計画など）。

私に260の都市がある場合、ゼロベースのインデックス#iがどの都市を参照しているかをどのようにして知ることができますか？ city1とcity2をインデックスから取得して戻すために使用できる2つの式がありますか？ （例：インデックス＃33333は234から249までです）。

getIndex(city1, city2) // returns index 
getCities(Index)  // returns city1, city2 

Answer 1

いくつかの高校代数でこれらを導き出すことは難しくありません。しかし、それらを計算するのはかなり高価です。

は(i,j)が都市j > i市内i >= 1からエッジであると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 

j = floor((3 + sqrt(1))/2) == 2、p == 0については、他の道を行くために。その後、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頂点を持つグラフの：

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 

右手側は二列に書かれたベクトルです。奇数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 

定数kとkkアレイが作成され、一度に計算することができます。

他の方法に進むには、j' = floor(p/n)とi' = p mod nとします。その後、

i = i' + 1, j = j' + 2     if j' <= i' 
i = n - i', j = n - j'     othewise 

ケースnの場合でも調整します。

これらは、通常の2d配列インデックス作成よりもわずかに高価ですが、その都度2方向分岐があるためです。