Statistics
| Branch: | Revision:

mobicen / util / UnitDiskGraph.py @ 0a4aa24d

History | View | Annotate | Download (4 KB)

1 e1cf8bea LoreBz
# https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance
2
3
import networkx as nx
4 1ef4948a LoreBz
from scipy.spatial import KDTree
5
from scipy.spatial.distance import cdist
6
import code  # code.interact(local=dict(globals(), **locals()))
7 0a4aa24d LoreBz
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 e1cf8bea LoreBz
63
class UnitDiskGraph:
64
65
    def __init__(self, points, radius):
66 2dbcade9 LoreBz
        self.nxG = nx.Graph()
67
        self.nxG.add_nodes_from(range(len(points)))
68 1ef4948a LoreBz
        
69 2dbcade9 LoreBz
        self.gtG = gt.Graph(directed=False)
70 23c7ab1e LoreBz
        self.gtG.add_vertex(len(points))
71 2dbcade9 LoreBz
        self.edge_weights = self.gtG.new_edge_property('float')
72
        self.gtG.edge_properties['weight'] = self.edge_weights        
73
74 1ef4948a LoreBz
        self.generateGraphCDIST(points, radius)
75
        
76
        
77 e1cf8bea LoreBz
    def genereateGraphFromKDtree(self, points, radius):
78 1ef4948a LoreBz
        tree = KDTree(points)
79 e1cf8bea LoreBz
        edges = tree.query_pairs(r=radius)
80 1ef4948a LoreBz
        #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 27b1b922 LoreBz
                    edges.append([r,c, 1.0])
97 2dbcade9 LoreBz
        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 23c7ab1e LoreBz
        self.gtG.add_edge_list(edges, eprops=eprops)
102 0a4aa24d LoreBz
        #out=self.gtG.get_out_degrees(self.gtG.get_vertices())
103
        reconnectGraph(self.gtG, distM)
104
            
105 e1cf8bea LoreBz
106
    def getGraph(self):
107 2dbcade9 LoreBz
        return self.gtG, self.nxG
108 0a4aa24d LoreBz
109
    
110
111
112
113
114