8000 Assertion errors in `DistanceFromCut::operator[]` · Issue #200 · kahypar/kahypar · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Assertion errors in DistanceFromCut::opera 8000 tor[] #200

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
twesterhout opened this issue May 6, 2024 · 15 comments
Open

Assertion errors in DistanceFromCut::operator[] #200

twesterhout opened this issue May 6, 2024 · 15 comments

Comments

@twesterhout
Copy link

Hello,

I'm getting the following assertion failures in v1.3.5:

external_tools/WHFC/datastructure/node_border.h:22: whfc::HopDistance& whfc::DistanceFromCut::operator[](size_t): Assertion `idx < distance.size()' failed.

[2way_fm_refiner.h:200:refineImpl]: Assertion `best_metrics.cut == metrics::hyperedgeCut(_hg)` failed: best_metrics.cut = 15 metrics::hyperedgeCut(_hg) = 13

Do you have any idea what could be causing it?
@SebastianSchlag
Copy link
Member

Hey @twesterhout,

thanks for reaching out. Could you provide us with the input hypergraph and the configuration you used?

@larsgottesbueren this looks like some violation in the hyperflowcutter code. Could you take a look?

@twesterhout
Copy link
Author
twesterhout commented May 7, 2024 •
edited
Loading

So here's the configuration that kahypar displays (this is just the cut_kKaHyPar_sea20.ini profile)

*******************************************************************************
*                            Partitioning Context                             *
*******************************************************************************
Partitioning Parameters:
  Hypergraph:
  Partition File:
  Mode:                               direct
  Objective:                          cut
  k:                                  2
  epsilon:                            0.02
  seed:                               42
  # V-cycles:                         0
  time limit:                         -1s
  hyperedge size ignore threshold:    1000
  hyperedge size removal threshold:   4294967295
  use individual block weights:       false
  L_opt:                              801000
  L_max:                              817020
-------------------------------------------------------------------------------
Preprocessing Parameters:
  enable deduplication:               false
  enable min hash sparsifier:         true
  enable community detection:         true
-------------------------------------------------------------------------------
MinHash Sparsifier Parameters:
  max hyperedge size:                 1200
  max cluster size:                   10
  min cluster size:                   2
  number of hash functions:           5
  number of combined hash functions:  100
  active at median net size >=:       28
  sparsifier is active:               false
-------------------------------------------------------------------------------
Community Detection Parameters:
  use community detection in IP:      true
  maximum louvain-pass iterations:    100
  minimum quality improvement:        0.0001
  graph edge weight:                  uniform
  reuse community structure:          false
  large HE threshold:                 4294967295
-------------------------------------------------------------------------------
Coarsening Parameters:
  Algorithm:                          ml_style
  max-allowed-weight-multiplier:      1
  contraction-limit-multiplier:       160
  hypernode weight fraction:          0.003125
  max. allowed hypernode weight:      5007
  contraction limit:                  320
  Rating Parameters:
    Rating Function:                  heavy_edge
    Use Community Structure:          true
    Heavy Node Penalty:               no_penalty
    Acceptance Policy:                best_prefer_unmatched
    Partition Policy:                 normal
    Fixed Vertex Acceptance Policy:   fixed_vertex_allowed
-------------------------------------------------------------------------------
Initial Partitioning Parameters:
  # IP trials:                        20
  Mode:                               recursive
  Technique:                          multilevel
  Algorithm:                          pool
  Bin Packing algorithm:              worst_fit
    early restart on infeasible:      true
    late restart on infeasible:       true
IP Coarsening:
Coarsening Parameters:
  Algorithm:                          ml_style
  max-allowed-weight-multiplier:      1
  contraction-limit-multiplier:       150
  hypernode weight fraction:          determined before IP
  max. allowed hypernode weight:      determined before IP
  contraction limit:                  determined before IP
  Rating Parameters:
    Rating Function:                  heavy_edge
    Use Community Structure:          true
    Heavy Node Penalty:               no_penalty
    Acceptance Policy:                best_prefer_unmatched
    Partition Policy:                 normal
    Fixed Vertex Acceptance Policy:   fixed_vertex_allowed
IP Local Search:
Local Search Parameters:
  Algorithm:                          twoway_fm
  iterations per level:               2147483647
  stopping rule:                      simple
  max. # fruitless moves:             50
  Flow Refinement Parameters:
    execution policy:                 UNDEFINED
-------------------------------------------------------------------------------
Local Search Parameters:
  Algorithm:                          kway_fm_hyperflow_cutter
  iterations per level:               2147483647
  stopping rule:                      adaptive_opt
  adaptive stopping alpha:            1
  Flow Refinement Parameters:
    execution policy:                 exponential
-------------------------------------------------------------------------------

I'm using kahypar through the Python interface. Here's the kwargs dict that I'm passing to the Hypergraph constructor:

{'num_nodes': 646, 'num_edges': 801, 'index_vector': [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382, 384, 386, 388, 390, 392, 394, 396, 398, 400, 402, 404, 406, 408, 410, 412, 414, 416, 418, 420, 422, 424, 426, 428, 430, 432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478, 480, 482, 484, 486, 488, 490, 492, 494, 496, 498, 500, 502, 504, 506, 508, 510, 512, 514, 516, 518, 520, 522, 524, 526, 528, 530, 532, 534, 536, 538, 540, 542, 544, 546, 548, 550, 552, 554, 556, 558, 560, 562, 564, 566, 568, 570, 572, 574, 576, 578, 580, 582, 584, 586, 588, 590, 592, 594, 596, 598, 600, 602, 604, 606, 608, 610, 612, 614, 616, 618, 620, 622, 624, 626, 628, 630, 632, 634, 636, 638, 640, 642, 644, 646, 648, 650, 652, 654, 656, 658, 660, 662, 664, 666, 668, 670, 672, 674, 676, 678, 680, 682, 684, 686, 688, 690, 692, 694, 696, 698, 700, 702, 704, 706, 708, 710, 712, 714, 716, 718, 720, 722, 724, 726, 728, 730, 732, 734, 736, 738, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766, 768, 770, 772, 774, 776, 778, 780, 782, 784, 786, 788, 790, 792, 794, 796, 798, 800, 802, 804, 806, 808, 810, 812, 814, 816, 818, 820, 822, 824, 826, 828, 830, 832, 834, 836, 838, 840, 842, 844, 846, 848, 850, 852, 854, 856, 858, 860, 862, 864, 866, 868, 870, 872, 874, 876, 878, 880, 882, 884, 886, 888, 890, 892, 894, 896, 898, 900, 902, 904, 906, 908, 910, 912, 914, 916, 918, 920, 922, 924, 926, 928, 930, 932, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958, 960, 962, 964, 966, 968, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990, 992, 994, 996, 998, 1000, 1002, 1004, 1006, 1008, 1010, 1012, 1014, 1016, 1018, 1020, 1022, 1024, 1026, 1028, 1030, 1032, 1034, 1036, 1038, 1040, 1042, 1044, 1046, 1048, 1050, 1052, 1054, 1056, 1058, 1060, 1062, 1064, 1066, 1068, 1070, 1072, 1074, 1076, 1078, 1080, 1082, 1084, 1086, 1088, 1090, 1092, 1094, 1096, 1098, 1100, 1102, 1104, 1106, 1108, 1110, 1112, 1114, 1116, 1118, 1120, 1122, 1124, 1126, 1128, 1130, 1132, 1134, 1136, 1138, 1140, 1142, 1144, 1146, 1148, 1150, 1152, 1154, 1156, 1158, 1160, 1162, 1164, 1166, 1168, 1170, 1172, 1174, 1176, 1178, 1180, 1182, 1184, 1186, 1188, 1190, 1192, 1194, 1196, 1198, 1200, 1202, 1204, 1206, 1208, 1210, 1212, 1214, 1216, 1218, 1220, 1222, 1224, 1226, 1228, 1230, 1232, 1234, 1236, 1238, 1240, 1242, 1244, 1246, 1248, 1250, 1252, 1254, 1256, 1258, 1260, 1262, 1264, 1266, 1268, 1270, 1272, 1274, 1276, 1278, 1280, 1282, 1284, 1286, 1288, 1290, 1292, 1294, 1296, 1298, 1300, 1302, 1304, 1306, 1308, 1310, 1312, 1314, 1316, 1318, 1320, 1322, 1324, 1326, 1328, 1330, 1332, 1334, 1336, 1338, 1340, 1342, 1344, 1346, 1348, 1350, 1352, 1354, 1356, 1358, 1360, 1362, 1364, 1366, 1368, 1370, 1372, 1374, 1376, 1378, 1380, 1382, 1384, 1386, 1388, 1390, 1392, 1394, 1396, 1398, 1400, 1402, 1404, 1406, 1408, 1410, 1412, 1414, 1416, 1418, 1420, 1422, 1424, 1426, 1428, 1430, 1432, 1434, 1436, 1438, 1440, 1442, 1444, 1446, 1448, 1450, 1452, 1454, 1456, 1458, 1460, 1462, 1464, 1466, 1468, 1470, 1472, 1474, 1476, 1478, 1480, 1482, 1484, 1486, 1488, 1490, 1492, 1494, 1496, 1498, 1500, 1502, 1504, 1506, 1508, 1510, 1512, 1514, 1516, 1518, 1520, 1522, 1524, 1526, 1528, 1530, 1532, 1534, 1536, 1538, 1540, 1542, 1544, 1546, 1548, 1550, 1552, 1554, 1556, 1558, 1560, 1562, 1564, 1566, 1568, 1570, 1572, 1574, 1576, 1578, 1580, 1582, 1584, 1586, 1588, 1590, 1592, 1594, 1596, 1598, 1600, 1602], 'edge_vector': [0, 1, 0, 611, 1, 3, 2, 3, 2, 623, 3, 7, 3, 4, 4, 9, 5, 9, 5, 613, 6, 8, 6, 601, 7, 8, 8, 13, 8, 15, 9, 10, 9, 12, 10, 20, 11, 18, 11, 627, 12, 19, 13, 18, 14, 17, 14, 609, 15, 17, 16, 19, 16, 625, 17, 25, 17, 26, 18, 24, 18, 21, 19, 27, 19, 581, 20, 30, 21, 30, 22, 31, 22, 599, 23, 28, 23, 617, 24, 31, 25, 28, 26, 29, 27, 29, 28, 36, 28, 39, 29, 40, 29, 42, 30, 34, 30, 32, 31, 35, 31, 37, 32, 46, 33, 45, 33, 622, 34, 49, 35, 45, 36, 44, 37, 44, 38, 43, 38, 628, 39, 43, 40, 46, 41, 47, 41, 607, 42, 47, 43, 56, 43, 57, 44, 54, 44, 55, 45, 52, 45, 48, 46, 58, 46, 554, 47, 59, 47, 555, 48, 62, 49, 62, 50, 65, 50, 634, 51, 63, 51, 616, 52, 65, 53, 61, 53, 602, 54, 63, 55, 60, 56, 61, 57, 64, 58, 60, 59, 64, 60, 73, 60, 77, 61, 71, 61, 75, 62, 66, 62, 67, 63, 69, 63, 72, 64, 76, 64, 79, 65, 68, 65, 70, 66, 86, 67, 81, 68, 88, 69, 83, 70, 83, 71, 84, 72, 84, 73, 81, 74, 85, 74, 604, 75, 85, 76, 82, 77, 82, 78, 80, 78, 624, 79, 80, 80, 99, 80, 513, 81, 95, 81, 514, 82, 98, 82, 515, 83, 90, 83, 91, 84, 93, 84, 94, 85, 96, 85, 97, 86, 106, 87, 100, 87, 614, 88, 108, 89, 103, 89, 631, 90, 100, 91, 105, 92, 104, 92, 618, 93, 103, 94, 102, 95, 105, 96, 104, 97, 101, 98, 102, 99, 101, 100, 107, 100, 110, 101, 118, 101, 121, 102, 114, 102, 119, 103, 109, 103, 113, 104, 112, 104, 117, 105, 111, 105, 115, 106, 125, 107, 128, 108, 128, 109, 123, 110, 123, 111, 125, 112, 126, 113, 126, 114, 124, 115, 124, 116, 129, 116, 620, 117, 129, 118, 122, 119, 122, 120, 127, 120, 605, 121, 127, 122, 143, 122, 469, 123, 134, 123, 135, 124, 140, 124, 471, 125, 136, 125, 472, 126, 138, 126, 139, 127, 144, 127, 474, 128, 131, 128, 132, 129, 141, 129, 142, 130, 150, 130, 633, 131, 153, 132, 151, 133, 148, 133, 615, 134, 150, 135, 147, 136, 151, 137, 149, 137, 600, 138, 148, 139, 145, 140, 147, 141, 149, 142, 146, 143, 145, 144, 146, 145, 160, 145, 165, 146, 164, 146, 167, 147, 156, 147, 161, 148, 154, 148, 159, 149, 158, 149, 163, 150, 152, 150, 155, 151, 453, 151, 157, 152, 168, 153, 168, 154, 173, 155, 173, 156, 172, 157, 172, 158, 170, 159, 170, 160, 174, 161, 174, 162, 169, 162, 603, 163, 169, 164, 175, 165, 175, 166, 171, 166, 621, 167, 171, 168, 177, 168, 178, 169, 187, 169, 188, 170, 184, 170, 185, 171, 190, 171, 426, 172, 182, 172, 427, 173, 180, 173, 181, 174, 186, 174, 429, 175, 189, 175, 430, 176, 195, 176, 612, 177, 199, 178, 192, 179, 194, 179, 629, 180, 195, 181, 193, 182, 192, 183, 191, 183, 610, 184, 194, 185, 197, 186, 193, 187, 191, 188, 196, 189, 197, 190, 196, 191, 204, 191, 209, 192, 402, 192, 203, 193, 202, 193, 207, 194, 200, 194, 205, 195, 198, 195, 201, 196, 210, 196, 213, 197, 206, 197, 211, 198, 220, 199, 220, 200, 221, 201, 221, 202, 214, 203, 214, 204, 215, 205, 215, 206, 216, 207, 216, 208, 218, 208, 619, 209, 218, 210, 217, 211, 217, 212, 219, 212, 598, 213, 219, 214, 228, 214, 377, 215, 230, 215, 231, 216, 232, 216, 379, 217, 235, 217, 380, 218, 233, 218, 234, 219, 236, 219, 382, 220, 223, 220, 224, 221, 226, 221, 227, 222, 242, 222, 632, 223, 245, 224, 243, 225, 237, 225, 608, 226, 242, 227, 240, 228, 243, 229, 238, 229, 630, 230, 237, 231, 241, 232, 240, 233, 238, 234, 239, 235, 241, 236, 239, 237, 246, 237, 251, 238, 250, 238, 356, 239, 254, 239, 357, 240, 248, 240, 253, 241, 252, 241, 255, 242, 244, 242, 247, 243, 361, 243, 249, 244, 260, 245, 260, 246, 257, 247, 257, 248, 259, 249, 259, 250, 261, 251, 261, 252, 258, 253, 258, 254, 256, 255, 256, 256, 272, 256, 337, 257, 266, 257, 267, 258, 271, 258, 339, 259, 268, 259, 340, 260, 263, 260, 264, 261, 269, 261, 270, 262, 274, 262, 606, 263, 279, 264, 276, 265, 275, 265, 626, 266, 274, 267, 277, 268, 276, 269, 275, 270, 273, 271, 277, 272, 273, 273, 284, 273, 321, 274, 278, 274, 281, 275, 280, 275, 323, 276, 324, 276, 283, 277, 282, 277, 285, 278, 286, 279, 286, 280, 289, 281, 289, 282, 288, 283, 288, 284, 287, 285, 287, 286, 309, 286, 290, 287, 293, 287, 310, 288, 292, 288, 311, 289, 312, 289, 291, 290, 295, 291, 294, 292, 295, 293, 294, 294, 296, 294, 303, 295, 304, 295, 297, 296, 298, 297, 298, 298, 299, 298, 300, 299, 300, 300, 301, 300, 302, 301, 303, 302, 304, 303, 306, 303, 308, 304, 305, 304, 307, 305, 309, 306, 312, 307, 311, 308, 310, 309, 313, 309, 314, 310, 319, 310, 320, 311, 317, 311, 318, 312, 315, 312, 316, 313, 322, 314, 327, 315, 323, 316, 322, 317, 325, 318, 324, 319, 321, 320, 325, 321, 334, 321, 336, 322, 326, 322, 330, 323, 329, 323, 333, 324, 328, 324, 332, 325, 331, 325, 335, 327, 341, 328, 341, 329, 643, 330, 338, 331, 338, 332, 340, 333, 342, 334, 342, 335, 339, 336, 337, 337, 353, 337, 354, 338, 345, 338, 346, 339, 351, 339, 352, 340, 347, 340, 348, 341, 343, 341, 344, 342, 349, 342, 350, 343, 360, 344, 363, 345, 355, 346, 360, 347, 358, 348, 361, 349, 356, 350, 355, 351, 359, 352, 358, 353, 357, 354, 359, 355, 365, 355, 370, 356, 369, 356, 373, 357, 374, 357, 376, 358, 367, 358, 372, 359, 371, 359, 375, 360, 362, 360, 366, 361, 364, 361, 368, 363, 383, 364, 383, 366, 384, 367, 384, 368, 377, 370, 378, 371, 378, 372, 379, 373, 381, 374, 381, 375, 380,
8000
 376, 382, 377, 389, 377, 390, 378, 391, 378, 392, 379, 393, 379, 394, 380, 397, 380, 398, 381, 395, 381, 396, 382, 399, 382, 400, 383, 385, 383, 386, 384, 387, 384, 388, 385, 405, 386, 409, 387, 404, 388, 405, 389, 403, 390, 402, 391, 401, 392, 404, 393, 407, 394, 403, 396, 401, 397, 406, 398, 407, 400, 406, 401, 415, 401, 419, 402, 410, 402, 414, 403, 413, 403, 418, 404, 411, 404, 416, 405, 408, 405, 412, 406, 420, 406, 422, 407, 417, 407, 421, 409, 423, 410, 423, 412, 428, 413, 428, 414, 427, 416, 425, 417, 425, 418, 429, 419, 424, 420, 424, 421, 430, 422, 426, 423, 431, 423, 432, 424, 441, 424, 442, 425, 437, 425, 438, 426, 445, 426, 446, 427, 435, 427, 436, 428, 433, 428, 434, 429, 439, 429, 440, 430, 443, 430, 444, 431, 452, 432, 455, 433, 450, 434, 452, 435, 449, 436, 453, 437, 451, 438, 450, 439, 447, 440, 449, 441, 645, 442, 451, 443, 448, 444, 447, 445, 642, 446, 448, 447, 463, 447, 467, 448, 466, 448, 468, 449, 459, 449, 464, 450, 457, 450, 462, 451, 461, 451, 465, 452, 454, 452, 458, 453, 456, 453, 460, 454, 638, 455, 475, 456, 475, 458, 470, 459, 470, 460, 472, 462, 473, 463, 473, 464, 471, 465, 476, 466, 476, 467, 469, 468, 474, 469, 489, 469, 490, 470, 480, 470, 481, 471, 485, 471, 486, 472, 482, 472, 477, 473, 483, 473, 484, 474, 491, 474, 492, 475, 478, 475, 479, 476, 487, 476, 488, 477, 499, 478, 493, 479, 501, 480, 496, 481, 493, 482, 498, 483, 497, 484, 496, 485, 495, 486, 498, 488, 497, 489, 494, 490, 495, 492, 494, 493, 500, 493, 503, 494, 510, 494, 512, 495, 507, 495, 511, 496, 502, 496, 506, 497, 505, 497, 509, 498, 504, 498, 508, 499, 519, 501, 521, 503, 516, 504, 516, 506, 517, 507, 517, 508, 514, 509, 518, 510, 518, 511, 515, 512, 513, 513, 531, 513, 532, 514, 526, 514, 520, 515, 529, 515, 530, 516, 522, 516, 523, 517, 524, 517, 525, 518, 527, 518, 528, 519, 535, 520, 535, 521, 538, 522, 536, 523, 538, 524, 534, 525, 536, 526, 533, 527, 639, 528, 534, 529, 537, 530, 533, 531, 644, 532, 537, 533, 546, 533, 549, 534, 544, 534, 547, 535, 539, 535, 540, 536, 542, 536, 545, 537, 548, 537, 550, 538, 541, 538, 543, 539, 553, 540, 558, 542, 636, 543, 553, 544, 640, 545, 552, 546, 552, 547, 551, 548, 551, 549, 554, 550, 555, 551, 562, 551, 563, 552, 560, 552, 561, 553, 559, 553, 557, 554, 564, 554, 556, 555, 565, 555, 566, 556, 569, 558, 569, 559, 570, 560, 567, 561, 570, 563, 567, 564, 568, 566, 568, 567, 574, 567, 576, 568, 577, 568, 578, 569, 572, 569, 571, 570, 573, 570, 575, 571, 582, 572, 580, 575, 580, 576, 579, 577, 579, 578, 581, 579, 586, 579, 587, 580, 585, 580, 583, 581, 588, 581, 584, 582, 590, 584, 590, 585, 589, 587, 589, 588, 641, 589, 593, 589, 594, 590, 591, 590, 592, 591, 595, 593, 635, 594, 595, 595, 597, 595, 596, 597, 637], 'k': 2, 'edge_weights': [], 'node_weights': (2000, 2000, 2000, 4000, 2000, 2000, 2000, 2000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 4000, 4000, 2000, 2000, 4000, 2000, 4000, 2000, 2000, 4000, 4000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 1000, 2000, 2000, 1000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 1000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 1000, 2000, 2000, 1000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 1000, 2000, 2000, 2000, 1000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 1000, 2000, 1000, 2000, 2000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 4000, 2000, 2000, 1000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 4000, 4000, 2000, 1000, 2000, 2000, 2000, 2000, 1000, 2000, 2000, 1000, 2000, 4000, 4000, 4000, 4000, 2000, 2000, 1000, 1000, 2000, 2000, 2000, 2000, 4000, 4000, 4000, 2000, 1000, 2000, 2000, 1000, 2000, 2000, 4000, 4000, 2000, 1000, 2000, 2000, 4000, 1000, 2000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000)

@larsgottesbueren larsgottesbueren mentioned this issue May 7, 2024
Open
@larsgottesbueren
Copy link
Member

Hi,

I fixed the out-of-bounds operator[] (PR is linked). Can you try running it again? As the memory backing the out-of-bounds access was actually there, just the size was wrong, I suspect that the second assertion failure can still pop up:
[2way_fm_refiner.h:200:refineImpl]: Assertion `best_metrics.cut == metrics::hyperedgeCut(_hg)` failed: best_metrics.cut = 15 metrics::hyperedgeCut(_hg) = 13

In my test, it doesn't, but I also had to test through the binary :)
Can you share what epsilon you're using, and the specific call to kahypar from python.

@twesterhout
Copy link
Author

Hello @larsgottesbueren, thanks for the quick fix! I tried your PR, and like you suspected, the original assertion failure is replaced with various failures of the form:

[2way_fm_refiner.h:200:refineImpl]: Assertion `best_metrics.cut == metrics::hyperedgeCut(_hg)` failed: best_metrics.cut = 16287 metrics::hyperedgeCut(_hg) = 14254

I'll try to create a complete reproducer for you. I'm using Cotengra to optimize some tensor network contractions, and it's calling KaHyPar many times with different hyperparameters, so it's not always trivial to trace back the exact parameters used.

@twesterhout
Copy link
Author

@larsgottesbueren could you give this a try: https://gist.github.com/twesterhout/cab4dda947aa7aad21968ac184e44379 ? Does it fail on your side too?

@twesterhout
Copy link
Author

Any updates on this? I'd be happy to do testing of any work-in-progress PRs.

@larsgottesbueren
Copy link
Member

Sorry for the delay. Please give #201 another try :)

@twesterhout
Copy link
Author

Hm... still failing, but with yet another error:

(deploy pid=3247124) part = 0 _hg.partWeight(part) = 0 _pq.isEnabled(part) = 0 _pq.size(part) = 1 _context.initial_partitioning.upper_allowed_partition_weight[part] = 1
(deploy pid=3247124) [greedy_hypergraph_growing_initial_partitioner.h:209:initialPartition]: Assertion `[&]() { bool exist_unassigned_node = Base::getUnassignedNode() != kInvalidNode; for (PartitionID part = 0; part < _context.initial_partitioning.k; ++part) { if (!_pq.isEnabled(part) && part != _context.initial_partitioning.unassigned_part) { if ((exist_unassigned_node && _pq.size(part) > 0) && _hg.partWeight(part) + Base::getMaxHypernodeWeight() <= _context.initial_partitioning.upper_allowed_partition_weight[part]) { !(true) ? (void)0 : kahypar::LoggerVoidify() & kahypar::Logger(true) << "part" << "=" << part << "_hg.partWeight(part)" << "=" << _hg.partWeight(part) << "_pq.isEnabled(part)" << "=" << _pq.isEnabled(part) << "_pq.size(part)" << "=" << _pq.size(part) << "_context.initial_partitioning.upper_allowed_partition_weight[part]" << "=" << _context.initial_partitioning.upper_allowed_partition_weight[part]; return false; } } } return true; } ()` failed: There is a PQ, which is disabled, but the hypernode with  maximum weight can be placed inside this part!

Do you happen to have an idea what the error is related to?

@larsgottesbueren
Copy link
Member

Can you please share the instance where this assertion fails.

@twesterhout
Copy link
Author

Sure thing @larsgottesbueren! I've updated the gist: https://gist.github.com/twesterhout/cab4dda947aa7aad21968ac184e44379#file-other_assert-py (other_assert.py should trigger the assertion)

@larsgottesbueren
Copy link
Member

This is in the initial partitioning code. After some quick debugging it seems that the max part weights aren't set up correctly. @kittobi1992 Can you take a look at this one? You'll know this code best.

@SebastianSchlag
Copy link
Member

@kittobi1992 / @TobiasHeuer Do you have an idea what could go wrong here?

@twesterhout
Copy link
Author

@kittobi1992 @TobiasHeuer @SebastianSchlag do you happen to have any new insights into the failures?

@SebastianSchlag
Copy link
Member

@larsgottesbueren Since we don't see these failures in the current master branch, could it be that something is off with #201?

@larsgottesbueren
Copy link
Member

For me, these failures appear on master.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@SebastianSchlag @twesterhout @larsgottesbueren
0