mobicen / util / UnitDiskGraph.py @ 0a4aa24d
History | View | Annotate | Download (4 KB)
1 |
# https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance
|
---|---|
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 |
|