Changeset 7963:aad78c2dc66d in orange
 Timestamp:
 06/01/11 15:56:02 (3 years ago)
 Branch:
 default
 Convert:
 2aca6d5263c5829b62160a2d4fb88226d73bc057
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

orange/Orange/network/network.py
r7949 r7963 1 import math 2 import numpy 1 3 import networkx as nx 2 import readwrite 4 3 5 import Orange 4 6 import orangeom 5 7 8 import readwrite 9 6 10 from networkx import algorithms 7 11 from networkx.classes import function 12 13 14 class MdsTypeClass(): 15 def __init__(self): 16 self.componentMDS = 0 17 self.exactSimulation = 1 18 self.MDS = 2 19 20 MdsType = MdsTypeClass() 21 8 22 9 23 class BaseGraph(): … … 106 120 107 121 def __init__(self): 108 pass 109 122 self.graph = None 123 self.items_matrix = None 124 110 125 def set_graph(self, graph=None, positions=None): 111 126 """Initialize graph structure … … 114 129 115 130 """ 131 self.graph = graph 132 116 133 if positions is not None and len(positions) == graph.number_of_nodes(): 117 134 orangeom.GraphLayout.set_graph(self, graph, positions) … … 181 198 self.coors[1][component] = y + y_center 182 199 200 def rotate_components(self, maxSteps=100, minMoment=0.000000001, 201 callbackProgress=None, callbackUpdateCanvas=None): 202 """Rotate the network components using a spring model.""" 203 if self.items_matrix == None: 204 return 1 205 206 if self.graph == None: 207 return 1 208 209 if self.items_matrix.dim != self.graph.number_of_nodes(): 210 return 1 211 212 self.stopRotate = 0 213 214 # rotate only components with more than one vertex 215 components = [component for component \ 216 in Orange.network.nx.algorithms.components.connected_components(self.graph) \ 217 if len(component) > 1] 218 vertices = set(range(self.graph.number_of_nodes())) 219 step = 0 220 M = [1] 221 temperature = [[30.0, 1] for i in range(len(components))] 222 dirChange = [0] * len(components) 223 while step < maxSteps and (max(M) > minMoment or \ 224 min(M) < minMoment) and not self.stopRotate: 225 M = [0] * len(components) 226 227 for i in range(len(components)): 228 component = components[i] 229 230 outer_vertices = vertices  set(component) 231 232 x = self.coors[0][component] 233 y = self.coors[1][component] 234 235 x_center = x.mean() 236 y_center = y.mean() 237 238 for j in range(len(component)): 239 u = component[j] 240 241 for v in outer_vertices: 242 d = self.items_matrix[u, v] 243 u_x = self.coors[0][u] 244 u_y = self.coors[1][u] 245 v_x = self.coors[0][v] 246 v_y = self.coors[1][v] 247 L = [(u_x  v_x), (u_y  v_y)] 248 R = [(u_x  x_center), (u_y  y_center)] 249 e = math.sqrt((v_x  x_center) ** 2 + \ 250 (v_y  y_center) ** 2) 251 252 M[i] += (1  d) / (e ** 2) * numpy.cross(R, L) 253 254 tmpM = numpy.array(M) 255 #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM)) 256 257 phi = [0] * len(components) 258 #print "rotating", temperature, M 259 for i in range(len(M)): 260 if M[i] > 0: 261 if temperature[i][1] < 0: 262 temperature[i][0] = temperature[i][0] * 5 / 10 263 temperature[i][1] = 1 264 dirChange[i] += 1 265 266 phi[i] = temperature[i][0] * numpy.pi / 180 267 elif M[i] < 0: 268 if temperature[i][1] > 0: 269 temperature[i][0] = temperature[i][0] * 5 / 10 270 temperature[i][1] = 1 271 dirChange[i] += 1 272 273 phi[i] = temperature[i][0] * numpy.pi / 180 274 275 # stop rotating when phi is to small to notice the rotation 276 if max(phi) < numpy.pi / 1800: 277 #print "breaking" 278 break 279 280 self.rotate_vertices(components, phi) 281 if callbackUpdateCanvas: callbackUpdateCanvas() 282 if callbackProgress : callbackProgress(min([dirChange[i] for i \ 283 in range(len(dirChange)) if M[i] != 0]), 9) 284 step += 1 285 286 def mds_update_data(self, components, mds, callbackUpdateCanvas): 287 """Translate and rotate the network components to computed positions.""" 288 component_props = [] 289 x_mds = [] 290 y_mds = [] 291 phi = [None] * len(components) 292 self.diag_coors = math.sqrt(( \ 293 min(self.coors[0])  max(self.coors[0]))**2 + \ 294 (min(self.coors[1])  max(self.coors[1]))**2) 295 296 if self.mdsType == MdsType.MDS: 297 x = [mds.points[u][0] for u in range(self.graph.number_of_nodes())] 298 y = [mds.points[u][1] for u in range(self.graph.number_of_nodes())] 299 self.coors[0][range(self.graph.number_of_nodes())] = x 300 self.coors[1][range(self.graph.number_of_nodes())] = y 301 if callbackUpdateCanvas: 302 callbackUpdateCanvas() 303 return 304 305 for i in range(len(components)): 306 component = components[i] 307 308 if len(mds.points) == len(components): # if average linkage before 309 x_avg_mds = mds.points[i][0] 310 y_avg_mds = mds.points[i][1] 311 else: # if not average linkage before 312 x = [mds.points[u][0] for u in component] 313 y = [mds.points[u][1] for u in component] 314 315 x_avg_mds = sum(x) / len(x) 316 y_avg_mds = sum(y) / len(y) 317 # compute rotation angle 318 c = [numpy.linalg.norm(numpy.cross(mds.points[u], \ 319 [self.coors[0][u],self.coors[1][u]])) \ 320 for u in component] 321 n = [numpy.vdot([self.coors[0][u], \ 322 self.coors[1][u]], \ 323 [self.coors[0][u], \ 324 self.coors[1][u]]) for u in component] 325 phi[i] = sum(c) / sum(n) 326 #print phi 327 328 x = self.coors[0][component] 329 y = self.coors[1][component] 330 331 x_avg_graph = sum(x) / len(x) 332 y_avg_graph = sum(y) / len(y) 333 334 x_mds.append(x_avg_mds) 335 y_mds.append(y_avg_mds) 336 337 component_props.append((x_avg_graph, y_avg_graph, \ 338 x_avg_mds, y_avg_mds, phi)) 339 340 w = max(self.coors[0])  min(self.coors[0]) 341 h = max(self.coors[1])  min(self.coors[1]) 342 d = math.sqrt(w**2 + h**2) 343 #d = math.sqrt(w*h) 344 e = [math.sqrt((self.coors[0][u]  self.coors[0][v])**2 + 345 (self.coors[1][u]  self.coors[1][v])**2) for 346 (u, v) in self.graph.edges()] 347 348 if self.scalingRatio == 0: 349 pass 350 elif self.scalingRatio == 1: 351 self.mdsScaleRatio = d 352 elif self.scalingRatio == 2: 353 self.mdsScaleRatio = d / sum(e) * float(len(e)) 354 elif self.scalingRatio == 3: 355 self.mdsScaleRatio = 1 / sum(e) * float(len(e)) 356 elif self.scalingRatio == 4: 357 self.mdsScaleRatio = w * h 358 elif self.scalingRatio == 5: 359 self.mdsScaleRatio = math.sqrt(w * h) 360 elif self.scalingRatio == 6: 361 self.mdsScaleRatio = 1 362 elif self.scalingRatio == 7: 363 e_fr = 0 364 e_count = 0 365 for i in range(self.graph.number_of_nodes()): 366 for j in range(i + 1, self.graph.number_of_nodes()): 367 x1 = self.coors[0][i] 368 y1 = self.coors[1][i] 369 x2 = self.coors[0][j] 370 y2 = self.coors[1][j] 371 e_fr += math.sqrt((x1x2)**2 + (y1y2)**2) 372 e_count += 1 373 self.mdsScaleRatio = e_fr / e_count 374 elif self.scalingRatio == 8: 375 e_fr = 0 376 e_count = 0 377 for i in range(len(components)): 378 for j in range(i + 1, len(components)): 379 x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \ 380 y_avg_mds_i, phi_i = component_props[i] 381 x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \ 382 y_avg_mds_j, phi_j = component_props[j] 383 e_fr += math.sqrt((x_avg_graph_ix_avg_graph_j)**2 + \ 384 (y_avg_graph_iy_avg_graph_j)**2) 385 e_count += 1 386 self.mdsScaleRatio = e_fr / e_count 387 elif self.scalingRatio == 9: 388 e_fr = 0 389 e_count = 0 390 for i in range(len(components)): 391 component = components[i] 392 x = self.coors[0][component] 393 y = self.coors[1][component] 394 for i in range(len(x)): 395 for j in range(i + 1, len(y)): 396 x1 = x[i] 397 y1 = y[i] 398 x2 = x[j] 399 y2 = y[j] 400 e_fr += math.sqrt((x1x2)**2 + (y1y2)**2) 401 e_count += 1 402 self.mdsScaleRatio = e_fr / e_count 403 404 diag_mds = math.sqrt((max(x_mds)  min(x_mds))**2 + (max(y_mds)  \ 405 min(y_mds))**2) 406 e = [math.sqrt((self.coors[0][u]  self.coors[0][v])**2 + 407 (self.coors[1][u]  self.coors[1][v])**2) for 408 (u, v) in self.graph.edges()] 409 e = sum(e) / float(len(e)) 410 411 x = [mds.points[u][0] for u in range(len(mds.points))] 412 y = [mds.points[u][1] for u in range(len(mds.points))] 413 w = max(x)  min(x) 414 h = max(y)  min(y) 415 d = math.sqrt(w**2 + h**2) 416 417 if len(x) == 1: 418 r = 1 419 else: 420 if self.scalingRatio == 0: 421 r = self.mdsScaleRatio / d * e 422 elif self.scalingRatio == 1: 423 r = self.mdsScaleRatio / d 424 elif self.scalingRatio == 2: 425 r = self.mdsScaleRatio / d * e 426 elif self.scalingRatio == 3: 427 r = self.mdsScaleRatio * e 428 elif self.scalingRatio == 4: 429 r = self.mdsScaleRatio / (w * h) 430 elif self.scalingRatio == 5: 431 r = self.mdsScaleRatio / math.sqrt(w * h) 432 elif self.scalingRatio == 6: 433 r = 1 / math.sqrt(self.graph.number_of_nodes()) 434 elif self.scalingRatio == 7: 435 e_mds = 0 436 e_count = 0 437 for i in range(len(mds.points)): 438 for j in range(i): 439 x1 = mds.points[i][0] 440 y1 = mds.points[i][1] 441 x2 = mds.points[j][0] 442 y2 = mds.points[j][1] 443 e_mds += math.sqrt((x1x2)**2 + (y1y2)**2) 444 e_count += 1 445 r = self.mdsScaleRatio / e_mds * e_count 446 elif self.scalingRatio == 8: 447 e_mds = 0 448 e_count = 0 449 for i in range(len(components)): 450 for j in range(i + 1, len(components)): 451 x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, \ 452 y_avg_mds_i, phi_i = component_props[i] 453 x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, \ 454 y_avg_mds_j, phi_j = component_props[j] 455 e_mds += math.sqrt((x_avg_mds_ix_avg_mds_j)**2 + \ 456 (y_avg_mds_iy_avg_mds_j)**2) 457 e_count += 1 458 r = self.mdsScaleRatio / e_mds * e_count 459 elif self.scalingRatio == 9: 460 e_mds = 0 461 e_count = 0 462 for i in range(len(mds.points)): 463 for j in range(i): 464 x1 = mds.points[i][0] 465 y1 = mds.points[i][1] 466 x2 = mds.points[j][0] 467 y2 = mds.points[j][1] 468 e_mds += math.sqrt((x1x2)**2 + (y1y2)**2) 469 e_count += 1 470 r = self.mdsScaleRatio / e_mds * e_count 471 472 #r = self.mdsScaleRatio / d 473 #print "d", d, "r", r 474 #r = self.mdsScaleRatio / math.sqrt(self.graph.number_of_nodes()) 475 476 for i in range(len(components)): 477 component = components[i] 478 x_avg_graph, y_avg_graph, x_avg_mds, \ 479 y_avg_mds, phi = component_props[i] 480 481 # if phi[i]: # rotate vertices 482 # #print "rotate", i, phi[i] 483 # r = numpy.array([[numpy.cos(phi[i]), numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]]) #rotation matrix 484 # c = [x_avg_graph, y_avg_graph] # center of mass in FR coordinate system 485 # v = [numpy.dot(numpy.array([self.coors[0][u], self.coors[1][u]])  c, r) + c for u in component] 486 # self.coors[0][component] = [u[0] for u in v] 487 # self.coors[1][component] = [u[1] for u in v] 488 489 # translate vertices 490 if not self.rotationOnly: 491 self.coors[0][component] = \ 492 (self.coors[0][component]  x_avg_graph) / r + x_avg_mds 493 self.coors[1][component] = \ 494 (self.coors[1][component]  y_avg_graph) / r + y_avg_mds 495 496 if callbackUpdateCanvas: 497 callbackUpdateCanvas() 498 499 def mds_callback(self, a, b=None): 500 """Refresh the UI when running MDS on network components.""" 501 if not self.mdsStep % self.mdsRefresh: 502 self.mds_update_data(self.mdsComponentList, 503 self.mds, 504 self.callbackUpdateCanvas) 505 506 if self.mdsType == MdsType.exactSimulation: 507 self.mds.points = [[self.coors[0][i], \ 508 self.coors[1][i]] \ 509 for i in range(len(self.coors))] 510 self.mds.freshD = 0 511 512 if self.callbackProgress != None: 513 self.callbackProgress(self.mds.avg_stress, self.mdsStep) 514 515 self.mdsStep += 1 516 517 if self.stopMDS: 518 return 0 519 else: 520 return 1 521 522 def mds_components(self, mdsSteps, mdsRefresh, callbackProgress=None, \ 523 callbackUpdateCanvas=None, torgerson=0, \ 524 minStressDelta=0, avgLinkage=False, rotationOnly=False,\ 525 mdsType=MdsType.componentMDS, scalingRatio=0, \ 526 mdsFromCurrentPos=0): 527 """Position the network components according to similarities among 528 them. 529 530 """ 531 532 if self.items_matrix == None: 533 self.information('Set distance matrix to input signal') 534 return 1 535 536 if self.graph == None: 537 return 1 538 539 if self.items_matrix.dim != self.graph.number_of_nodes(): 540 return 1 541 542 self.mdsComponentList = Orange.network.nx.algorithms.components.connected_components(self.graph) 543 self.mdsRefresh = mdsRefresh 544 self.mdsStep = 0 545 self.stopMDS = 0 546 self.items_matrix.matrixType = Orange.core.SymMatrix.Symmetric 547 self.diag_coors = math.sqrt((min(self.coors[0])  \ 548 max(self.coors[0]))**2 + \ 549 (min(self.coors[1])  \ 550 max(self.coors[1]))**2) 551 self.rotationOnly = rotationOnly 552 self.mdsType = mdsType 553 self.scalingRatio = scalingRatio 554 555 w = max(self.coors[0])  min(self.coors[0]) 556 h = max(self.coors[1])  min(self.coors[1]) 557 d = math.sqrt(w**2 + h**2) 558 #d = math.sqrt(w*h) 559 e = [math.sqrt((self.coors[0][u]  self.coors[0][v])**2 + 560 (self.coors[1][u]  self.coors[1][v])**2) for 561 (u, v) in self.graph.edges()] 562 self.mdsScaleRatio = d / sum(e) * float(len(e)) 563 #print d / sum(e) * float(len(e)) 564 565 if avgLinkage: 566 matrix = self.items_matrix.avgLinkage(self.mdsComponentList) 567 else: 568 matrix = self.items_matrix 569 570 #if self.mds == None: 571 self.mds = Orange.projection.mds.MDS(matrix) 572 573 if mdsFromCurrentPos: 574 if avgLinkage: 575 for u, c in enumerate(self.mdsComponentList): 576 x = sum(self.coors[0][c]) / len(c) 577 y = sum(self.coors[1][c]) / len(c) 578 self.mds.points[u][0] = x 579 self.mds.points[u][1] = y 580 else: 581 for u in range(self.graph.number_of_nodes()): 582 self.mds.points[u][0] = self.coors[0][u] 583 self.mds.points[u][1] = self.coors[1][u] 584 585 # set min stress difference between 0.01 and 0.00001 586 self.minStressDelta = minStressDelta 587 self.callbackUpdateCanvas = callbackUpdateCanvas 588 self.callbackProgress = callbackProgress 589 590 if torgerson: 591 self.mds.Torgerson() 592 593 self.mds.optimize(mdsSteps, Orange.projection.mds.SgnRelStress, self.minStressDelta,\ 594 progress_callback=self.mds_callback) 595 self.mds_update_data(self.mdsComponentList, self.mds, callbackUpdateCanvas) 596 597 if callbackProgress != None: 598 callbackProgress(self.mds.avg_stress, self.mdsStep) 599 600 del self.rotationOnly 601 del self.diag_coors 602 del self.mdsRefresh 603 del self.mdsStep 604 #del self.mds 605 del self.mdsComponentList 606 del self.minStressDelta 607 del self.callbackUpdateCanvas 608 del self.callbackProgress 609 del self.mdsType 610 del self.mdsScaleRatio 611 del self.scalingRatio 612 return 0 613 614 def mds_components_avg_linkage(self, mdsSteps, mdsRefresh, \ 615 callbackProgress=None, \ 616 callbackUpdateCanvas=None, torgerson=0, \ 617 minStressDelta = 0, scalingRatio=0,\ 618 mdsFromCurrentPos=0): 619 return self.mds_components(mdsSteps, mdsRefresh, callbackProgress, \ 620 callbackUpdateCanvas, torgerson, \ 621 minStressDelta, True, \ 622 scalingRatio=scalingRatio, \ 623 mdsFromCurrentPos=mdsFromCurrentPos) 624 625 ########################################################################## 626 ### BEGIN: DEPRECATED METHODS (TO DELETE IN ORANGE 3.0) ### 627 ########################################################################## 628 629 630 631
Note: See TracChangeset
for help on using the changeset viewer.