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