Changeset 7947:c9db90e11c0d in orange


Ignore:
Timestamp:
05/27/11 14:21:50 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
3fcc7df974be4fd41259d4b361bc106f25501eee
Message:

Fixed layout optimization bug. Added methods for networkx support.

Location:
source/orangeom
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orangeom/graph_layout.cpp

    r7866 r7947  
    6868} 
    6969 
     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 
    7079int TGraphLayout::random() 
    7180{ 
     
    290299    // type = 2 - smooth fr 
    291300    int u, v; 
    292     for (v = 0; v < nVertices - 1; v++) { 
    293         for (u = v + 1; u < nVertices; u++) { 
     301    for (v = 0; v < nVertices; v++) { 
     302        for (u = 0; u < v; u++) { 
    294303            if (type == 1) { 
    295304                if (level[u] == level[v]) { 
     
    320329 
    321330            if (dif2 < kk2) { 
    322                 if (dif2 == 0) 
     331                if (dif2 == 0) { 
    323332                    dif2 = 1; 
    324  
     333                } 
    325334                double dX = difX * k2 / dif2; 
    326335                double dY = difY * k2 / dif2; 
     
    336345} 
    337346 
    338 void TGraphLayout::fr_attractive_force(int type) 
     347void TGraphLayout::fr_attractive_force(int type, bool weighted) 
    339348{ 
    340349    // type = 0 - classic fr 
     
    368377 
    369378        double dif = sqrt(difX * difX + difY * difY); 
    370                  
    371         double dX = difX * dif / k * weights[j]; 
    372         double dY = difY * dif / k * weights[j]; 
     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        } 
    373389 
    374390        disp[0][v] -= dX; 
     
    388404        double dif = sqrt(pow(disp[0][v], 2) + pow(disp[1][v], 2)); 
    389405 
    390         if (dif == 0) 
     406        if (dif == 0) { 
    391407            dif = 1; 
    392  
    393         pos[0][v] = pos[0][v] + (disp[0][v] * min(fabs(disp[0][v]), temperature) / dif); 
    394         pos[1][v] = pos[1][v] + (disp[1][v] * min(fabs(disp[1][v]), temperature) / dif); 
     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); 
    395411 
    396412        //pos[v][0] = min((double)width,  max((double)0, pos[v][0])); 
     
    411427    kk = 2 * k; 
    412428    double kk2 = kk * kk; 
    413  
     429     
    414430    // iterations 
    415431    for (i = 0; i < steps; i++) { 
    416432        clear_disp(); 
    417433        fr_repulsive_force(kk2, 0); 
    418         fr_attractive_force(0); 
     434        fr_attractive_force(0, weighted); 
    419435        fr_limit_displacement(); 
    420436        temperature = temperature * coolFactor; 
     
    441457        clear_disp(); 
    442458        fr_repulsive_force(kk2, 1); 
    443         fr_attractive_force(1); 
     459        fr_attractive_force(1, false); 
    444460        fr_limit_displacement(); 
    445461        // limit the maximum displacement to the temperature t 
     
    577593int TGraphLayout::set_graph(PyObject *graph) 
    578594{ 
     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    } 
    579611    PyObject* nodes = PyObject_GetAttrString(graph, "node"); 
    580612    PyObject* adj = PyObject_GetAttrString(graph, "adj"); 
     
    607639 
    608640    PyObject *key_u, *value_u, *key_v, *value_v; 
    609     Py_ssize_t pos_u = 0, pos_v = 0; 
     641    Py_ssize_t pos_u = 0; 
    610642 
    611643    while (PyDict_Next(adj, &pos_u, &key_u, &value_u)) { 
    612         int u = PyInt_AS_LONG(key_u) - 1; 
    613  
     644        int u = PyInt_AS_LONG(key_u); 
     645 
     646        Py_ssize_t pos_v = 0; 
    614647        while (PyDict_Next(value_u, &pos_v, &key_v, &value_v)) { 
    615             int v = PyInt_AS_LONG(key_v) - 1; 
     648            int v = PyInt_AS_LONG(key_v); 
    616649            links[0].push_back(u); 
    617650            links[1].push_back(v); 
     
    655688{ 
    656689  PyTRY 
    657     PyObject* graph; 
    658  
    659     if (!PyArg_ParseTuple(args, "O:GraphLayout.set_graph", &graph)) 
     690    PyObject* graph = Py_None; 
     691    PyObject* positions = Py_None; 
     692 
     693    if (!PyArg_ParseTuple(args, "|OO:GraphLayout.set_graph", &graph, &positions)) { 
    660694          return PYNULL; 
     695    } 
    661696 
    662697    CAST_TO(TGraphLayout, graph_layout); 
    663      
    664     graph_layout->set_graph(graph); 
     698 
     699    if (graph == Py_None) { 
     700        graph_layout->set_graph(NULL); 
     701    } else { 
     702        graph_layout->set_graph(graph); 
     703 
     704        if (positions != Py_None) { 
     705            int i; 
     706            for (i = 0; i < graph_layout->nVertices; i++) { 
     707                double x,y; 
     708                PyArg_ParseTuple(PyList_GetItem(positions, i), "dd", &x, &y); 
     709                graph_layout->pos[0][i] = x; 
     710                graph_layout->pos[1][i] = y; 
     711            } 
     712        } 
     713    } 
    665714     
    666715    RETURN_NONE; 
     
    722771 
    723772    if (graph_layout->fr(steps, weighted) > 0) { 
    724         PYERROR(PyExc_SystemError, "fr failed", NULL); 
     773        PYERROR(PyExc_SystemError, "fr failed", PYNULL); 
    725774    } 
    726775 
     
    10441093} 
    10451094 
     1095PyObject *GraphLayout_edges_from_distance_matrix(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(matrix, lower, upper, kNN) -> list of edges") 
     1096{ 
     1097  PyTRY 
     1098    PyObject *pyMatrix; 
     1099    double lower; 
     1100    double upper; 
     1101    int kNN = 0; 
     1102    int andor = 0; 
     1103 
     1104    if (!PyArg_ParseTuple(args, "Odd|ii:GraphLayout.edges_from_distance_matrix", &pyMatrix, &lower, &upper, &kNN)) 
     1105        return PYNULL; 
     1106 
     1107    TSymMatrix *matrix = &dynamic_cast<TSymMatrix &>(PyOrange_AsOrange(pyMatrix).getReference()); 
     1108    //cout << "kNN: " << kNN << endl; 
     1109    //cout << "andor: " << andor << endl; 
     1110 
     1111    int i,j; 
     1112    //vector<coord_t> edges_interval; 
     1113    PyObject* edges = PyList_New(0); 
     1114 
     1115    if (matrix->matrixType == 0) { 
     1116        // lower 
     1117        for (i = 0; i < matrix->dim; i++) { 
     1118            bool connected = false; 
     1119            for (j = i+1; j < matrix->dim; j++) { 
     1120                //cout << "i " << i << " j " << j; 
     1121                double value = matrix->getitem(j,i); 
     1122                //cout << " value " << value << endl; 
     1123                if (lower <=  value && value <= upper) { 
     1124                    connected = true; 
     1125                    //edges_interval.push_back(coord_t(j, i)); 
     1126                    PyObject *nel = Py_BuildValue("iid", j, i, value); 
     1127                    PyList_Append(edges, nel); 
     1128                    Py_DECREF(nel); 
     1129                } 
     1130            } 
     1131        } 
     1132    } else { 
     1133        // upper 
     1134        for (i = 0; i < matrix->dim; i++) { 
     1135            bool connected = false; 
     1136            for (j = i+1; j < matrix->dim; j++) { 
     1137                double value = matrix->getitem(i,j); 
     1138                if (lower <=  value && value <= upper) { 
     1139                    connected = true; 
     1140                    //edges_interval.push_back(coord_t(i, j)); 
     1141                    PyObject *nel = Py_BuildValue("iid", i, j, value); 
     1142                    PyList_Append(edges, nel); 
     1143                    Py_DECREF(nel); 
     1144                } 
     1145            } 
     1146        } 
     1147    } 
     1148     
     1149    //PyObject* edges_knn = PyList_New(0); 
     1150    if (kNN > 0) { 
     1151        for (i = 0; i < matrix->dim; i++) { 
     1152            vector<int> closest; 
     1153            matrix->getknn(i, kNN, closest); 
     1154 
     1155            for (j = 0; j < closest.size(); j++) { 
     1156                //edges_knn.push_back(coord_t(i, closest[j])); 
     1157                double value = matrix->getitem(i, closest[j]); 
     1158                PyObject *nel = Py_BuildValue("iid", i, closest[j], value); 
     1159                PyList_Append(edges, nel); 
     1160                Py_DECREF(nel); 
     1161            } 
     1162        } 
     1163    } 
     1164 
     1165    if (andor == 0) { 
     1166         
     1167    } 
     1168 
     1169    return edges; 
     1170  PyCATCH; 
     1171} 
     1172 
     1173 
     1174WRAPPER(ExampleTable) 
     1175 
     1176int getWords1(string const& s, vector<string> &container) 
     1177{ 
     1178    int n = 0; 
     1179    bool quotation = false; 
     1180    container.clear(); 
     1181    string::const_iterator it = s.begin(), end = s.end(), first; 
     1182    for (first = it; it != end; ++it) { 
     1183        // Examine each character and if it matches the delimiter 
     1184        if ((!quotation && (' ' == *it || '\t' == *it || '\r' == *it || '\f' == *it || '\v' == *it || ',' == *it)) || ('\n' == *it)) { 
     1185            if (first != it) { 
     1186                // extract the current field from the string and 
     1187                // append the current field to the given container 
     1188                container.push_back(string(first, it)); 
     1189                ++n; 
     1190 
     1191                // skip the delimiter 
     1192                first = it + 1; 
     1193            } else { 
     1194                ++first; 
     1195            } 
     1196        } 
     1197        else if (('\"' == *it) || ('\'' == *it) || ('(' == *it) || (')' == *it)) { 
     1198            if (quotation) { 
     1199                quotation = false; 
     1200 
     1201                // extract the current field from the string and 
     1202                // append the current field to the given container 
     1203                container.push_back(string(first, it)); 
     1204                ++n; 
     1205 
     1206                // skip the delimiter 
     1207                first = it + 1; 
     1208            } else { 
     1209                quotation = true; 
     1210 
     1211                // skip the quotation 
     1212                first = it + 1; 
     1213            } 
     1214        } 
     1215    } 
     1216    if (first != it) { 
     1217        // extract the last field from the string and 
     1218        // append the last field to the given container 
     1219        container.push_back(string(first, it)); 
     1220        ++n; 
     1221    } 
     1222    return n; 
     1223} 
     1224 
     1225PyObject *GraphLayout_readPajek(PyObject *self, PyObject *args) PYARGS(METH_VARARGS, "(fn) -> Edge List") 
     1226{ 
     1227  PyTRY 
     1228    TDomain *domain = new TDomain(); 
     1229    PDomain wdomain = domain; 
     1230    TExampleTable *table; 
     1231    PExampleTable wtable; 
     1232    PyObject *edgeList = PyList_New(0); 
     1233    PyObject *arcList = PyList_New(0); 
     1234    char *fn; 
     1235 
     1236    if (!PyArg_ParseTuple(args, "s:GraphLayout.readPajek", &fn)) 
     1237        PYERROR(PyExc_TypeError, "invalid arguments (string expected)", PYNULL); 
     1238 
     1239    string line; 
     1240     
     1241    istream *stream; 
     1242    ifstream file = ifstream(fn); 
     1243    istringstream text(fn, istringstream::in); 
     1244 
     1245    if (file.is_open()) { 
     1246        stream = &file; 
     1247    } else { 
     1248        if (text.good()) { 
     1249            stream = &text;  
     1250        } else { 
     1251            PyErr_Format(PyExc_SystemError, "Unable to read network.", fn); 
     1252            return PYNULL; 
     1253        } 
     1254    } 
     1255     
     1256    string graphName = ""; 
     1257    string description = ""; 
     1258    int nVertices = 0; 
     1259    int nEdges = 0; 
     1260 
     1261    TFloatVariable *indexVar = new TFloatVariable("index"); 
     1262    indexVar->numberOfDecimals = 0; 
     1263    domain->addVariable(indexVar); 
     1264    domain->addVariable(new TStringVariable("label")); 
     1265    domain->addVariable(new TFloatVariable("x")); 
     1266    domain->addVariable(new TFloatVariable("y")); 
     1267    domain->addVariable(new TFloatVariable("z")); 
     1268    domain->addVariable(new TStringVariable("shape")); 
     1269    domain->addVariable(new TFloatVariable("size")); 
     1270    domain->addVariable(new TStringVariable("vertex color")); 
     1271    domain->addVariable(new TStringVariable("boundary color")); 
     1272    domain->addVariable(new TFloatVariable("boundary width")); 
     1273    table = new TExampleTable(domain); 
     1274    wtable = table; 
     1275    vector<string> words; 
     1276 
     1277    // read head 
     1278    while (!stream->eof()) { 
     1279        getline(*stream, line); 
     1280        int n = getWords1(line, words); 
     1281        if (n > 0)  { 
     1282            std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower); 
     1283            if (words[0].compare("*network") == 0) { 
     1284                if (n > 1) { 
     1285                    graphName = words[1]; 
     1286                } 
     1287            } else if (words[0].compare("*description") == 0) { 
     1288                if (n > 1) { 
     1289                    description = words[1]; 
     1290                } 
     1291            } else if (words[0].compare("*vertices") == 0) { 
     1292                if (n > 1) { 
     1293                    nVertices = atoi(words[1].c_str()); 
     1294                    if (nVertices < 1) { 
     1295                        file.close(); 
     1296                        PYERROR(PyExc_SystemError, "Invalid number of vertices.", PYNULL); 
     1297                    } 
     1298                } else { 
     1299                    file.close(); 
     1300                    PYERROR(PyExc_SystemError, "Invalid file format. Number of vertices not given.", PYNULL); 
     1301                } 
     1302                if (n > 2) { 
     1303                    nEdges = atoi(words[2].c_str()); 
     1304                } 
     1305 
     1306                // read vertices 
     1307                int row = 0; 
     1308                while (!stream->eof()) { 
     1309                    getline(*stream, line); 
     1310                    int n = getWords1(line, words); 
     1311                    if (n > 0) { 
     1312                        std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower); 
     1313                        if (words[0].compare("*arcs") == 0 || words[0].compare("*edges") == 0) 
     1314                            break; 
     1315 
     1316                        TExample *example = new TExample(domain); 
     1317                        float index = -1; istringstream strIndex(words[0]); strIndex >> index; 
     1318                             
     1319                        if ((index <= 0) || (index > nVertices)) { 
     1320                            file.close(); 
     1321                            PYERROR(PyExc_SystemError, "Invalid file format. Invalid vertex index.", PYNULL); 
     1322                        } 
     1323 
     1324                        (*example)[0] = TValue(index); 
     1325                        if (n > 1) { 
     1326                            string label = words[1]; 
     1327                            (*example)[1] = TValue(new TStringValue(label), STRINGVAR); 
     1328 
     1329                            int i = 2; 
     1330                            char *xyz = "  xyz"; 
     1331                            // read coordinates 
     1332                            while ((i <= 4) && (i < n)) { 
     1333                                double coor = -1; istringstream strCoor(words[i]); strCoor >> coor; 
     1334                                (*example)[i] = TValue((float)coor); 
     1335 
     1336                                // if only 2 coordinates are given, shape follows 
     1337                                if ((i == 4) && (coor == -1)) { 
     1338                                    (*example)[i+1] = TValue(new TStringValue(words[i]), STRINGVAR); 
     1339                                } else if ((i == 4) && (n > i + 1)) { 
     1340                                    (*example)[i+1] = TValue(new TStringValue(words[i+1]), STRINGVAR); 
     1341                                } 
     1342                                i++; 
     1343                            } 
     1344                            // read attributes 
     1345                            while (i < n) { 
     1346                                if (stricmp(words[i].c_str(), "s_size") == 0) { 
     1347                                    if (i + 1 < n) { 
     1348                                        i++; 
     1349                                    } else { 
     1350                                        file.close(); 
     1351                                        PYERROR(PyExc_SystemError, "invalid file format. Error reading vertex size.", PYNULL); 
     1352                                    } 
     1353                                    float size = -1; istringstream strSize(words[i]); strSize >> size; 
     1354                                    (*example)[6] = TValue(size); 
     1355 
     1356                                } else if (stricmp(words[i].c_str(), "ic") == 0) { 
     1357                                    if (i + 1 < n) { 
     1358                                        i++; 
     1359                                    } else { 
     1360                                        file.close(); 
     1361                                        PYERROR(PyExc_SystemError, "invalid file format. Error reading vertex color.", PYNULL); 
     1362                                    } 
     1363                                    (*example)[7] = TValue(new TStringValue(words[i]), STRINGVAR); 
     1364 
     1365                                } else if (stricmp(words[i].c_str(), "bc") == 0) { 
     1366                                    if (i + 1 < n) { 
     1367                                        i++; 
     1368                                    } else { 
     1369                                        file.close(); 
     1370                                        PYERROR(PyExc_SystemError, "invalid file format. Error reading boundary color.", PYNULL); 
     1371                                    } 
     1372                                    (*example)[8] = TValue(new TStringValue(words[i]), STRINGVAR); 
     1373                                } else if (stricmp(words[i].c_str(), "bw") == 0) { 
     1374                                    if (i + 1 < n) { 
     1375                                        i++; 
     1376                                    } else { 
     1377                                        file.close(); 
     1378                                        PYERROR(PyExc_SystemError, "invalid file format. Error reading boundary width.", PYNULL); 
     1379                                    } 
     1380                                    float bwidth = -1; istringstream strBWidth(words[i]); strBWidth >> bwidth; 
     1381                                    (*example)[9] = TValue(bwidth); 
     1382                                } 
     1383                                i++; 
     1384                            } 
     1385                        } 
     1386                        example->id = getExampleId(); 
     1387                        table->push_back(example); 
     1388                    } 
     1389                    row++; 
     1390                } 
     1391            } 
     1392            if (words[0].compare("*arcs") == 0) { 
     1393                // read arcs 
     1394                while (!stream->eof()) { 
     1395                    getline(*stream, line); 
     1396                    //vector<string> words; 
     1397                    int n = getWords1(line, words); 
     1398                    if (n > 0) { 
     1399                        std::transform(words[0].begin(), words[0].end(), words[0].begin(), ::tolower); 
     1400                        if (words[0].compare("*edges") == 0) { 
     1401                            break; 
     1402                        } 
     1403                        if (n > 1) { 
     1404                            int i1 = -1; istringstream strI1(words[0]); strI1 >> i1; 
     1405                            int i2 = -1; istringstream strI2(words[1]); strI2 >> i2; 
     1406                                 
     1407                            if ((i1 <= 0) || (i1 > nVertices) || (i2 <= 0) || (i2 > nVertices)) { 
     1408                                file.close(); 
     1409                                PYERROR(PyExc_SystemError, "Invalid file format. Adding arcs: vertex index out of range.", PYNULL); 
     1410                            } 
     1411 
     1412                            if (i1 == i2) continue; 
     1413                            if (n > 2) { 
     1414                                vector<string> weights; 
     1415                                int m = getWords1(words[2], weights); 
     1416                                int i; 
     1417                                for (i=0; i < m; i++) { 
     1418                                    double i3 = 0; istringstream strI3(weights[i]); strI3 >> i3; 
     1419                                    PyObject *nel = Py_BuildValue("iid", i1 - 1, i2 - 1, i3); 
     1420                                    PyList_Append(arcList, nel); 
     1421                                    Py_DECREF(nel); 
     1422                                } 
     1423                            } 
     1424                        } 
     1425                    } 
     1426                } 
     1427            } 
     1428            if (words[0].compare("*edges") == 0) { 
     1429                // read edges 
     1430                while (!stream->eof()) { 
     1431                    getline(*stream, line); 
     1432                    int n = getWords1(line, words); 
     1433                    if (n > 1) { 
     1434                        int i1 = -1; istringstream strI1(words[0]); strI1 >> i1; 
     1435                        int i2 = -1; istringstream strI2(words[1]); strI2 >> i2; 
     1436                             
     1437                        if ((i1 <= 0) || (i1 > nVertices) || (i2 <= 0) || (i2 > nVertices)) { 
     1438                            file.close(); 
     1439                            PYERROR(PyExc_SystemError, "Invalid file format. Adding edges: vertex index out of range.", PYNULL); 
     1440                        } 
     1441 
     1442                        if (i1 == i2) continue; 
     1443                        if (n > 2) { 
     1444                            vector<string> weights; 
     1445                            int m = getWords1(words[2], weights); 
     1446                            int i; 
     1447                            for (i=0; i < m; i++) { 
     1448                                double i3 = 0; istringstream strI3(weights[i]); strI3 >> i3; 
     1449                                PyObject *nel = Py_BuildValue("iid", i1 - 1, i2 - 1, i3); 
     1450                                PyList_Append(edgeList, nel); 
     1451                                Py_DECREF(nel); 
     1452                            } 
     1453                        } 
     1454                    } 
     1455                } 
     1456            } 
     1457        } 
     1458    } 
     1459    file.close(); 
     1460    return Py_BuildValue("NNN", edgeList, arcList, WrapOrange(wtable)); 
     1461  PyCATCH 
     1462} 
     1463 
    10461464#include "graph_layout.px" 
  • source/orangeom/graph_layout.hpp

    r7866 r7947  
    4141#include <fstream> 
    4242#include <string> 
     43#include <algorithm> 
    4344#include <time.h> 
    4445#include <queue> 
     
    5152#include "root.hpp" 
    5253#include "stringvars.hpp" 
     54#include "table.hpp" 
     55#include "symmatrix.hpp" 
    5356 
    5457using namespace std; 
     
    6366    int set_graph(PyObject *graph); 
    6467    void dump_coordinates(); 
     68    void dump_disp(); 
    6569    void clear_disp(); 
    6670    // graph layout optimization 
    6771    int random(); 
    6872    void fr_repulsive_force(double kk2, int type); 
    69     void fr_attractive_force(int type); 
     73    void fr_attractive_force(int type, bool weighted); 
    7074    void fr_limit_displacement(); 
    7175    int fr(int steps, bool weighted); 
Note: See TracChangeset for help on using the changeset viewer.