source: orange/source/orangeom/graph_layout.cpp @ 9514:d6a1b6e618eb

Revision 9514:d6a1b6e618eb, 38.8 KB checked in by miha <miha.stajdohar@…>, 2 years ago (diff)

If no weight specified, use default weight 1.

Line 
1/*
2    This file is part of Orange.
3   
4    Copyright 1996-2010 Faculty of Computer and Information Science, University of Ljubljana
5    Author: Miha Stajdohar, 1996--2010
6    Contact: janez.demsar@fri.uni-lj.si
7
8    Orange is free software: you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation, either version 3 of the License, or
11    (at your option) any later version.
12
13    Orange is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with Orange.  If not, see <http://www.gnu.org/licenses/>.
20*/
21
22
23#include "ppp/graph_layout.ppp"
24#define PI 3.14159265
25
26TGraphLayout::TGraphLayout()
27{
28
29    //cout << "TGraphLayout::constructor" << endl;
30    import_array();
31
32    nVertices = 0;
33    nLinks = 0;
34
35    k = 1;
36    k2 = 1;
37    radius = 1;
38    width = 10000;
39    height = 10000;
40    temperature = sqrt(width*width + height*height) / 10;
41    coolFactor = 0.96;
42    coors = NULL;
43    pos = NULL;
44    //networkx_graph = NULL;
45    //cout << "constructor end" << endl;
46}
47
48#ifdef _MSC_VER
49#if _MSC_VER < 1300
50template<class T>
51inline T &min(const T&x, const T&y)
52{ return x<y ? x : y; }
53#endif
54#endif
55
56TGraphLayout::~TGraphLayout()
57{
58    free_Carrayptrs(pos);
59    /*Py_XDECREF(coors);*/
60}
61
62void TGraphLayout::dump_coordinates()
63{
64    for (int i = 0; i < nVertices; i++)
65    {
66        cout << pos[0][i] << "  " << pos[1][i] << endl;
67    }
68}
69
70void TGraphLayout::dump_disp()
71{
72    for (int i = 0; i < nVertices; i++)
73    {
74        cout << disp[0][i] << "  " << disp[1][i] << endl;
75    }
76}
77
78
79int TGraphLayout::random()
80{
81    srand(time(NULL));
82    int i;
83    for (i = 0; i < nVertices; i++)
84    {
85        pos[0][i] = rand() % (int)width;
86        pos[1][i] = rand() % (int)height;
87    }
88    return 0;
89}
90
91int TGraphLayout::circular_crossing_reduction()
92{
93    vector<QueueVertex*> vertices;
94    vector<QueueVertex*> original;
95
96    int i;
97    for (i = 0; i < nVertices; i++)
98    {
99        vector<int> neighbours;
100        /* network->getNeighbours(i, neighbours); TODO: FIX! */
101
102        QueueVertex *vertex = new QueueVertex();
103        vertex->ndx = i;
104        vertex->unplacedNeighbours = neighbours.size();
105        vertex->neighbours = neighbours;
106
107        vertices.push_back(vertex);
108    }
109    original.assign(vertices.begin(), vertices.end());
110
111    deque<int> positions;
112    while (vertices.size() > 0)
113    {
114        sort(vertices.begin(), vertices.end(), QueueVertex());
115        QueueVertex *vertex = vertices.back();
116
117
118        // update neighbours
119        for (i = 0; i < vertex->neighbours.size(); i++)
120        {
121            int ndx = vertex->neighbours[i];
122
123            original[ndx]->placedNeighbours++;
124            original[ndx]->unplacedNeighbours--;
125        }
126
127        // count left & right crossings
128        if (vertex->placedNeighbours > 0)
129        {
130            int left = 0;
131            vector<int> lCrossings;
132            vector<int> rCrossings;
133            for (i = 0; i < positions.size(); i++)
134            {
135                int ndx = positions[i];
136
137                if (vertex->hasNeighbour(ndx))
138                {
139                    lCrossings.push_back(left);
140                    left += original[ndx]->unplacedNeighbours;
141                    rCrossings.push_back(left);
142                }
143                else
144                    left += original[ndx]->unplacedNeighbours;
145            }
146
147            int leftCrossings = 0;
148            int rightCrossings = 0;
149
150            for (i = 0; i < lCrossings.size(); i++)
151                leftCrossings += lCrossings[i];
152
153            rCrossings.push_back(left);
154            for (i = rCrossings.size() - 1; i > 0 ; i--)
155                rightCrossings += rCrossings[i] - rCrossings[i - 1];
156            //cout << "left: " << leftCrossings << " right: " <<rightCrossings << endl;
157            if (leftCrossings < rightCrossings)
158                positions.push_front(vertex->ndx);
159            else
160                positions.push_back(vertex->ndx);
161
162        }
163        else
164            positions.push_back(vertex->ndx);
165
166        vertices.pop_back();
167    }
168
169    // Circular sifting
170    for (i = 0; i < positions.size(); i++)
171        original[positions[i]]->position = i;
172
173    int step;
174    for (step = 0; step < 5; step++)
175    {
176        for (i = 0; i < nVertices; i++)
177        {
178            bool stop = false;
179            int switchNdx = -1;
180            QueueVertex *u = original[positions[i]];
181            int vNdx = (i + 1) % nVertices;
182
183            while (!stop)
184            {
185                QueueVertex *v = original[positions[vNdx]];
186
187                int midCrossings = u->neighbours.size() * v->neighbours.size() / 2;
188                int crossings = 0;
189                int j,k;
190                for (j = 0; j < u->neighbours.size(); j++)
191                    for (k = 0; k < v->neighbours.size(); k++)
192                        if ((original[u->neighbours[j]]->position == v->position) || (original[v->neighbours[k]]->position == u->position))
193                            midCrossings = (u->neighbours.size() - 1) * (v->neighbours.size() - 1) / 2;
194                        else if ((original[u->neighbours[j]]->position + nVertices - u->position) % nVertices < (original[v->neighbours[k]]->position + nVertices - u->position) % nVertices)
195                            crossings++;
196
197                //cout << "v: " <<  v->ndx << " crossings: " << crossings << " u.n.size: " << u->neighbours.size() << " v.n.size: " << v->neighbours.size() << " mid: " << midCrossings << endl;
198                if (crossings > midCrossings)
199                    switchNdx = vNdx;
200                else
201                    stop = true;
202
203                vNdx = (vNdx + 1) % nVertices;
204            }
205            int j;
206            if (switchNdx > -1)
207            {
208                //cout << "u: " << u->ndx << " switch: " << original[switchNdx]->ndx << endl << endl;
209                positions.erase(positions.begin() + i);
210                positions.insert(positions.begin() + switchNdx, u->ndx);
211
212                for (j = i; j <= switchNdx; j++)
213                    original[positions[j]]->position = j;
214            }
215            //else
216            //  cout << "u: " << u->ndx << " switch: " << switchNdx << endl;
217        }
218    }
219
220    int xCenter = width / 2;
221    int yCenter = height / 2;
222    int r = (width < height) ? width * 0.38 : height * 0.38;
223
224    double fi = PI;
225    double fiStep = 2 * PI / nVertices;
226
227    for (i = 0; i < nVertices; i++)
228    {
229        pos[0][positions[i]] = r * cos(fi) + xCenter;
230        pos[1][positions[i]] = r * sin(fi) + yCenter;
231
232        fi = fi - fiStep;
233    }
234
235    for (vector<QueueVertex*>::iterator i = original.begin(); i != original.end(); ++i)
236        delete *i;
237
238    original.clear();
239    vertices.clear();
240
241    return 0;
242}
243
244int TGraphLayout::circular(int type)
245{
246    // type
247    // 0 - original
248    // 1 - random
249    int xCenter = width / 2;
250    int yCenter = height / 2;
251    int r = (width < height) ? width * 0.38 : height * 0.38;
252
253    int i;
254    double fi = PI;
255    double step = 2 * PI / nVertices;
256
257    srand(time(NULL));
258    vector<int> vertices;
259    if (type == 1)
260        for (i = 0; i < nVertices; i++)
261            vertices.push_back(i);
262
263    for (i = 0; i < nVertices; i++)
264    {
265        if (type == 0)
266        {
267            pos[0][i] = r * cos(fi) + xCenter;
268            pos[1][i] = r * sin(fi) + yCenter;
269        }
270        else if (type == 1)
271        {
272            int ndx = rand() % vertices.size();
273
274            pos[0][vertices[ndx]] = r * cos(fi) + xCenter;
275            pos[1][vertices[ndx]] = r * sin(fi) + yCenter;
276
277            vertices.erase(vertices.begin() + ndx);
278        }
279
280        fi = fi - step;
281    }
282
283    return 0;
284}
285
286void TGraphLayout::clear_disp()
287{
288    int j;
289    for (j = 0; j < nVertices; j++) {
290            disp[0][j] = 0;
291            disp[1][j] = 0;
292    }
293}
294
295void TGraphLayout::fr_repulsive_force(double kk2, int type)
296{
297    // type = 0 - classic fr
298    // type = 1 - radial fr
299    // type = 2 - smooth fr
300    int u, v;
301    for (v = 0; v < nVertices; v++) {
302        for (u = 0; u < v; u++) {
303            if (type == 1) {
304                if (level[u] == level[v]) {
305                    k = kVector[level[u]];
306                } else {
307                    k = radius;
308                }
309                //kk = 2 * k;
310                k2 = k*k;
311            } else if (type == 2) {
312                if (level[u] == level[v]) {
313                    if (level[u] == 0) {
314                        k = kVector[0];
315                    } else {
316                        k = kVector[1];
317                    }
318                } else {
319                    k = kVector[2];
320                }
321                k2 = k * k;
322                kk2 = 4 * k2;
323            }
324
325            double difX = pos[0][v] - pos[0][u];
326            double difY = pos[1][v] - pos[1][u];
327
328            double dif2 = difX * difX + difY * difY;
329
330            if (dif2 < kk2) {
331                if (dif2 == 0) {
332                    dif2 = 1;
333                }
334                double dX = difX * k2 / dif2;
335                double dY = difY * k2 / dif2;
336
337                disp[0][v] += dX;
338                disp[1][v] += dY;
339
340                disp[0][u] -= dX;
341                disp[1][u] -= dY;
342            }
343        }
344    }
345}
346
347void TGraphLayout::fr_attractive_force(int type, bool weighted)
348{
349    // type = 0 - classic fr
350    // type = 1 - radial fr
351    // type = 2 - smooth fr
352    int j, u, v;
353    for (j = 0; j < nLinks; j++) {
354        v = links[0][j];
355        u = links[1][j];
356       
357        if (type == 1) {
358            if (level[u] == level[v]) {
359                k = kVector[level[u]];
360            } else {
361                k = radius;
362            }
363        } else if (type == 2) {
364            if (level[u] == level[v]) {
365                if (level[u] == 0) {
366                    k = kVector[0];
367                } else {
368                    k = kVector[1];
369                }
370            } else {
371                k = kVector[2];
372            }
373        }
374
375        double difX = pos[0][v] - pos[0][u];
376        double difY = pos[1][v] - pos[1][u];
377
378        double dif = sqrt(difX * difX + difY * difY);
379       
380        double dX, dY;
381
382        if (weighted) {
383            dX = difX * dif / k * weights[j];
384            dY = difY * dif / k * weights[j];
385        } else {
386            dX = difX * dif / k;
387            dY = difY * dif / k;
388        }
389
390        disp[0][v] -= dX;
391        disp[1][v] -= dY;
392
393        disp[0][u] += dX;
394        disp[1][u] += dY;
395    }
396}
397
398void TGraphLayout::fr_limit_displacement()
399{
400    int v;
401    // limit the maximum displacement to the temperature t
402    // and then prevent from being displaced outside frame
403    for (v = 0; v < nVertices; v++) {
404        double dif = sqrt(pow(disp[0][v], 2) + pow(disp[1][v], 2));
405
406        if (dif == 0) {
407            dif = 1;
408        }
409        pos[0][v] += (disp[0][v] * min(fabs(disp[0][v]), temperature) / dif);
410        pos[1][v] += (disp[1][v] * min(fabs(disp[1][v]), temperature) / dif);
411
412        //pos[v][0] = min((double)width,  max((double)0, pos[v][0]));
413        //pos[v][1] = min((double)height, max((double)0, pos[v][1]));
414    }
415}
416
417int TGraphLayout::fr(int steps, bool weighted)
418{
419    int i;
420    int count = 0;
421    double kk = 1;
422    double localTemparature = 5;
423    double area = width * height;
424
425    k2 = area / nVertices;
426    k = sqrt(k2);
427    kk = 2 * k;
428    double kk2 = kk * kk;
429   
430    // iterations
431    for (i = 0; i < steps; i++) {
432        clear_disp();
433        fr_repulsive_force(kk2, 0);
434        fr_attractive_force(0, weighted);
435        fr_limit_displacement();
436        temperature = temperature * coolFactor;
437    }
438
439    return 0;
440}
441
442int TGraphLayout::fr_radial(int steps, int nCircles)
443{
444    int i, v;
445    radius = width / nCircles / 2;
446    int count = 0;
447    double kk = 1;
448    double localTemparature = 5;
449    double area = width * height;
450
451    k2 = area / nVertices;
452    k = sqrt(k2);
453    kk = 2 * k;
454    double kk2 = kk * kk;
455    // iterations
456    for (i = 0; i < steps; i++) {
457        clear_disp();
458        fr_repulsive_force(kk2, 1);
459        fr_attractive_force(1, false);
460        fr_limit_displacement();
461        // limit the maximum displacement to the temperature t
462        // and then prevent from being displaced outside frame
463
464        for (v = 0; v < nCircles; v++) {
465            levelMin[v] = INT_MAX;
466            levelMax[v] = 0;
467        }
468
469        for (v = 0; v < nVertices; v++) {
470            double distance = (pos[0][v] - (width/2)) * (pos[0][v] - (width/2)) + (pos[1][v] - (height/2)) * (pos[1][v] - (height/2));
471
472            if (distance < levelMin[level[v]])
473                levelMin[level[v]] = distance;
474
475            if (distance > levelMax[level[v]])
476                levelMax[level[v]] = distance;
477        }
478
479        for (v = 1; v < nCircles; v++) {
480            levelMin[v] = (v - 1) * radius / sqrt(levelMin[v]);
481            levelMax[v] =  v      * radius / sqrt(levelMax[v]);
482        }
483
484        for (v = 0; v < nVertices; v++) {
485            double distance = sqrt((pos[0][v] - (width/2)) * (pos[0][v] - (width/2)) + (pos[1][v] - (height/2)) * (pos[1][v] - (height/2)));
486
487            if (level[v] == 0) {
488                // move to center
489                pos[0][v] = width / 2;
490                pos[1][v] = height / 2;
491
492                //cout << "center, x: " << pos[v][0] << " y: " << pos[v][1] << endl;
493            } else if (distance > level[v] * radius - radius / 2) {
494                // move to outer ring
495                if (levelMax[level[v]] < 1) {
496                    double fi = 0;
497                    double x = pos[0][v] - (width / 2);
498                    double y = pos[1][v] - (height / 2);
499
500                    if (x < 0)
501                        fi = atan(y / x) + PI;
502                    else if ((x > 0) && (y >= 0))
503                        fi = atan(y / x);
504                    else if ((x > 0) && (y < 0))
505                        fi = atan(y / x) + 2 * PI;
506                    else if ((x == 0) && (y > 0))
507                        fi = PI / 2;
508                    else if ((x == 0) && (y < 0))
509                        fi = 3 * PI / 2;
510
511                    pos[0][v] = levelMax[level[v]] * distance * cos(fi) + (width / 2);
512                    pos[1][v] = levelMax[level[v]] * distance * sin(fi) + (height / 2);
513
514                    //cout << "outer, x: " << pos[v][0] << " y: " << pos[v][1] << " radius: " << radius << " fi: " << fi << " level: " << level[v] << " v: " << v << endl;
515                }
516            } else if (distance < (level[v] - 1) * radius + radius / 2) {
517                // move to inner ring
518                if (levelMin[level[v]] > 1) {
519                    double fi = 0;
520                    double x = pos[0][v] - (width / 2);
521                    double y = pos[1][v] - (height / 2);
522
523                    if (x < 0)
524                        fi = atan(y / x) + PI;
525                    else if ((x > 0) && (y >= 0))
526                        fi = atan(y / x);
527                    else if ((x > 0) && (y < 0))
528                        fi = atan(y / x) + 2 * PI;
529                    else if ((x == 0) && (y > 0))
530                        fi = PI / 2;
531                    else if ((x == 0) && (y < 0))
532                        fi = 3 * PI / 2;
533
534                    pos[0][v] = levelMin[level[v]] * distance * cos(fi) + (width / 2);
535                    pos[1][v] = levelMin[level[v]] * distance * sin(fi) + (height / 2);
536
537                    //cout << "inner, x: " << pos[v][0] << " y: " << pos[v][1] << endl;
538                }
539            }
540        }
541        temperature = temperature * coolFactor;
542    }
543    return 0;
544}
545
546/* ==== Free a double *vector (vec of pointers) ========================== */
547void TGraphLayout::free_Carrayptrs(double **v)  {
548
549    free((char*) v);
550}
551
552/* ==== Allocate a double *vector (vec of pointers) ======================
553    Memory is Allocated!  See void free_Carray(double ** )                  */
554double **TGraphLayout::ptrvector(int n)  {
555    double **v;
556    v=(double **)malloc((size_t) (n*sizeof(double *)));
557
558    if (!v)   {
559        printf("In **ptrvector. Allocation of memory for double array failed.");
560        exit(0);
561    }
562    return v;
563}
564
565/* ==== Create Carray from PyArray ======================
566    Assumes PyArray is contiguous in memory.
567    Memory is allocated!                                    */
568double **TGraphLayout::pymatrix_to_Carrayptrs(PyArrayObject *arrayin)  {
569    double **c, *a;
570    int i,n,m;
571
572    n = arrayin->dimensions[0];
573    m = arrayin->dimensions[1];
574    c = ptrvector(n);
575    a = (double *) arrayin->data;  /* pointer to arrayin data as double */
576
577    for (i = 0; i < n; i++) {
578        c[i] = a + i * m;
579    }
580
581    return c;
582}
583
584/* ==== Create 1D Carray from PyArray ======================
585 129     Assumes PyArray is contiguous in memory.             */
586bool *TGraphLayout::pyvector_to_Carrayptrs(PyArrayObject *arrayin)  {
587    int n;
588
589    n = arrayin->dimensions[0];
590    return (bool *) arrayin->data;  /* pointer to arrayin data as double */
591}
592
593int TGraphLayout::set_graph(PyObject *graph)
594{
595    if (graph == NULL) {
596        nVertices = 0;
597        nLinks = 0;
598        npy_intp dims[2];
599        dims[0] = 2;
600        dims[1] = nVertices;
601        free_Carrayptrs(pos);
602        coors = NULL;
603        pos = NULL;
604        links[0].clear();
605        links[1].clear();
606        weights.clear();
607        disp[0].clear();
608        disp[1].clear();
609        return 0;
610    }
611    PyObject* nodes = PyObject_GetAttrString(graph, "node");
612    PyObject* adj = PyObject_GetAttrString(graph, "adj");
613
614    nVertices = PyDict_Size(nodes);
615    nLinks = 0;
616
617    npy_intp dims[2];
618    dims[0] = 2;
619    dims[1] = nVertices;
620
621    free_Carrayptrs(pos);
622    /*Py_XDECREF(coors);*/
623
624    coors = (PyArrayObject *) PyArray_SimpleNew(2, dims, NPY_DOUBLE);
625    pos = pymatrix_to_Carrayptrs(coors);
626    /*Py_INCREF(coors);*/
627    srand(time(NULL));
628    int i;
629    for (i = 0; i < nVertices; i++) {
630        pos[0][i] = rand() % 10000;
631        pos[1][i] = rand() % 10000;
632    }
633
634    links[0].clear();
635    links[1].clear();
636    weights.clear();
637    disp[0].resize(nVertices, 0);
638    disp[1].resize(nVertices, 0);
639
640    // iterate all nodes
641    PyObject *key, *value;
642    Py_ssize_t pos = 0;
643    vector<int> nodes_vec;
644    while (PyDict_Next(nodes, &pos, &key, &value)) {
645        int node = PyInt_AS_LONG(key);
646        nodes_vec.push_back(node);
647    }
648
649    // create a dict of node id | node index
650    sort(nodes_vec.begin(), nodes_vec.end());
651    map<int, int> nodes_map;
652    for (i = 0; i < nodes_vec.size(); i++) {
653        nodes_map[nodes_vec[i]] = i;
654    }
655
656    // iterate all edges
657    PyObject *key_u, *value_u, *key_v, *value_v;
658    Py_ssize_t pos_u = 0;
659    while (PyDict_Next(adj, &pos_u, &key_u, &value_u)) {
660        int u = PyInt_AS_LONG(key_u);
661
662        Py_ssize_t pos_v = 0;
663        while (PyDict_Next(value_u, &pos_v, &key_v, &value_v)) {
664            int v = PyInt_AS_LONG(key_v);
665            links[0].push_back(nodes_map[u]);
666            links[1].push_back(nodes_map[v]);
667            weights.push_back(1); // TODO: compute weight
668            nLinks++;
669        }
670    }
671
672    return 0;
673}
674
675#include "externs.px"
676#include "orange_api.hpp"
677
678PyObject *GraphLayout_new(PyTypeObject *type, PyObject *args, PyObject *keyw) BASED_ON (Orange, "() -> None")
679{
680  PyTRY
681    /*
682      PyObject *pygraph;
683
684    if (PyArg_ParseTuple(args, "O:GraphLayout", &pygraph))
685    {
686        TGraphAsList *graph = &dynamic_cast<TGraphAsList &>(PyOrange_AsOrange(pygraph).getReference());
687
688        if (graph->nVertices < 2)
689          PYERROR(PyExc_AttributeError, "graph has less than two nodes", NULL);
690
691        //return WrapNewOrange(new TGraphOptimization(graph->nVertices, pos, nLinks, links), type);
692        return WrapNewOrange(new TGraphLayout(), type);
693    }
694    else
695    {
696        return WrapNewOrange(new TGraphLayout(), type);
697    }
698    */
699    return WrapNewOrange(new TGraphLayout(), type);
700  PyCATCH
701}
702
703PyObject *GraphLayout_set_graph(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(Orange.network.Graph) -> None")
704{
705  PyTRY
706    PyObject* graph = Py_None;
707    PyObject* positions = Py_None;
708
709    if (!PyArg_ParseTuple(args, "|OO:GraphLayout.set_graph", &graph, &positions)) {
710          return PYNULL;
711    }
712
713    CAST_TO(TGraphLayout, graph_layout);
714
715    if (graph == Py_None) {
716        graph_layout->set_graph(NULL);
717    } else {
718        graph_layout->set_graph(graph);
719
720        if (positions != Py_None && PyList_Size(positions) == graph_layout->nVertices) {
721            int i;
722            for (i = 0; i < graph_layout->nVertices; i++) {
723                double x,y;
724                PyArg_ParseTuple(PyList_GetItem(positions, i), "dd", &x, &y);
725                graph_layout->pos[0][i] = x;
726                graph_layout->pos[1][i] = y;
727            }
728        }
729    }
730   
731    RETURN_NONE;
732  PyCATCH
733}
734
735PyObject *GraphLayout_get_coors(PyObject *self, PyObject *args) /*P Y A RGS(METH_VARARGS, "() -> Coors")*/
736{
737  PyTRY
738    CAST_TO(TGraphLayout, graph_layout);
739    Py_INCREF(graph_layout->coors);
740    return (PyObject *)graph_layout->coors;
741  PyCATCH
742}
743
744bool has_vertex(int vertex, vector<int> list)
745{
746    int i;
747    for (i = 0; i < list.size(); i++)
748    {
749        //cout << list[i] << " " << vertex << endl;
750        if (list[i] == vertex)
751            return true;
752    }
753
754    return false;
755}
756
757PyObject *GraphLayout_random(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None")
758{
759  PyTRY
760    CAST_TO(TGraphLayout, graph_layout);
761    graph_layout->random();
762    RETURN_NONE;
763  PyCATCH
764}
765
766PyObject *GraphLayout_fr(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(steps, temperature, coolFactor, weighted) -> temperature")
767{
768  PyTRY
769    int steps;
770    double temperature = 0;
771    double coolFactor = 0;
772    bool weighted = false;
773
774    if (!PyArg_ParseTuple(args, "id|db:GraphLayout.fr", &steps, &temperature, &coolFactor, &weighted)) {
775        return NULL;
776    }
777
778    CAST_TO(TGraphLayout, graph_layout);
779
780    graph_layout->temperature = temperature;
781
782    if (coolFactor == 0) {
783        graph_layout->coolFactor = exp(log(10.0/10000.0) / steps);
784    } else { 
785        graph_layout->coolFactor = coolFactor;
786    }
787
788    if (graph_layout->fr(steps, weighted) > 0) {
789        PYERROR(PyExc_SystemError, "fr failed", PYNULL);
790    }
791
792    return Py_BuildValue("d", graph_layout->temperature);
793  PyCATCH
794}
795
796PyObject *GraphLayout_fr_radial(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(center, steps, temperature) -> temperature")
797{
798  PyTRY
799
800    int steps, center;
801    double temperature = 0;
802
803    if (!PyArg_ParseTuple(args, "iid:GraphLayout.fr_radial", &center, &steps, &temperature))
804        return NULL;
805
806    CAST_TO(TGraphLayout, graph_layout);
807
808    graph_layout->pos[0][center] = graph_layout->width / 2;
809    graph_layout->pos[1][center] = graph_layout->height / 2;
810
811    int nCircles = 6;
812    int r = graph_layout->width / nCircles / 2;
813
814    graph_layout->level = new int[graph_layout->nVertices];
815    graph_layout->kVector = new double[nCircles];
816    graph_layout->levelMin = new double[nCircles];
817    graph_layout->levelMax = new double[nCircles];
818    int i;
819    for (i = 0; i < graph_layout->nVertices; i++)
820        graph_layout->level[i] = nCircles;
821
822    for (i = 0; i < nCircles; i++)
823    {
824        graph_layout->kVector[i] = 0;
825        graph_layout->levelMin[i] = INT_MAX;
826        graph_layout->levelMax[i] = 0;
827    }
828    vector<int> removedLinks[2];
829    vector<int> vertices;
830    vector<int> allVertices;
831    vertices.push_back(center);
832    graph_layout->level[center] = 0;
833
834    for (i = 0; i < nCircles; i++)
835    {
836        // position vertices
837        double fi = 360 / vertices.size();
838        int v;
839        for (v = 0; v < vertices.size(); v++)
840        {
841            double x = i * r * cos(v * fi * PI / 180) + (graph_layout->width / 2);
842            double y = i * r * sin(v * fi * PI / 180) + (graph_layout->height / 2);
843
844            graph_layout->pos[0][vertices[v]] = x;
845            graph_layout->pos[1][vertices[v]] = y;
846
847            //cout << "v: " << vertices[v] << " X: " << x << " Y: " << y << " level: " << graph_layout->level[vertices[v]] << endl;
848        }
849        //cout << endl;
850        vector<int> newVertices;
851        for (v = 0; v < vertices.size(); v++)
852        {
853            int j;
854            int node = vertices[v];
855
856            for (j = graph_layout->links[0].size() - 1; j >= 0; j--)
857            {
858                if (graph_layout->links[0][j] == node)
859                {
860                    //cout << "j: " << j << " u: " << graph_layout->links1[0][j] << " v: " << graph_layout->links1[1][j] << endl;
861                    removedLinks[0].push_back(graph_layout->links[0][j]);
862                    removedLinks[1].push_back(graph_layout->links[1][j]);
863
864                    if (!has_vertex(graph_layout->links[1][j], allVertices))
865                    {
866                        newVertices.push_back(graph_layout->links[1][j]);
867                        allVertices.push_back(graph_layout->links[1][j]);
868                        graph_layout->level[graph_layout->links[1][j]] = i + 1;
869                    }
870                    graph_layout->links[0].erase(graph_layout->links[0].begin() + j);
871                    graph_layout->links[1].erase(graph_layout->links[1].begin() + j);
872                }
873                else if (graph_layout->links[1][j] == node)
874                {
875                    //cout << "j: " << j << " u: " << graph_layout->links1[0][j] << " v: " << graph_layout->links1[1][j] << endl;
876                    removedLinks[0].push_back(graph_layout->links[0][j]);
877                    removedLinks[1].push_back(graph_layout->links[1][j]);
878
879                    if (!has_vertex(graph_layout->links[0][j], allVertices))
880                    {
881                        //cout << "adding: " <<
882                        newVertices.push_back(graph_layout->links[0][j]);
883                        allVertices.push_back(graph_layout->links[0][j]);
884                        graph_layout->level[graph_layout->links[0][j]] = i + 1;
885                    }
886
887                    graph_layout->links[0].erase(graph_layout->links[0].begin() + j);
888                    graph_layout->links[1].erase(graph_layout->links[1].begin() + j);
889                }
890            }
891        }
892
893        vertices.clear();
894
895        if (newVertices.size() == 0)
896            break;
897
898        for (v = 0; v < newVertices.size(); v++)
899        {
900            vertices.push_back(newVertices[v]);
901        }
902    }
903    // adds back removed links
904    for (i = 0; i < removedLinks[0].size(); i++)
905    {
906        graph_layout->links[0].push_back(removedLinks[0][i]);
907        graph_layout->links[1].push_back(removedLinks[1][i]);
908    }
909
910
911    for (i = 0; i < graph_layout->nVertices; i++)
912    {
913        if (graph_layout->level[i] >= nCircles)
914            graph_layout->level[i] = nCircles - 1;
915
916        graph_layout->kVector[graph_layout->level[i]]++;
917    }
918
919    double radius = graph_layout->width / nCircles / 2;
920    for (i = 0; i < nCircles; i++)
921    {
922        //cout << "n: " << graph_layout->kVector[i] << endl;
923        //cout << "r: " << radius * i;
924        if (graph_layout->kVector[i] > 0)
925            graph_layout->kVector[i] = 2 * i * radius * sin(PI / graph_layout->kVector[i]);
926        else
927            graph_layout->kVector[i] = -1;
928
929        //cout << "kvec: " << graph_layout->kVector[i] << endl;
930    }
931
932    graph_layout->temperature = temperature;
933    graph_layout->coolFactor = exp(log(10.0/10000.0) / steps);
934    /*
935    for (i = 0; i < graph_layout->nVertices; i++)
936        cout << "level " << i << ": " << graph_layout->level[i] << endl;
937    /**/
938    if (graph_layout->fr_radial(steps, nCircles) > 0)
939    {
940        delete[] graph_layout->level;
941        delete[] graph_layout->kVector;
942        delete[] graph_layout->levelMin;
943        delete[] graph_layout->levelMax;
944        PYERROR(PyExc_SystemError, "fr_radial failed", NULL);
945    }
946
947    delete[] graph_layout->level;
948    delete[] graph_layout->kVector;
949    delete[] graph_layout->levelMin;
950    delete[] graph_layout->levelMax;
951    return Py_BuildValue("d", graph_layout->temperature);
952  PyCATCH
953}
954
955PyObject *GraphLayout_circular_original(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None")
956{
957  PyTRY
958    CAST_TO(TGraphLayout, graph_layout);
959    graph_layout->circular(0);
960    RETURN_NONE;
961  PyCATCH
962}
963
964PyObject *GraphLayout_circular_random(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None")
965{
966  PyTRY
967    CAST_TO(TGraphLayout, graph_layout);
968    graph_layout->circular(1);
969    RETURN_NONE;
970  PyCATCH
971}
972
973PyObject *GraphLayout_circular_crossing_reduction(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "() -> None")
974{
975  PyTRY
976    CAST_TO(TGraphLayout, graph_layout);
977    graph_layout->circular_crossing_reduction();
978    RETURN_NONE;
979  PyCATCH
980}
981
982int *get_vertex_powers(TGraphLayout *graph)
983{
984    int *vertexPower = new int[graph->nVertices];
985
986    int i;
987    for (i=0; i < graph->nVertices; i++)
988    {
989        vertexPower[i] = 0;
990    }
991
992    for (i=0; i < graph->nLinks; i++)
993    {
994        vertexPower[graph->links[0][i]]++;
995        vertexPower[graph->links[1][i]]++;
996    }
997
998  return vertexPower;
999}
1000
1001PyObject *GraphLayout_get_vertex_powers(PyObject *self, PyObject *) PYARGS(METH_NOARGS, "() -> list")
1002{
1003  PyTRY
1004    CAST_TO(TGraphLayout, graph);
1005    int *vertexPower = get_vertex_powers(graph);
1006    PyObject *pypowers = PyList_New(graph->nVertices);
1007    for(int i =0; i < graph->nVertices; i++)
1008      PyList_SetItem(pypowers, i, PyInt_FromLong(vertexPower[i]));
1009    delete [] vertexPower;
1010    return pypowers;
1011  PyCATCH;
1012}
1013
1014PyObject *GraphLayout_closest_vertex(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(x, y) -> vertex id")
1015{
1016  PyTRY
1017    double x;
1018    double y;
1019
1020    if (!PyArg_ParseTuple(args, "dd:GraphLayout.closest_vertex", &x, &y))
1021        return NULL;
1022
1023    CAST_TO(TGraphLayout, graph);
1024
1025    int i;
1026    double min = 100000000;
1027    int ndx = -1;
1028    for (i=0; i < graph->nVertices; i++)
1029    {
1030        double dX = graph->pos[0][i] - x;
1031        double dY = graph->pos[1][i] - y;
1032        double d = dX*dX + dY*dY;
1033
1034        if (d < min)
1035        {
1036            min = d;
1037            ndx = i;
1038        }
1039    }
1040
1041    return Py_BuildValue("id", ndx, sqrt(min));
1042  PyCATCH
1043}
1044
1045PyObject *GraphLayout_vertex_distances(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(x, y) -> List of (distance, vertex)")
1046{
1047  PyTRY
1048    double x;
1049    double y;
1050
1051    if (!PyArg_ParseTuple(args, "dd:GraphLayout.vertex_distances", &x, &y))
1052        return NULL;
1053
1054    CAST_TO(TGraphLayout, graph);
1055
1056    int i;
1057    PyObject* distancies = PyList_New(0);
1058    for (i=0; i < graph->nVertices; i++)
1059    {
1060        double dX = graph->pos[0][i] - x;
1061        double dY = graph->pos[1][i] - y;
1062        double d = dX*dX + dY*dY;
1063
1064        PyObject *nel = Py_BuildValue("di", d, i);
1065        PyList_Append(distancies, nel);
1066        Py_DECREF(nel);
1067    }
1068
1069    return distancies;
1070  PyCATCH
1071}
1072
1073PyObject *GraphLayout_get_vertices_in_rect(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(x1, y1, x2, y2) -> list of vertices")
1074{
1075  PyTRY
1076    double x1, y1, x2, y2;
1077
1078    if (!PyArg_ParseTuple(args, "dddd:GraphLayout.get_vertices_in_rect", &x1, &y1, &x2, &y2))
1079        return NULL;
1080
1081    if (x1 > x2) {
1082        double tmp = x2;
1083        x2 = x1;
1084        x1 = tmp;
1085    }
1086
1087    if (y1 > y2) {
1088        double tmp = y2;
1089        y2 = y1;
1090        y1 = tmp;
1091    }
1092
1093    CAST_TO(TGraphLayout, graph);
1094    PyObject* vertices = PyList_New(0);
1095    int i;
1096    for (i = 0; i < graph->nVertices; i++) {
1097        double vX = graph->pos[0][i];
1098        double vY = graph->pos[1][i];
1099
1100        if ((x1 <= vX) && (x2 >= vX) && (y1 <= vY) && (y2 >= vY)) {
1101            PyObject *nel = Py_BuildValue("i", i);
1102            PyList_Append(vertices, nel);
1103            Py_DECREF(nel);
1104        }
1105    }
1106
1107    return vertices;
1108  PyCATCH
1109}
1110
1111PyObject *GraphLayout_edges_from_distance_matrix(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(matrix, lower, upper, kNN) -> list of edges")
1112{
1113  PyTRY
1114    PyObject *pyMatrix;
1115    double lower;
1116    double upper;
1117    int kNN = 0;
1118    int andor = 0;
1119
1120    if (!PyArg_ParseTuple(args, "Odd|ii:GraphLayout.edges_from_distance_matrix", &pyMatrix, &lower, &upper, &kNN))
1121        return PYNULL;
1122
1123    TSymMatrix *matrix = &dynamic_cast<TSymMatrix &>(PyOrange_AsOrange(pyMatrix).getReference());
1124    //cout << "kNN: " << kNN << endl;
1125    //cout << "andor: " << andor << endl;
1126
1127    int i,j;
1128    //vector<coord_t> edges_interval;
1129    PyObject* edges = PyList_New(0);
1130
1131    if (matrix->matrixType == 0) {
1132        // lower
1133        for (i = 0; i < matrix->dim; i++) {
1134            bool connected = false;
1135            for (j = i+1; j < matrix->dim; j++) {
1136                //cout << "i " << i << " j " << j;
1137                double value = matrix->getitem(j,i);
1138                //cout << " value " << value << endl;
1139                if (lower <=  value && value <= upper) {
1140                    connected = true;
1141                    //edges_interval.push_back(coord_t(j, i));
1142                    PyObject *nel = Py_BuildValue("iid", j, i, value);
1143                    PyList_Append(edges, nel);
1144                    Py_DECREF(nel);
1145                }
1146            }
1147        }
1148    } else {
1149        // upper
1150        for (i = 0; i < matrix->dim; i++) {
1151            bool connected = false;
1152            for (j = i+1; j < matrix->dim; j++) {
1153                double value = matrix->getitem(i,j);
1154                if (lower <=  value && value <= upper) {
1155                    connected = true;
1156                    //edges_interval.push_back(coord_t(i, j));
1157                    PyObject *nel = Py_BuildValue("iid", i, j, value);
1158                    PyList_Append(edges, nel);
1159                    Py_DECREF(nel);
1160                }
1161            }
1162        }
1163    }
1164   
1165    //PyObject* edges_knn = PyList_New(0);
1166    if (kNN > 0) {
1167        for (i = 0; i < matrix->dim; i++) {
1168            vector<int> closest;
1169            matrix->getknn(i, kNN, closest);
1170
1171            for (j = 0; j < closest.size(); j++) {
1172                //edges_knn.push_back(coord_t(i, closest[j]));
1173                double value = matrix->getitem(i, closest[j]);
1174                PyObject *nel = Py_BuildValue("iid", i, closest[j], value);
1175                PyList_Append(edges, nel);
1176                Py_DECREF(nel);
1177            }
1178        }
1179    }
1180
1181    if (andor == 0) {
1182       
1183    }
1184
1185    return edges;
1186  PyCATCH;
1187}
1188
1189
1190WRAPPER(ExampleTable)
1191
1192int getWords1(string const& s, vector<string> &container)
1193{
1194    int n = 0;
1195    bool quotation = false;
1196    container.clear();
1197    string::const_iterator it = s.begin(), end = s.end(), first;
1198    for (first = it; it != end; ++it) {
1199        // Examine each character and if it matches the delimiter
1200        if ((!quotation && (' ' == *it || '\t' == *it || '\r' == *it || '\f' == *it || '\v' == *it || ',' == *it)) || ('\n' == *it)) {
1201            if (first != it) {
1202                // extract the current field from the string and
1203                // append the current field to the given container
1204                container.push_back(string(first, it));
1205                ++n;
1206
1207                // skip the delimiter
1208                first = it + 1;
1209            } else {
1210                ++first;
1211            }
1212        }
1213        else if (('\"' == *it) || ('\'' == *it) || ('(' == *it) || (')' == *it)) {
1214            if (quotation) {
1215                quotation = false;
1216
1217                // extract the current field from the string and
1218                // append the current field to the given container
1219                container.push_back(string(first, it));
1220                ++n;
1221
1222                // skip the delimiter
1223                first = it + 1;
1224            } else {
1225                quotation = true;
1226
1227                // skip the quotation
1228                first = it + 1;
1229            }
1230        }
1231    }
1232    if (first != it) {
1233        // extract the last field from the string and
1234        // append the last field to the given container
1235        container.push_back(string(first, it));
1236        ++n;
1237    }
1238    return n;
1239}
1240
1241PyObject *GraphLayout_readPajek(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(fn, project) -> Edge List")
1242{
1243  PyTRY
1244    TDomain *domain = new TDomain();
1245    PDomain wdomain = domain;
1246    char *fn;
1247    unsigned char project = 0;
1248    bool hasGraph = 0;
1249
1250    if (!PyArg_ParseTuple(args, "s|b:GraphLayout.readPajek", &fn, &project))
1251        PYERROR(PyExc_TypeError, "invalid arguments (a string and optionally a boolean expected)", PYNULL);
1252
1253    string line;
1254   
1255    istream *stream;
1256    ifstream file(fn);
1257    istringstream text(fn, istringstream::in);
1258
1259    if (file.is_open()) {
1260        stream = &file;
1261    } else {
1262        if (text.good()) {
1263            stream = &text; 
1264        } else {
1265            PyErr_Format(PyExc_SystemError, "Unable to read network.", fn);
1266            return PYNULL;
1267        }
1268    }
1269   
1270    string graphName = "";
1271    string description = "";
1272    int nVertices = 0;
1273    int nEdges = 0;
1274
1275    TFloatVariable *indexVar = new TFloatVariable("index");
1276    indexVar->numberOfDecimals = 0;
1277    domain->addVariable(indexVar);
1278    domain->addVariable(new TStringVariable("label"));
1279    domain->addVariable(new TFloatVariable("x"));
1280    domain->addVariable(new TFloatVariable("y"));
1281    domain->addVariable(new TFloatVariable("z"));
1282    domain->addVariable(new TStringVariable("shape"));
1283    domain->addVariable(new TFloatVariable("size"));
1284    domain->addVariable(new TStringVariable("vertex color"));
1285    domain->addVariable(new TStringVariable("boundary color"));
1286    domain->addVariable(new TFloatVariable("boundary width"));
1287
1288    vector<string> words;
1289
1290    PyObject *networks;
1291    TExampleTable *table;
1292    PExampleTable wtable;
1293    PyObject *vertexList;
1294    PyObject *edgeList;
1295    PyObject *arcList;
1296    if (project)
1297        networks = PyList_New(0);
1298
1299    // read head
1300    bool hasLine = 0;
1301    int n;
1302    while (!stream->eof()) {
1303        if (!hasLine) {
1304            getline(*stream, line);
1305            n = getWords1(line, words);
1306        }
1307        hasLine = 0;
1308
1309        if (n > 0)  {
1310            std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower);
1311            if (words[0].compare("*network") == 0) {
1312                if (hasGraph && !project)
1313                    PYERROR(PyExc_SystemError, "Invalid file format. More than one network in a non-project file (parameter project is set to FALSE).", PYNULL);
1314
1315                hasGraph = 1;
1316                vertexList = PyList_New(0);
1317                edgeList = PyList_New(0);
1318                arcList = PyList_New(0);
1319                table = new TExampleTable(domain);
1320                wtable = table;
1321
1322                if (n > 1) {
1323                    graphName = words[1];
1324                } else {
1325                    graphName = "";
1326                }
1327
1328                if (project) {
1329                    PyObject *net = Py_BuildValue("sNNNN", graphName.c_str(), vertexList, edgeList, arcList, WrapOrange(wtable));
1330                    PyList_Append(networks, net);
1331                }
1332
1333                continue;
1334            }
1335
1336            if (hasGraph && (words[0].compare("*description") == 0)) {
1337                if (n > 1) {
1338                    description = words[1];
1339                }
1340                continue;
1341            }
1342
1343            if (hasGraph && (words[0].compare("*vertices") == 0)) {
1344                if (n > 1) {
1345                    nVertices = atoi(words[1].c_str());
1346                    if (nVertices < 1) {
1347                        file.close();
1348                        PYERROR(PyExc_SystemError, "Invalid number of vertices.", PYNULL);
1349                    }
1350                } else {
1351                    file.close();
1352                    PYERROR(PyExc_SystemError, "Invalid file format. Number of vertices not given.", PYNULL);
1353                }
1354                if (n > 2) {
1355                    nEdges = atoi(words[2].c_str());
1356                }
1357
1358                // read vertices
1359                int row = 0;
1360                while (!stream->eof()) {
1361                    getline(*stream, line);
1362                    int n = getWords1(line, words);
1363                    hasLine = 1;
1364                    if (n > 0) {
1365                        std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower);
1366                        if (words[0][0] == '*')
1367                            break;
1368
1369                        TExample *example = new TExample(domain);
1370                        float index = -1; istringstream strIndex(words[0]); strIndex >> index;
1371
1372                        PyObject *vData = PyDict_New();
1373                        PyList_Append(vertexList, vData);
1374
1375                        if ((index <= 0) || (index > nVertices)) {
1376                            file.close();
1377                            PYERROR(PyExc_SystemError, "Invalid file format. Invalid vertex index.", PYNULL);
1378                        }
1379
1380                        (*example)[0] = TValue(index);
1381                        if (n > 1) {
1382                            string label = words[1];
1383                            (*example)[1] = TValue(new TStringValue(label), STRINGVAR);
1384
1385                            int i = 2;
1386                            char *xyz = "  xyz";
1387                            // read coordinates
1388                            while ((i <= 4) && (i < n)) {
1389                                double coor = -1; istringstream strCoor(words[i]); strCoor >> coor;
1390                                (*example)[i] = TValue((float)coor);
1391
1392                                // if only 2 coordinates are given, shape follows
1393                                if ((i == 4) && (coor == -1)) {
1394                                    (*example)[i+1] = TValue(new TStringValue(words[i]), STRINGVAR);
1395                                } else if ((i == 4) && (n > i + 1)) {
1396                                    (*example)[i+1] = TValue(new TStringValue(words[i+1]), STRINGVAR);
1397                                }
1398                                i++;
1399                            }
1400                            // read attributes
1401                            while (i+1 < n) {
1402                                if (stricmp(words[i].c_str(), "s_size") == 0) {
1403                                    float size = -1; istringstream strSize(words[i+1]); strSize >> size;
1404                                    (*example)[6] = TValue(size);
1405                                } else if (stricmp(words[i].c_str(), "ic") == 0) {
1406                                    (*example)[7] = TValue(new TStringValue(words[i+1]), STRINGVAR);
1407                                } else if (stricmp(words[i].c_str(), "bc") == 0) {
1408                                    (*example)[8] = TValue(new TStringValue(words[i+1]), STRINGVAR);
1409                                } else if (stricmp(words[i].c_str(), "bw") == 0) {
1410                                    float bwidth = -1; istringstream strBWidth(words[i]); strBWidth >> bwidth;
1411                                    (*example)[9] = TValue(bwidth);
1412                                }
1413
1414                                PyDict_SetItemString(vData, words[i].c_str(),
1415                                        PyString_FromString(words[i+1].c_str()));
1416                                i += 2;
1417                            }
1418                        }
1419                        example->id = getExampleId();
1420                        table->push_back(example);
1421                    }
1422                    row++;
1423                }
1424                continue;
1425            }
1426
1427            if (hasGraph && (words[0].compare("*arcs") == 0)) {
1428                // read arcs
1429                while (!stream->eof()) {
1430                    getline(*stream, line);
1431                    int n = getWords1(line, words);
1432                    hasLine = 1;
1433                    if (n > 0) {
1434                        std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower);
1435                        if (words[0][0]=='*') {
1436                            break;
1437                        }
1438                        if (n > 1) {
1439                            int i1 = -1; istringstream strI1(words[0]); strI1 >> i1;
1440                            int i2 = -1; istringstream strI2(words[1]); strI2 >> i2;
1441                               
1442                            if ((i1 <= 0) || (i1 > nVertices) || (i2 <= 0) || (i2 > nVertices)) {
1443                                file.close();
1444                                PYERROR(PyExc_SystemError, "Invalid file format. Adding arcs: vertex index out of range.", PYNULL);
1445                            }
1446
1447                            if (i1 == i2) continue;
1448
1449                            // read attributes
1450                            PyObject *aData = PyDict_New();
1451                            int i = 3;
1452                            while(i+1<n) {
1453                                PyDict_SetItemString(aData, words[i].c_str(),
1454                                PyString_FromString(words[i+1].c_str()));
1455                                i += 2;
1456                            }
1457
1458                            // read weights
1459                            if (n > 2) {
1460                                vector<string> weights;
1461                                int m = getWords1(words[2], weights);
1462                                int i;
1463                                for (i=0; i < m; i++) {
1464                                    double i3 = 0; istringstream strI3(weights[i]); strI3 >> i3;
1465                                    PyObject *nel = Py_BuildValue("iidN", i1 - 1, i2 - 1, i3, aData);
1466                                    PyList_Append(arcList, nel);
1467                                    Py_DECREF(nel);
1468                                }
1469                            }
1470                            // if no weight specified, use default weight 1
1471                            else
1472                            {
1473                                double i3 = 1;
1474                                PyObject *nel = Py_BuildValue("iidN", i1 - 1, i2 - 1, i3, aData);
1475                                PyList_Append(arcList, nel);
1476                                Py_DECREF(nel);
1477                            }
1478                        }
1479                    }
1480                }
1481                continue;
1482            }
1483
1484            if (hasGraph && (words[0].compare("*edges") == 0)) {
1485                // read edges
1486                while (!stream->eof()) {
1487                    getline(*stream, line);
1488                    int n = getWords1(line, words);
1489                    hasLine = 1;
1490                    if (n > 0) {
1491                        std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower);
1492                        if (words[0][0]=='*') {
1493                            break;
1494                        }
1495                    }
1496                    if (n > 1) {
1497                        int i1 = -1; istringstream strI1(words[0]); strI1 >> i1;
1498                        int i2 = -1; istringstream strI2(words[1]); strI2 >> i2;
1499                           
1500                        if ((i1 <= 0) || (i1 > nVertices) || (i2 <= 0) || (i2 > nVertices)) {
1501                            file.close();
1502                            PYERROR(PyExc_SystemError, "Invalid file format. Adding edges: vertex index out of range.", PYNULL);
1503                        }
1504
1505                        if (i1 == i2) continue;
1506
1507                        // read attributes
1508                        PyObject *eData = PyDict_New();
1509                        int i = 3;
1510                        while(i+1<n) {
1511                            PyDict_SetItemString(eData, words[i].c_str(),
1512                            PyString_FromString(words[i+1].c_str()));
1513                            i += 2;
1514                        }
1515
1516                        // read weights
1517                        if (n > 2) {
1518                            vector<string> weights;
1519                            int m = getWords1(words[2], weights);
1520                            int i;
1521                            for (i=0; i < m; i++) {
1522                                double i3 = 0; istringstream strI3(weights[i]); strI3 >> i3;
1523                                PyObject *nel = Py_BuildValue("iidN", i1 - 1, i2 - 1, i3, eData);
1524                                PyList_Append(edgeList, nel);
1525                                Py_DECREF(nel);
1526                            }
1527                        }
1528                        // if no weight specified, use default weight 1
1529                        else
1530                        {
1531                            double i3 = 1;
1532                            PyObject *nel = Py_BuildValue("iidN", i1 - 1, i2 - 1, i3, eData);
1533                            PyList_Append(edgeList, nel);
1534                            Py_DECREF(nel);
1535                        }
1536                    }
1537                }
1538                continue;
1539            }
1540
1541            if  ((hasGraph && (words[0].compare("*date") == 0)) || words[0][0]=='#') {
1542                continue;
1543            }
1544
1545            if ((words[0][0]=='*') && project)
1546                hasGraph = 0;
1547            else
1548            {
1549                cout << words[0] << endl;
1550                PYERROR(PyExc_SystemError, "Invalid file format. Invalid keyword.", PYNULL);
1551            }
1552        }
1553    }
1554    file.close();
1555    if (project)
1556        return Py_BuildValue("N", networks);
1557    else if (hasGraph)
1558        return Py_BuildValue("sNNNN", graphName.c_str(), vertexList, edgeList, arcList, WrapOrange(wtable));
1559    else
1560        return Py_BuildValue("");
1561  PyCATCH
1562}
1563
1564#include "graph_layout.px"
Note: See TracBrowser for help on using the repository browser.