Statistics
| Branch: | Revision:

mobicen / util / UnitDiskGraph.py @ 05763cfb

History | View | Annotate | Download (4.21 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, 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