Revision 0a4aa24d util/UnitDiskGraph.py

View differences:

util/UnitDiskGraph.py
4 4
```from scipy.spatial import KDTree
```
5 5
```from scipy.spatial.distance import cdist
```
6 6
```import code  # code.interact(local=dict(globals(), **locals()))
```
7
```import graph_tool as gt
```
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

8 62

9 63
```class UnitDiskGraph:
```
10 64

......
45 99
```        self.gtG.ep["weight"] = self.gtG.new_edge_property("float")
```
46 100
```        eprops = [self.gtG.ep["weight"]]
```
47 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
```
```
48 105

49 106
```    def getGraph(self):
```
50 107
```        return self.gtG, self.nxG
```
108

109
```
```
110

111

112

113

114

115

Also available in: Unified diff