Statistics
| Branch: | Revision:

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