Statistics
| Branch: | Revision:

## mobicen / util / UnitDiskGraph.py @ 0a4aa24d

 1 ```# https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance ``` ```import networkx as nx ``` ```from scipy.spatial import KDTree ``` ```from scipy.spatial.distance import cdist ``` ```import code # code.interact(local=dict(globals(), **locals())) ``` ```import graph_tool.all as gt ``` ```import numpy as np ``` ```from pprint import pprint ``` ```import time ``` ```from heapq import nsmallest ``` ```from collections import defaultdict ``` ```def second_smallest(numbers): ``` ``` return nsmallest(2, numbers)[-1] ``` ```def reconnectGraph(g, distM): ``` ``` labels, hist=gt.label_components(g, directed=False) ``` ``` # While not only a single component ``` ``` while (not all(e==0 for e in labels.a)): ``` ``` #code.interact(local=dict(globals(), **locals())) ``` ``` # Divide node by component ``` ``` comp2nodes = defaultdict(list) ``` ``` for i in range(len(labels.a)): ``` ``` comp2nodes[labels.a[i]].append(i) ``` ``` # se il grafo e' sconnesso solo per un singolo nodo staccato ``` ``` if len(set(labels.a))==2 and min(map(len, comp2nodes.values()))==1: ``` ``` #print "Isolated node" ``` ``` #code.interact(local=dict(globals(), **locals())) ``` ``` out=g.get_out_degrees(g.get_vertices()) ``` ``` for i in range(0,len(out),1): ``` ``` if out[i]==0: ``` ``` dp=distM[i] ``` ``` closest=second_smallest(dp) ``` ``` near_neigh=[k for k in range(len(dp)) if dp[k]==closest][0] ``` ``` g.add_edge(g.vertex(i), g.vertex(near_neigh)) ``` ``` break ``` ``` else: ``` ``` #iteratively attach the smallest compo to the closest ``` ``` #print "Separated Compo" ``` ``` #code.interact(local=dict(globals(), **locals())) ``` ``` d={k:len(v) for k,v in comp2nodes.items()} ``` ``` minCompoLabel=min(d, key=d.get) ``` ``` minCompo=comp2nodes[minCompoLabel] ``` ``` couple=None ``` ``` nearest_dist=10000000 ``` ``` for n in minCompo: ``` ``` dp=distM[n] ``` ``` for v in range(0,len(distM), 1): ``` ``` if n==v: continue ``` ``` if labels.a[v] == labels.a[n]: continue ``` ``` closest=distM[n][v] ``` ``` if closest < nearest_dist: ``` ``` nearest_dist = closest ``` ``` couple=n,v ``` ``` g.add_edge(g.vertex(couple[0]), g.vertex(couple[1])) ``` ``` #print "Connecting %d--%d, which are %.04f distant" % (couple[0], couple[1], nearest_dist) ``` ``` labels, hist=gt.label_components(g, directed=False) ``` ```class UnitDiskGraph: ``` ``` def __init__(self, points, radius): ``` ``` self.nxG = nx.Graph() ``` ``` self.nxG.add_nodes_from(range(len(points))) ``` ``` ``` ``` self.gtG = gt.Graph(directed=False) ``` ``` self.gtG.add_vertex(len(points)) ``` ``` self.edge_weights = self.gtG.new_edge_property('float') ``` ``` self.gtG.edge_properties['weight'] = self.edge_weights ``` ``` self.generateGraphCDIST(points, radius) ``` ``` ``` ``` ``` ``` def genereateGraphFromKDtree(self, points, radius): ``` ``` tree = KDTree(points) ``` ``` edges = tree.query_pairs(r=radius) ``` ``` #edges = [e+(1.0,) for e in edges] ``` ``` #pos = {k:points[k] for k in range(0,len(points))} ``` ``` #self.G.add_weighted_edges_from(edges, weight='weight') ``` ``` for e in edges: ``` ``` e = self.G.add_edge(e[0],e[1]) ``` ``` self.edge_weights[e] = 1.0 ``` ``` def generateGraphCDIST(self, points, radius): ``` ``` distM = cdist(points, points, 'euclidean') ``` ``` edges = [] ``` ``` for r in range(len(points)): ``` ``` for c in range(len(points)): ``` ``` if r==c: ``` ``` continue ``` ``` if distM[r][c] <= radius: ``` ``` edges.append([r,c, 1.0]) ``` ``` self.nxG.add_weighted_edges_from(edges, weight='weight') ``` ``` ``` ``` self.gtG.ep["weight"] = self.gtG.new_edge_property("float") ``` ``` eprops = [self.gtG.ep["weight"]] ``` ``` self.gtG.add_edge_list(edges, eprops=eprops) ``` ``` #out=self.gtG.get_out_degrees(self.gtG.get_vertices()) ``` ``` reconnectGraph(self.gtG, distM) ``` ``` ``` ``` def getGraph(self): ``` ``` return self.gtG, self.nxG ``` ``` ```