Changeset 7256:63b181134e87 in orange


Ignore:
Timestamp:
02/02/11 22:25:42 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
b9105641902b5e134f8b8e689f8da637e926d950
Message:
 
File:
1 edited

Legend:

Unmodified
Added
Removed
  • orange/Orange/network/__init__.py

    r7253 r7256  
     1import orangeom 
     2import random 
     3 
    14from orange import Graph, GraphAsList, GraphAsMatrix, GraphAsTree 
     5 
     6class MdsTypeClass(): 
     7    def __init__(self): 
     8        self.componentMDS = 0 
     9        self.exactSimulation = 1 
     10        self.MDS = 2 
     11 
     12MdsType = MdsTypeClass() 
     13 
     14class Network(orangeom.Network): 
     15    """Orange data structure for representing directed and undirected networks with various types of weighted connections and other data.""" 
     16     
     17    def __init__(self, *args): 
     18        #print "orngNetwork.Network" 
     19        self.optimization = NetworkOptimization(self) 
     20        self.clustering = NetworkClustering(self) 
     21         
     22    def getDistanceMatrixThreshold(self, matrix, ratio): 
     23        """Return lower and upper distance threshold values for given ratio of edges""" 
     24        values = [] 
     25        for i in range(matrix.dim): 
     26            for j in range(i): 
     27                values.append((matrix[i,j], i, j)) 
     28                 
     29        values.sort() 
     30        return values[0][0], values[int(ratio*len(values))][0] 
     31         
     32    def save(self, fileName): 
     33        """Saves network to Pajek (.net) file.""" 
     34        self.saveNetwork(fileName) 
     35         
     36    def saveNetwork(self, fileName): 
     37        """Save network to file.""" 
     38         
     39        try: 
     40            root, ext = os.path.splitext(fileName) 
     41            if ext == '': 
     42                fileName = root + '.net' 
     43            graphFile = open(fileName, 'w+') 
     44        except IOError: 
     45            return 1 
     46             
     47        root, ext = os.path.splitext(fileName) 
     48        if ext.lower() == ".gml": 
     49            self.saveGML(graphFile) 
     50        else: 
     51            self.savePajek(graphFile) 
     52 
     53    def saveGML(self, fp): 
     54        """Save network to GML (.gml) file format.""" 
     55         
     56        fp.write("graph\n[\n") 
     57        tabs = "\t" 
     58        fp.write("%slabel\t\"%s\"\n" % (tabs, self.name)) 
     59         
     60        for v in range(self.nVertices): 
     61            try: 
     62                label = self.items[v]['label'] 
     63            except: 
     64                label = "" 
     65             
     66            fp.write("\tnode\n\t[\n\t\tid\t%d\n\t\tlabel\t\"%s\"\n\t]\n" % (v, label)) 
     67         
     68        for u,v in self.getEdges(): 
     69            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, "")) 
     70         
     71        fp.write("]\n") 
     72         
     73        if self.items != None and len(self.items) > 0: 
     74            (name, ext) = os.path.splitext(fp.name) 
     75            self.items.save(name + "_items.tab") 
     76             
     77        if hasattr(self, 'links') and self.links != None and len(self.links) > 0: 
     78            (name, ext) = os.path.splitext(fp.name) 
     79            self.links.save(name + "_links.tab") 
     80         
     81    def savePajek(self, fp): 
     82        """Save network to Pajek (.net) file format.""" 
     83        name = '' 
     84        fp.write('### This file was generated with Orange Network Visualizer ### \n\n\n') 
     85        if name == '': 
     86            fp.write('*Network ' + '"no name" \n\n') 
     87        else: 
     88            fp.write('*Network ' + str(name) + ' \n\n') 
     89 
     90        # print node descriptions 
     91        fp.write('*Vertices %8d %8d\n' % (self.nVertices, self.nEdgeTypes)) 
     92        for v in range(self.nVertices): 
     93            fp.write('% 8d ' % (v + 1)) 
     94            try: 
     95                label = self.items[v]['label'] 
     96                fp.write(str('"' + str(label) + '"') + ' \t') 
     97            except: 
     98                fp.write(str('"' + str(v) + '"') + ' \t') 
     99             
     100            if hasattr(self, 'coors'): 
     101                x = self.coors[0][v] 
     102                y = self.coors[1][v] 
     103                z = 0.5000 
     104                fp.write('%.4f    %.4f    %.4f\t' % (x, y, z)) 
     105            fp.write('\n') 
     106 
     107        # print edge descriptions 
     108        # not directed edges 
     109        if self.directed: 
     110            fp.write('*Arcs \n') 
     111            for (i, j) in self.getEdges(): 
     112                if len(self[i, j]) > 0: 
     113                    if self.nEdgeTypes > 1: 
     114                        edge_str = str(self[i, j]) 
     115                    else: 
     116                        edge_str = "%f" % float(str(self[i, j])) 
     117                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                     
     118                    fp.write('\n') 
     119        # directed edges 
     120        else: 
     121            fp.write('*Edges \n') 
     122            writtenEdges = {} 
     123            for (i, j) in self.getEdges(): 
     124                if len(self[i, j]) > 0: 
     125                    if i > j: i,j = j,i 
     126                     
     127                    if not (i,j) in writtenEdges: 
     128                        writtenEdges[(i,j)] = 1 
     129                    else: 
     130                        continue 
     131 
     132                    if self.nEdgeTypes > 1: 
     133                        edge_str = str(self[i, j]) 
     134                    else: 
     135                        edge_str = "%f" % float(str(self[i, j])) 
     136                    fp.write('%8d %8d %s' % (i + 1, j + 1, edge_str))                     
     137                    fp.write('\n') 
     138 
     139        fp.write('\n') 
     140         
     141        if self.items != None and len(self.items) > 0: 
     142            (name, ext) = os.path.splitext(fp.name) 
     143            self.items.save(name + "_items.tab") 
     144             
     145        if hasattr(self, 'links') and self.links != None and len(self.links) > 0: 
     146            (name, ext) = os.path.splitext(fp.name) 
     147            self.links.save(name + "_links.tab") 
     148 
     149        return 0 
     150         
     151    @staticmethod 
     152    def read(fileName, directed=0): 
     153        """Read network. Supported network formats: from Pajek (.net) file, GML.""" 
     154        if type(fileName) == file: 
     155            root, ext = os.path.splitext(fileName.name) 
     156            if ext.lower() == ".net": 
     157                net = Network(2,0).parseNetwork(fileName.read(), directed) 
     158                net.optimization = NetworkOptimization(net) 
     159                return net 
     160            else: 
     161                print "invalid network type", fileName.name 
     162                return None 
     163        else: 
     164            root, ext = os.path.splitext(fileName) 
     165            net = None 
     166            if ext.lower() == ".net": 
     167                net = Network(2,0).readPajek(fileName, directed) 
     168            elif ext.lower() == ".gml": 
     169                net = Network(2,0).readGML(fileName) 
     170            else: 
     171                print "Invalid file type %s" % fileName 
     172                 
     173            if net is not None: 
     174                net.optimization = NetworkOptimization(net) 
     175            return net  
     176 
     177class NetworkOptimization(orangeom.NetworkOptimization): 
     178    """main class for performing network layout optimization. Network structure is defined in orangeom.Network class.""" 
     179     
     180    def __init__(self, network=None, name="None"): 
     181        if network is None: 
     182            network = orangeom.Network(2, 0) 
     183             
     184        self.setGraph(network) 
     185        self.graph = network 
     186         
     187        self.maxWidth = 1000 
     188        self.maxHeight = 1000 
     189         
     190        self.attributeList = {} 
     191        self.attributeValues = {} 
     192        self.vertexDistance = None 
     193        self.mds = None 
     194         
     195    def computeForces(self): 
     196        n = self.graph.nVertices 
     197        vertices = set(range(n)) 
     198        e_avg = 0 
     199        edges = self.graph.getEdges() 
     200        for u,v in edges: 
     201            u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) 
     202            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]]) 
     203            e_avg += numpy.linalg.norm(u_ - v_) 
     204        e_avg /= len(edges) 
     205         
     206        forces = [] 
     207        maxforce = [] 
     208        components = self.graph.getConnectedComponents() 
     209        for component in components: 
     210            outer_vertices = vertices - set(component) 
     211             
     212            for u in component: 
     213                u_ = numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) 
     214                force = numpy.array([0.0, 0.0])                 
     215                for v in outer_vertices: 
     216                    v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]]) 
     217                    d = self.vertexDistance[u, v] 
     218                    norm = numpy.linalg.norm(v_ - u_) 
     219                    force += (d - norm) * (v_ - u_) / norm  
     220             
     221                forces.append(force) 
     222                maxforce.append(numpy.linalg.norm(force)) 
     223             
     224        maxforce = max(maxforce) 
     225        rv = [] 
     226        for v in range(n): 
     227            force = forces[v] 
     228            v_ = numpy.array([self.graph.coors[0][v], self.graph.coors[1][v]]) 
     229            f = force * e_avg / maxforce 
     230            rv.append(([v_[0], v_[0] + f[0]],[v_[1], v_[1] + f[1]])) 
     231 
     232        return rv 
     233     
     234    def collapse(self): 
     235        if len(self.graph.getNodes(1)) > 0: 
     236            nodes = list(set(range(self.graph.nVertices)) - set(self.graph.getNodes(1))) 
     237                 
     238            if len(nodes) > 0: 
     239                subgraph = orangeom.Network(self.graph.getSubGraph(nodes)) 
     240                oldcoors = self.coors 
     241                self.setGraph(subgraph) 
     242                self.graph = subgraph 
     243                     
     244                for i in range(len(nodes)): 
     245                    self.coors[0][i] = oldcoors[0][nodes[i]] 
     246                    self.coors[1][i] = oldcoors[1][nodes[i]] 
     247 
     248        else: 
     249            fullgraphs = self.graph.getLargestFullGraphs() 
     250            subgraph = self.graph 
     251             
     252            if len(fullgraphs) > 0: 
     253                used = set() 
     254                graphstomerge = list() 
     255                #print fullgraphs 
     256                for fullgraph in fullgraphs: 
     257                    #print fullgraph 
     258                    fullgraph_set = set(fullgraph) 
     259                    if len(used & fullgraph_set) == 0: 
     260                        graphstomerge.append(fullgraph) 
     261                        used |= fullgraph_set 
     262                         
     263                #print graphstomerge 
     264                #print used 
     265                subgraph = orangeom.Network(subgraph.getSubGraphMergeClusters(graphstomerge)) 
     266                                    
     267                nodescomp = list(set(range(self.graph.nVertices)) - used) 
     268                 
     269                #subgraph.setattr("items", self.graph.items.getitems(nodescomp)) 
     270                #subgraph.items.append(self.graph.items[0]) 
     271                oldcoors = self.coors 
     272                self.setGraph(subgraph) 
     273                self.graph = subgraph 
     274                for i in range(len(nodescomp)): 
     275                    self.coors[0][i] = oldcoors[0][nodescomp[i]] 
     276                    self.coors[1][i] = oldcoors[1][nodescomp[i]] 
     277                     
     278                # place meta vertex in center of cluster     
     279                x, y = 0, 0 
     280                for node in used: 
     281                    x += oldcoors[0][node] 
     282                    y += oldcoors[1][node] 
     283                     
     284                x = x / len(used) 
     285                y = y / len(used) 
     286                 
     287                self.coors[0][len(nodescomp)] = x 
     288                self.coors[1][len(nodescomp)] = y 
     289             
     290    def getVars(self): 
     291        vars = [] 
     292        if (self.graph != None): 
     293            if hasattr(self.graph, "items"): 
     294                if isinstance(self.graph.items, orange.ExampleTable): 
     295                    vars[:0] = self.graph.items.domain.variables 
     296                 
     297                    metas = self.graph.items.domain.getmetas(0) 
     298                    for i, var in metas.iteritems(): 
     299                        vars.append(var) 
     300        return vars 
     301     
     302    def getEdgeVars(self): 
     303        vars = [] 
     304        if (self.graph != None): 
     305            if hasattr(self.graph, "links"): 
     306                if isinstance(self.graph.links, orange.ExampleTable): 
     307                    vars[:0] = self.graph.links.domain.variables 
     308                 
     309                    metas = self.graph.links.domain.getmetas(0) 
     310                    for i, var in metas.iteritems(): 
     311                        vars.append(var) 
     312                         
     313        return [x for x in vars if str(x.name) != 'u' and str(x.name) != 'v'] 
     314     
     315    def getData(self, i, j): 
     316        if self.graph.items is orange.ExampleTable: 
     317            return self.data[i][j] 
     318        elif self.graph.data is type([]): 
     319            return self.data[i][j] 
     320         
     321    def nVertices(self): 
     322        if self.graph: 
     323            return self.graph.nVertices 
     324         
     325    def rotateVertices(self, components, phi):    
     326        #print phi  
     327        for i in range(len(components)): 
     328            if phi[i] == 0: 
     329                continue 
     330             
     331            component = components[i] 
     332             
     333            x = self.graph.coors[0][component] 
     334            y = self.graph.coors[1][component] 
     335             
     336            x_center = x.mean() 
     337            y_center = y.mean() 
     338             
     339            x = x - x_center 
     340            y = y - y_center 
     341             
     342            r = numpy.sqrt(x ** 2 + y ** 2) 
     343            fi = numpy.arctan2(y, x) 
     344             
     345            fi += phi[i] 
     346            #fi += factor * M[i] * numpy.pi / 180 
     347                 
     348            x = r * numpy.cos(fi) 
     349            y = r * numpy.sin(fi) 
     350             
     351            self.graph.coors[0][component] = x + x_center 
     352            self.graph.coors[1][component] = y + y_center 
     353             
     354    def rotateComponents(self, maxSteps=100, minMoment=0.000000001, callbackProgress=None, callbackUpdateCanvas=None): 
     355        """Rotate the network components using a spring model.""" 
     356        if self.vertexDistance == None: 
     357            return 1 
     358         
     359        if self.graph == None: 
     360            return 1 
     361         
     362        if self.vertexDistance.dim != self.graph.nVertices: 
     363            return 1 
     364         
     365        self.stopRotate = 0 
     366         
     367        # rotate only components with more than one vertex 
     368        components = [component for component in self.graph.getConnectedComponents() if len(component) > 1] 
     369        vertices = set(range(self.graph.nVertices)) 
     370        step = 0 
     371        M = [1] 
     372        temperature = [[30.0, 1] for i in range(len(components))] 
     373        dirChange = [0] * len(components) 
     374        while step < maxSteps and (max(M) > minMoment or min(M) < -minMoment) and not self.stopRotate: 
     375            M = [0] * len(components)  
     376             
     377            for i in range(len(components)): 
     378                component = components[i] 
     379                 
     380                outer_vertices = vertices - set(component) 
     381                 
     382                x = self.graph.coors[0][component] 
     383                y = self.graph.coors[1][component] 
     384                 
     385                x_center = x.mean() 
     386                y_center = y.mean() 
     387                 
     388                for j in range(len(component)): 
     389                    u = component[j] 
     390 
     391                    for v in outer_vertices: 
     392                        d = self.vertexDistance[u, v] 
     393                        u_x = self.graph.coors[0][u] 
     394                        u_y = self.graph.coors[1][u] 
     395                        v_x = self.graph.coors[0][v] 
     396                        v_y = self.graph.coors[1][v] 
     397                        L = [(u_x - v_x), (u_y - v_y)] 
     398                        R = [(u_x - x_center), (u_y - y_center)] 
     399                        e = math.sqrt((v_x - x_center) ** 2 + (v_y - y_center) ** 2) 
     400                         
     401                        M[i] += (1 - d) / (e ** 2) * numpy.cross(R, L) 
     402             
     403            tmpM = numpy.array(M) 
     404            #print numpy.min(tmpM), numpy.max(tmpM),numpy.average(tmpM),numpy.min(numpy.abs(tmpM)) 
     405             
     406            phi = [0] * len(components) 
     407            #print "rotating", temperature, M 
     408            for i in range(len(M)): 
     409                if M[i] > 0: 
     410                    if temperature[i][1] < 0: 
     411                        temperature[i][0] = temperature[i][0] * 5 / 10 
     412                        temperature[i][1] = 1 
     413                        dirChange[i] += 1 
     414                         
     415                    phi[i] = temperature[i][0] * numpy.pi / 180 
     416                elif M[i] < 0:   
     417                    if temperature[i][1] > 0: 
     418                        temperature[i][0] = temperature[i][0] * 5 / 10 
     419                        temperature[i][1] = -1 
     420                        dirChange[i] += 1 
     421                     
     422                    phi[i] = -temperature[i][0] * numpy.pi / 180 
     423             
     424            # stop rotating when phi is to small to notice the rotation 
     425            if max(phi) < numpy.pi / 1800: 
     426                #print "breaking" 
     427                break 
     428             
     429            self.rotateVertices(components, phi) 
     430            if callbackUpdateCanvas: callbackUpdateCanvas() 
     431            if callbackProgress : callbackProgress(min([dirChange[i] for i in range(len(dirChange)) if M[i] != 0]), 9) 
     432            step += 1 
     433     
     434    def mdsUpdateData(self, components, mds, callbackUpdateCanvas): 
     435        """Translate and rotate the network components to computed positions.""" 
     436        component_props = [] 
     437        x_mds = [] 
     438        y_mds = [] 
     439        phi = [None] * len(components) 
     440        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) 
     441         
     442        if self.mdsType == MdsType.MDS: 
     443            x = [mds.points[u][0] for u in range(self.graph.nVertices)] 
     444            y = [mds.points[u][1] for u in range(self.graph.nVertices)] 
     445            self.graph.coors[0][range(self.graph.nVertices)] =  x 
     446            self.graph.coors[1][range(self.graph.nVertices)] =  y 
     447            if callbackUpdateCanvas: 
     448                callbackUpdateCanvas() 
     449            return 
     450         
     451        for i in range(len(components)):     
     452            component = components[i] 
     453             
     454            if len(mds.points) == len(components):  # if average linkage before 
     455                x_avg_mds = mds.points[i][0] 
     456                y_avg_mds = mds.points[i][1] 
     457            else:                                   # if not average linkage before 
     458                x = [mds.points[u][0] for u in component] 
     459                y = [mds.points[u][1] for u in component] 
     460         
     461                x_avg_mds = sum(x) / len(x)  
     462                y_avg_mds = sum(y) / len(y) 
     463                # compute rotation angle 
     464                c = [numpy.linalg.norm(numpy.cross(mds.points[u], [self.graph.coors[0][u],self.graph.coors[1][u]])) for u in component] 
     465                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] 
     466                phi[i] = sum(c) / sum(n) 
     467                #print phi 
     468             
     469            x = self.graph.coors[0][component] 
     470            y = self.graph.coors[1][component] 
     471             
     472            x_avg_graph = sum(x) / len(x) 
     473            y_avg_graph = sum(y) / len(y) 
     474             
     475            x_mds.append(x_avg_mds)  
     476            y_mds.append(y_avg_mds) 
     477 
     478            component_props.append((x_avg_graph, y_avg_graph, x_avg_mds, y_avg_mds, phi)) 
     479         
     480        w = max(self.graph.coors[0]) - min(self.graph.coors[0]) 
     481        h = max(self.graph.coors[1]) - min(self.graph.coors[1]) 
     482        d = math.sqrt(w**2 + h**2) 
     483        #d = math.sqrt(w*h) 
     484        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 +  
     485                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for  
     486                  (u, v) in self.graph.getEdges()] 
     487         
     488        if self.scalingRatio == 0: 
     489            pass 
     490        elif self.scalingRatio == 1: 
     491            self.mdsScaleRatio = d 
     492        elif self.scalingRatio == 2: 
     493            self.mdsScaleRatio = d / sum(e) * float(len(e)) 
     494        elif self.scalingRatio == 3: 
     495            self.mdsScaleRatio = 1 / sum(e) * float(len(e)) 
     496        elif self.scalingRatio == 4: 
     497            self.mdsScaleRatio = w * h 
     498        elif self.scalingRatio == 5: 
     499            self.mdsScaleRatio = math.sqrt(w * h) 
     500        elif self.scalingRatio == 6: 
     501            self.mdsScaleRatio = 1 
     502        elif self.scalingRatio == 7: 
     503            e_fr = 0 
     504            e_count = 0 
     505            for i in range(self.graph.nVertices): 
     506                for j in range(i + 1, self.graph.nVertices): 
     507                    x1 = self.graph.coors[0][i] 
     508                    y1 = self.graph.coors[1][i] 
     509                    x2 = self.graph.coors[0][j] 
     510                    y2 = self.graph.coors[1][j] 
     511                    e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2) 
     512                    e_count += 1 
     513            self.mdsScaleRatio = e_fr / e_count 
     514        elif self.scalingRatio == 8: 
     515            e_fr = 0 
     516            e_count = 0 
     517            for i in range(len(components)): 
     518                for j in range(i + 1, len(components)): 
     519                    x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, y_avg_mds_i, phi_i = component_props[i] 
     520                    x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, y_avg_mds_j, phi_j = component_props[j] 
     521                    e_fr += math.sqrt((x_avg_graph_i-x_avg_graph_j)**2 + (y_avg_graph_i-y_avg_graph_j)**2) 
     522                    e_count += 1 
     523            self.mdsScaleRatio = e_fr / e_count        
     524        elif self.scalingRatio == 9: 
     525            e_fr = 0 
     526            e_count = 0 
     527            for i in range(len(components)):     
     528                component = components[i] 
     529                x = self.graph.coors[0][component] 
     530                y = self.graph.coors[1][component] 
     531                for i in range(len(x)): 
     532                    for j in range(i + 1, len(y)): 
     533                        x1 = x[i] 
     534                        y1 = y[i] 
     535                        x2 = x[j] 
     536                        y2 = y[j] 
     537                        e_fr += math.sqrt((x1-x2)**2 + (y1-y2)**2) 
     538                        e_count += 1 
     539            self.mdsScaleRatio = e_fr / e_count 
     540         
     541        diag_mds =  math.sqrt((max(x_mds) - min(x_mds))**2 + (max(y_mds) - min(y_mds))**2) 
     542        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 +  
     543                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for  
     544                  (u, v) in self.graph.getEdges()] 
     545        e = sum(e) / float(len(e)) 
     546         
     547        x = [mds.points[u][0] for u in range(len(mds.points))] 
     548        y = [mds.points[u][1] for u in range(len(mds.points))] 
     549        w = max(x) - min(x) 
     550        h = max(y) - min(y) 
     551        d = math.sqrt(w**2 + h**2) 
     552         
     553        if len(x) == 1: 
     554            r = 1 
     555        else: 
     556            if self.scalingRatio == 0: 
     557                r = self.mdsScaleRatio / d * e 
     558            elif self.scalingRatio == 1: 
     559                r = self.mdsScaleRatio / d 
     560            elif self.scalingRatio == 2: 
     561                r = self.mdsScaleRatio / d * e 
     562            elif self.scalingRatio == 3: 
     563                r = self.mdsScaleRatio * e 
     564            elif self.scalingRatio == 4: 
     565                r = self.mdsScaleRatio / (w * h) 
     566            elif self.scalingRatio == 5: 
     567                r = self.mdsScaleRatio / math.sqrt(w * h) 
     568            elif self.scalingRatio == 6: 
     569                r = 1 / math.sqrt(self.graph.nVertices) 
     570            elif self.scalingRatio == 7: 
     571                e_mds = 0 
     572                e_count = 0 
     573                for i in range(len(mds.points)): 
     574                    for j in range(i): 
     575                        x1 = mds.points[i][0] 
     576                        y1 = mds.points[i][1] 
     577                        x2 = mds.points[j][0] 
     578                        y2 = mds.points[j][1] 
     579                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2) 
     580                        e_count += 1 
     581                r = self.mdsScaleRatio / e_mds * e_count 
     582            elif self.scalingRatio == 8: 
     583                e_mds = 0 
     584                e_count = 0 
     585                for i in range(len(components)): 
     586                    for j in range(i + 1, len(components)): 
     587                        x_avg_graph_i, y_avg_graph_i, x_avg_mds_i, y_avg_mds_i, phi_i = component_props[i] 
     588                        x_avg_graph_j, y_avg_graph_j, x_avg_mds_j, y_avg_mds_j, phi_j = component_props[j] 
     589                        e_mds += math.sqrt((x_avg_mds_i-x_avg_mds_j)**2 + (y_avg_mds_i-y_avg_mds_j)**2) 
     590                        e_count += 1 
     591                r = self.mdsScaleRatio / e_mds * e_count 
     592            elif self.scalingRatio == 9: 
     593                e_mds = 0 
     594                e_count = 0 
     595                for i in range(len(mds.points)): 
     596                    for j in range(i): 
     597                        x1 = mds.points[i][0] 
     598                        y1 = mds.points[i][1] 
     599                        x2 = mds.points[j][0] 
     600                        y2 = mds.points[j][1] 
     601                        e_mds += math.sqrt((x1-x2)**2 + (y1-y2)**2) 
     602                        e_count += 1 
     603                r = self.mdsScaleRatio / e_mds * e_count 
     604                 
     605            #r = self.mdsScaleRatio / d 
     606            #print "d", d, "r", r 
     607            #r = self.mdsScaleRatio / math.sqrt(self.graph.nVertices) 
     608             
     609        for i in range(len(components)): 
     610            component = components[i] 
     611            x_avg_graph, y_avg_graph, x_avg_mds, y_avg_mds, phi = component_props[i] 
     612             
     613#            if phi[i]:  # rotate vertices 
     614#                #print "rotate", i, phi[i] 
     615#                r = numpy.array([[numpy.cos(phi[i]), -numpy.sin(phi[i])], [numpy.sin(phi[i]), numpy.cos(phi[i])]])  #rotation matrix 
     616#                c = [x_avg_graph, y_avg_graph]  # center of mass in FR coordinate system 
     617#                v = [numpy.dot(numpy.array([self.graph.coors[0][u], self.graph.coors[1][u]]) - c, r) + c for u in component] 
     618#                self.graph.coors[0][component] = [u[0] for u in v] 
     619#                self.graph.coors[1][component] = [u[1] for u in v] 
     620                 
     621            # translate vertices 
     622            if not self.rotationOnly: 
     623                self.graph.coors[0][component] = (self.graph.coors[0][component] - x_avg_graph) / r + x_avg_mds 
     624                self.graph.coors[1][component] = (self.graph.coors[1][component] - y_avg_graph) / r + y_avg_mds 
     625                
     626        if callbackUpdateCanvas: 
     627            callbackUpdateCanvas() 
     628     
     629    def mdsCallback(self, a,b=None): 
     630        """Refresh the UI when running  MDS on network components.""" 
     631        if not self.mdsStep % self.mdsRefresh: 
     632            self.mdsUpdateData(self.mdsComponents, self.mds, self.callbackUpdateCanvas) 
     633             
     634            if self.mdsType == MdsType.exactSimulation: 
     635                self.mds.points = [[self.graph.coors[0][i], self.graph.coors[1][i]] for i in range(len(self.graph.coors))] 
     636                self.mds.freshD = 0 
     637             
     638            if self.callbackProgress != None: 
     639                self.callbackProgress(self.mds.avgStress, self.mdsStep) 
     640                 
     641        self.mdsStep += 1 
     642 
     643        if self.stopMDS: 
     644            return 0 
     645        else: 
     646            return 1 
     647             
     648    def mdsComponents(self, mdsSteps, mdsRefresh, callbackProgress=None, callbackUpdateCanvas=None, torgerson=0, minStressDelta = 0, avgLinkage=False, rotationOnly=False, mdsType=MdsType.componentMDS, scalingRatio=0, mdsFromCurrentPos=0): 
     649        """Position the network components according to similarities among them.""" 
     650 
     651        if self.vertexDistance == None: 
     652            self.information('Set distance matrix to input signal') 
     653            return 1 
     654         
     655        if self.graph == None: 
     656            return 1 
     657         
     658        if self.vertexDistance.dim != self.graph.nVertices: 
     659            return 1 
     660         
     661        self.mdsComponents = self.graph.getConnectedComponents() 
     662        self.mdsRefresh = mdsRefresh 
     663        self.mdsStep = 0 
     664        self.stopMDS = 0 
     665        self.vertexDistance.matrixType = orange.SymMatrix.Symmetric 
     666        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) 
     667        self.rotationOnly = rotationOnly 
     668        self.mdsType = mdsType 
     669        self.scalingRatio = scalingRatio 
     670 
     671        w = max(self.graph.coors[0]) - min(self.graph.coors[0]) 
     672        h = max(self.graph.coors[1]) - min(self.graph.coors[1]) 
     673        d = math.sqrt(w**2 + h**2) 
     674        #d = math.sqrt(w*h) 
     675        e = [math.sqrt((self.graph.coors[0][u] - self.graph.coors[0][v])**2 +  
     676                  (self.graph.coors[1][u] - self.graph.coors[1][v])**2) for  
     677                  (u, v) in self.graph.getEdges()] 
     678        self.mdsScaleRatio = d / sum(e) * float(len(e)) 
     679        #print d / sum(e) * float(len(e)) 
     680         
     681        if avgLinkage: 
     682            matrix = self.vertexDistance.avgLinkage(self.mdsComponents) 
     683        else: 
     684            matrix = self.vertexDistance 
     685         
     686        #if self.mds == None:  
     687        self.mds = orngMDS.MDS(matrix) 
     688         
     689        if mdsFromCurrentPos: 
     690            if avgLinkage: 
     691                for u, c in enumerate(self.mdsComponents): 
     692                    x = sum(self.graph.coors[0][c]) / len(c) 
     693                    y = sum(self.graph.coors[1][c]) / len(c) 
     694                    self.mds.points[u][0] = x 
     695                    self.mds.points[u][1] = y 
     696            else: 
     697                for u in range(self.graph.nVertices): 
     698                    self.mds.points[u][0] = self.graph.coors[0][u]  
     699                    self.mds.points[u][1] = self.graph.coors[1][u] 
     700             
     701        # set min stress difference between 0.01 and 0.00001 
     702        self.minStressDelta = minStressDelta 
     703        self.callbackUpdateCanvas = callbackUpdateCanvas 
     704        self.callbackProgress = callbackProgress 
     705         
     706        if torgerson: 
     707            self.mds.Torgerson()  
     708 
     709        self.mds.optimize(mdsSteps, orngMDS.SgnRelStress, self.minStressDelta, progressCallback=self.mdsCallback) 
     710        self.mdsUpdateData(self.mdsComponents, self.mds, callbackUpdateCanvas) 
     711         
     712        if callbackProgress != None: 
     713            callbackProgress(self.mds.avgStress, self.mdsStep) 
     714         
     715        del self.rotationOnly 
     716        del self.diag_coors 
     717        del self.mdsRefresh 
     718        del self.mdsStep 
     719        #del self.mds 
     720        del self.mdsComponents 
     721        del self.minStressDelta 
     722        del self.callbackUpdateCanvas 
     723        del self.callbackProgress 
     724        del self.mdsType 
     725        del self.mdsScaleRatio 
     726        del self.scalingRatio 
     727        return 0 
     728 
     729    def mdsComponentsAvgLinkage(self, mdsSteps, mdsRefresh, callbackProgress=None, callbackUpdateCanvas=None, torgerson=0, minStressDelta = 0, scalingRatio=0, mdsFromCurrentPos=0): 
     730        return self.mdsComponents(mdsSteps, mdsRefresh, callbackProgress, callbackUpdateCanvas, torgerson, minStressDelta, True, scalingRatio=scalingRatio, mdsFromCurrentPos=mdsFromCurrentPos) 
     731 
     732    def saveNetwork(self, fn): 
     733        print "This method is deprecated. You should use orngNetwork.Network.saveNetwork" 
     734        name = '' 
     735        try: 
     736            root, ext = os.path.splitext(fn) 
     737            if ext == '': 
     738                fn = root + '.net' 
     739             
     740            graphFile = file(fn, 'w+') 
     741        except IOError: 
     742            return 1 
     743 
     744        graphFile.write('### This file was generated with Orange Network Visualizer ### \n\n\n') 
     745        if name == '': 
     746            graphFile.write('*Network ' + '"no name" \n\n') 
     747        else: 
     748            graphFile.write('*Network ' + str(name) + ' \n\n') 
     749 
     750 
     751        #izpis opisov vozlisc 
     752        print "e", self.graph.nEdgeTypes 
     753        graphFile.write('*Vertices %8d %8d\n' % (self.graph.nVertices, self.graph.nEdgeTypes)) 
     754        for v in range(self.graph.nVertices): 
     755            graphFile.write('% 8d ' % (v + 1)) 
     756#            if verticesParms[v].label!='': 
     757#                self.GraphFile.write(str('"'+ verticesParms[v].label + '"') + ' \t') 
     758#            else: 
     759            try: 
     760                label = self.graph.items[v]['label'] 
     761                graphFile.write(str('"' + str(label) + '"') + ' \t') 
     762            except: 
     763                graphFile.write(str('"' + str(v) + '"') + ' \t') 
     764             
     765            x = self.network.coors[0][v] 
     766            y = self.network.coors[1][v] 
     767            #if x < 0: x = 0 
     768            #if x >= 1: x = 0.9999 
     769            #if y < 0: y = 0 
     770            #if y >= 1: y = 0.9999 
     771            z = 0.5000 
     772            graphFile.write('%.4f    %.4f    %.4f\t' % (x, y, z)) 
     773            graphFile.write('\n') 
     774 
     775        #izpis opisov povezav 
     776        #najprej neusmerjene 
     777        if self.graph.directed: 
     778            graphFile.write('*Arcs \n') 
     779            for (i, j) in self.graph.getEdges(): 
     780                if len(self.graph[i, j]) > 0: 
     781                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, float(str(self.graph[i, j])))) 
     782                    graphFile.write('\n') 
     783        else: 
     784            graphFile.write('*Edges \n') 
     785            for (i, j) in self.graph.getEdges(): 
     786                if len(self.graph[i, j]) > 0: 
     787                    graphFile.write('%8d %8d %f' % (i + 1, j + 1, float(str(self.graph[i, j])))) 
     788                    graphFile.write('\n') 
     789 
     790        graphFile.write('\n') 
     791        graphFile.close() 
     792         
     793        if self.graph.items != None and len(self.graph.items) > 0: 
     794            (name, ext) = os.path.splitext(fn) 
     795            self.graph.items.save(name + "_items.tab") 
     796             
     797        if self.graph.links != None and len(self.graph.links) > 0: 
     798            (name, ext) = os.path.splitext(fn) 
     799            self.graph.links.save(name + "_links.tab") 
     800 
     801        return 0 
     802     
     803    def readNetwork(self, fn, directed=0): 
     804        print "This method is deprecated. You should use orngNetwork.Network.readNetwork" 
     805        network = Network(1,directed) 
     806        net = network.readPajek(fn, directed) 
     807        self.setGraph(net) 
     808        self.graph = net 
     809        return net 
     810     
     811class NetworkClustering(): 
     812 
     813    random.seed(0) 
     814     
     815    def __init__(self, network): 
     816        self.net = network 
     817         
     818         
     819    def labelPropagation(self, results2items=0, resultHistory2items=0): 
     820        """Label propagation method from Raghavan et al., 2007""" 
     821         
     822        vertices = range(self.net.nVertices) 
     823        labels = range(self.net.nVertices) 
     824        lblhistory = [] 
     825        #consecutiveStop = 0 
     826        for i in range(1000): 
     827            random.shuffle(vertices) 
     828            stop = 1 
     829            for v in vertices: 
     830                nbh = self.net.getNeighbours(v) 
     831                if len(nbh) == 0: 
     832                    continue 
     833                 
     834                lbls = [labels[u] for u in nbh] 
     835                lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)] 
     836                m = max(lbls)[0] 
     837                mlbls = [l for c, l in lbls if c >= m] 
     838                lbl = random.choice(mlbls) 
     839                 
     840                if labels[v] not in mlbls: stop = 0 
     841                labels[v] = lbl 
     842                 
     843            lblhistory.append([str(l) for l in labels]) 
     844            # if stopping condition might be satisfied, check it 
     845            if stop: 
     846                for v in vertices: 
     847                    nbh = self.net.getNeighbours(v) 
     848                    if len(nbh) == 0: continue 
     849                    lbls = [labels[u] for u in nbh] 
     850                    lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)] 
     851                    m = max(lbls)[0] 
     852                    mlbls = [l for c, l in lbls if c >= m] 
     853                    if labels[v] not in mlbls:  
     854                        stop = 0 
     855                        break 
     856                if stop: break 
     857                     
     858        if results2items and not resultHistory2items: 
     859            attrs = [orange.EnumVariable('clustering label propagation', values=list(set([l for l in lblhistory[-1]])))] 
     860            dom = orange.Domain(attrs, 0) 
     861            data = orange.ExampleTable(dom, [[l] for l in lblhistory[-1]]) 
     862            self.net.items = data if self.net.items == None else orange.ExampleTable([self.net.items, data]) 
     863        if resultHistory2items: 
     864            attrs = [orange.EnumVariable('c'+ str(i), values=list(set([l for l in lblhistory[0]]))) for i,labels in enumerate(lblhistory)] 
     865            dom = orange.Domain(attrs, 0) 
     866            # transpose history 
     867            data = map(list, zip(*lblhistory)) 
     868            data = orange.ExampleTable(dom, data) 
     869            self.net.items = data if self.net.items == None else orange.ExampleTable([self.net.items, data]) 
     870 
     871        return labels 
     872     
     873     
Note: See TracChangeset for help on using the changeset viewer.