mobicen / util / UnitDiskGraph.py @ 1ef4948a
History  View  Annotate  Download (1.71 KB)
1 
# https://stackoverflow.com/questions/32424604/findallnearestneighborswithinaspecificdistance


2  
3 
import networkx as nx 
4 
from scipy.spatial import KDTree 
5 
from scipy.spatial.distance import cdist 
6 
import code # code.interact(local=dict(globals(), **locals())) 
7 
import graph_tool as gt 
8  
9 
class UnitDiskGraph: 
10  
11 
def __init__(self, points, radius): 
12 
self.G = nx.Graph()

13 
self.G.add_nodes_from(range(len(points))) 
14 
'''

15 
self.G = gt.Graph(directed=False)

16 
self.G.add_vertex(len(points))

17 
self.edge_weights = self.G.new_edge_property('double')

18 
self.G.edge_properties['weight'] = self.edge_weights'''

19 

20 
self.generateGraphCDIST(points, radius)

21 

22 

23 
def genereateGraphFromKDtree(self, points, radius): 
24 
tree = KDTree(points) 
25 
edges = tree.query_pairs(r=radius) 
26 
#edges = [e+(1.0,) for e in edges]

27 
#pos = {k:points[k] for k in range(0,len(points))}

28 
#self.G.add_weighted_edges_from(edges, weight='weight')

29 
for e in edges: 
30 
e = self.G.add_edge(e[0],e[1]) 
31 
self.edge_weights[e] = 1.0 
32  
33  
34 
def generateGraphCDIST(self, points, radius): 
35 
distM = cdist(points, points, 'euclidean')

36 
edges = [] 
37 
for r in range(len(points)): 
38 
for c in range(len(points)): 
39 
if r==c:

40 
continue

41 
if distM[r][c] <= radius:

42 
edges.append((r,c,1.0))

43 
self.G.add_weighted_edges_from(edges, weight='weight') 
44 
'''code.interact(local=dict(globals(), **locals()))

45 
for e in edges:

46 
e = self.G.add_edge(e[0],e[1])

47 
self.edge_weights[e] = 1.0'''

48  
49 
def getGraph(self): 
50 
return self.G 