Changeset 7259:f4f4b3ab135b in orange


Ignore:
Timestamp:
02/02/11 22:35:58 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
3f12ffdaa286903c0e97cfcf4772d733b1f41649
Message:
 
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 
     1from Orange.network import MdsTypeClass 
     2from Orange.network import Network, NetworkOptimization, NetworkClustering 
    163 
    174MdsType = 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 1 
    51              
    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 descriptions 
    96         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.5000 
    109                 fp.write('%.4f    %.4f    %.4f\t' % (x, y, z)) 
    110             fp.write('\n') 
    111  
    112         # print edge descriptions 
    113         # not directed edges 
    114         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 edges 
    125         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,i 
    131                      
    132                     if not (i,j) in writtenEdges: 
    133                         writtenEdges[(i,j)] = 1 
    134                     else: 
    135                         continue 
    136  
    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 0 
    155          
    156     @staticmethod 
    157     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 net 
    165             else: 
    166                 print "invalid network type", fileName.name 
    167                 return None 
    168         else: 
    169             root, ext = os.path.splitext(fileName) 
    170             net = None 
    171             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" % fileName 
    177                  
    178             if net is not None: 
    179                 net.optimization = NetworkOptimization(net) 
    180             return net  
    181  
    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 = network 
    191          
    192         self.maxWidth = 1000 
    193         self.maxHeight = 1000 
    194          
    195         self.attributeList = {} 
    196         self.attributeValues = {} 
    197         self.vertexDistance = None 
    198         self.mds = None 
    199          
    200     def computeForces(self): 
    201         n = self.graph.nVertices 
    202         vertices = set(range(n)) 
    203         e_avg = 0 
    204         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_) / norm  
    225              
    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 / maxforce 
    235             rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]])) 
    236  
    237         return rv 
    238      
    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.coors 
    246                 self.setGraph(subgraph) 
    247                 self.graph = subgraph 
    248                      
    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.graph 
    256              
    257             if len(fullgraphs) > 0: 
    258                 used = set() 
    259                 graphstomerge = list() 
    260                 #print fullgraphs 
    261                 for fullgraph in fullgraphs: 
    262                     #print fullgraph 
    263                     fullgraph_set = set(fullgraph) 
    264                     if len(used & fullgraph_set) == 0: 
    265                         graphstomerge.append(fullgraph) 
    266                         used |= fullgraph_set 
    267                          
    268                 #print graphstomerge 
    269                 #print used 
    270                 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.coors 
    277                 self.setGraph(subgraph) 
    278                 self.graph = subgraph 
    279                 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 cluster     
    284                 x, y = 0, 0 
    285                 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)] = x 
    293                 self.coors[1][len(nodescomp)] = y 
    294              
    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.variables 
    301                  
    302                     metas = self.graph.items.domain.getmetas(0) 
    303                     for i, var in metas.iteritems(): 
    304                         vars.append(var) 
    305         return vars 
    306      
    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.variables 
    313                  
    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.nVertices 
    329          
    330     def rotateVertices(self, components, phi):    
    331         #print phi  
    332         for i in range(len(components)): 
    333             if phi[i] == 0: 
    334                 continue 
    335              
    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_center 
    345             y = y - y_center 
    346              
    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 / 180 
    352                  
    353             x = r * numpy.cos(fi) 
    354             y = r * numpy.sin(fi) 
    355              
    356             self.graph.coors[0][component] = x + x_center 
    357             self.graph.coors[1][component] = y + y_center 
    358              
    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 1 
    363          
    364         if self.graph == None: 
    365             return 1 
    366          
    367         if self.vertexDistance.dim != self.graph.nVertices: 
    368             return 1 
    369          
    370         self.stopRotate = 0 
    371          
    372         # rotate only components with more than one vertex 
    373         components = [component for component in self.graph.getConnectedComponents() if len(component) > 1] 
    374         vertices = set(range(self.graph.nVertices)) 
    375         step = 0 
    376         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, M 
    413             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 / 10 
    417                         temperature[i][1] = 1 
    418                         dirChange[i] += 1 
    419                          
    420                     phi[i] = temperature[i][0] * numpy.pi / 180 
    421                 elif M[i] < 0:   
    422                     if temperature[i][1] > 0: 
    423                         temperature[i][0] = temperature[i][0] * 5 / 10 
    424                         temperature[i][1] = -1 
    425                         dirChange[i] += 1 
    426                      
    427                     phi[i] = -temperature[i][0] * numpy.pi / 180 
    428              
    429             # stop rotating when phi is to small to notice the rotation 
    430             if max(phi) < numpy.pi / 1800: 
    431                 #print "breaking" 
    432                 break 
    433              
    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 += 1 
    438      
    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)] =  x 
    451             self.graph.coors[1][range(self.graph.nVertices)] =  y 
    452             if callbackUpdateCanvas: 
    453                 callbackUpdateCanvas() 
    454             return 
    455          
    456         for i in range(len(components)):     
    457             component = components[i] 
    458              
    459             if len(mds.points) == len(components):  # if average linkage before 
    460                 x_avg_mds = mds.points[i][0] 
    461                 y_avg_mds = mds.points[i][1] 
    462             else:                                   # if not average linkage before 
    463                 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 angle 
    469                 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 phi 
    473              
    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) for  
    491                   (u, v) in self.graph.getEdges()] 
    492          
    493         if self.scalingRatio == 0: 
    494             pass 
    495         elif self.scalingRatio == 1: 
    496             self.mdsScaleRatio = d 
    497         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 * h 
    503         elif self.scalingRatio == 5: 
    504             self.mdsScaleRatio = math.sqrt(w * h) 
    505         elif self.scalingRatio == 6: 
    506             self.mdsScaleRatio = 1 
    507         elif self.scalingRatio == 7: 
    508             e_fr = 0 
    509             e_count = 0 
    510             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((x1-x2)**2 + (y1-y2)**2) 
    517                     e_count += 1 
    518             self.mdsScaleRatio = e_fr / e_count 
    519         elif self.scalingRatio == 8: 
    520             e_fr = 0 
    521             e_count = 0 
    522             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_i-x_avg_graph_j)**2 + (y_avg_graph_i-y_avg_graph_j)**2) 
    527                     e_count += 1 
    528             self.mdsScaleRatio = e_fr / e_count        
    529         elif self.scalingRatio == 9: 
    530             e_fr = 0 
    531             e_count = 0 
    532             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((x1-x2)**2 + (y1-y2)**2) 
    543                         e_count += 1 
    544             self.mdsScaleRatio = e_fr / e_count 
    545          
    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) for  
    549                   (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 = 1 
    560         else: 
    561             if self.scalingRatio == 0: 
    562                 r = self.mdsScaleRatio / d * e 
    563             elif self.scalingRatio == 1: 
    564                 r = self.mdsScaleRatio / d 
    565             elif self.scalingRatio == 2: 
    566                 r = self.mdsScaleRatio / d * e 
    567             elif self.scalingRatio == 3: 
    568                 r = self.mdsScaleRatio * e 
    569             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 = 0 
    577                 e_count = 0 
    578                 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((x1-x2)**2 + (y1-y2)**2) 
    585                         e_count += 1 
    586                 r = self.mdsScaleRatio / e_mds * e_count 
    587             elif self.scalingRatio == 8: 
    588                 e_mds = 0 
    589                 e_count = 0 
    590                 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_i-x_avg_mds_j)**2 + (y_avg_mds_i-y_avg_mds_j)**2) 
    595                         e_count += 1 
    596                 r = self.mdsScaleRatio / e_mds * e_count 
    597             elif self.scalingRatio == 9: 
    598                 e_mds = 0 
    599                 e_count = 0 
    600                 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((x1-x2)**2 + (y1-y2)**2) 
    607                         e_count += 1 
    608                 r = self.mdsScaleRatio / e_mds * e_count 
    609                  
    610             #r = self.mdsScaleRatio / d 
    611             #print "d", d, "r", r 
    612             #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 vertices 
    619 #                #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 matrix 
    621 #                c = [x_avg_graph, y_avg_graph]  # center of mass in FR coordinate system 
    622 #                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 vertices 
    627             if not self.rotationOnly: 
    628                 self.graph.coors[0][component] = (self.graph.coors[0][component] - x_avg_graph) / r + x_avg_mds 
    629                 self.graph.coors[1][component] = (self.graph.coors[1][component] - y_avg_graph) / r + y_avg_mds 
    630                 
    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 = 0 
    642              
    643             if self.callbackProgress != None: 
    644                 self.callbackProgress(self.mds.avgStress, self.mdsStep) 
    645                  
    646         self.mdsStep += 1 
    647  
    648         if self.stopMDS: 
    649             return 0 
    650         else: 
    651             return 1 
    652              
    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 1 
    659          
    660         if self.graph == None: 
    661             return 1 
    662          
    663         if self.vertexDistance.dim != self.graph.nVertices: 
    664             return 1 
    665          
    666         self.mdsComponents = self.graph.getConnectedComponents() 
    667         self.mdsRefresh = mdsRefresh 
    668         self.mdsStep = 0 
    669         self.stopMDS = 0 
    670         self.vertexDistance.matrixType = orange.SymMatrix.Symmetric 
    671         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 = rotationOnly 
    673         self.mdsType = mdsType 
    674         self.scalingRatio = scalingRatio 
    675  
    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) for  
    682                   (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.vertexDistance 
    690          
    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] = x 
    700                     self.mds.points[u][1] = y 
    701             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.00001 
    707         self.minStressDelta = minStressDelta 
    708         self.callbackUpdateCanvas = callbackUpdateCanvas 
    709         self.callbackProgress = callbackProgress 
    710          
    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.rotationOnly 
    721         del self.diag_coors 
    722         del self.mdsRefresh 
    723         del self.mdsStep 
    724         #del self.mds 
    725         del self.mdsComponents 
    726         del self.minStressDelta 
    727         del self.callbackUpdateCanvas 
    728         del self.callbackProgress 
    729         del self.mdsType 
    730         del self.mdsScaleRatio 
    731         del self.scalingRatio 
    732         return 0 
    733  
    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 1 
    748  
    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 vozlisc 
    757         print "e", self.graph.nEdgeTypes 
    758         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 = 0 
    773             #if x >= 1: x = 0.9999 
    774             #if y < 0: y = 0 
    775             #if y >= 1: y = 0.9999 
    776             z = 0.5000 
    777             graphFile.write('%.4f    %.4f    %.4f\t' % (x, y, z)) 
    778             graphFile.write('\n') 
    779  
    780         #izpis opisov povezav 
    781         #najprej neusmerjene 
    782         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 0 
    807      
    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 = net 
    814         return net 
    815      
    816 class NetworkClustering(): 
    817     random.seed(0) 
    818      
    819     def __init__(self, network): 
    820         self.net = network 
    821          
    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 = 0 
    830         for i in range(1000): 
    831             random.shuffle(vertices) 
    832             stop = 1 
    833             for v in vertices: 
    834                 nbh = self.net.getNeighbours(v) 
    835                 if len(nbh) == 0: 
    836                     continue 
    837                  
    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 = 0 
    845                 labels[v] = lbl 
    846                  
    847             lblhistory.append([str(l) for l in labels]) 
    848             # if stopping condition might be satisfied, check it 
    849             if stop: 
    850                 for v in vertices: 
    851                     nbh = self.net.getNeighbours(v) 
    852                     if len(nbh) == 0: continue 
    853                     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 = 0 
    859                         break 
    860                 if stop: break 
    861                      
    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 history 
    871             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.