[31] | 1 | package vnsim.socialNet; |
---|
| 2 | |
---|
| 3 | import java.io.File; |
---|
| 4 | import java.io.FileInputStream; |
---|
| 5 | import java.io.ObjectInputStream; |
---|
| 6 | import java.util.ArrayList; |
---|
| 7 | |
---|
| 8 | import vnsim.map.object.Globals; |
---|
| 9 | import vnsim.map.object.Map; |
---|
| 10 | import vnsim.map.object.Point; |
---|
| 11 | import vnsim.map.object.Road; |
---|
| 12 | import vnsim.vehicular.scenarios.Route; |
---|
| 13 | import vnsim.vehicular.routePlan.*; |
---|
| 14 | |
---|
| 15 | public class Util { |
---|
| 16 | |
---|
| 17 | public static void getCellSize(String nume){ |
---|
| 18 | try { |
---|
| 19 | |
---|
| 20 | ObjectInputStream ois=new ObjectInputStream(new FileInputStream(System.getProperty("user.home") + File.separatorChar + "maps" + |
---|
| 21 | File.separatorChar + "map" + File.separatorChar + nume)); |
---|
| 22 | |
---|
| 23 | Map currentMap=(vnsim.map.object.Map)ois.readObject(); |
---|
| 24 | Globals.map = currentMap; |
---|
| 25 | |
---|
| 26 | Point tmpPoint, minPoint, maxPoint; |
---|
| 27 | Road tmpRoad; |
---|
| 28 | int i, j; |
---|
| 29 | i = 0; |
---|
| 30 | //currentMap = Globals.map; |
---|
| 31 | |
---|
| 32 | minPoint = new Point((double) 180, (double) 90); |
---|
| 33 | maxPoint = new Point((double) -180, (double) -90); |
---|
| 34 | while (i < currentMap.roads.size()) { |
---|
| 35 | tmpRoad = (Road) currentMap.roads.get(i); |
---|
| 36 | j = 0; |
---|
| 37 | while (j < tmpRoad.points.size()) {// for evey points from the selected road |
---|
| 38 | tmpPoint = (Point) tmpRoad.points.get(j); |
---|
| 39 | if (tmpPoint.getLatitude() < minPoint.getLatitude()) { |
---|
| 40 | minPoint.setLatitude(tmpPoint.getLatitude()); |
---|
| 41 | } |
---|
| 42 | if (tmpPoint.getLongitude() < minPoint.getLongitude()) { |
---|
| 43 | minPoint.setLongitude(tmpPoint.getLongitude()); |
---|
| 44 | } |
---|
| 45 | |
---|
| 46 | if (tmpPoint.getLatitude() > maxPoint.getLatitude()) { |
---|
| 47 | maxPoint.setLatitude(tmpPoint.getLatitude()); |
---|
| 48 | } |
---|
| 49 | if (tmpPoint.getLongitude() > maxPoint.getLongitude()) { |
---|
| 50 | maxPoint.setLongitude(tmpPoint.getLongitude()); |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | j++; |
---|
| 54 | } |
---|
| 55 | i++; |
---|
| 56 | } |
---|
| 57 | //System.out.println("Pct maxim ( "+maxPoint.getLatitude()+" "+maxPoint.getLongitude()+" )"); |
---|
| 58 | //System.out.println("Pct min ( "+minPoint.getLatitude()+" "+minPoint.getLongitude()+" )"); |
---|
| 59 | |
---|
| 60 | GlobalNetwork.pointMax = maxPoint; |
---|
| 61 | GlobalNetwork.pointMin = minPoint; |
---|
| 62 | |
---|
| 63 | ois.close(); |
---|
| 64 | } catch (Exception ex) { |
---|
| 65 | ex.printStackTrace(); |
---|
| 66 | //throw ex; |
---|
| 67 | } |
---|
| 68 | } |
---|
| 69 | |
---|
| 70 | public static boolean intersecRoad(CellInformation ci){ |
---|
| 71 | Map currentMap = Globals.map; |
---|
| 72 | Point tmpPoint; |
---|
| 73 | Road tmpRoad; |
---|
| 74 | int i, j; |
---|
| 75 | boolean gasit = false; |
---|
| 76 | i = 0; |
---|
| 77 | while (i < currentMap.roads.size()) { |
---|
| 78 | tmpRoad = (Road) currentMap.roads.get(i); |
---|
| 79 | j = 0; |
---|
| 80 | while (j < tmpRoad.points.size()){ |
---|
| 81 | tmpPoint = (Point) tmpRoad.points.get(j); |
---|
| 82 | if((ci.pointMin.getLatitude()<tmpPoint.getLatitude())&&(tmpPoint.getLatitude()<ci.pointMax.getLatitude())){ |
---|
| 83 | if((ci.pointMin.getLongitude()<tmpPoint.getLongitude())&&(tmpPoint.getLongitude()<ci.pointMax.getLongitude())){ |
---|
| 84 | ci.addValidPoint(tmpPoint); |
---|
| 85 | ci.addValidLocation(i, j); |
---|
| 86 | gasit = true; |
---|
| 87 | } |
---|
| 88 | } |
---|
| 89 | j++; |
---|
| 90 | } |
---|
| 91 | i++; |
---|
| 92 | } |
---|
| 93 | return gasit; |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | public static boolean isInGroup(int i,int group[],int members){ |
---|
| 97 | boolean result=false; |
---|
| 98 | |
---|
| 99 | for (int k=0;k<members;k++) |
---|
| 100 | if (group[k]==i) { |
---|
| 101 | result=true; |
---|
| 102 | } |
---|
| 103 | return result; |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | public static boolean areInAGroup(int i,int j,int groups[][],int nrGroups,int numberOfMembers[]){ |
---|
| 107 | |
---|
| 108 | boolean result=false; |
---|
| 109 | |
---|
| 110 | for (int k=0;k<nrGroups;k++) { |
---|
| 111 | |
---|
| 112 | if (isInGroup(i,groups[k],numberOfMembers[k])) |
---|
| 113 | if (isInGroup(j,groups[k],numberOfMembers[k])) { |
---|
| 114 | result=true; |
---|
| 115 | } |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | return result; |
---|
| 119 | } |
---|
| 120 | |
---|
| 121 | public static void assign_distance(double distance[], int d, int assigned[], ArrayList<NodeInformation> ni, int pred[][], int predNum[], int nrHosts) { |
---|
| 122 | |
---|
| 123 | for (int k=0;k<nrHosts; k++) |
---|
| 124 | if (distance[k]==d) { |
---|
| 125 | for (int r=0;r<nrHosts;r++) |
---|
| 126 | if (ni.get(k).getAdjacency(r)==1) |
---|
| 127 | if (assigned[r]==1) { |
---|
| 128 | distance[r]=d+1; |
---|
| 129 | assigned[r]=0; |
---|
| 130 | boolean found=false; |
---|
| 131 | for (int p=0;p<predNum[r]; p++) |
---|
| 132 | if (pred[r][p]==k) found=true; |
---|
| 133 | if (found==false) { |
---|
| 134 | pred[r][predNum[r]]=k; |
---|
| 135 | predNum[r]=predNum[r]+1; |
---|
| 136 | } |
---|
| 137 | } |
---|
| 138 | } |
---|
| 139 | |
---|
| 140 | } |
---|
| 141 | |
---|
| 142 | public static void calculate_b (double betw[], double distance[], int pred[][], int predNum[], int nrHosts) { |
---|
| 143 | |
---|
| 144 | for (int dist=15;dist>-1;dist--) |
---|
| 145 | |
---|
| 146 | for (int k=0; k<nrHosts; k++) |
---|
| 147 | if (distance[k]==dist) { |
---|
| 148 | for (int i=0; i<predNum[k]; i++) { |
---|
| 149 | betw[pred[k][i]]=betw[pred[k][i]]+betw[k]/predNum[k]; |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | } |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | public static void calculate_betweenness(double res_betw[],ArrayList<NodeInformation> ni,int nrHosts){ |
---|
| 156 | |
---|
| 157 | double distance[]= new double[nrHosts]; |
---|
| 158 | int assigned[]= new int[nrHosts]; |
---|
| 159 | int predNum[]= new int[nrHosts]; |
---|
| 160 | double betw[]= new double[nrHosts]; |
---|
| 161 | double current_betw[]=new double[nrHosts]; |
---|
| 162 | |
---|
| 163 | for (int i=0; i<nrHosts;i++) { |
---|
| 164 | assigned[i]=1; |
---|
| 165 | distance[i]=15; |
---|
| 166 | betw[i]=1; |
---|
| 167 | current_betw[i]=0; |
---|
| 168 | } |
---|
| 169 | |
---|
| 170 | int pred[][]= new int[nrHosts][nrHosts]; |
---|
| 171 | |
---|
| 172 | for (int i=0; i<nrHosts; i++) { |
---|
| 173 | for (int s=0; s<nrHosts;s++) { |
---|
| 174 | assigned[s]=1; |
---|
| 175 | distance[s]=16; |
---|
| 176 | predNum[s]=0; |
---|
| 177 | betw[s]=1; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | assigned[i]=0; |
---|
| 181 | distance[i]=0; |
---|
| 182 | for (int d=0;d<15;d++) |
---|
| 183 | assign_distance(distance,d,assigned,ni,pred,predNum,nrHosts); |
---|
| 184 | |
---|
| 185 | calculate_b(betw, distance, pred, predNum,nrHosts); |
---|
| 186 | |
---|
| 187 | for (int z=0;z<nrHosts;z++) { |
---|
| 188 | current_betw[z]=current_betw[z]+betw[z]; |
---|
| 189 | } |
---|
| 190 | } |
---|
| 191 | |
---|
| 192 | for (int z=0;z<nrHosts;z++) |
---|
| 193 | res_betw[z]=current_betw[z]; |
---|
| 194 | |
---|
| 195 | } |
---|
| 196 | |
---|
| 197 | public static void assignToAGroup (int current, int currentGroup, ArrayList<NodeInformation> ni, ArrayList<Integer> groups,int nrHosts,boolean assigned[]) { |
---|
| 198 | |
---|
| 199 | for (int k=0;k<nrHosts;k++) |
---|
| 200 | |
---|
| 201 | if (ni.get(current).getAdjacency(k)==1) |
---|
| 202 | if (current!=k) |
---|
| 203 | if (assigned[k]==false) { |
---|
| 204 | groups.add(k+1); |
---|
| 205 | assigned[k]=true; |
---|
| 206 | assignToAGroup(k,currentGroup,ni, groups, nrHosts, assigned); |
---|
| 207 | } |
---|
| 208 | } |
---|
| 209 | |
---|
| 210 | public static int getGroups(ArrayList<NodeInformation> ni,ArrayList<ArrayList<Integer>> groups, int nrHosts) { |
---|
| 211 | |
---|
| 212 | int numberOfGroups=0; |
---|
| 213 | boolean assigned[] = new boolean[nrHosts]; |
---|
| 214 | |
---|
| 215 | for (int i=0; i<nrHosts; i++) { |
---|
| 216 | assigned[i]=false; |
---|
| 217 | } |
---|
| 218 | |
---|
| 219 | for (int i=0; i<nrHosts; i++) { |
---|
| 220 | |
---|
| 221 | if (assigned[i]==false) { |
---|
| 222 | numberOfGroups++; |
---|
| 223 | ArrayList<Integer> aux = new ArrayList<Integer>(); |
---|
| 224 | aux.add(new Integer(i+1)); |
---|
| 225 | assigned[i]=true; |
---|
| 226 | assignToAGroup(i,numberOfGroups,ni, aux, nrHosts, assigned); |
---|
| 227 | groups.add(aux); |
---|
| 228 | } |
---|
| 229 | } |
---|
| 230 | return numberOfGroups; |
---|
| 231 | } |
---|
| 232 | |
---|
| 233 | public static boolean inGroup(int i,ArrayList<Integer> group){ |
---|
| 234 | boolean result=false; |
---|
| 235 | |
---|
| 236 | for (int k=0;k<group.size();k++) |
---|
| 237 | if (group.get(k).intValue()==i) { |
---|
| 238 | result=true; |
---|
| 239 | } |
---|
| 240 | return result; |
---|
| 241 | } |
---|
| 242 | |
---|
| 243 | public static boolean areInSameGroup(int i,int j,ArrayList<ArrayList<Integer>> groups,int nrGroups){ |
---|
| 244 | |
---|
| 245 | boolean result=false; |
---|
| 246 | |
---|
| 247 | for (int k=0;k<nrGroups;k++) { |
---|
| 248 | |
---|
| 249 | if (inGroup(i,groups.get(k))) |
---|
| 250 | if (inGroup(j,groups.get(k))) { |
---|
| 251 | result=true; |
---|
| 252 | } |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | return result; |
---|
| 256 | } |
---|
| 257 | |
---|
| 258 | public static void splitNetwork (ArrayList<NodeInformation> ni, double betw[],int nrHosts) { |
---|
| 259 | |
---|
| 260 | int best=0; |
---|
| 261 | double bestBetw=0; |
---|
| 262 | |
---|
| 263 | double betw2[] = new double[nrHosts]; |
---|
| 264 | |
---|
| 265 | for (int i=0;i<nrHosts;i++) { |
---|
| 266 | if (betw[i]>bestBetw) { |
---|
| 267 | bestBetw=betw[i]; |
---|
| 268 | best=i; |
---|
| 269 | } |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | double minBetw=bestBetw; |
---|
| 273 | int linkToDelete=0; |
---|
| 274 | for (int i=0;i<nrHosts;i++) { |
---|
| 275 | if ((ni.get(best).getAdjacency(i)==1)&&(best!=i)){ |
---|
| 276 | ni.get(best).setAdjacency(i, 0); |
---|
| 277 | ni.get(i).setAdjacency(best, 0); |
---|
| 278 | calculate_betweenness(betw2, ni, nrHosts); |
---|
| 279 | if (betw2[best]<minBetw) { |
---|
| 280 | minBetw=betw2[best]; |
---|
| 281 | linkToDelete=i; |
---|
| 282 | } |
---|
| 283 | ni.get(best).setAdjacency(i, 1); |
---|
| 284 | ni.get(i).setAdjacency(best, 1); |
---|
| 285 | |
---|
| 286 | } |
---|
| 287 | } |
---|
| 288 | |
---|
| 289 | ni.get(best).setAdjacency(linkToDelete, 0); |
---|
| 290 | ni.get(linkToDelete).setAdjacency(best, 0); |
---|
| 291 | |
---|
| 292 | } |
---|
| 293 | |
---|
| 294 | |
---|
| 295 | public static double splitNetwork_Threshold (ArrayList<NodeInformation> ni, double betw[], int nrHosts, double modThreshold) { |
---|
| 296 | |
---|
| 297 | int numberOfGroups_after=0; |
---|
| 298 | double numberOfLinks_before=0; |
---|
| 299 | |
---|
| 300 | ArrayList<ArrayList<Integer>> groups_before= new ArrayList<ArrayList<Integer>>(); |
---|
| 301 | ArrayList<ArrayList<Integer>> groups_after= new ArrayList<ArrayList<Integer>>(); |
---|
| 302 | |
---|
| 303 | double totalResults[][]= new double[nrHosts][nrHosts]; |
---|
| 304 | int adjacency_before[][]= new int[nrHosts][nrHosts]; |
---|
| 305 | |
---|
| 306 | for (int i=0;i<nrHosts;i++) |
---|
| 307 | for (int j=0;j<nrHosts;j++) { |
---|
| 308 | adjacency_before[i][j]=ni.get(i).getAdjacency(j); |
---|
| 309 | } |
---|
| 310 | |
---|
| 311 | getGroups(ni, groups_before,nrHosts); |
---|
| 312 | |
---|
| 313 | splitNetwork(ni, betw, nrHosts); |
---|
| 314 | |
---|
| 315 | numberOfGroups_after=getGroups(ni, groups_after ,nrHosts); |
---|
| 316 | |
---|
| 317 | double modularity[][]= new double[nrHosts][nrHosts]; |
---|
| 318 | double modularity_num[][]= new double[nrHosts][nrHosts]; |
---|
| 319 | |
---|
| 320 | for (int i=0;i<numberOfGroups_after;i++) |
---|
| 321 | for (int j=0;j<numberOfGroups_after;j++) { |
---|
| 322 | modularity_num[i][j]=0; |
---|
| 323 | } |
---|
| 324 | |
---|
| 325 | for (int i=0;i<nrHosts;i++){ |
---|
| 326 | for (int j=0;j<nrHosts;j++) { |
---|
| 327 | if (adjacency_before[i][j]==1){ |
---|
| 328 | numberOfLinks_before=numberOfLinks_before+1; |
---|
| 329 | } |
---|
| 330 | } |
---|
| 331 | } |
---|
| 332 | |
---|
| 333 | |
---|
| 334 | for (int i=0;i<nrHosts;i++) |
---|
| 335 | for (int j=0;j<nrHosts;j++) { |
---|
| 336 | if (adjacency_before[i][j]==1) { |
---|
| 337 | for (int g1=0;g1<numberOfGroups_after;g1++) { |
---|
| 338 | if (inGroup(i+1,groups_after.get(g1))) { |
---|
| 339 | for (int g2=0;g2<numberOfGroups_after;g2++) |
---|
| 340 | if (inGroup(j+1,groups_after.get(g2))) { |
---|
| 341 | modularity_num[g1][g2]=modularity_num[g1][g2]+1; |
---|
| 342 | } |
---|
| 343 | } |
---|
| 344 | } |
---|
| 345 | } |
---|
| 346 | } |
---|
| 347 | |
---|
| 348 | for (int i=0;i<numberOfGroups_after;i++) |
---|
| 349 | for (int j=0;j<numberOfGroups_after;j++) { |
---|
| 350 | modularity[i][j]=modularity_num[i][j]/numberOfLinks_before; |
---|
| 351 | } |
---|
| 352 | |
---|
| 353 | double total1=0; |
---|
| 354 | for (int i=0;i<numberOfGroups_after;i++) |
---|
| 355 | total1=total1+modularity[i][i]; |
---|
| 356 | |
---|
| 357 | for (int i=0;i<numberOfGroups_after;i++) { |
---|
| 358 | for (int j=0;j<numberOfGroups_after;j++) { |
---|
| 359 | double partial=0; |
---|
| 360 | for (int t=0;t<numberOfGroups_after;t++) |
---|
| 361 | partial=partial+modularity[i][t]*modularity[t][j]; |
---|
| 362 | totalResults[i][j] = partial; |
---|
| 363 | } |
---|
| 364 | } |
---|
| 365 | |
---|
| 366 | double total2=0; |
---|
| 367 | for (int i=0;i<numberOfGroups_after;i++) |
---|
| 368 | for (int j=0;j<numberOfGroups_after;j++) |
---|
| 369 | total2=total2+totalResults[i][j]; |
---|
| 370 | |
---|
| 371 | double q=total1-total2; |
---|
| 372 | |
---|
| 373 | if (numberOfGroups_after==nrHosts) { |
---|
| 374 | return -1; |
---|
| 375 | } |
---|
| 376 | |
---|
| 377 | if (q>modThreshold) { |
---|
| 378 | return q; |
---|
| 379 | |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | else { |
---|
| 383 | for (int i=0;i<nrHosts;i++) |
---|
| 384 | for (int j=0;j<nrHosts;j++) { |
---|
| 385 | ni.get(i).setAdjacency(j, adjacency_before[i][j]); |
---|
| 386 | } |
---|
| 387 | return -1; |
---|
| 388 | } |
---|
| 389 | |
---|
| 390 | } |
---|
| 391 | |
---|
| 392 | } |
---|