Changeset 7963:aad78c2dc66d in orange


Ignore:
Timestamp:
06/01/11 15:56:02 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
2aca6d5263c5829b62160a2d4fb88226d73bc057
Message:

Added FragViz methods.

File:
1 edited

Legend:

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

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