mobicen / util / UnitDiskGraph.py @ 05763cfb
History  View  Annotate  Download (4.21 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, nxG, 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 

39 
break

40 
else:

41 
#iteratively attach the smallest compo to the closest

42 
#print "Separated Compo"

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 
#code.interact(local=dict(globals(), **locals()))

59 
#print "Connecting %d%d, which are %.04f distant" % (couple[0], couple[1], nearest_dist)

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

62 
#at the end reconnect also nxG graph

63 
for e in g.edges(): 
64 
if not nxG.has_edge(e.source(), e.target()): 
65 
nxG.add_edge(int(str(e.source())), int(str(e.target())), weight=1.0) 
66  
67  
68 
class UnitDiskGraph: 
69  
70 
def __init__(self, points, radius): 
71 
self.nxG = nx.Graph()

72 
self.nxG.add_nodes_from(range(len(points))) 
73 

74 
self.gtG = gt.Graph(directed=False) 
75 
self.gtG.add_vertex(len(points)) 
76 
self.edge_weights = self.gtG.new_edge_property('float') 
77 
self.gtG.edge_properties['weight'] = self.edge_weights 
78  
79 
self.generateGraphCDIST(points, radius)

80 

81 

82 
def genereateGraphFromKDtree(self, points, radius): 
83 
tree = KDTree(points) 
84 
edges = tree.query_pairs(r=radius) 
85 
#edges = [e+(1.0,) for e in edges]

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

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

88 
for e in edges: 
89 
e = self.G.add_edge(e[0],e[1]) 
90 
self.edge_weights[e] = 1.0 
91  
92  
93 
def generateGraphCDIST(self, points, radius): 
94 
distM = cdist(points, points, 'euclidean')

95 
edges = [] 
96 
for r in range(len(points)): 
97 
for c in range(len(points)): 
98 
if r==c:

99 
continue

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

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

102 
self.nxG.add_weighted_edges_from(edges, weight='weight') 
103 

104 
self.gtG.ep["weight"] = self.gtG.new_edge_property("float") 
105 
eprops = [self.gtG.ep["weight"]] 
106 
self.gtG.add_edge_list(edges, eprops=eprops)

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

108 
reconnectGraph(self.gtG, self.nxG, distM) 
109 

110  
111 
def getGraph(self): 
112 
return self.gtG, self.nxG 