Changeset 8624:654f50dbeba6 in orange


Ignore:
Timestamp:
08/06/11 10:37:59 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
b0dba53f9b855402f3397bcba4cbb94901a4c6aa
Message:

Added circular layout optimization functions.

Location:
source/orangeplot
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • source/orangeplot/networkcurve.cpp

    r8622 r8624  
    353353} 
    354354 
     355#define PI 3.14159265 
     356 
     357int NetworkCurve::circular(CircularLayoutType type) 
     358{ 
     359    // type 
     360    // 0 - original 
     361    // 1 - random 
     362    // 2 - crossing reduction 
     363 
     364    if (type == NetworkCurve::circular_crossing) 
     365    { 
     366        qDebug() << "crossing_reduction"; 
     367        return circular_crossing_reduction(); 
     368    } 
     369 
     370    if (type == NetworkCurve::circular_original) 
     371        qDebug() << "original"; 
     372 
     373    if (type == NetworkCurve::circular_random) 
     374            qDebug() << "random"; 
     375 
     376    QRectF rect = data_rect(); 
     377    int xCenter = rect.width() / 2; 
     378    int yCenter = rect.height() / 2; 
     379    int r = (rect.width() < rect.height()) ? rect.width() * 0.38 : rect.height() * 0.38; 
     380 
     381    int i; 
     382    double fi = PI; 
     383    double step = 2 * PI / m_nodes.size(); 
     384 
     385    srand(time(NULL)); 
     386    std::vector<int> vertices; 
     387    Nodes::ConstIterator it; 
     388    for (it = m_nodes.constBegin(); it != m_nodes.constEnd(); ++it) 
     389    { 
     390        vertices.push_back(it.key()); 
     391    } 
     392 
     393    for (i = 0; i < m_nodes.size(); ++i) 
     394    { 
     395        if (type == NetworkCurve::circular_original) 
     396        { 
     397            m_nodes[vertices[i]]->set_x(r * cos(fi) + xCenter); 
     398            m_nodes[vertices[i]]->set_y(r * sin(fi) + yCenter); 
     399        } 
     400        else if (type == NetworkCurve::circular_random) 
     401        { 
     402            int ndx = rand() % vertices.size(); 
     403            m_nodes[vertices[ndx]]->set_x(r * cos(fi) + xCenter); 
     404            m_nodes[vertices[ndx]]->set_y(r * sin(fi) + yCenter); 
     405            vertices.erase(vertices.begin() + ndx); 
     406        } 
     407        fi = fi - step; 
     408    } 
     409    return 0; 
     410} 
     411 
     412 
     413int NetworkCurve::circular_crossing_reduction() 
     414{ 
     415    QMap<int, QueueVertex*> qvertices; 
     416    std::vector<QueueVertex*> vertices; 
     417    std::vector<QueueVertex*> original; 
     418 
     419    Nodes::ConstIterator it; 
     420    for (it = m_nodes.constBegin(); it != m_nodes.constEnd(); ++it) 
     421    { 
     422        QueueVertex *vertex = new QueueVertex(); 
     423        vertex->ndx = it.key(); 
     424        qvertices[it.key()] = vertex; 
     425 
     426        std::vector<int> neighbours; 
     427        vertex->unplacedNeighbours = neighbours.size(); 
     428        vertex->neighbours = neighbours; 
     429        vertices.push_back(vertex); 
     430    } 
     431    int i; 
     432    EdgeItem *edge; 
     433    for (i = 0; i < m_edges.size(); i++) 
     434    { 
     435        edge = m_edges[i]; 
     436        int u = edge->u()->index(); 
     437        int v = edge->v()->index(); 
     438        qvertices[u]->neighbours.push_back(v); 
     439        qvertices[u]->unplacedNeighbours += 1; 
     440        qvertices[v]->neighbours.push_back(u); 
     441        qvertices[v]->unplacedNeighbours += 1; 
     442    } 
     443    original.assign(vertices.begin(), vertices.end()); 
     444 
     445    std::deque<int> positions; 
     446    while (vertices.size() > 0) 
     447    { 
     448        std::sort(vertices.begin(), vertices.end(), QueueVertex()); 
     449        QueueVertex *vertex = vertices.back(); 
     450 
     451 
     452        // update neighbours 
     453        for (i = 0; i < vertex->neighbours.size(); i++) 
     454        { 
     455            int ndx = vertex->neighbours[i]; 
     456 
     457            original[ndx]->placedNeighbours++; 
     458            original[ndx]->unplacedNeighbours--; 
     459        } 
     460 
     461        // count left & right crossings 
     462        if (vertex->placedNeighbours > 0) 
     463        { 
     464            int left = 0; 
     465            std::vector<int> lCrossings; 
     466            std::vector<int> rCrossings; 
     467            for (i = 0; i < positions.size(); i++) 
     468            { 
     469                int ndx = positions[i]; 
     470 
     471                if (vertex->hasNeighbour(ndx)) 
     472                { 
     473                    lCrossings.push_back(left); 
     474                    left += original[ndx]->unplacedNeighbours; 
     475                    rCrossings.push_back(left); 
     476                } 
     477                else 
     478                    left += original[ndx]->unplacedNeighbours; 
     479            } 
     480 
     481            int leftCrossings = 0; 
     482            int rightCrossings = 0; 
     483 
     484            for (i = 0; i < lCrossings.size(); i++) 
     485                leftCrossings += lCrossings[i]; 
     486 
     487            rCrossings.push_back(left); 
     488            for (i = rCrossings.size() - 1; i > 0 ; i--) 
     489                rightCrossings += rCrossings[i] - rCrossings[i - 1]; 
     490            //cout << "left: " << leftCrossings << " right: " <<rightCrossings << endl; 
     491            if (leftCrossings < rightCrossings) 
     492                positions.push_front(vertex->ndx); 
     493            else 
     494                positions.push_back(vertex->ndx); 
     495 
     496        } 
     497        else 
     498            positions.push_back(vertex->ndx); 
     499 
     500        vertices.pop_back(); 
     501    } 
     502 
     503    // Circular sifting 
     504    for (i = 0; i < positions.size(); i++) 
     505        original[positions[i]]->position = i; 
     506 
     507    int step; 
     508    for (step = 0; step < 5; step++) 
     509    { 
     510        for (i = 0; i < m_nodes.size(); i++) 
     511        { 
     512            bool stop = false; 
     513            int switchNdx = -1; 
     514            QueueVertex *u = original[positions[i]]; 
     515            int vNdx = (i + 1) % m_nodes.size(); 
     516 
     517            while (!stop) 
     518            { 
     519                QueueVertex *v = original[positions[vNdx]]; 
     520 
     521                int midCrossings = u->neighbours.size() * v->neighbours.size() / 2; 
     522                int crossings = 0; 
     523                int j,k; 
     524                for (j = 0; j < u->neighbours.size(); j++) 
     525                    for (k = 0; k < v->neighbours.size(); k++) 
     526                        if ((original[u->neighbours[j]]->position == v->position) || (original[v->neighbours[k]]->position == u->position)) 
     527                            midCrossings = (u->neighbours.size() - 1) * (v->neighbours.size() - 1) / 2; 
     528                        else if ((original[u->neighbours[j]]->position + m_nodes.size() - u->position) % m_nodes.size() < (original[v->neighbours[k]]->position + m_nodes.size() - u->position) % m_nodes.size()) 
     529                            crossings++; 
     530 
     531                //cout << "v: " <<  v->ndx << " crossings: " << crossings << " u.n.size: " << u->neighbours.size() << " v.n.size: " << v->neighbours.size() << " mid: " << midCrossings << endl; 
     532                if (crossings > midCrossings) 
     533                    switchNdx = vNdx; 
     534                else 
     535                    stop = true; 
     536 
     537                vNdx = (vNdx + 1) % m_nodes.size(); 
     538            } 
     539            int j; 
     540            if (switchNdx > -1) 
     541            { 
     542                //cout << "u: " << u->ndx << " switch: " << original[switchNdx]->ndx << endl << endl; 
     543                positions.erase(positions.begin() + i); 
     544                positions.insert(positions.begin() + switchNdx, u->ndx); 
     545 
     546                for (j = i; j <= switchNdx; j++) 
     547                    original[positions[j]]->position = j; 
     548            } 
     549            //else 
     550            //  cout << "u: " << u->ndx << " switch: " << switchNdx << endl; 
     551        } 
     552    } 
     553 
     554    QRectF rect = data_rect(); 
     555    int xCenter = rect.width() / 2; 
     556    int yCenter = rect.height() / 2; 
     557    int r = (rect.width() < rect.height()) ? rect.width() * 0.38 : rect.height() * 0.38; 
     558    double fi = PI; 
     559    double fiStep = 2 * PI / m_nodes.size(); 
     560 
     561    for (i = 0; i < m_nodes.size(); i++) 
     562    { 
     563        m_nodes[positions[i]]->set_x(r * cos(fi) + xCenter); 
     564        m_nodes[positions[i]]->set_y(r * sin(fi) + yCenter); 
     565        fi = fi - fiStep; 
     566    } 
     567 
     568    for (std::vector<QueueVertex*>::iterator i = original.begin(); i != original.end(); ++i) 
     569        delete *i; 
     570 
     571    original.clear(); 
     572    vertices.clear(); 
     573    qvertices.clear(); 
     574    return 0; 
     575} 
     576 
    355577int NetworkCurve::fr(int steps, bool weighted, bool smooth_cooling) 
    356578{ 
  • source/orangeplot/networkcurve.h

    r8613 r8624  
    55#include "point.h" 
    66#include "plot.h" 
     7#include <deque> 
     8#include <algorithm> 
     9 
     10class QueueVertex 
     11{ 
     12public: 
     13    int ndx; 
     14    int position; 
     15    unsigned int unplacedNeighbours; 
     16    unsigned int placedNeighbours; 
     17    std::vector<int> neighbours; 
     18 
     19    bool hasNeighbour(int index) 
     20    { 
     21        std::vector<int>::iterator iter; 
     22 
     23        for (iter = neighbours.begin(); iter != neighbours.end(); iter++) 
     24            if (*iter == index) 
     25                return true; 
     26 
     27        return false; 
     28    } 
     29 
     30    friend std::ostream & operator<<(std::ostream &os, const QueueVertex &v) 
     31    { 
     32        os << "ndx: " << v.ndx << " unplaced: " << v.unplacedNeighbours << " placed: " << v.placedNeighbours << " neighbours: "; 
     33        int i; 
     34        for (i = 0; i < v.neighbours.size(); i++) 
     35            os << v.neighbours[i] << " "; 
     36 
     37        return (os); 
     38    } 
     39 
     40    QueueVertex(int index = -1, unsigned int neighbours = 0) 
     41    { 
     42        ndx = index; 
     43        unplacedNeighbours = neighbours; 
     44        placedNeighbours = 0; 
     45    } 
     46 
     47    bool operator () (const QueueVertex * a, const QueueVertex * b) 
     48    { 
     49        if (a->unplacedNeighbours < b->unplacedNeighbours) 
     50            return false; 
     51        else if (a->unplacedNeighbours > b->unplacedNeighbours) 
     52            return true; 
     53        else 
     54        { 
     55            return a->placedNeighbours < b->placedNeighbours; 
     56        } 
     57    } 
     58}; 
    759 
    860class EdgeItem; 
     
    146198{ 
    147199public: 
     200    enum CircularLayoutType 
     201    { 
     202        circular_original = 0x01, 
     203        circular_random = 0x02, 
     204        circular_crossing = 0x03 
     205    }; 
     206 
    148207    typedef QList<EdgeItem*> Edges; 
    149208    typedef QMap<int, NodeItem*> Nodes; 
     
    157216     
    158217    int random(); 
     218    int circular(CircularLayoutType type); 
     219    int circular_crossing_reduction(); 
    159220    int fr(int steps, bool weighted, bool smooth_cooling); 
    160221     
  • source/orangeplot/networkcurve.sip

    r8607 r8624  
    7474{ 
    7575public: 
     76    enum CircularLayoutType 
     77    { 
     78        circular_original = 0x01, 
     79        circular_random = 0x02, 
     80        circular_crossing = 0x03 
     81    }; 
     82     
    7683    typedef QList<EdgeItem*> Edges; 
    7784    typedef QMap<int, NodeItem*> Nodes; 
     
    8491     
    8592    int random(); 
     93    int circular(NetworkCurve::CircularLayoutType type); 
    8694    int fr(int steps, bool weighted, bool smooth_cooling); 
    8795 
Note: See TracChangeset for help on using the changeset viewer.