Pythonでの近接グラフ

Question

私は比較的Pythonコーディングに慣れています（私は主にランニングタイムスピードのためにRから切り替えています）、私は近接グラフをコーディングする方法を理解しようとしています。

これは、私がd次元のユークリッド空間に等間隔の点の配列を持っていると仮定すると、これらは私のノードになります。私は、それらが離れている場合にのみ、2つの点を接続することによってこれらを無向グラフにしたいと考えています。

• N：Rの寸法^ D
• E：存在するエッジに対して許容される最大距離と同じ軸上の2点
• Dとの間の間隔はどのようにパラメータを使用してこの機能コードすることができます。

Answer 1

graph-toolライブラリはmuch of the functionality you needである。だから、あなたはnumpyとgraph-toolを持っていると仮定すると、このような何かを行うことができます：

coords = numpy.meshgrid(*(numpy.linspace(0, (n-1)*delta, n) for i in range(d))) 
# coords is a Python list of numpy arrays 
coords = [c.flatten() for c in coords] 
# now coords is a Python list of 1-d numpy arrays 
coords = numpy.array(coords).transpose() 
# now coords is a numpy array, one row per point 
g = graph_tool.generation.geometric_graph(coords, e*(1+1e-9)) 

愚かe*(1+1e-9)事はあなたの基準は「距離< = E」であるとgeometric_graphの基準は 『距離< E』であるからです。

パラメータnについてのあなたの説明は、2つのパラメータ（ポイント間の間隔とポイント数）に関わっていると思われるため、deltaというパラメータがあります。

Answer 2

このコードは動作しますが、これは確かに効率的ではありません。それは各ノードを通過し、他のすべてのノード（それと比較していないノード）までの距離をチェックします。その距離が値eより小さい場合、接続されたマトリックスの対応する値は1に設定されます。ゼロは、2つのノードが接続されていないことを示します。

このコードでは、nodeListは、nodeList = [[x1,y1,...],[x2,y2,...],...[xN,yN,...]]のデカルト座標のリストであると仮定しています。また、calcDistanceという2つのデカルト座標の間のユークリッド距離を返す関数があるとします。これは、私がコードを書いていないことを実装するのに十分な基本的なものであり、どのような場合でも関数を使用することで、将来の一般化と変更が可能になります。

numNodes = len(nodeList) 
connected = np.zeros([numNodes,numNodes]) 
for i, n1 in enumerate(nodeList): 
    for j, n2 in enumerate(nodeList[i:]): 
     dist = calcDistance(n1, n2) 
     if dist < e: 
      connected[i,j] = 1 
      connected[j,i] = 1