min_dpa.py
Go to the documentation of this file.
00001 import math, sys, random, dijkstra, numpy, gv
00002 
00003 def calculate_approximate_degrees(S,p,r):
00004 
00005     approximate_degrees = [0]*len(S)
00006     
00007     for i, node in enumerate(S):
00008         for j, node in enumerate(S):
00009             distance = math.sqrt(math.pow((p[i][0]-p[j][0]),2)+math.pow((p[i][1]-p[j][1]),2))          
00010             if (distance < r) & (distance > 0):
00011                 approximate_degrees[i] += 1
00012                   
00013     return approximate_degrees
00014 
00015 
00016 def disk_belongs_square_area(center, r, l):
00017     
00018     # endpoints (0,0) (l,0) (0,l) (l,l)
00019     D = [[0,0],[l,0],[0,l],[l,l]]   
00020 
00021     # If delta is less than 0 then the line does not intersect the sphere.
00022     # If it equals 0 then the line is a tangent to the sphere intersecting it at one point, namely at u = -b/2a.
00023     # If it is greater then 0 the line intersects the sphere at two points.
00024 
00025     # for segment [0][0] -> [l][0] (0->1)
00026     a = (D[1][0]-D[0][0])**2+(D[1][1]-D[0][1])**2
00027     b = 2*((D[1][0]-D[0][0])*(D[0][0]-center[0])+(D[1][1]-D[0][1])*(D[0][1]-center[1]))
00028     c = center[0]**2 + center[1]**2 + D[0][0]**2 + D[0][1]**2 - 2*(center[0]*D[0][0]+center[1]*D[0][1])-r**2
00029 
00030     delta = b*b-4*a*c
00031 
00032     if delta < 0:
00033         pass
00034     elif delta >= 0:
00035         return False
00036 
00037     # for segment [0][0] -> [0][l] (0->2)
00038     a = (D[2][0]-D[0][0])**2+(D[2][1]-D[0][1])**2
00039     b = 2*((D[2][0]-D[0][0])*(D[0][0]-center[0])+(D[2][1]-D[0][1])*(D[0][1]-center[1]))
00040     c = center[0]**2 + center[1]**2 + D[0][0]**2 + D[0][1]**2 - 2*(center[0]*D[0][0]+center[1]*D[0][1])-r**2
00041 
00042     delta = b*b-4*a*c
00043 
00044     if delta < 0:
00045         pass
00046     elif delta >= 0:
00047         return False
00048 
00049     # for segment [0][l] -> [l][l] (2->3)
00050     a = (D[3][0]-D[2][0])**2+(D[3][1]-D[2][1])**2
00051     b = 2*((D[3][0]-D[2][0])*(D[2][0]-center[0])+(D[3][1]-D[2][1])*(D[2][1]-center[1]))
00052     c = center[0]**2 + center[1]**2 + D[2][0]**2 + D[2][1]**2 - 2*(center[0]*D[2][0]+center[1]*D[2][1])-r**2
00053 
00054     delta = b*b-4*a*c
00055 
00056     if delta < 0:
00057         pass
00058     elif delta >= 0:
00059         return False
00060 
00061     # for segment [l][0] -> [l][l] (1->3)
00062     a = (D[3][0]-D[1][0])**2+(D[3][1]-D[1][1])**2
00063     b = 2*((D[3][0]-D[1][0])*(D[1][0]-center[0])+(D[3][1]-D[1][1])*(D[1][1]-center[1]))
00064     c = center[0]**2 + center[1]**2 + D[1][0]**2 + D[1][1]**2 - 2*(center[0]*D[1][0]+center[1]*D[1][1])-r**2
00065 
00066     delta = b*b-4*a*c
00067 
00068     if delta < 0:
00069         pass
00070     elif delta >= 0:
00071         return False
00072 
00073     # return True if all deltas less than 0
00074     return True
00075 
00076 def weighted_choice(weights):
00077     totals = []
00078     running_total = 0
00079 
00080     for w in weights:
00081         running_total += w
00082         totals.append(running_total)
00083 
00084     rnd = random.random() * running_total
00085 
00086     for i, total in enumerate(totals):
00087         if rnd < total:
00088             return i
00089 
00090 
00091 def point_belongs_square_area(p,l):
00092 
00093     D = [[0,0],[l,0],[0,l],[l,l]]
00094 
00095     if ((p[0] > 0) & (p[0] < l)) & ((p[1] > 0) & (p[1] < l)):
00096         return True
00097     else:
00098         return False
00099 
00100 
00101 def proximity_test(pz,p,d0):
00102 
00103     for node in enumerate(p):
00104         distance = math.sqrt((node[1][0]-pz[0])**2+(node[1][1]-pz[1])**2)
00105         if (distance < d0) & (distance > 0):
00106             return False
00107     return True
00108 
00109 
00110 def form_candidate_graph(S,p,gtr):
00111     
00112     # create empty dictionaries
00113     Gc = {}
00114     neighbours = {}
00115 
00116     for i in range(0,len(S)):
00117         for j in range(0,len(S)):
00118             if i != j:
00119                 distance = math.sqrt((p[j][0]-p[i][0])**2+(p[j][1]-p[i][1])**2)
00120                 if distance <= gtr:
00121                     neighbours[S[j]] = distance
00122         Gc[S[i]] = neighbours
00123         neighbours = {}
00124     
00125     return Gc
00126 
00127 
00128 def min_dpa(N,d,l,d0):
00129     
00130     r = math.sqrt((d*l*l)/(math.pi*(N-1)))
00131     
00132     connected = False  
00133     while not connected:
00134 
00135         # graph construction initial step: create first node randomly
00136         x = random.random()*l
00137         y = random.random()*l
00138         p = [[x,y]]
00139         S = ['node_1']
00140         
00141         # for the next rounds (>= 2nd round)
00142         for k in range(2, N):
00143 
00144             degrees = calculate_approximate_degrees(S,p,r) #of all nodes in Sk-1
00145 
00146             L = min(degrees) # min of approximate degrees
00147 
00148             weight = [0]*len(S)
00149 
00150             # for each node m in Sk-1 that has degree L do:
00151             for m, node in enumerate(S):
00152                 if degrees[m] == L:
00153                     if disk_belongs_square_area(p[m], r, l):
00154                         weight[m] = 1
00155                     else:
00156                         weight[m] = 2./3
00157         
00158             # C(xc,yc) = randomize_center_select(weight)
00159             i = weighted_choice(weight)
00160             xc = p[i][0]
00161             yc = p[i][1]
00162 
00163             accepted = False
00164             while not accepted:
00165                 v = random.random()*(r**2)
00166                 a = math.sqrt(v)
00167                 theta = random.random()*(2*math.pi)
00168                 xz = xc + a*math.cos(theta)
00169                 yz = yc + a*math.sin(theta)
00170 
00171                 if not point_belongs_square_area([xz,yz],l):
00172                     print "New point not accepted: outside square region"
00173                 elif not proximity_test([xz,yz],p,d0):
00174                     print "New point not accepted: failed proximity test"
00175                 else:
00176                     p.append([xz,yz])
00177                     S.append('node_'+str(k))
00178                     accepted = True
00179 
00180         # Calculate edge lenghts lij = norm(pi,pj)
00181         edge_ij = []
00182         for i in range(0,len(S)):
00183             for j in range(i+1,len(S)):
00184                 edge_ij.append(math.sqrt(math.pow((p[i][0]-p[j][0]),2)+math.pow((p[i][1]-p[j][1]),2)))
00185 
00186         # Sort lij i,j in {1,2,..., N}
00187         edge_ij.sort()
00188 
00189         # Select ((N*d)/2) shortest (to determine the actual transmition radius of the graph)
00190         try:
00191             graph_transmition_radius = edge_ij.pop((N*d)/2)
00192 
00193             # Form candidate graph Gc with ((N*d)/2) edges
00194             graph = form_candidate_graph(S,p,graph_transmition_radius)
00195 
00196             # Run Dijkstra for Gc
00197             Distances,Predecessors = dijkstra.Dijkstra(graph,S[0])
00198 
00199             # if all costs finite the connected will be True
00200             for i in graph:
00201                 for j in graph[i]:
00202                     if graph[i][j] != numpy.inf:
00203                         connected = True
00204                     else:
00205                         connected = False
00206         except IndexError:
00207             print "Approximate degrees to high for the number of total nodes!"
00208             S = []
00209             p = []
00210             graph = {}
00211             return S,p,graph
00212 
00213     return S,p,graph


saap_pkg
Author(s): Joao Manuel Leitao Quintas
autogenerated on Mon Jan 6 2014 11:26:19