Changeset 4027:51bdef60a161 in orange


Ignore:
Timestamp:
07/26/07 14:40:20 (7 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
703dd820eeff3089df6b565f3442c73e5509d72b
Message:

crossing reduction in circular layout done

Location:
source/orangeom
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orangeom/networkoptimization.cpp

    r4026 r4027  
    108108        sort(vertices.begin(), vertices.end(), QueueVertex()); 
    109109        QueueVertex *vertex = vertices.back(); 
    110         /* 
    111         cout << "vertices" << endl; 
    112         for (i = 0; i < vertices.size(); i++) 
    113             cout << *vertices[i] << endl; 
    114         cout << "ndx: " << vertex->ndx << endl; 
    115         /**/ 
     110 
     111 
    116112        // update neighbours 
    117113        for (i = 0; i < vertex->neighbours.size(); i++) 
     
    122118            original[ndx]->unplacedNeighbours--; 
    123119        } 
     120 
    124121        // count left & right crossings 
    125122        if (vertex->placedNeighbours > 0) 
     
    163160        vertices.pop_back(); 
    164161    } 
    165     /* 
    166     cout << "original" << endl; 
    167     for (i = 0; i < original.size(); i++) 
    168         cout << *original[i] << endl; 
    169  
    170     cout << "positions" << endl; 
     162 
     163    // Circular sifting 
    171164    for (i = 0; i < positions.size(); i++) 
    172         cout << positions[i] << endl; 
    173     /**/ 
    174     // TODO: Circular sifting 
    175      
    176  
     165        original[positions[i]]->position = i; 
     166 
     167    int step; 
     168    for (step = 0; step < 5; step++) 
     169    { 
     170        for (i = 0; i < nVertices; i++) 
     171        { 
     172            bool stop = false; 
     173            int switchNdx = -1; 
     174            QueueVertex *u = original[positions[i]]; 
     175            int vNdx = (i + 1) % nVertices; 
     176 
     177            while (!stop) 
     178            { 
     179                QueueVertex *v = original[positions[vNdx]]; 
     180 
     181                int midCrossings = u->neighbours.size() * v->neighbours.size() / 2; 
     182                int crossings = 0; 
     183                int j,k; 
     184                for (j = 0; j < u->neighbours.size(); j++) 
     185                    for (k = 0; k < v->neighbours.size(); k++) 
     186                        if ((original[u->neighbours[j]]->position == v->position) || (original[v->neighbours[k]]->position == u->position)) 
     187                            midCrossings = (u->neighbours.size() - 1) * (v->neighbours.size() - 1) / 2; 
     188                        else if ((original[u->neighbours[j]]->position + nVertices - u->position) % nVertices < (original[v->neighbours[k]]->position + nVertices - u->position) % nVertices) 
     189                            crossings++; 
     190 
     191                //cout << "v: " <<  v->ndx << " crossings: " << crossings << " u.n.size: " << u->neighbours.size() << " v.n.size: " << v->neighbours.size() << " mid: " << midCrossings << endl; 
     192                if (crossings > midCrossings) 
     193                    switchNdx = vNdx; 
     194                else 
     195                    stop = true; 
     196 
     197                vNdx = (vNdx + 1) % nVertices; 
     198            } 
     199            int j; 
     200            if (switchNdx > -1) 
     201            { 
     202                //cout << "u: " << u->ndx << " switch: " << original[switchNdx]->ndx << endl << endl; 
     203                positions.erase(positions.begin() + i); 
     204                positions.insert(positions.begin() + switchNdx, u->ndx); 
     205 
     206                for (j = i; j <= switchNdx; j++) 
     207                    original[positions[j]]->position = j; 
     208            } 
     209            //else 
     210            //  cout << "u: " << u->ndx << " switch: " << switchNdx << endl; 
     211        } 
     212    } 
    177213 
    178214    int xCenter = width / 2; 
     
    181217 
    182218    double fi = PI; 
    183     double step = 2 * PI / nVertices; 
     219    double fiStep = 2 * PI / nVertices; 
    184220 
    185221    for (i = 0; i < nVertices; i++) 
     
    188224        pos[positions[i]][1] = r * sin(fi) + yCenter; 
    189225     
    190         fi = fi - step; 
     226        fi = fi - fiStep; 
    191227    } 
    192228 
  • source/orangeom/networkoptimization.hpp

    r4026 r4027  
    101101public: 
    102102    int ndx; 
     103    int position; 
    103104    unsigned int unplacedNeighbours; 
    104105    unsigned int placedNeighbours; 
Note: See TracChangeset for help on using the changeset viewer.