Changeset 3691:7e2a7dc6e936 in orange


Ignore:
Timestamp:
05/27/07 14:51:27 (7 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
79c6373940dcd863c1a1b7ef7f196c523c6cfad6
Message:

* empty log message *

Location:
source/orangeom
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orangeom/networkoptimization.cpp

    r3687 r3691  
    3636    links = NULL; 
    3737    pos = NULL; 
    38     temperature = sqrt((double)(width*width + height*height)) / 10; 
     38    temperature = sqrt(width*width + height*height) / 10; 
    3939    coolFactor = 0.96; 
    4040} 
     
    7979    for (i = 0; i < nVertices; i++) 
    8080    { 
    81             pos[i][0] = rand() % width; 
    82             pos[i][1] = rand() % height; 
    83     } 
    84 } 
     81        pos[i][0] = rand() % (int)width; 
     82        pos[i][1] = rand() % (int)height; 
     83    } 
     84} 
     85 
     86static int julery_isqrt(int val) { 
     87        int temp, g=0, b = 0x8000, bshft = 15; 
     88        do { 
     89            if (val >= (temp = (((g << 1) + b)<<bshft--))) { 
     90               g += b; 
     91               val -= temp; 
     92            } 
     93        } while (b >>= 1); 
     94        return g; 
     95    } 
    8596 
    8697int TNetworkOptimization::fruchtermanReingold(int steps) 
     
    8899    /* 
    89100    cout << "nVertices: " << nVertices << endl << endl; 
    90     dumpCoordinates(pos, nVertices, 2); 
     101    dumpCoordinates(); 
    91102    /**/ 
     103    double **disp = (double**)malloc(nVertices * sizeof (double)); 
    92104    int i = 0; 
     105    for (i = 0; i < nVertices; i++) 
     106    { 
     107        disp[i] = (double *)calloc(2, sizeof(double)); 
     108 
     109        if (disp[i] == NULL) 
     110        { 
     111            cerr << "Couldn't allocate memory (disp[])\n"; 
     112            return 1; 
     113        } 
     114    } 
     115 
    93116    int count = 0; 
    94117    double kk = 1; 
    95     double **disp = (double**)malloc(nVertices * sizeof (double)); 
    96118    double localTemparature = 5; 
    97  
    98     for (i = 0; i < nVertices; i++) 
    99     { 
    100         disp[i] = (double *)calloc(2, sizeof(double)); 
    101  
    102         if (disp[i] == NULL) 
    103         { 
    104             cerr << "Couldn't allocate memory (disp[])\n"; 
    105             return 1; 
    106         } 
    107     } 
    108  
    109     int area = width * height; 
     119    double area = width * height; 
     120 
    110121    k2 = area / nVertices; 
    111122    k = sqrt(k2); 
    112123    kk = 2 * k; 
     124    double kk2 = kk * kk; 
    113125 
    114126    // iterations 
    115127    for (i = 0; i < steps; i++) 
    116128    { 
     129        //cout << "iteration: " << i << endl; 
    117130        // reset disp 
    118131        int j = 0; 
     
    123136        } 
    124137 
     138        int v = 0; 
    125139        // calculate repulsive force 
    126         int v = 0; 
     140        //cout << "repulsive" << endl; 
    127141        for (v = 0; v < nVertices - 1; v++) 
    128142        { 
     
    132146                double difY = pos[v][1] - pos[u][1]; 
    133147 
    134                 double dif = sqrt(difX * difX + difY * difY); 
    135  
    136                 if (dif < kk) 
    137                 { 
    138                     if (dif == 0) 
    139                         dif = 0.01; 
    140  
    141                     double d = dif * dif / k2; 
    142                     double dX = difX / d; 
    143                     double dY = difY / d; 
     148                double dif2 = difX * difX + difY * difY;  
     149 
     150                if (dif2 < kk2) 
     151                { 
     152                    if (dif2 == 0) 
     153                        dif2 = 1; 
     154 
     155                    double dX = difX * k2 / dif2; 
     156                    double dY = difY * k2 / dif2; 
    144157 
    145158                    disp[v][0] = disp[v][0] + dX; 
     
    151164            } 
    152165        } 
    153  
    154166        // calculate attractive forces 
     167        //cout << "attractive" << endl; 
    155168        for (j = 0; j < nLinks; j++) 
    156169        { 
     
    158171            int u = links[j][1]; 
    159172 
    160             //cout << "v: " << v << " u: " << u << endl; 
    161  
    162             // cout << "     v: " << v << " u: " << u << " w: " << edge->weights << endl; 
    163173            double difX = pos[v][0] - pos[u][0]; 
    164174            double difY = pos[v][1] - pos[u][1]; 
     
    166176            double dif = sqrt(difX * difX + difY * difY); 
    167177 
    168             if (dif == 0) 
    169                 dif = 0.01; 
    170  
    171             double d = dif / k; 
    172             double dX = difX * d; 
    173             double dY = difY * d; 
     178            double dX = difX * dif / k; 
     179            double dY = difY * dif / k; 
    174180 
    175181            disp[v][0] = disp[v][0] - dX; 
     
    179185            disp[u][1] = disp[u][1] + dY; 
    180186        } 
    181  
     187        //cout << "limit" << endl; 
    182188        // limit the maximum displacement to the temperature t 
    183189        // and then prevent from being displaced outside frame 
     
    187193 
    188194            if (dif == 0) 
    189                 dif = 0.01; 
    190  
    191             pos[v][0] = pos[v][0] + (disp[v][0] / dif * min(fabs(disp[v][0]), temperature)); 
    192             pos[v][1] = pos[v][1] + (disp[v][1] / dif * min(fabs(disp[v][1]), temperature)); 
     195                dif = 1; 
     196 
     197            pos[v][0] = pos[v][0] + (disp[v][0] * min(abs(disp[v][0]), temperature) / dif); 
     198            pos[v][1] = pos[v][1] + (disp[v][1] * min(abs(disp[v][1]), temperature) / dif); 
    193199 
    194200            //pos[v][0] = min((double)width,  max((double)0, pos[v][0])); 
     
    198204        temperature = temperature * coolFactor; 
    199205    } 
     206 
     207    //cout << "end coors: " << endl; 
     208    //dumpCoordinates(); 
    200209 
    201210    // free space 
     
    208217    free(disp); 
    209218    disp = NULL; 
    210     //dumpCoordinates(); 
     219     
    211220    return 0; 
    212221} 
     
    242251/* ==== Allocate a double *vector (vec of pointers) ====================== 
    243252    Memory is Allocated!  See void free_Carray(double ** )                  */ 
    244 double **TNetworkOptimization::ptrvector(long n)  { 
     253double **TNetworkOptimization::ptrvector(double n)  { 
    245254    double **v; 
    246255    v=(double **)malloc((size_t) (n*sizeof(double))); 
     256 
    247257    if (!v)   { 
    248258        printf("In **ptrvector. Allocation of memory for double array failed."); 
    249         exit(0);  } 
     259        exit(0);   
     260    } 
    250261    return v; 
    251262} 
     
    263274    a = (double *) arrayin->data;  /* pointer to arrayin data as double */ 
    264275     
    265     for (i = 0; i < n; i++) 
    266     { 
     276    for (i = 0; i < n; i++) { 
    267277        c[i] = a + i * m; 
    268278    } 
     
    447457 
    448458    graph->temperature = temperature; 
    449     graph->coolFactor = exp(log(0.02) / steps); 
     459    graph->coolFactor = exp(log(10.0/10000.0) / steps); 
    450460     
    451461    if (graph->fruchtermanReingold(steps) > 0) 
  • source/orangeom/networkoptimization.hpp

    r3686 r3691  
    6363    void dumpCoordinates(); 
    6464 
    65     double **ptrvector(long n); 
     65    double **ptrvector(double n); 
    6666    double **pymatrix_to_Carrayptrs(PyArrayObject *arrayin); 
    6767    bool *pyvector_to_Carrayptrs(PyArrayObject *arrayin); 
     
    8686    } 
    8787 
    88     float k; //PR 
    89     float k2; //PR 
     88    double k; //PR 
     89    double k2; //PR 
    9090    double temperature; 
    9191    double coolFactor; 
    92     int width; //P 
    93     int height; //PR 
     92    double width; //P 
     93    double height; //PR 
    9494    PyArrayObject *coors; 
    9595 
Note: See TracChangeset for help on using the changeset viewer.