ポイントの配列とエッジの配列から隣接行列を作る方法

Question

私は画像を持っており、グラフの頂点を表す領域の重心を表すいくつかの点を集めました。 ポイントの私のリストは、次のようになります。

[(455, 472), (343, 472), (208, 471), (478, 456), (460, 441), (428, 439), 
(413, 458), (48, 439), (107, 460), (130, 413), (179, 385), (250, 396), 
(20, 373), (431, 381), (483, 355), (342, 390), (441, 343), (312, 344), 
(283, 336), (259, 342), (409, 329),..............................] 

今、私はいくつかのエッジを探し、そして私のコードでは、いくつかの操作を行うことはp1が---- p2があるのリストのこのタイプ（P1、P2）を生成edge：

DijksraやBFSのようなアルゴリズムを実装したいと思います。 他の質問と実装を見ると、そのグラフのほとんどは隣接行列として表されています。 私はちょうど私がしたようにエッジを追加する代わりに、ハッシュテーブルや辞書オブジェクトに直接追加することを考えました。問題は - 頂点にはどのような名前を付けるのですか？私は(343,472)を持っていると言うと、私はどのように移動し、このような外見に変わるのか分かりません：{A : [p1,p2...], B: [p3,....], ... }

これを行うにはどうすればよい方法でしょうか？あなたのグラフが重み付けされていないで、あなただけのset値でdefaultdictを使用することができmultiedgesを持っていない場合は

def makeEdgesFromSpots(centroids, imageForEdges): 
edges = [] 
for c1 in centroids: 
    for c2 in centroids: 
     if(c1[0] == c2[0] and c1[1] == c2[1]): 
      continue 
     else: 
      //checkPointsForPath does some testing, 
      // to check if I want these points as an edge. 
      isLine = checkPointsForPath(c1,c2,imageForEdges) 
      if isLine == True: 
       edges.append((c1,c2)) 
return edges 

Answer 1

：私は、現時点では、エッジの表現を作成する方法を示すコードを追加し

from collections import defaultdict 
import pprint 

edges = [((343, 472), (342, 390)), ((343, 472), (312, 344)), 
     ((343, 472), (337, 302)), ((478, 456), (460, 441))] 
adj_matrix = defaultdict(set) 

for x, y in edges: 
    adj_matrix[x].add(y) 
    adj_matrix[y].add(x) # Assuming undirected graph 

pprint.pprint(adj_matrix) 

出力：

defaultdict(<class 'set'>, 
      {(312, 344): {(343, 472)}, 
      (337, 302): {(343, 472)}, 
      (342, 390): {(343, 472)}, 
      (343, 472): {(312, 344), (337, 302), (342, 390)}, 
      (460, 441): {(478, 456)}, 
      (478, 456): {(460, 441)}}) 

特定の目的に明示的に名前が必要な場合を除いて、頂点に名前を付ける必要はありません。