Changeset 4021:dd1c64a1df98 in orange


Ignore:
Timestamp:
07/25/07 00:06:48 (7 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
8c2fe204b807a015cd8590b8c037055caf6aaf58
Message:

Added:

  • radial F-R algorithm
  • circular original
  • circular random
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • orange/OrangeWidgets/Prototypes/OWNetwork.py

    r4006 r4021  
    135135        self.optimizeBox = OWGUI.radioButtonsInBox(self.mainTab, self, "optimizeWhat", [], "Optimize", addSpace=True) 
    136136        OWGUI.button(self.optimizeBox, self, "Random", callback=self.random) 
    137         OWGUI.button(self.optimizeBox, self, "F-R", callback=self.ff) 
    138         OWGUI.button(self.optimizeBox, self, "Circular", callback=self.circular) 
     137        OWGUI.button(self.optimizeBox, self, "F-R", callback=self.fr) 
     138        OWGUI.button(self.optimizeBox, self, "F-R Radial", callback=self.frRadial) 
     139        OWGUI.button(self.optimizeBox, self, "Circular Original", callback=self.circularOriginal) 
     140        OWGUI.button(self.optimizeBox, self, "Circular Random", callback=self.circularRandom) 
    139141        OWGUI.separator(self.optimizeBox) 
    140142        OWGUI.widgetLabel("Optimize") 
     
    406408         
    407409         
    408     def ff(self): 
     410    def fr(self): 
    409411        print "OWNetwork/ff..." 
    410412        if self.visualize == None:   #grafa se ni 
     
    418420        if refreshRate <   1: refreshRate = 1; 
    419421        if refreshRate > 1500: refreshRate = 1500; 
    420         print "refreshRate: " + str(refreshRate) 
    421         #najprej nakljucne koordinate za vsa vozlisca 
    422         #- self.visualize.nVertices() / 50 + 100 
    423         #if refreshRate < 5: 
    424         #    refreshRate = 5; 
    425          
     422        print "refreshRate: " + str(refreshRate)         
    426423        tolerance = 5 
    427424        initTemp = 1000 
    428         #refreshRate = 1 
    429425        initTemp = self.visualize.fruchtermanReingold(refreshRate, initTemp, self.graph.hiddenNodes) 
    430426        self.updateCanvas() 
    431          
    432 #        self.visualize.fruchtermanReingold(refreshRate, initTemp) 
    433          
    434 #        while True: 
    435 #            print initTemp 
    436 #            initTemp = self.visualize.fruchtermanReingold(refreshRate, initTemp) 
    437 #             
    438 #            if (initTemp <= tolerance): 
    439 #                #self.visualize.postProcess() 
    440 #                print "OWNetwork/ff: updating canvas..." 
    441 #                self.updateCanvas() 
    442 #                return 
    443 #            print "OWNetwork/ff: updating canvas..." 
    444 #            self.updateCanvas() 
    445427        print "done." 
    446428         
    447     def circular(self): 
    448         pass 
     429    def frRadial(self): 
     430        print "F-R Radial" 
     431         
     432        k = 1.13850193174e-008 
     433        nodes = self.visualize.nVertices() 
     434        t = k * nodes * nodes 
     435        refreshRate = int(5.0 / t) 
     436        if refreshRate <   1: refreshRate = 1; 
     437        if refreshRate > 1500: refreshRate = 1500; 
     438        print "refreshRate: " + str(refreshRate) 
     439         
     440        tolerance = 5 
     441        initTemp = 100 
     442         
     443        initTemp = self.visualize.radialFruchtermanReingold(0, refreshRate, initTemp) 
     444        self.updateCanvas() 
     445         
     446    def circularOriginal(self): 
     447        print "Circular Original" 
     448        self.visualize.circularOriginal() 
     449        self.updateCanvas() 
     450         
     451    def circularRandom(self): 
     452        print "Circular Random" 
     453        self.visualize.circularRandom() 
     454        self.updateCanvas() 
    449455 
    450456    def setVertexColor(self): 
  • source/orangeom/networkoptimization.cpp

    r3999 r4021  
    2121 
    2222#include "ppp/networkoptimization.ppp" 
     23#define PI 3.14159265 
    2324 
    2425TNetworkOptimization::TNetworkOptimization() 
     
    4647#endif 
    4748#endif 
    48  
     49  
    4950TNetworkOptimization::~TNetworkOptimization() 
    5051{ 
     
    8384 
    8485 
     86// type 
     87// 0 - original 
     88// 1 - random 
     89int TNetworkOptimization::circular(int type) 
     90{ 
     91    int xCenter = width / 2; 
     92    int yCenter = height / 2; 
     93    int r = (width < height) ? width * 0.38 : height * 0.38; 
     94 
     95    int i; 
     96    double fi = PI; 
     97    double step = 2 * PI / nVertices; 
     98 
     99    srand(time(NULL)); 
     100    vector<int> vertices; 
     101    if (type == 1) 
     102        for (i = 0; i < nVertices; i++) 
     103            vertices.push_back(i); 
     104 
     105    for (i = 0; i < nVertices; i++) 
     106    { 
     107        if (type == 0) 
     108        { 
     109            pos[i][0] = r * cos(fi) + width; 
     110            pos[i][1] = r * sin(fi) + height; 
     111        } 
     112        else if (type == 1) 
     113        { 
     114            int ndx = rand() % vertices.size(); 
     115 
     116            pos[vertices[ndx]][0] = r * cos(fi) + width; 
     117            pos[vertices[ndx]][1] = r * sin(fi) + height; 
     118             
     119            vertices.erase(vertices.begin() + ndx); 
     120        } 
     121 
     122        fi = fi - step; 
     123    } 
     124 
     125    return 0; 
     126} 
    85127int TNetworkOptimization::fruchtermanReingold(int steps) 
    86 { 
     128{  
    87129    /* 
    88130    cout << "nVertices: " << nVertices << endl << endl; 
     
    210252    return 0; 
    211253} 
     254 
     255 
     256int TNetworkOptimization::radialFruchtermanReingold(int steps, int nCircles) 
     257{  
     258    /* 
     259    cout << "nVertices: " << nVertices << endl << endl; 
     260    dumpCoordinates(); 
     261    /**/ 
     262    double **disp = (double**)malloc(nVertices * sizeof (double)); 
     263    int i = 0; 
     264 
     265    for (i = 0; i < nVertices; i++) 
     266    { 
     267        disp[i] = (double *)calloc(2, sizeof(double)); 
     268 
     269        if (disp[i] == NULL) 
     270        { 
     271            cerr << "Couldn't allocate memory (disp[])\n"; 
     272            return 1; 
     273        } 
     274    } 
     275 
     276    int radius = width / nCircles / 2; 
     277    //cout << "radius: " << radius << endl; 
     278    int count = 0; 
     279    double kk = 1; 
     280    double localTemparature = 5; 
     281    double area = width * height; 
     282 
     283    k2 = area / nVertices; 
     284    k = sqrt(k2); 
     285    kk = 2 * k; 
     286    double kk2 = kk * kk; 
     287    cout << "Miha" << endl; 
     288    // iterations 
     289    for (i = 0; i < steps; i++) 
     290    { 
     291        //cout << "iteration: " << i << endl; 
     292        // reset disp 
     293        int j = 0; 
     294        for (j = 0; j < nVertices; j++) 
     295        { 
     296            disp[j][0] = 0; 
     297            disp[j][1] = 0; 
     298        } 
     299 
     300        int v = 0; 
     301        // calculate repulsive force 
     302        for (v = 0; v < nVertices - 1; v++) 
     303        { 
     304            for (int u = v + 1; u < nVertices; u++) 
     305            { 
     306                // only for vertices on the same level 
     307                //if (level[v] != level[u]) 
     308                //  continue; 
     309         
     310                double difX = pos[v][0] - pos[u][0]; 
     311                double difY = pos[v][1] - pos[u][1]; 
     312 
     313                double dif2 = difX * difX + difY * difY;  
     314 
     315                if (dif2 < kk2) 
     316                { 
     317                    if (dif2 == 0) 
     318                        dif2 = 1; 
     319 
     320                    double dX = difX * k2 / dif2; 
     321                    double dY = difY * k2 / dif2; 
     322 
     323                    disp[v][0] = disp[v][0] + dX; 
     324                    disp[v][1] = disp[v][1] + dY; 
     325 
     326                    disp[u][0] = disp[u][0] - dX; 
     327                    disp[u][1] = disp[u][1] - dY; 
     328                } 
     329            } 
     330        } 
     331        // calculate attractive forces 
     332        for (j = 0; j < nLinks; j++) 
     333        { 
     334            int v = links[0][j]; 
     335            int u = links[1][j]; 
     336 
     337            // only for vertices on the same level 
     338            //if (level[v] != level[u]) 
     339            //  continue; 
     340 
     341            double difX = pos[v][0] - pos[u][0]; 
     342            double difY = pos[v][1] - pos[u][1]; 
     343 
     344            double dif = sqrt(difX * difX + difY * difY); 
     345 
     346            double dX = difX * dif / k; 
     347            double dY = difY * dif / k; 
     348 
     349            disp[v][0] = disp[v][0] - dX; 
     350            disp[v][1] = disp[v][1] - dY; 
     351 
     352            disp[u][0] = disp[u][0] + dX; 
     353            disp[u][1] = disp[u][1] + dY; 
     354        } 
     355        // limit the maximum displacement to the temperature t 
     356        // and then prevent from being displaced outside frame 
     357        for (v = 0; v < nVertices; v++) 
     358        { 
     359            double dif = sqrt(disp[v][0] * disp[v][0] + disp[v][1] * disp[v][1]); 
     360 
     361            if (dif == 0) 
     362                dif = 1; 
     363 
     364            pos[v][0] = pos[v][0] + (disp[v][0] * min(fabs(disp[v][0]), temperature) / dif); 
     365            pos[v][1] = pos[v][1] + (disp[v][1] * min(fabs(disp[v][1]), temperature) / dif); 
     366 
     367            double distance = (pos[v][0] - (width/2)) * (pos[v][0] - (width/2)) + (pos[v][1] - (height/2)) * (pos[v][1] - (height/2)); 
     368            //cout << "x: " << pos[v][0] << " y: " << pos[v][1] << " width: " << width << " height: " << height << endl; 
     369            //cout << "distance: " << distance << " radius: " << (level[v] * radius) * (level[v] * radius) << endl; 
     370            if (level[v] == 0) 
     371            { 
     372                // move to center 
     373                pos[v][0] = width / 2; 
     374                pos[v][1] = height / 2; 
     375 
     376                //cout << "center, x: " << pos[v][0] << " y: " << pos[v][1] << endl; 
     377            } 
     378            //* 
     379            else if (distance > ((level[v] * radius) * (level[v] * radius))) 
     380            { 
     381                // move to outer ring 
     382                double fi = atan((pos[v][1] - (height / 2)) / (pos[v][0] - (width / 2))); 
     383 
     384                pos[v][0] = level[v] * radius * cos(fi) + (width / 2); 
     385                pos[v][1] = level[v] * radius * sin(fi) + (height / 2); 
     386 
     387                //cout << "outer, x: " << pos[v][0] << " y: " << pos[v][1] << " radius: " << radius << " fi: " << fi << " level: " << level[v] << " v: " << v << endl; 
     388            } 
     389            else if (distance < (((level[v] - 1) * radius) * ((level[v] - 1) * radius))) 
     390            { 
     391                // move to inner ring 
     392                double fi = atan((pos[v][1] - (height / 2)) / (pos[v][0] - (width / 2))); 
     393 
     394                pos[v][0] = (level[v] - 1) * radius * cos(fi) + (width / 2); 
     395                pos[v][1] = (level[v] - 1) * radius * sin(fi) + (height / 2); 
     396 
     397                //cout << "inner, x: " << pos[v][0] << " y: " << pos[v][1] << endl; 
     398            } 
     399            /**/ 
     400        } 
     401        //cout << temperature << ", "; 
     402        temperature = temperature * coolFactor; 
     403    } 
     404    /* 
     405    for (i = 0; i < nVertices; i++) 
     406        cout << "level " << i << ": " << level[i] << endl; 
     407    /**/ 
     408    //cout << "end coors: " << endl; 
     409    //dumpCoordinates(); 
     410 
     411    // free space 
     412    for (i = 0; i < nVertices; i++) 
     413    { 
     414        free(disp[i]); 
     415        disp[i] = NULL; 
     416    } 
     417    //cout << endl; 
     418    free(disp); 
     419    disp = NULL; 
     420     
     421    return 0; 
     422} 
     423 
    212424 
    213425 
     
    407619    //cout << "networkoptimization.cpp/setGraph: setting graph..." << endl; 
    408620    if (graphOpt->setGraph(graph) > 0) 
    409     { 
    410621        PYERROR(PyExc_SystemError, "setGraph failed", NULL); 
    411     } 
     622     
     623    graphOpt->graphStructure = graph; 
    412624 
    413625    //cout << "done." << endl; 
     626    RETURN_NONE; 
     627  PyCATCH 
     628} 
     629 
     630bool hasVertex(int vertex, vector<int> list) 
     631{ 
     632    int i; 
     633    for (i = 0; i < list.size(); i++) 
     634    { 
     635        //cout << list[i] << " " << vertex << endl; 
     636        if (list[i] == vertex) 
     637            return true; 
     638    } 
     639 
     640    return false; 
     641} 
     642 
     643PyObject *NetworkOptimization_radialFruchtermanReingold(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(center, steps, temperature) -> temperature") 
     644{ 
     645  PyTRY 
     646    int steps, center; 
     647    double temperature = 0; 
     648 
     649    if (!PyArg_ParseTuple(args, "iid:NetworkOptimization.radialFruchtermanReingold", &center, &steps, &temperature)) 
     650        return NULL; 
     651 
     652    CAST_TO(TNetworkOptimization, graph); 
     653 
     654    graph->pos[center][0] = graph->width / 2; 
     655    graph->pos[center][1] = graph->height / 2; 
     656 
     657    int nCircles = 6; 
     658    int r = graph->width / nCircles / 2; 
     659 
     660    graph->level = new int[graph->nVertices]; 
     661    int i; 
     662    for (i = 0; i < graph->nVertices; i++) 
     663        graph->level[i] = nCircles; 
     664 
     665    vector<int> removedLinks[2]; 
     666    vector<int> vertices; 
     667    vector<int> allVertices; 
     668    vertices.push_back(center); 
     669    graph->level[center] = 0; 
     670 
     671    for (i = 0; i < nCircles; i++) 
     672    { 
     673        // position vertices 
     674        double fi = 360 / vertices.size(); 
     675        int v; 
     676        for (v = 0; v < vertices.size(); v++) 
     677        { 
     678            double x = i * r * cos(v * fi * PI / 180) + (graph->width / 2); 
     679            double y = i * r * sin(v * fi * PI / 180) + (graph->height / 2); 
     680 
     681            graph->pos[vertices[v]][0] = x; 
     682            graph->pos[vertices[v]][1] = y; 
     683 
     684            //cout << "v: " << vertices[v] << " X: " << x << " Y: " << y << " level: " << graph->level[vertices[v]] << endl; 
     685        } 
     686        //cout << endl; 
     687        vector<int> newVertices; 
     688        for (v = 0; v < vertices.size(); v++) 
     689        { 
     690            int j; 
     691            int node = vertices[v]; 
     692 
     693            for (j = graph->links[0].size() - 1; j >= 0; j--) 
     694            { 
     695                if (graph->links[0][j] == node) 
     696                { 
     697                    //cout << "j: " << j << " u: " << graph->links1[0][j] << " v: " << graph->links1[1][j] << endl; 
     698                    removedLinks[0].push_back(graph->links[0][j]); 
     699                    removedLinks[1].push_back(graph->links[1][j]); 
     700 
     701                    if (!hasVertex(graph->links[1][j], allVertices)) 
     702                    { 
     703                        newVertices.push_back(graph->links[1][j]); 
     704                        allVertices.push_back(graph->links[1][j]); 
     705                        graph->level[graph->links[1][j]] = i + 1; 
     706                    } 
     707                    graph->links[0].erase(graph->links[0].begin() + j); 
     708                    graph->links[1].erase(graph->links[1].begin() + j); 
     709                } 
     710                else if (graph->links[1][j] == node) 
     711                { 
     712                    //cout << "j: " << j << " u: " << graph->links1[0][j] << " v: " << graph->links1[1][j] << endl; 
     713                    removedLinks[0].push_back(graph->links[0][j]); 
     714                    removedLinks[1].push_back(graph->links[1][j]); 
     715 
     716                    if (!hasVertex(graph->links[0][j], allVertices)) 
     717                    { 
     718                        //cout << "adding: " <<  
     719                        newVertices.push_back(graph->links[0][j]); 
     720                        allVertices.push_back(graph->links[0][j]); 
     721                        graph->level[graph->links[0][j]] = i + 1; 
     722                    } 
     723 
     724                    graph->links[0].erase(graph->links[0].begin() + j); 
     725                    graph->links[1].erase(graph->links[1].begin() + j); 
     726                } 
     727            } 
     728        } 
     729 
     730        vertices.clear(); 
     731 
     732        if (newVertices.size() == 0) 
     733            break; 
     734 
     735        for (v = 0; v < newVertices.size(); v++) 
     736        { 
     737            vertices.push_back(newVertices[v]); 
     738        } 
     739    } 
     740    // adds back removed links 
     741    for (i = 0; i < removedLinks[0].size(); i++) 
     742    { 
     743        graph->links[0].push_back(removedLinks[0][i]); 
     744        graph->links[1].push_back(removedLinks[1][i]); 
     745    } 
     746 
     747    graph->temperature = temperature; 
     748    graph->coolFactor = exp(log(10.0/10000.0) / steps); 
     749    /* 
     750    for (i = 0; i < graph->nVertices; i++) 
     751        cout << "level " << i << ": " << graph->level[i] << endl; 
     752    /**/ 
     753    if (graph->radialFruchtermanReingold(steps, nCircles) > 0) 
     754    { 
     755        delete[] graph->level; 
     756        PYERROR(PyExc_SystemError, "radialFruchtermanReingold failed", NULL); 
     757    } 
     758 
     759    delete[] graph->level; 
     760 
     761    return Py_BuildValue("d", graph->temperature); 
     762  PyCATCH 
     763} 
     764 
     765 
     766PyObject *NetworkOptimization_circularOriginal(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None") 
     767{ 
     768  PyTRY 
     769    CAST_TO(TNetworkOptimization, graph); 
     770    graph->circular(0); 
     771    RETURN_NONE; 
     772  PyCATCH 
     773} 
     774 
     775PyObject *NetworkOptimization_circularRandom(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None") 
     776{ 
     777  PyTRY 
     778    CAST_TO(TNetworkOptimization, graph); 
     779    graph->circular(1); 
    414780    RETURN_NONE; 
    415781  PyCATCH 
  • source/orangeom/networkoptimization.hpp

    r3748 r4021  
    6565    void random(); 
    6666    int fruchtermanReingold(int steps); 
     67    int radialFruchtermanReingold(int steps, int nCircles); 
     68    int circular(int type); 
     69    //int circularRandom(); 
    6770    double getTemperature() {return temperature;} 
    6871    void setTemperature(double t) {temperature = t;} 
     
    8285    double height;  
    8386    PyArrayObject *coors; 
     87    TGraph *graphStructure; 
    8488 
    8589    int nLinks; 
     
    8791    vector<int> links[2]; 
    8892    double **pos; 
     93    int *level; 
    8994}; 
    9095 
Note: See TracChangeset for help on using the changeset viewer.