mobicen / util / UnitDiskGraph.py @ 0a4aa24d
History  View  Annotate  Download (4 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.all as gt 
8 
import numpy as np 
9 
from pprint import pprint 
10 
import time 
11 
from heapq import nsmallest 
12 
from collections import defaultdict 
13  
14 
def second_smallest(numbers): 
15 
return nsmallest(2, numbers)[1] 
16  
17  
18 
def reconnectGraph(g, distM): 
19 
labels, hist=gt.label_components(g, directed=False)

20 
# While not only a single component

21 
while (not all(e==0 for e in labels.a)): 
22 
#code.interact(local=dict(globals(), **locals()))

23 
# Divide node by component

24 
comp2nodes = defaultdict(list)

25 
for i in range(len(labels.a)): 
26 
comp2nodes[labels.a[i]].append(i) 
27 
# se il grafo e' sconnesso solo per un singolo nodo staccato

28 
if len(set(labels.a))==2 and min(map(len, comp2nodes.values()))==1: 
29 
#print "Isolated node"

30 
#code.interact(local=dict(globals(), **locals()))

31 
out=g.get_out_degrees(g.get_vertices()) 
32 
for i in range(0,len(out),1): 
33 
if out[i]==0: 
34 
dp=distM[i] 
35 
closest=second_smallest(dp) 
36 
near_neigh=[k for k in range(len(dp)) if dp[k]==closest][0] 
37 
g.add_edge(g.vertex(i), g.vertex(near_neigh)) 
38 
break

39 
else:

40 
#iteratively attach the smallest compo to the closest

41 
#print "Separated Compo"

42 
#code.interact(local=dict(globals(), **locals()))

43 
d={k:len(v) for k,v in comp2nodes.items()} 
44 
minCompoLabel=min(d, key=d.get)

45 
minCompo=comp2nodes[minCompoLabel] 
46 
couple=None

47 
nearest_dist=10000000

48 
for n in minCompo: 
49 
dp=distM[n] 
50 
for v in range(0,len(distM), 1): 
51 
if n==v: continue 
52 
if labels.a[v] == labels.a[n]: continue 
53 
closest=distM[n][v] 
54 
if closest < nearest_dist:

55 
nearest_dist = closest 
56 
couple=n,v 
57 
g.add_edge(g.vertex(couple[0]), g.vertex(couple[1])) 
58 
#print "Connecting %d%d, which are %.04f distant" % (couple[0], couple[1], nearest_dist)

59  
60 
labels, hist=gt.label_components(g, directed=False)

61  
62  
63 
class UnitDiskGraph: 
64  
65 
def __init__(self, points, radius): 
66 
self.nxG = nx.Graph()

67 
self.nxG.add_nodes_from(range(len(points))) 
68 

69 
self.gtG = gt.Graph(directed=False) 
70 
self.gtG.add_vertex(len(points)) 
71 
self.edge_weights = self.gtG.new_edge_property('float') 
72 
self.gtG.edge_properties['weight'] = self.edge_weights 
73  
74 
self.generateGraphCDIST(points, radius)

75 

76 

77 
def genereateGraphFromKDtree(self, points, radius): 
78 
tree = KDTree(points) 
79 
edges = tree.query_pairs(r=radius) 
80 
#edges = [e+(1.0,) for e in edges]

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

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

83 
for e in edges: 
84 
e = self.G.add_edge(e[0],e[1]) 
85 
self.edge_weights[e] = 1.0 
86  
87  
88 
def generateGraphCDIST(self, points, radius): 
89 
distM = cdist(points, points, 'euclidean')

90 
edges = [] 
91 
for r in range(len(points)): 
92 
for c in range(len(points)): 
93 
if r==c:

94 
continue

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

96 
edges.append([r,c, 1.0])

97 
self.nxG.add_weighted_edges_from(edges, weight='weight') 
98 

99 
self.gtG.ep["weight"] = self.gtG.new_edge_property("float") 
100 
eprops = [self.gtG.ep["weight"]] 
101 
self.gtG.add_edge_list(edges, eprops=eprops)

102 
#out=self.gtG.get_out_degrees(self.gtG.get_vertices())

103 
reconnectGraph(self.gtG, distM)

104 

105  
106 
def getGraph(self): 
107 
return self.gtG, self.nxG 
108  
109 

110  
111  
112  
113  
114  
115 