Metis gives segmentation fault when dealing with large number partitions
shuaiwangvu opened this issue · 6 comments
Dear developers,
I noticed that when I would like to divide a graph into several partitions, there can be segmentation fault. I don't really know where the problem comes from. For example, it gives me an error when I try to cut the following graph into 8 partitions:
adj= {0: [85, 287], 1: [2], 2: [208, 215, 233, 275, 3, 89, 214, 300, 272, 241], 3: [4, 5], 4: [217], 5: [249, 100, 127, 287], 6: [285, 7, 287, 8], 7: [47], 8: [211, 11], 9: [297, 78, 223], 10: [285, 244, 114], 11: [79, 44, 287, 272], 12: [13, 14], 13: [14], 14: [4, 287, 29], 15: [16], 16: [261, 29, 30], 17: [297, 97, 41, 0], 18: [223], 19: [11], 20: [21, 14], 21: [227, 168, 256, 169, 30, 87], 22: [23, 24], 23: [214], 24: [300], 25: [110], 26: [72], 27: [192, 72], 28: [272], 29: [287], 30: [39, 92, 196, 245, 185, 223], 31: [258, 49, 256], 32: [247, 276, 33, 34, 35, 237, 272], 33: [267, 221], 34: [32, 74], 35: [162, 214, 287], 36: [37], 37: [208, 124, 77, 211, 128, 261, 121, 161, 112], 38: [229, 117, 251], 39: [4, 40, 264, 41, 42], 40: [104, 287], 41: [84, 85], 42: [243], 43: [44], 44: [198, 205, 105, 202, 251], 45: [211, 46, 47, 240, 26, 27], 46: [95], 47: [247, 229, 256, 178], 48: [203, 0], 49: [69, 126, 130], 50: [236, 253], 51: [257, 23], 52: [296, 78, 287], 53: [270, 255, 54, 2], 54: [107, 296, 184, 66], 55: [56, 57, 256, 263], 56: [15, 287], 57: [167, 243], 58: [246, 297, 35, 59, 256, 52, 272], 59: [64], 60: [68], 61: [75], 62: [63], 63: [258, 262, 135], 64: [68, 37, 256, 204], 65: [225], 66: [274, 202, 287], 67: [16], 68: [208, 292, 249, 34, 128, 35, 129, 272, 130], 69: [234, 70, 211, 23, 35, 214, 71, 272, 72, 73], 70: [63, 109], 71: [281, 160], 72: [61, 136, 214], 73: [294, 86, 91, 195], 74: [23, 232], 75: [208], 76: [258, 77], 77: [83], 78: [85, 116], 79: [80], 80: [0], 81: [224, 55], 82: [43, 287, 83], 83: [256], 84: [290, 299], 85: [287], 86: [297], 87: [69, 95, 211, 101, 90], 88: [1], 89: [254, 90], 90: [280, 156], 91: [294, 256], 92: [58], 93: [51, 211, 94], 94: [134], 95: [23, 96], 96: [68], 97: [32, 84, 17], 98: [99], 99: [247, 202, 211, 184], 100: [247], 101: [211, 259, 153], 102: [93], 103: [211], 104: [224], 105: [237], 106: [256, 190], 107: [266], 108: [95, 87], 109: [271], 110: [258, 259, 23], 111: [32, 276], 112: [132, 142, 101, 256, 221, 11, 272], 113: [48, 114], 114: [285, 244, 88, 202, 222, 139, 181, 11], 115: [116], 116: [293, 287], 117: [158], 118: [256], 119: [120, 121], 120: [226, 4, 157, 170, 287, 0], 121: [244, 98, 231, 300, 237], 122: [213, 36, 25], 123: [244], 124: [200], 125: [247, 238, 197, 221], 126: [115, 255, 240], 127: [58], 128: [259], 129: [68, 63], 130: [289, 75, 38, 171, 221], 131: [255], 132: [211, 212, 148], 133: [211], 134: [208], 135: [28], 136: [242], 137: [262], 138: [21, 220], 139: [48, 287], 140: [166, 149], 141: [225], 142: [93], 143: [176, 204], 144: [289, 262, 145], 145: [247, 214, 83], 146: [69, 258], 147: [207], 148: [22], 149: [287], 150: [133], 151: [58], 152: [244, 21, 120], 153: [37, 87], 154: [155], 155: [0], 156: [211], 157: [45, 150, 158], 158: [58, 256, 185], 159: [282], 160: [72], 161: [238, 158], 162: [32], 163: [2], 164: [199], 165: [1, 222], 166: [294], 167: [39, 44], 168: [12, 17], 169: [120], 170: [293], 171: [116], 172: [218], 173: [194, 174], 174: [247], 175: [69], 176: [231], 177: [223], 178: [99], 179: [183], 180: [181], 181: [211], 182: [3, 255, 154, 2], 183: [20, 53, 173, 256], 184: [55, 33], 185: [246, 211], 186: [32, 296, 147], 187: [72], 188: [244, 64, 223], 189: [38, 119, 122, 253], 190: [257], 191: [287], 192: [262], 193: [274], 194: [20], 195: [186, 237], 196: [260, 273, 11], 197: [225, 237], 198: [196, 197], 199: [256], 200: [201, 202, 203], 201: [238, 239, 240], 202: [139, 287, 120, 264, 140, 141], 203: [202, 56], 204: [49], 205: [206], 206: [32], 207: [297], 208: [209], 209: [266, 258, 255, 211, 28, 2], 210: [211, 212], 211: [238, 199], 212: [208], 213: [214], 214: [211, 175, 230, 272, 240], 215: [216, 217], 216: [1], 217: [14], 218: [17, 18, 256], 219: [220], 220: [34, 280, 155, 29, 223, 272], 221: [250, 19, 81, 163, 174, 256, 287, 272], 222: [76, 211, 287, 121, 225, 11, 0], 223: [219, 244, 23, 74], 224: [225], 225: [276, 202, 165, 256, 251, 191], 226: [227], 227: [29], 228: [229, 230], 229: [228, 256, 287], 230: [214], 231: [208, 210, 23, 64, 287, 159, 160, 72, 156], 232: [214, 74], 233: [234, 235], 234: [276, 249, 61, 62, 63, 37, 64, 65, 272, 2, 66], 235: [225], 236: [237], 237: [247, 146, 222, 182, 99, 112, 87, 0, 193, 284], 238: [224, 254, 118, 287, 239], 239: [125, 139, 161], 240: [211, 111, 214, 126], 241: [272], 242: [208], 243: [182], 244: [246, 6, 218, 9, 5, 10, 256, 287, 11], 245: [228, 222, 256], 246: [247, 248, 249, 220], 247: [211, 287, 288], 248: [244], 249: [6, 58, 60, 2], 250: [251, 225], 251: [164, 21, 110, 182, 120, 161, 114], 252: [253], 253: [32, 125, 256], 254: [255, 256, 197], 255: [202, 211, 256, 287, 272, 8], 256: [244, 238, 144, 229, 178, 179], 257: [258, 259, 256, 239], 258: [22, 93, 211, 102, 37, 103, 87], 259: [211, 143], 260: [261, 262, 225], 261: [113, 116, 237], 262: [211, 102, 54, 188, 223, 235], 263: [276, 82, 152, 180, 186], 264: [285, 248, 276, 253, 189, 112, 272], 265: [208, 210], 266: [237], 267: [268, 269], 268: [116, 272], 269: [297, 18, 220], 270: [261], 271: [272], 272: [58, 67, 68, 131, 23, 222, 256, 287, 26, 27], 273: [225], 274: [252, 218, 299, 221, 106], 275: [276], 276: [50, 51, 211, 52], 277: [23, 160], 278: [279, 280, 265, 225], 279: [63, 46], 280: [244, 211, 111, 203, 103], 281: [282, 283, 284], 282: [208], 283: [222], 284: [23], 285: [247, 244, 286], 286: [209], 287: [6, 245, 238, 123, 51, 151, 35, 277, 222, 31, 140, 225, 237, 11], 288: [5], 289: [211], 290: [289, 291], 291: [55, 211], 292: [213], 293: [63, 287], 294: [295, 296], 295: [112], 296: [137, 203, 114, 138], 297: [298, 256, 299, 300, 0], 298: [172], 299: [150, 256, 264], 300: [278, 297, 3, 244, 32, 45, 108, 170, 177, 262, 187]}
It gives me Segmentation fault: 11
Thank you and looking forward to your reply.
Regards,
Shuai
Could you provide a full example script? (Please use triple backquotes to enclose source code.)
like this
import pymetis
num_partitions = 5
adj= {0: [85, 287], 1: [2], 2: [208, 215, 233, 275, 3, 89, 214, 300, 272, 241], 3: [4, 5], 4: [217], 5: [249, 100, 127, 287], 6: [285, 7, 287, 8], 7: [47], 8: [211, 11], 9: [297, 78, 223], 10: [285, 244, 114], 11: [79, 44, 287, 272], 12: [13, 14], 13: [14], 14: [4, 287, 29], 15: [16], 16: [261, 29, 30], 17: [297, 97, 41, 0], 18: [223], 19: [11], 20: [21, 14], 21: [227, 168, 256, 169, 30, 87], 22: [23, 24], 23: [214], 24: [300], 25: [110], 26: [72], 27: [192, 72], 28: [272], 29: [287], 30: [39, 92, 196, 245, 185, 223], 31: [258, 49, 256], 32: [247, 276, 33, 34, 35, 237, 272], 33: [267, 221], 34: [32, 74], 35: [162, 214, 287], 36: [37], 37: [208, 124, 77, 211, 128, 261, 121, 161, 112], 38: [229, 117, 251], 39: [4, 40, 264, 41, 42], 40: [104, 287], 41: [84, 85], 42: [243], 43: [44], 44: [198, 205, 105, 202, 251], 45: [211, 46, 47, 240, 26, 27], 46: [95], 47: [247, 229, 256, 178], 48: [203, 0], 49: [69, 126, 130], 50: [236, 253], 51: [257, 23], 52: [296, 78, 287], 53: [270, 255, 54, 2], 54: [107, 296, 184, 66], 55: [56, 57, 256, 263], 56: [15, 287], 57: [167, 243], 58: [246, 297, 35, 59, 256, 52, 272], 59: [64], 60: [68], 61: [75], 62: [63], 63: [258, 262, 135], 64: [68, 37, 256, 204], 65: [225], 66: [274, 202, 287], 67: [16], 68: [208, 292, 249, 34, 128, 35, 129, 272, 130], 69: [234, 70, 211, 23, 35, 214, 71, 272, 72, 73], 70: [63, 109], 71: [281, 160], 72: [61, 136, 214], 73: [294, 86, 91, 195], 74: [23, 232], 75: [208], 76: [258, 77], 77: [83], 78: [85, 116], 79: [80], 80: [0], 81: [224, 55], 82: [43, 287, 83], 83: [256], 84: [290, 299], 85: [287], 86: [297], 87: [69, 95, 211, 101, 90], 88: [1], 89: [254, 90], 90: [280, 156], 91: [294, 256], 92: [58], 93: [51, 211, 94], 94: [134], 95: [23, 96], 96: [68], 97: [32, 84, 17], 98: [99], 99: [247, 202, 211, 184], 100: [247], 101: [211, 259, 153], 102: [93], 103: [211], 104: [224], 105: [237], 106: [256, 190], 107: [266], 108: [95, 87], 109: [271], 110: [258, 259, 23], 111: [32, 276], 112: [132, 142, 101, 256, 221, 11, 272], 113: [48, 114], 114: [285, 244, 88, 202, 222, 139, 181, 11], 115: [116], 116: [293, 287], 117: [158], 118: [256], 119: [120, 121], 120: [226, 4, 157, 170, 287, 0], 121: [244, 98, 231, 300, 237], 122: [213, 36, 25], 123: [244], 124: [200], 125: [247, 238, 197, 221], 126: [115, 255, 240], 127: [58], 128: [259], 129: [68, 63], 130: [289, 75, 38, 171, 221], 131: [255], 132: [211, 212, 148], 133: [211], 134: [208], 135: [28], 136: [242], 137: [262], 138: [21, 220], 139: [48, 287], 140: [166, 149], 141: [225], 142: [93], 143: [176, 204], 144: [289, 262, 145], 145: [247, 214, 83], 146: [69, 258], 147: [207], 148: [22], 149: [287], 150: [133], 151: [58], 152: [244, 21, 120], 153: [37, 87], 154: [155], 155: [0], 156: [211], 157: [45, 150, 158], 158: [58, 256, 185], 159: [282], 160: [72], 161: [238, 158], 162: [32], 163: [2], 164: [199], 165: [1, 222], 166: [294], 167: [39, 44], 168: [12, 17], 169: [120], 170: [293], 171: [116], 172: [218], 173: [194, 174], 174: [247], 175: [69], 176: [231], 177: [223], 178: [99], 179: [183], 180: [181], 181: [211], 182: [3, 255, 154, 2], 183: [20, 53, 173, 256], 184: [55, 33], 185: [246, 211], 186: [32, 296, 147], 187: [72], 188: [244, 64, 223], 189: [38, 119, 122, 253], 190: [257], 191: [287], 192: [262], 193: [274], 194: [20], 195: [186, 237], 196: [260, 273, 11], 197: [225, 237], 198: [196, 197], 199: [256], 200: [201, 202, 203], 201: [238, 239, 240], 202: [139, 287, 120, 264, 140, 141], 203: [202, 56], 204: [49], 205: [206], 206: [32], 207: [297], 208: [209], 209: [266, 258, 255, 211, 28, 2], 210: [211, 212], 211: [238, 199], 212: [208], 213: [214], 214: [211, 175, 230, 272, 240], 215: [216, 217], 216: [1], 217: [14], 218: [17, 18, 256], 219: [220], 220: [34, 280, 155, 29, 223, 272], 221: [250, 19, 81, 163, 174, 256, 287, 272], 222: [76, 211, 287, 121, 225, 11, 0], 223: [219, 244, 23, 74], 224: [225], 225: [276, 202, 165, 256, 251, 191], 226: [227], 227: [29], 228: [229, 230], 229: [228, 256, 287], 230: [214], 231: [208, 210, 23, 64, 287, 159, 160, 72, 156], 232: [214, 74], 233: [234, 235], 234: [276, 249, 61, 62, 63, 37, 64, 65, 272, 2, 66], 235: [225], 236: [237], 237: [247, 146, 222, 182, 99, 112, 87, 0, 193, 284], 238: [224, 254, 118, 287, 239], 239: [125, 139, 161], 240: [211, 111, 214, 126], 241: [272], 242: [208], 243: [182], 244: [246, 6, 218, 9, 5, 10, 256, 287, 11], 245: [228, 222, 256], 246: [247, 248, 249, 220], 247: [211, 287, 288], 248: [244], 249: [6, 58, 60, 2], 250: [251, 225], 251: [164, 21, 110, 182, 120, 161, 114], 252: [253], 253: [32, 125, 256], 254: [255, 256, 197], 255: [202, 211, 256, 287, 272, 8], 256: [244, 238, 144, 229, 178, 179], 257: [258, 259, 256, 239], 258: [22, 93, 211, 102, 37, 103, 87], 259: [211, 143], 260: [261, 262, 225], 261: [113, 116, 237], 262: [211, 102, 54, 188, 223, 235], 263: [276, 82, 152, 180, 186], 264: [285, 248, 276, 253, 189, 112, 272], 265: [208, 210], 266: [237], 267: [268, 269], 268: [116, 272], 269: [297, 18, 220], 270: [261], 271: [272], 272: [58, 67, 68, 131, 23, 222, 256, 287, 26, 27], 273: [225], 274: [252, 218, 299, 221, 106], 275: [276], 276: [50, 51, 211, 52], 277: [23, 160], 278: [279, 280, 265, 225], 279: [63, 46], 280: [244, 211, 111, 203, 103], 281: [282, 283, 284], 282: [208], 283: [222], 284: [23], 285: [247, 244, 286], 286: [209], 287: [6, 245, 238, 123, 51, 151, 35, 277, 222, 31, 140, 225, 237, 11], 288: [5], 289: [211], 290: [289, 291], 291: [55, 211], 292: [213], 293: [63, 287], 294: [295, 296], 295: [112], 296: [137, 203, 114, 138], 297: [298, 256, 299, 300, 0], 298: [172], 299: [150, 256, 264], 300: [278, 297, 3, 244, 32, 45, 108, 170, 177, 262, 187]}
cuts, part_vert = pymetis.part_graph(num_partitions, adjacency=adj)
print (len(part_vert))
it gives me an error :
Segmentation fault: 11
I can reproduce the bug. The backtrace suggests that it's an issue within metis's graph coarsening algorithm. I'd be curious to see whether you can reproduce the problem by just running the metis binary. If so, that would mean the bug is unrelated to the wrapper.
sorry. I'm not familiar with metis. That's why I posted here to ask. Could you please help?
Thanks a lot.
import pymetis num_partitions = 5 adj= {0: [85, 287], 1: [2], 2: [208, 215, 233, 275, 3, 89, 214, 300, 272, 241], 3: [4, 5], 4: [217], 5: [249, 100, 127, 287], 6: [285, 7, 287, 8], 7: [47], 8: [211, 11], 9: [297, 78, 223], 10: [285, 244, 114], 11: [79, 44, 287, 272], 12: [13, 14], 13: [14], 14: [4, 287, 29], 15: [16], 16: [261, 29, 30], 17: [297, 97, 41, 0], 18: [223], 19: [11], 20: [21, 14], 21: [227, 168, 256, 169, 30, 87], 22: [23, 24], 23: [214], 24: [300], 25: [110], 26: [72], 27: [192, 72], 28: [272], 29: [287], 30: [39, 92, 196, 245, 185, 223], 31: [258, 49, 256], 32: [247, 276, 33, 34, 35, 237, 272], 33: [267, 221], 34: [32, 74], 35: [162, 214, 287], 36: [37], 37: [208, 124, 77, 211, 128, 261, 121, 161, 112], 38: [229, 117, 251], 39: [4, 40, 264, 41, 42], 40: [104, 287], 41: [84, 85], 42: [243], 43: [44], 44: [198, 205, 105, 202, 251], 45: [211, 46, 47, 240, 26, 27], 46: [95], 47: [247, 229, 256, 178], 48: [203, 0], 49: [69, 126, 130], 50: [236, 253], 51: [257, 23], 52: [296, 78, 287], 53: [270, 255, 54, 2], 54: [107, 296, 184, 66], 55: [56, 57, 256, 263], 56: [15, 287], 57: [167, 243], 58: [246, 297, 35, 59, 256, 52, 272], 59: [64], 60: [68], 61: [75], 62: [63], 63: [258, 262, 135], 64: [68, 37, 256, 204], 65: [225], 66: [274, 202, 287], 67: [16], 68: [208, 292, 249, 34, 128, 35, 129, 272, 130], 69: [234, 70, 211, 23, 35, 214, 71, 272, 72, 73], 70: [63, 109], 71: [281, 160], 72: [61, 136, 214], 73: [294, 86, 91, 195], 74: [23, 232], 75: [208], 76: [258, 77], 77: [83], 78: [85, 116], 79: [80], 80: [0], 81: [224, 55], 82: [43, 287, 83], 83: [256], 84: [290, 299], 85: [287], 86: [297], 87: [69, 95, 211, 101, 90], 88: [1], 89: [254, 90], 90: [280, 156], 91: [294, 256], 92: [58], 93: [51, 211, 94], 94: [134], 95: [23, 96], 96: [68], 97: [32, 84, 17], 98: [99], 99: [247, 202, 211, 184], 100: [247], 101: [211, 259, 153], 102: [93], 103: [211], 104: [224], 105: [237], 106: [256, 190], 107: [266], 108: [95, 87], 109: [271], 110: [258, 259, 23], 111: [32, 276], 112: [132, 142, 101, 256, 221, 11, 272], 113: [48, 114], 114: [285, 244, 88, 202, 222, 139, 181, 11], 115: [116], 116: [293, 287], 117: [158], 118: [256], 119: [120, 121], 120: [226, 4, 157, 170, 287, 0], 121: [244, 98, 231, 300, 237], 122: [213, 36, 25], 123: [244], 124: [200], 125: [247, 238, 197, 221], 126: [115, 255, 240], 127: [58], 128: [259], 129: [68, 63], 130: [289, 75, 38, 171, 221], 131: [255], 132: [211, 212, 148], 133: [211], 134: [208], 135: [28], 136: [242], 137: [262], 138: [21, 220], 139: [48, 287], 140: [166, 149], 141: [225], 142: [93], 143: [176, 204], 144: [289, 262, 145], 145: [247, 214, 83], 146: [69, 258], 147: [207], 148: [22], 149: [287], 150: [133], 151: [58], 152: [244, 21, 120], 153: [37, 87], 154: [155], 155: [0], 156: [211], 157: [45, 150, 158], 158: [58, 256, 185], 159: [282], 160: [72], 161: [238, 158], 162: [32], 163: [2], 164: [199], 165: [1, 222], 166: [294], 167: [39, 44], 168: [12, 17], 169: [120], 170: [293], 171: [116], 172: [218], 173: [194, 174], 174: [247], 175: [69], 176: [231], 177: [223], 178: [99], 179: [183], 180: [181], 181: [211], 182: [3, 255, 154, 2], 183: [20, 53, 173, 256], 184: [55, 33], 185: [246, 211], 186: [32, 296, 147], 187: [72], 188: [244, 64, 223], 189: [38, 119, 122, 253], 190: [257], 191: [287], 192: [262], 193: [274], 194: [20], 195: [186, 237], 196: [260, 273, 11], 197: [225, 237], 198: [196, 197], 199: [256], 200: [201, 202, 203], 201: [238, 239, 240], 202: [139, 287, 120, 264, 140, 141], 203: [202, 56], 204: [49], 205: [206], 206: [32], 207: [297], 208: [209], 209: [266, 258, 255, 211, 28, 2], 210: [211, 212], 211: [238, 199], 212: [208], 213: [214], 214: [211, 175, 230, 272, 240], 215: [216, 217], 216: [1], 217: [14], 218: [17, 18, 256], 219: [220], 220: [34, 280, 155, 29, 223, 272], 221: [250, 19, 81, 163, 174, 256, 287, 272], 222: [76, 211, 287, 121, 225, 11, 0], 223: [219, 244, 23, 74], 224: [225], 225: [276, 202, 165, 256, 251, 191], 226: [227], 227: [29], 228: [229, 230], 229: [228, 256, 287], 230: [214], 231: [208, 210, 23, 64, 287, 159, 160, 72, 156], 232: [214, 74], 233: [234, 235], 234: [276, 249, 61, 62, 63, 37, 64, 65, 272, 2, 66], 235: [225], 236: [237], 237: [247, 146, 222, 182, 99, 112, 87, 0, 193, 284], 238: [224, 254, 118, 287, 239], 239: [125, 139, 161], 240: [211, 111, 214, 126], 241: [272], 242: [208], 243: [182], 244: [246, 6, 218, 9, 5, 10, 256, 287, 11], 245: [228, 222, 256], 246: [247, 248, 249, 220], 247: [211, 287, 288], 248: [244], 249: [6, 58, 60, 2], 250: [251, 225], 251: [164, 21, 110, 182, 120, 161, 114], 252: [253], 253: [32, 125, 256], 254: [255, 256, 197], 255: [202, 211, 256, 287, 272, 8], 256: [244, 238, 144, 229, 178, 179], 257: [258, 259, 256, 239], 258: [22, 93, 211, 102, 37, 103, 87], 259: [211, 143], 260: [261, 262, 225], 261: [113, 116, 237], 262: [211, 102, 54, 188, 223, 235], 263: [276, 82, 152, 180, 186], 264: [285, 248, 276, 253, 189, 112, 272], 265: [208, 210], 266: [237], 267: [268, 269], 268: [116, 272], 269: [297, 18, 220], 270: [261], 271: [272], 272: [58, 67, 68, 131, 23, 222, 256, 287, 26, 27], 273: [225], 274: [252, 218, 299, 221, 106], 275: [276], 276: [50, 51, 211, 52], 277: [23, 160], 278: [279, 280, 265, 225], 279: [63, 46], 280: [244, 211, 111, 203, 103], 281: [282, 283, 284], 282: [208], 283: [222], 284: [23], 285: [247, 244, 286], 286: [209], 287: [6, 245, 238, 123, 51, 151, 35, 277, 222, 31, 140, 225, 237, 11], 288: [5], 289: [211], 290: [289, 291], 291: [55, 211], 292: [213], 293: [63, 287], 294: [295, 296], 295: [112], 296: [137, 203, 114, 138], 297: [298, 256, 299, 300, 0], 298: [172], 299: [150, 256, 264], 300: [278, 297, 3, 244, 32, 45, 108, 170, 177, 262, 187]} cuts, part_vert = pymetis.part_graph(num_partitions, adjacency=adj) print (len(part_vert))
your adj is not a correct adjacency matrix, so you get a error!