Changeset 7947:c9db90e11c0d in orange
 Timestamp:
 05/27/11 14:21:50 (3 years ago)
 Branch:
 default
 Convert:
 3fcc7df974be4fd41259d4b361bc106f25501eee
 Location:
 source/orangeom
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

source/orangeom/graph_layout.cpp
r7866 r7947 68 68 } 69 69 70 void 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 70 79 int TGraphLayout::random() 71 80 { … … 290 299 // type = 2  smooth fr 291 300 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++) { 294 303 if (type == 1) { 295 304 if (level[u] == level[v]) { … … 320 329 321 330 if (dif2 < kk2) { 322 if (dif2 == 0) 331 if (dif2 == 0) { 323 332 dif2 = 1; 324 333 } 325 334 double dX = difX * k2 / dif2; 326 335 double dY = difY * k2 / dif2; … … 336 345 } 337 346 338 void TGraphLayout::fr_attractive_force(int type )347 void TGraphLayout::fr_attractive_force(int type, bool weighted) 339 348 { 340 349 // type = 0  classic fr … … 368 377 369 378 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 } 373 389 374 390 disp[0][v] = dX; … … 388 404 double dif = sqrt(pow(disp[0][v], 2) + pow(disp[1][v], 2)); 389 405 390 if (dif == 0) 406 if (dif == 0) { 391 407 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); 395 411 396 412 //pos[v][0] = min((double)width, max((double)0, pos[v][0])); … … 411 427 kk = 2 * k; 412 428 double kk2 = kk * kk; 413 429 414 430 // iterations 415 431 for (i = 0; i < steps; i++) { 416 432 clear_disp(); 417 433 fr_repulsive_force(kk2, 0); 418 fr_attractive_force(0 );434 fr_attractive_force(0, weighted); 419 435 fr_limit_displacement(); 420 436 temperature = temperature * coolFactor; … … 441 457 clear_disp(); 442 458 fr_repulsive_force(kk2, 1); 443 fr_attractive_force(1 );459 fr_attractive_force(1, false); 444 460 fr_limit_displacement(); 445 461 // limit the maximum displacement to the temperature t … … 577 593 int TGraphLayout::set_graph(PyObject *graph) 578 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 } 579 611 PyObject* nodes = PyObject_GetAttrString(graph, "node"); 580 612 PyObject* adj = PyObject_GetAttrString(graph, "adj"); … … 607 639 608 640 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; 610 642 611 643 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; 614 647 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); 616 649 links[0].push_back(u); 617 650 links[1].push_back(v); … … 655 688 { 656 689 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)) { 660 694 return PYNULL; 695 } 661 696 662 697 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 } 665 714 666 715 RETURN_NONE; … … 722 771 723 772 if (graph_layout>fr(steps, weighted) > 0) { 724 PYERROR(PyExc_SystemError, "fr failed", NULL);773 PYERROR(PyExc_SystemError, "fr failed", PYNULL); 725 774 } 726 775 … … 1044 1093 } 1045 1094 1095 PyObject *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, "Oddii: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 1174 WRAPPER(ExampleTable) 1175 1176 int 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 1225 PyObject *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 1046 1464 #include "graph_layout.px" 
source/orangeom/graph_layout.hpp
r7866 r7947 41 41 #include <fstream> 42 42 #include <string> 43 #include <algorithm> 43 44 #include <time.h> 44 45 #include <queue> … … 51 52 #include "root.hpp" 52 53 #include "stringvars.hpp" 54 #include "table.hpp" 55 #include "symmatrix.hpp" 53 56 54 57 using namespace std; … … 63 66 int set_graph(PyObject *graph); 64 67 void dump_coordinates(); 68 void dump_disp(); 65 69 void clear_disp(); 66 70 // graph layout optimization 67 71 int random(); 68 72 void fr_repulsive_force(double kk2, int type); 69 void fr_attractive_force(int type );73 void fr_attractive_force(int type, bool weighted); 70 74 void fr_limit_displacement(); 71 75 int fr(int steps, bool weighted);
Note: See TracChangeset
for help on using the changeset viewer.