將點陣轉換爲圖形？

Question

假設我有一個點間距相等的d倍Z的點陣，我怎樣纔能有效地將它轉換成一個圖形，其中節點是點和兩點之間的邊，當且僅當這些點是相鄰的？

例如：假設我們是在給定的整數平方點對應於正方形的頂點...... 我們如何轉換成4這4矩陣（或圖形）的條目1或0有是連接兩個節點（其對應於分的整數平方）

的示例是簡單的，原因有二邊：

• 該點位於中的R的平方，所以輸入的2維數組（其中通常輸入將是d維陣列; d> 1
• 大多數點以明顯的方式連接在一起......但是模式（至少我發現）在d維中變得不那麼明顯，每個軸上的點越多......（如果我們採用8點躺在立方體的邊緣上）。

我正在尋找一個代碼，可以實現這個給定的任何這樣的數組（作爲輸入），並輸出一個（必然對稱）的矩陣，表示圖形上的節點之間的邊緣。我在R編程（並且開放給學習Python）。

Ps.s：我對奇語法道歉......這種交流不是用乳膠顯然兼容...：0

Answer 1

這可以在Python中實現像這樣：

from itertools import product 

def print_lattice_edges(lattice): 
    """prints all edges of a lattice, given as a list of lists of coordinates""" 
    for idim, dim_coords in enumerate(lattice): 
     for other_coords in product(*lattice[:idim] + lattice[idim+1:]): 
      for coord1, coord2 in zip(dim_coords[:-1], dim_coords[1:]): 
       edge1 = other_coords[:idim] + (coord1,) + other_coords[idim:] 
       edge2 = other_coords[:idim] + (coord2,) + other_coords[idim:] 
       print edge1, '->', edge2 

說明：

• 在所有維度第一個循環，選擇所有的座標爲維

• 通過移除所選維度創建一個新的網格，並用itertools.product

• 對於選定的尺寸迭代的其餘尺寸座標的所有可能組合的Cartesian product，遍歷所有可能的對連續座標。

• 通過將所選尺寸的座標放回到正確位置的笛卡爾積中來生成邊的兩個座標。

如果您的應用程序涉及數百萬個點和速度是一個問題，你也許可以做到通過生成使用numpy笛卡爾乘積類似的東西。

一些快速測試：

In [23]: print_lattice_edges([[0, 1], [0, 1]]) # your example 
(0, 0) -> (1, 0) 
(0, 1) -> (1, 1) 
(0, 0) -> (0, 1) 
(1, 0) -> (1, 1) 

In [24]: print_lattice_edges([[0, 1], [3, 4, 5]]) # 2x3 points, 7 edges 
(0, 3) -> (1, 3) 
(0, 4) -> (1, 4) 
(0, 5) -> (1, 5) 
(0, 3) -> (0, 4) 
(0, 4) -> (0, 5) 
(1, 3) -> (1, 4) 
(1, 4) -> (1, 5) 

In [25]: print_lattice_edges([[0, 1], [0, 1], [0, 1]]) # cube, 12 edges 
(0, 0, 0) -> (1, 0, 0) 
(0, 0, 1) -> (1, 0, 1) 
(0, 1, 0) -> (1, 1, 0) 
(0, 1, 1) -> (1, 1, 1) 
(0, 0, 0) -> (0, 1, 0) 
(0, 0, 1) -> (0, 1, 1) 
(1, 0, 0) -> (1, 1, 0) 
(1, 0, 1) -> (1, 1, 1) 
(0, 0, 0) -> (0, 0, 1) 
(0, 1, 0) -> (0, 1, 1) 
(1, 0, 0) -> (1, 0, 1) 
(1, 1, 0) -> (1, 1, 1)