Statistics
| Branch: | Revision:

mobicen / util / UnitDiskGraph.py @ 23c7ab1e

History | View | Annotate | Download (1.73 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 as gt
8

    
9
class UnitDiskGraph:
10

    
11
    def __init__(self, points, radius):
12
        self.nxG = nx.Graph()
13
        self.nxG.add_nodes_from(range(len(points)))
14
        
15
        self.gtG = gt.Graph(directed=False)
16
        self.gtG.add_vertex(len(points))
17
        self.edge_weights = self.gtG.new_edge_property('float')
18
        self.gtG.edge_properties['weight'] = self.edge_weights        
19

    
20
        self.generateGraphCDIST(points, radius)
21
        
22
        
23
    def genereateGraphFromKDtree(self, points, radius):
24
        tree = KDTree(points)
25
        edges = tree.query_pairs(r=radius)
26
        #edges = [e+(1.0,) for e in edges]
27
        #pos = {k:points[k] for k in range(0,len(points))}        
28
        #self.G.add_weighted_edges_from(edges, weight='weight')
29
        for e in edges:
30
            e = self.G.add_edge(e[0],e[1])
31
            self.edge_weights[e] = 1.0
32

    
33

    
34
    def generateGraphCDIST(self, points, radius):
35
        distM = cdist(points, points, 'euclidean')
36
        edges = []
37
        for r in range(len(points)):
38
            for c in range(len(points)):
39
                if r==c:
40
                    continue
41
                if distM[r][c] <= radius:
42
                    edges.append([r,c, 1.0])
43
        self.nxG.add_weighted_edges_from(edges, weight='weight')
44
        
45
        self.gtG.ep["weight"] = self.gtG.new_edge_property("float")
46
        eprops = [self.gtG.ep["weight"]]
47
        self.gtG.add_edge_list(edges, eprops=eprops)
48

    
49
    def getGraph(self):
50
        return self.gtG, self.nxG