Changeset 4026:4f4e433e6441 in orange


Ignore:
Timestamp:
07/26/07 12:15:39 (7 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
5a988c3f5445e29b2c3837f05a906cb7adedd492
Message:

improved circular crossing reduction (still todo: circular sifting)

Location:
source/orangeom
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orangeom/networkoptimization.cpp

    r4025 r4026  
    8585int TNetworkOptimization::circularCrossingReduction() 
    8686{ 
    87     // TODO!!! 
    8887    vector<QueueVertex*> vertices; 
    8988    vector<QueueVertex*> original; 
     
    104103    original.assign(vertices.begin(), vertices.end()); 
    105104 
    106     vector<int> positions; 
     105    deque<int> positions; 
    107106    while (vertices.size() > 0) 
    108107    { 
    109108        sort(vertices.begin(), vertices.end(), QueueVertex()); 
    110  
     109        QueueVertex *vertex = vertices.back(); 
     110        /* 
    111111        cout << "vertices" << endl; 
    112112        for (i = 0; i < vertices.size(); i++) 
    113113            cout << *vertices[i] << endl; 
    114  
    115         QueueVertex *vertex = vertices.back(); 
    116         positions.push_back(vertex->ndx); 
    117         //cout << "size: " << vertex->neighbours.size() <<endl; 
    118114        cout << "ndx: " << vertex->ndx << endl; 
    119         int j; 
    120         for (j = 0; j < vertex->neighbours.size(); j++) 
    121         { 
    122             int ndx = vertex->neighbours[j]; 
     115        /**/ 
     116        // update neighbours 
     117        for (i = 0; i < vertex->neighbours.size(); i++) 
     118        { 
     119            int ndx = vertex->neighbours[i]; 
    123120 
    124121            original[ndx]->placedNeighbours++; 
    125122            original[ndx]->unplacedNeighbours--; 
    126123        } 
     124        // count left & right crossings 
     125        if (vertex->placedNeighbours > 0) 
     126        { 
     127            int left = 0; 
     128            vector<int> lCrossings; 
     129            vector<int> rCrossings; 
     130            for (i = 0; i < positions.size(); i++) 
     131            { 
     132                int ndx = positions[i]; 
     133                 
     134                if (vertex->hasNeighbour(ndx)) 
     135                { 
     136                    lCrossings.push_back(left); 
     137                    left += original[ndx]->unplacedNeighbours; 
     138                    rCrossings.push_back(left); 
     139                } 
     140                else 
     141                    left += original[ndx]->unplacedNeighbours; 
     142            } 
     143 
     144            int leftCrossings = 0; 
     145            int rightCrossings = 0; 
     146 
     147            for (i = 0; i < lCrossings.size(); i++) 
     148                leftCrossings += lCrossings[i]; 
     149 
     150            rCrossings.push_back(left); 
     151            for (i = rCrossings.size() - 1; i > 0 ; i--) 
     152                rightCrossings += rCrossings[i] - rCrossings[i - 1]; 
     153            //cout << "left: " << leftCrossings << " right: " <<rightCrossings << endl; 
     154            if (leftCrossings < rightCrossings) 
     155                positions.push_front(vertex->ndx); 
     156            else 
     157                positions.push_back(vertex->ndx); 
     158 
     159        } 
     160        else 
     161            positions.push_back(vertex->ndx); 
    127162 
    128163        vertices.pop_back(); 
    129164    } 
    130  
     165    /* 
    131166    cout << "original" << endl; 
    132167    for (i = 0; i < original.size(); i++) 
     
    136171    for (i = 0; i < positions.size(); i++) 
    137172        cout << positions[i] << endl; 
     173    /**/ 
     174    // TODO: Circular sifting 
     175     
    138176 
    139177 
  • source/orangeom/networkoptimization.hpp

    r4022 r4026  
    105105    vector<int> neighbours; 
    106106 
     107    bool hasNeighbour(int index) 
     108    { 
     109        vector<int>::iterator iter; 
     110 
     111        for (iter = neighbours.begin(); iter != neighbours.end(); iter++) 
     112            if (*iter == index) 
     113                return true; 
     114 
     115        return false; 
     116    } 
     117 
    107118    friend ostream & operator<<(ostream &os, const QueueVertex &v) 
    108119    { 
Note: See TracChangeset for help on using the changeset viewer.