Changeset 7259:f4f4b3ab135b in orange
 Timestamp:
 02/02/11 22:35:58 (3 years ago)
 Branch:
 default
 Convert:
 3f12ffdaa286903c0e97cfcf4772d733b1f41649
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

orange/orngNetwork.py
r7176 r7259 1 import math 2 import numpy 3 import os.path 4 import orange 5 import orangeom 6 import orngMDS 7 import random 8 import numpy 9 import itertools 10 11 class MdsTypeClass(): 12 def __init__(self): 13 self.componentMDS = 0 14 self.exactSimulation = 1 15 self.MDS = 2 1 from Orange.network import MdsTypeClass 2 from Orange.network import Network, NetworkOptimization, NetworkClustering 16 3 17 4 MdsType = MdsTypeClass() 18 19 class Network(orangeom.Network):20 """Orange data structure for representing directed and undirected networks with various types of weighted connections and other data."""21 22 def __init__(self, *args):23 #print "orngNetwork.Network"24 self.optimization = NetworkOptimization(self)25 self.clustering = NetworkClustering(self)26 27 def getDistanceMatrixThreshold(self, matrix, ratio):28 """Return lower and upper distance threshold values for given ratio of edges"""29 values = []30 for i in range(matrix.dim):31 for j in range(i):32 values.append((matrix[i,j], i, j))33 34 values.sort()35 return values[0][0], values[int(ratio*len(values))][0]36 37 def save(self, fileName):38 """Saves network to Pajek (.net) file."""39 self.saveNetwork(fileName)40 41 def saveNetwork(self, fileName):42 """Save network to file."""43 44 try:45 root, ext = os.path.splitext(fileName)46 if ext == '':47 fileName = root + '.net'48 graphFile = open(fileName, 'w+')49 except IOError:50 return 151 52 root, ext = os.path.splitext(fileName)53 if ext.lower() == ".gml":54 self.saveGML(graphFile)55 else:56 self.savePajek(graphFile)57 58 def saveGML(self, fp):59 """Save network to GML (.gml) file format."""60 61 fp.write("graph\n[\n")62 tabs = "\t"63 fp.write("%slabel\t\"%s\"\n" % (tabs, self.name))64 65 for v in range(self.nVertices):66 try:67 label = self.items[v]['label']68 except:69 label = ""70 71 fp.write("\tnode\n\t[\n\t\tid\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % (v, label))72 73 for u,v in self.getEdges():74 fp.write("\tedge\n\t[\n\t\tsource\t%d\n\t\ttarget\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % (u, v, ""))75 76 fp.write("]\n")77 78 if self.items != None and len(self.items) > 0:79 (name, ext) = os.path.splitext(fp.name)80 self.items.save(name + "_items.tab")81 82 if hasattr(self, 'links') and self.links != None and len(self.links) > 0:83 (name, ext) = os.path.splitext(fp.name)84 self.links.save(name + "_links.tab")85 86 def savePajek(self, fp):87 """Save network to Pajek (.net) file format."""88 name = ''89 fp.write('### This file was generated with Orange Network Visualizer ### \n\n\n')90 if name == '':91 fp.write('*Network ' + '"no name" \n\n')92 else:93 fp.write('*Network ' + str(name) + ' \n\n')94 95 # print node descriptions96 fp.write('*Vertices %8d %8d\n' % (self.nVertices, self.nEdgeTypes))97 for v in range(self.nVertices):98 fp.write('% 8d ' % (v + 1))99 try:100 label = self.items[v]['label']101 fp.write(str('"' + str(label) + '"') + ' \t')102 except:103 fp.write(str('"' + str(v) + '"') + ' \t')104 105 if hasattr(self, 'coors'):106 x = self.coors[0][v]107 y = self.coors[1][v]108 z = 0.5000109 fp.write('%.4f %.4f %.4f\t' % (x, y, z))110 fp.write('\n')111 112 # print edge descriptions113 # not directed edges114 if self.directed:115 fp.write('*Arcs \n')116 for (i, j) in self.getEdges():117 if len(self[i, j]) > 0:118 if self.nEdgeTypes > 1:119 edge_str = str(self[i, j])120 else:121 edge_str = "%f" % float(str(self[i, j]))122 fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))123 fp.write('\n')124 # directed edges125 else:126 fp.write('*Edges \n')127 writtenEdges = {}128 for (i, j) in self.getEdges():129 if len(self[i, j]) > 0:130 if i > j: i,j = j,i131 132 if not (i,j) in writtenEdges:133 writtenEdges[(i,j)] = 1134 else:135 continue136 137 if self.nEdgeTypes > 1:138 edge_str = str(self[i, j])139 else:140 edge_str = "%f" % float(str(self[i, j]))141 fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))142 fp.write('\n')143 144 fp.write('\n')145 146 if self.items != None and len(self.items) > 0:147 (name, ext) = os.path.splitext(fp.name)148 self.items.save(name + "_items.tab")149 150 if hasattr(self, 'links') and self.links != None and len(self.links) > 0:151 (name, ext) = os.path.splitext(fp.name)152 self.links.save(name + "_links.tab")153 154 return 0155 156 @staticmethod157 def read(fileName, directed=0):158 """Read network. Supported network formats: from Pajek (.net) file, GML."""159 if type(fileName) == file:160 root, ext = os.path.splitext(fileName.name)161 if ext.lower() == ".net":162 net = Network(2,0).parseNetwork(fileName.read(), directed)163 net.optimization = NetworkOptimization(net)164 return net165 else:166 print "invalid network type", fileName.name167 return None168 else:169 root, ext = os.path.splitext(fileName)170 net = None171 if ext.lower() == ".net":172 net = Network(2,0).readPajek(fileName, directed)173 elif ext.lower() == ".gml":174 net = Network(2,0).readGML(fileName)175 else:176 print "Invalid file type %s" % fileName177 178 if net is not None:179 net.optimization = NetworkOptimization(net)180 return net181 182 class NetworkOptimization(orangeom.NetworkOptimization):183 """main class for performing network layout optimization. Network structure is defined in orangeom.Network class."""184 185 def __init__(self, network=None, name="None"):186 if network is None:187 network = orangeom.Network(2, 0)188 189 self.setGraph(network)190 self.graph = network191 192 self.maxWidth = 1000193 self.maxHeight = 1000194 195 self.attributeList = {}196 self.attributeValues = {}197 self.vertexDistance = None198 self.mds = None199 200 def computeForces(self):201 n = self.graph.nVertices202 vertices = set(range(n))203 e_avg = 0204 edges = self.graph.getEdges()205 for u,v in edges:206 u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]])207 v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])208 e_avg += numpy.linalg.norm(u_  v_)209 e_avg /= len(edges)210 211 forces = []212 maxforce = []213 components = self.graph.getConnectedComponents()214 for component in components:215 outer_vertices = vertices  set(component)216 217 for u in component:218 u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]])219 force = numpy.array([0.0, 0.0])220 for v in outer_vertices:221 v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])222 d = self.vertexDistance[u, v]223 norm = numpy.linalg.norm(v_  u_)224 force += (d  norm) * (v_  u_) / norm225 226 forces.append(force)227 maxforce.append(numpy.linalg.norm(force))228 229 maxforce = max(maxforce)230 rv = []231 for v in range(n):232 force = forces[v]233 v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]])234 f = force * e_avg / maxforce235 rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]]))236 237 return rv238 239 def collapse(self):240 if len(self.graph.getNodes(1)) > 0:241 nodes = list(set(range(self.graph.nVertices))  set(self.graph.getNodes(1)))242 243 if len(nodes) > 0:244 subgraph = orangeom.Network(self.graph.getSubGraph(nodes))245 oldcoors = self.coors246 self.setGraph(subgraph)247 self.graph = subgraph248 249 for i in range(len(nodes)):250 self.coors[0][i] = oldcoors[0][nodes[i]]251 self.coors[1][i] = oldcoors[1][nodes[i]]252 253 else:254 fullgraphs = self.graph.getLargestFullGraphs()255 subgraph = self.graph256 257 if len(fullgraphs) > 0:258 used = set()259 graphstomerge = list()260 #print fullgraphs261 for fullgraph in fullgraphs:262 #print fullgraph263 fullgraph_set = set(fullgraph)264 if len(used & fullgraph_set) == 0:265 graphstomerge.append(fullgraph)266 used = fullgraph_set267 268 #print graphstomerge269 #print used270 subgraph = orangeom.Network(subgraph.getSubGraphMergeClusters(graphstomerge))271 272 nodescomp = list(set(range(self.graph.nVertices))  used)273 274 #subgraph.setattr("items", self.graph.items.getitems(nodescomp))275 #subgraph.items.append(self.graph.items[0])276 oldcoors = self.coors277 self.setGraph(subgraph)278 self.graph = subgraph279 for i in range(len(nodescomp)):280 self.coors[0][i] = oldcoors[0][nodescomp[i]]281 self.coors[1][i] = oldcoors[1][nodescomp[i]]282 283 # place meta vertex in center of cluster284 x, y = 0, 0285 for node in used:286 x += oldcoors[0][node]287 y += oldcoors[1][node]288 289 x = x / len(used)290 y = y / len(used)291 292 self.coors[0][len(nodescomp)] = x293 self.coors[1][len(nodescomp)] = y294 295 def getVars(self):296 vars = []297 if (self.graph != None):298 if hasattr(self.graph, "items"):299 if isinstance(self.graph.items, orange.ExampleTable):300 vars[:0] = self.graph.items.domain.variables301 302 metas = self.graph.items.domain.getmetas(0)303 for i, var in metas.iteritems():304 vars.append(var)305 return vars306 307 def getEdgeVars(self):308 vars = []309 if (self.graph != None):310 if hasattr(self.graph, "links"):311 if isinstance(self.graph.links, orange.ExampleTable):312 vars[:0] = self.graph.links.domain.variables313 314 metas = self.graph.links.domain.getmetas(0)315 for i, var in metas.iteritems():316 vars.append(var)317 318 return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v']319 320 def getData(self, i, j):321 if self.graph.items is orange.ExampleTable:322 return self.data[i][j]323 elif self.graph.data is type([]):324 return self.data[i][j]325 326 def nVertices(self):327 if self.graph:328 return self.graph.nVertices329 330 def rotateVertices(self, components, phi):331 #print phi332 for i in range(len(components)):333 if phi[i] == 0:334 continue335 336 component = components[i]337 338 x = self.graph.coors[0][component]339 y = self.graph.coors[1][component]340 341 x_center = x.mean()342 y_center = y.mean()343 344 x = x  x_center345 y = y  y_center346 347 r = numpy.sqrt(x ** 2 + y ** 2)348 fi = numpy.arctan2(y, x)349 350 fi += phi[i]351 #fi += factor * M[i] * numpy.pi / 180352 353 x = r * numpy.cos(fi)354 y = r * numpy.sin(fi)355 356 self.graph.coors[0][component] = x + x_center357 self.graph.coors[1][component] = y + y_center358 359 def rotateComponents(self, maxSteps=100, minMoment=0.000000001, callbackProgress=None, callbackUpdateCanvas=None):360 """Rotate the network components using a spring model."""361 if self.vertexDistance == None:362 return 1363 364 if self.graph == None:365 return 1366 367 if self.vertexDistance.dim != self.graph.nVertices:368 return 1369 370 self.stopRotate = 0371 372 # rotate only components with more than one vertex373 components = [component for component in self.graph.getConnectedComponents() if len(component) > 1]374 vertices = set(range(self.graph.nVertices))375 step = 0376 M = [1]377 temperature = [[30.0, 1] for i in range(len(components))]378 dirChange = [0] * len(components)379 while step < maxSteps and (max(M) > minMoment or min(M) < minMoment) and not self.stopRotate:380 M = [0] * len(components)381 382 for i in range(len(components)):383 component = components[i]384 385 outer_vertices = vertices  set(component)386 387 x = self.graph.coors[0][component]388 y = self.graph.coors[1][component]389 390 x_center = x.mean()391 y_center = y.mean()392 393 for j in range(len(component)):394 u = component[j]395 396 for v in outer_vertices:397 d = self.vertexDistance[u, v]398 u_x = self.graph.coors[0][u]399 u_y = self.graph.coors[1][u]400 v_x = self.graph.coors[0][v]401 v_y = self.graph.coors[1][v]402 L = [(u_x  v_x), (u_y  v_y)]403 R = [(u_x  x_center), (u_y  y_center)]404 e = math.sqrt((v_x  x_center) ** 2 + (v_y  y_center) ** 2)405 406 M[i] += (1  d) / (e ** 2) * numpy.cross(R, L)407 408 tmpM = numpy.array(M)409 #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM))410 411 phi = [0] * len(components)412 #print "rotating", temperature, M413 for i in range(len(M)):414 if M[i] > 0:415 if temperature[i][1] < 0:416 temperature[i][0] = temperature[i][0] * 5 / 10417 temperature[i][1] = 1418 dirChange[i] += 1419 420 phi[i] = temperature[i][0] * numpy.pi / 180421 elif M[i] < 0:422 if temperature[i][1] > 0:423 temperature[i][0] = temperature[i][0] * 5 / 10424 temperature[i][1] = 1425 dirChange[i] += 1426 427 phi[i] = temperature[i][0] * numpy.pi / 180428 429 # stop rotating when phi is to small to notice the rotation430 if max(phi) < numpy.pi / 1800:431 #print "breaking"432 break433 434 self.rotateVertices(components, phi)435 if callbackUpdateCanvas: callbackUpdateCanvas()436 if callbackProgress : callbackProgress(min([dirChange[i] for i in range(len(dirChange)) if M[i] != 0]), 9)437 step += 1438 439 def mdsUpdateData(self, components, mds, callbackUpdateCanvas):440 """Translate and rotate the network components to computed positions."""441 component_props = []442 x_mds = []443 y_mds = []444 phi = [None] * len(components)445 self.diag_coors = math.sqrt((min(self.graph.coors[0])  max(self.graph.coors[0]))**2 + (min(self.graph.coors[1])  max(self.graph.coors[1]))**2)446 447 if self.mdsType == MdsType.MDS:448 x = [mds.points[u][0] for u in range(self.graph.nVertices)]449 y = [mds.points[u][1] for u in range(self.graph.nVertices)]450 self.graph.coors[0][range(self.graph.nVertices)] = x451 self.graph.coors[1][range(self.graph.nVertices)] = y452 if callbackUpdateCanvas:453 callbackUpdateCanvas()454 return455 456 for i in range(len(components)):457 component = components[i]458 459 if len(mds.points) == len(components): # if average linkage before460 x_avg_mds = mds.points[i][0]461 y_avg_mds = mds.points[i][1]462 else: # if not average linkage before463 x = [mds.points[u][0] for u in component]464 y = [mds.points[u][1] for u in component]465 466 x_avg_mds = sum(x) / len(x)467 y_avg_mds = sum(y) / len(y)468 # compute rotation angle469 c = [numpy.linalg.norm(numpy.cross(mds.points[u], [self.graph.coors[0][u],self.graph.coors[1][u]])) for u in component]470 n = [numpy.vdot([self.graph.coors[0][u],self.graph.coors[1][u]], [self.graph.coors[0][u],self.graph.coors[1][u]]) for u in component]471 phi[i] = sum(c) / sum(n)472 #print phi473 474 x = self.graph.coors[0][component]475 y = self.graph.coors[1][component]476 477 x_avg_graph = sum(x) / len(x)478 y_avg_graph = sum(y) / len(y)479 480 x_mds.append(x_avg_mds)481 y_mds.append(y_avg_mds)482 483 component_props.append((x_avg_graph, y_avg_graph, x_avg_mds, y_avg_mds, phi))484 485 w = max(self.graph.coors[0])  min(self.graph.coors[0])486 h = max(self.graph.coors[1])  min(self.graph.coors[1])487 d = math.sqrt(w**2 + h**2)488 #d = math.sqrt(w*h)489 e = [math.sqrt((self.graph.coors[0][u]  self.graph.coors[0][v])**2 +490 (self.graph.coors[1][u]  self.graph.coors[1][v])**2) for491 (u, v) in self.graph.getEdges()]492 493 if self.scalingRatio == 0:494 pass495 elif self.scalingRatio == 1:496 self.mdsScaleRatio = d497 elif self.scalingRatio == 2:498 self.mdsScaleRatio = d / sum(e) * float(len(e))499 elif self.scalingRatio == 3:500 self.mdsScaleRatio = 1 / sum(e) * float(len(e))501 elif self.scalingRatio == 4:502 self.mdsScaleRatio = w * h503 elif self.scalingRatio == 5:504 self.mdsScaleRatio = math.sqrt(w * h)505 elif self.scalingRatio == 6:506 self.mdsScaleRatio = 1507 elif self.scalingRatio == 7:508 e_fr = 0509 e_count = 0510 for i in range(self.graph.nVertices):511 for j in range(i + 1, self.graph.nVertices):512 x1 = self.graph.coors[0][i]513 y1 = self.graph.coors[1][i]514 x2 = self.graph.coors[0][j]515 y2 = self.graph.coors[1][j]516 e_fr += math.sqrt((x1x2)**2 + (y1y2)**2)517 e_count += 1518 self.mdsScaleRatio = e_fr / e_count519 elif self.scalingRatio == 8:520 e_fr = 0521 e_count = 0522 for i in range(len(components)):523 for j in range(i + 1, len(components)):524 x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, y_avg_mds_i, phi_i = component_props[i]525 x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, y_avg_mds_j, phi_j = component_props[j]526 e_fr += math.sqrt((x_avg_graph_ix_avg_graph_j)**2 + (y_avg_graph_iy_avg_graph_j)**2)527 e_count += 1528 self.mdsScaleRatio = e_fr / e_count529 elif self.scalingRatio == 9:530 e_fr = 0531 e_count = 0532 for i in range(len(components)):533 component = components[i]534 x = self.graph.coors[0][component]535 y = self.graph.coors[1][component]536 for i in range(len(x)):537 for j in range(i + 1, len(y)):538 x1 = x[i]539 y1 = y[i]540 x2 = x[j]541 y2 = y[j]542 e_fr += math.sqrt((x1x2)**2 + (y1y2)**2)543 e_count += 1544 self.mdsScaleRatio = e_fr / e_count545 546 diag_mds = math.sqrt((max(x_mds)  min(x_mds))**2 + (max(y_mds)  min(y_mds))**2)547 e = [math.sqrt((self.graph.coors[0][u]  self.graph.coors[0][v])**2 +548 (self.graph.coors[1][u]  self.graph.coors[1][v])**2) for549 (u, v) in self.graph.getEdges()]550 e = sum(e) / float(len(e))551 552 x = [mds.points[u][0] for u in range(len(mds.points))]553 y = [mds.points[u][1] for u in range(len(mds.points))]554 w = max(x)  min(x)555 h = max(y)  min(y)556 d = math.sqrt(w**2 + h**2)557 558 if len(x) == 1:559 r = 1560 else:561 if self.scalingRatio == 0:562 r = self.mdsScaleRatio / d * e563 elif self.scalingRatio == 1:564 r = self.mdsScaleRatio / d565 elif self.scalingRatio == 2:566 r = self.mdsScaleRatio / d * e567 elif self.scalingRatio == 3:568 r = self.mdsScaleRatio * e569 elif self.scalingRatio == 4:570 r = self.mdsScaleRatio / (w * h)571 elif self.scalingRatio == 5:572 r = self.mdsScaleRatio / math.sqrt(w * h)573 elif self.scalingRatio == 6:574 r = 1 / math.sqrt(self.graph.nVertices)575 elif self.scalingRatio == 7:576 e_mds = 0577 e_count = 0578 for i in range(len(mds.points)):579 for j in range(i):580 x1 = mds.points[i][0]581 y1 = mds.points[i][1]582 x2 = mds.points[j][0]583 y2 = mds.points[j][1]584 e_mds += math.sqrt((x1x2)**2 + (y1y2)**2)585 e_count += 1586 r = self.mdsScaleRatio / e_mds * e_count587 elif self.scalingRatio == 8:588 e_mds = 0589 e_count = 0590 for i in range(len(components)):591 for j in range(i + 1, len(components)):592 x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, y_avg_mds_i, phi_i = component_props[i]593 x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, y_avg_mds_j, phi_j = component_props[j]594 e_mds += math.sqrt((x_avg_mds_ix_avg_mds_j)**2 + (y_avg_mds_iy_avg_mds_j)**2)595 e_count += 1596 r = self.mdsScaleRatio / e_mds * e_count597 elif self.scalingRatio == 9:598 e_mds = 0599 e_count = 0600 for i in range(len(mds.points)):601 for j in range(i):602 x1 = mds.points[i][0]603 y1 = mds.points[i][1]604 x2 = mds.points[j][0]605 y2 = mds.points[j][1]606 e_mds += math.sqrt((x1x2)**2 + (y1y2)**2)607 e_count += 1608 r = self.mdsScaleRatio / e_mds * e_count609 610 #r = self.mdsScaleRatio / d611 #print "d", d, "r", r612 #r = self.mdsScaleRatio / math.sqrt(self.graph.nVertices)613 614 for i in range(len(components)):615 component = components[i]616 x_avg_graph, y_avg_graph, x_avg_mds, y_avg_mds, phi = component_props[i]617 618 # if phi[i]: # rotate vertices619 # #print "rotate", i, phi[i]620 # r = numpy.array([[numpy.cos(phi[i]), numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]]) #rotation matrix621 # c = [x_avg_graph, y_avg_graph] # center of mass in FR coordinate system622 # v = [numpy.dot(numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]])  c, r) + c for u in component]623 # self.graph.coors[0][component] = [u[0] for u in v]624 # self.graph.coors[1][component] = [u[1] for u in v]625 626 # translate vertices627 if not self.rotationOnly:628 self.graph.coors[0][component] = (self.graph.coors[0][component]  x_avg_graph) / r + x_avg_mds629 self.graph.coors[1][component] = (self.graph.coors[1][component]  y_avg_graph) / r + y_avg_mds630 631 if callbackUpdateCanvas:632 callbackUpdateCanvas()633 634 def mdsCallback(self, a,b=None):635 """Refresh the UI when running MDS on network components."""636 if not self.mdsStep % self.mdsRefresh:637 self.mdsUpdateData(self.mdsComponents, self.mds, self.callbackUpdateCanvas)638 639 if self.mdsType == MdsType.exactSimulation:640 self.mds.points = [[self.graph.coors[0][i], self.graph.coors[1][i]] for i in range(len(self.graph.coors))]641 self.mds.freshD = 0642 643 if self.callbackProgress != None:644 self.callbackProgress(self.mds.avgStress, self.mdsStep)645 646 self.mdsStep += 1647 648 if self.stopMDS:649 return 0650 else:651 return 1652 653 def mdsComponents(self, mdsSteps, mdsRefresh, callbackProgress=None, callbackUpdateCanvas=None, torgerson=0, minStressDelta = 0, avgLinkage=False, rotationOnly=False, mdsType=MdsType.componentMDS, scalingRatio=0, mdsFromCurrentPos=0):654 """Position the network components according to similarities among them."""655 656 if self.vertexDistance == None:657 self.information('Set distance matrix to input signal')658 return 1659 660 if self.graph == None:661 return 1662 663 if self.vertexDistance.dim != self.graph.nVertices:664 return 1665 666 self.mdsComponents = self.graph.getConnectedComponents()667 self.mdsRefresh = mdsRefresh668 self.mdsStep = 0669 self.stopMDS = 0670 self.vertexDistance.matrixType = orange.SymMatrix.Symmetric671 self.diag_coors = math.sqrt((min(self.graph.coors[0])  max(self.graph.coors[0]))**2 + (min(self.graph.coors[1])  max(self.graph.coors[1]))**2)672 self.rotationOnly = rotationOnly673 self.mdsType = mdsType674 self.scalingRatio = scalingRatio675 676 w = max(self.graph.coors[0])  min(self.graph.coors[0])677 h = max(self.graph.coors[1])  min(self.graph.coors[1])678 d = math.sqrt(w**2 + h**2)679 #d = math.sqrt(w*h)680 e = [math.sqrt((self.graph.coors[0][u]  self.graph.coors[0][v])**2 +681 (self.graph.coors[1][u]  self.graph.coors[1][v])**2) for682 (u, v) in self.graph.getEdges()]683 self.mdsScaleRatio = d / sum(e) * float(len(e))684 #print d / sum(e) * float(len(e))685 686 if avgLinkage:687 matrix = self.vertexDistance.avgLinkage(self.mdsComponents)688 else:689 matrix = self.vertexDistance690 691 #if self.mds == None:692 self.mds = orngMDS.MDS(matrix)693 694 if mdsFromCurrentPos:695 if avgLinkage:696 for u, c in enumerate(self.mdsComponents):697 x = sum(self.graph.coors[0][c]) / len(c)698 y = sum(self.graph.coors[1][c]) / len(c)699 self.mds.points[u][0] = x700 self.mds.points[u][1] = y701 else:702 for u in range(self.graph.nVertices):703 self.mds.points[u][0] = self.graph.coors[0][u]704 self.mds.points[u][1] = self.graph.coors[1][u]705 706 # set min stress difference between 0.01 and 0.00001707 self.minStressDelta = minStressDelta708 self.callbackUpdateCanvas = callbackUpdateCanvas709 self.callbackProgress = callbackProgress710 711 if torgerson:712 self.mds.Torgerson()713 714 self.mds.optimize(mdsSteps, orngMDS.SgnRelStress, self.minStressDelta, progressCallback=self.mdsCallback)715 self.mdsUpdateData(self.mdsComponents, self.mds, callbackUpdateCanvas)716 717 if callbackProgress != None:718 callbackProgress(self.mds.avgStress, self.mdsStep)719 720 del self.rotationOnly721 del self.diag_coors722 del self.mdsRefresh723 del self.mdsStep724 #del self.mds725 del self.mdsComponents726 del self.minStressDelta727 del self.callbackUpdateCanvas728 del self.callbackProgress729 del self.mdsType730 del self.mdsScaleRatio731 del self.scalingRatio732 return 0733 734 def mdsComponentsAvgLinkage(self, mdsSteps, mdsRefresh, callbackProgress=None, callbackUpdateCanvas=None, torgerson=0, minStressDelta = 0, scalingRatio=0, mdsFromCurrentPos=0):735 return self.mdsComponents(mdsSteps, mdsRefresh, callbackProgress, callbackUpdateCanvas, torgerson, minStressDelta, True, scalingRatio=scalingRatio, mdsFromCurrentPos=mdsFromCurrentPos)736 737 def saveNetwork(self, fn):738 print "This method is deprecated. You should use orngNetwork.Network.saveNetwork"739 name = ''740 try:741 root, ext = os.path.splitext(fn)742 if ext == '':743 fn = root + '.net'744 745 graphFile = file(fn, 'w+')746 except IOError:747 return 1748 749 graphFile.write('### This file was generated with Orange Network Visualizer ### \n\n\n')750 if name == '':751 graphFile.write('*Network ' + '"no name" \n\n')752 else:753 graphFile.write('*Network ' + str(name) + ' \n\n')754 755 756 #izpis opisov vozlisc757 print "e", self.graph.nEdgeTypes758 graphFile.write('*Vertices %8d %8d\n' % (self.graph.nVertices, self.graph.nEdgeTypes))759 for v in range(self.graph.nVertices):760 graphFile.write('% 8d ' % (v + 1))761 # if verticesParms[v].label!='':762 # self.GraphFile.write(str('"'+ verticesParms[v].label + '"') + ' \t')763 # else:764 try:765 label = self.graph.items[v]['label']766 graphFile.write(str('"' + str(label) + '"') + ' \t')767 except:768 graphFile.write(str('"' + str(v) + '"') + ' \t')769 770 x = self.network.coors[0][v]771 y = self.network.coors[1][v]772 #if x < 0: x = 0773 #if x >= 1: x = 0.9999774 #if y < 0: y = 0775 #if y >= 1: y = 0.9999776 z = 0.5000777 graphFile.write('%.4f %.4f %.4f\t' % (x, y, z))778 graphFile.write('\n')779 780 #izpis opisov povezav781 #najprej neusmerjene782 if self.graph.directed:783 graphFile.write('*Arcs \n')784 for (i, j) in self.graph.getEdges():785 if len(self.graph[i, j]) > 0:786 graphFile.write('%8d %8d %f' % (i + 1, j + 1, float(str(self.graph[i, j]))))787 graphFile.write('\n')788 else:789 graphFile.write('*Edges \n')790 for (i, j) in self.graph.getEdges():791 if len(self.graph[i, j]) > 0:792 graphFile.write('%8d %8d %f' % (i + 1, j + 1, float(str(self.graph[i, j]))))793 graphFile.write('\n')794 795 graphFile.write('\n')796 graphFile.close()797 798 if self.graph.items != None and len(self.graph.items) > 0:799 (name, ext) = os.path.splitext(fn)800 self.graph.items.save(name + "_items.tab")801 802 if self.graph.links != None and len(self.graph.links) > 0:803 (name, ext) = os.path.splitext(fn)804 self.graph.links.save(name + "_links.tab")805 806 return 0807 808 def readNetwork(self, fn, directed=0):809 print "This method is deprecated. You should use orngNetwork.Network.readNetwork"810 network = Network(1,directed)811 net = network.readPajek(fn, directed)812 self.setGraph(net)813 self.graph = net814 return net815 816 class NetworkClustering():817 random.seed(0)818 819 def __init__(self, network):820 self.net = network821 822 823 def labelPropagation(self, results2items=0, resultHistory2items=0):824 """Label propagation method from Raghavan et al., 2007"""825 826 vertices = range(self.net.nVertices)827 labels = range(self.net.nVertices)828 lblhistory = []829 #consecutiveStop = 0830 for i in range(1000):831 random.shuffle(vertices)832 stop = 1833 for v in vertices:834 nbh = self.net.getNeighbours(v)835 if len(nbh) == 0:836 continue837 838 lbls = [labels[u] for u in nbh]839 lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)]840 m = max(lbls)[0]841 mlbls = [l for c, l in lbls if c >= m]842 lbl = random.choice(mlbls)843 844 if labels[v] not in mlbls: stop = 0845 labels[v] = lbl846 847 lblhistory.append([str(l) for l in labels])848 # if stopping condition might be satisfied, check it849 if stop:850 for v in vertices:851 nbh = self.net.getNeighbours(v)852 if len(nbh) == 0: continue853 lbls = [labels[u] for u in nbh]854 lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)]855 m = max(lbls)[0]856 mlbls = [l for c, l in lbls if c >= m]857 if labels[v] not in mlbls:858 stop = 0859 break860 if stop: break861 862 if results2items and not resultHistory2items:863 attrs = [orange.EnumVariable('clustering label propagation', values=list(set([l for l in lblhistory[1]])))]864 dom = orange.Domain(attrs, 0)865 data = orange.ExampleTable(dom, [[l] for l in lblhistory[1]])866 self.net.items = data if self.net.items == None else orange.ExampleTable([self.net.items, data])867 if resultHistory2items:868 attrs = [orange.EnumVariable('c'+ str(i), values=list(set([l for l in lblhistory[0]]))) for i,labels in enumerate(lblhistory)]869 dom = orange.Domain(attrs, 0)870 # transpose history871 data = map(list, zip(*lblhistory))872 data = orange.ExampleTable(dom, data)873 self.net.items = data if self.net.items == None else orange.ExampleTable([self.net.items, data])874 875 return labels
Note: See TracChangeset
for help on using the changeset viewer.