get the connected components from an NxN adjacency matrix (1.0 for i-j connected, 0.0 for i-j not connected)
| 336 | |
| 337 | /// get the connected components from an NxN adjacency matrix (1.0 for i-j connected, 0.0 for i-j not connected) |
| 338 | std::vector<std::vector<unsigned>> findConnectedComponents(const Matrix& matrix) { |
| 339 | double tol = 0.001; |
| 340 | |
| 341 | std::vector<std::vector<unsigned>> result; |
| 342 | |
| 343 | size_t N = matrix.size1(); |
| 344 | if (N != matrix.size2()) { |
| 345 | return result; |
| 346 | } |
| 347 | |
| 348 | Matrix A(N, N, 0.0); |
| 349 | for (unsigned i = 0; i < N; ++i) { |
| 350 | |
| 351 | A(i, i) = 1.0; // must be self connected |
| 352 | if (std::abs(matrix(i, i) - 1.0) > tol) { |
| 353 | // warn |
| 354 | } |
| 355 | |
| 356 | for (unsigned j = i + 1; j < N; ++j) { |
| 357 | |
| 358 | if (matrix(i, j) < 0) { |
| 359 | // warn |
| 360 | } else if (matrix(i, j) > tol) { |
| 361 | A(i, j) = 1.0; |
| 362 | } |
| 363 | |
| 364 | if (matrix(j, i) < 0) { |
| 365 | // warn |
| 366 | } else if (matrix(j, i) > tol) { |
| 367 | A(j, i) = 1.0; |
| 368 | } |
| 369 | } |
| 370 | } |
| 371 | |
| 372 | // raise A to the Nth power, maximum distance between two nodes |
| 373 | for (unsigned n = 0; n < N; ++n) { |
| 374 | A = prod(A, A); |
| 375 | |
| 376 | // re-normalize |
| 377 | for (unsigned i = 0; i < N; ++i) { |
| 378 | for (unsigned j = 0; j < N; ++j) { |
| 379 | if (A(j, i) > 1) { |
| 380 | A(j, i) = 1; |
| 381 | } |
| 382 | } |
| 383 | } |
| 384 | } |
| 385 | |
| 386 | std::set<unsigned> added; |
| 387 | for (unsigned i = 0; i < N; ++i) { |
| 388 | if (added.find(i) != added.end()) { |
| 389 | continue; |
| 390 | } |
| 391 | |
| 392 | std::vector<unsigned> group; |
| 393 | group.push_back(i); |
| 394 | added.insert(i); |
| 395 |