-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathoptimal_bricks3.py
169 lines (127 loc) · 38.7 KB
/
optimal_bricks3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
import string
from collections import defaultdict
import gurobipy as gp
from gurobipy import GRB
import pickle
import os
o_file = "/Users/duch/Documents/Github/phd/optimization/match_edges.pkl"
o_file = os.path.abspath(o_file)
# vertices_rows = 60
# vertices_columns = 60
def ordered_pair(v1, v2):
return (v1, v2) if v1 < v2 else (v2, v1)
adj_lists = {0: [1, 802], 1: [2, 3, 0, 801], 2: [1, 779, 710, 20], 3: [747, 802, 1, 20], 4: [17, 746], 5: [6, 135, 806, 804], 6: [134, 5, 791, 13], 7: [756, 270, 271, 21], 8: [9, 737, 805], 9: [10, 599, 8, 803], 10: [11, 600, 9, 786], 11: [120, 562, 10, 787], 12: [257, 678, 82], 13: [139, 137, 6, 713], 14: [536, 139, 713, 598], 15: [726, 745, 16], 16: [62, 633, 15, 725], 17: [290, 634, 4, 728], 18: [301, 290, 728, 499], 19: [62, 725, 574, 65], 20: [516, 732, 3, 2], 21: [7, 494], 22: [672], 23: [485, 672], 24: [817, 742, 25], 25: [483, 722, 24, 721], 26: [28, 31, 457, 27], 27: [26, 458, 160, 29], 28: [26, 29, 524, 403], 29: [43, 30, 28, 27], 30: [29, 455, 525, 524], 31: [403, 402, 572, 26], 32: [35, 34, 414, 33], 33: [32, 416, 447, 448], 34: [36, 32, 531, 66], 35: [548, 531, 32, 448], 36: [34, 67, 68, 414], 37: [224, 40, 39, 474], 38: [40, 233, 231, 39], 39: [38, 439, 534, 37], 40: [38, 37, 41, 389], 41: [224, 260, 387, 40], 42: [45, 44, 43, 161], 43: [160, 42, 455, 29], 44: [42, 492, 493, 455], 45: [42, 250, 253, 492], 46: [48, 51, 520, 47], 47: [177, 178, 46, 333], 48: [178, 258, 49, 46], 49: [51, 48, 681], 50: [51, 411, 413, 520], 51: [46, 49, 412, 50], 52: [55, 53, 562, 405], 53: [266, 600, 52, 54], 54: [265, 53, 55, 625], 55: [52, 406, 621, 54], 56: [142, 478, 57, 144], 57: [56, 59, 58, 60], 58: [530, 769, 247, 57], 59: [57, 478, 186, 530], 60: [57, 247, 365, 144], 61: [62, 65, 385, 64], 62: [19, 61, 63, 16], 63: [64, 289, 633, 62], 64: [61, 498, 499, 63], 65: [61, 19, 575, 386], 66: [69, 67, 34, 163], 67: [267, 268, 36, 66], 68: [415, 36, 268, 487], 69: [391, 267, 66, 70], 70: [163, 517, 392, 69], 71: [76, 74, 72, 75], 72: [228, 71, 73, 466], 73: [74, 89, 93, 72], 74: [585, 73, 71, 586], 75: [71, 228, 109, 112], 76: [586, 71, 112, 469], 77: [79, 81, 571, 78], 78: [445, 80, 77, 570], 79: [77, 80, 392, 517], 80: [444, 393, 79, 78], 81: [433, 77, 517, 166], 82: [84, 83, 560, 12], 83: [87, 82, 85, 86], 84: [171, 85, 82, 678], 85: [311, 83, 84, 170], 86: [83, 311, 427, 419], 87: [560, 83, 419, 417], 88: [91, 92, 93, 89], 89: [585, 90, 88, 73], 90: [527, 91, 89, 532], 91: [88, 90, 526, 529], 92: [94, 88, 529, 296], 93: [94, 466, 73, 88], 94: [488, 93, 92, 322], 95: [685, 97, 369, 368], 96: [202, 369, 97, 207], 97: [95, 684, 533, 96], 98: [99, 101, 100, 338], 99: [584, 459, 98, 340], 100: [567, 370, 465, 98], 101: [98, 459, 567], 102: [106, 104, 103, 107], 103: [332, 102, 330, 331], 104: [609, 330, 102, 401], 105: [133, 106, 107, 619], 106: [105, 132, 401, 102], 107: [102, 332, 569, 105], 108: [795, 823, 279, 357], 109: [111, 75, 113, 579], 110: [253, 111, 579, 580], 111: [110, 251, 112, 109], 112: [111, 252, 76, 75], 113: [228, 225, 226, 109], 114: [117, 115, 544, 502], 115: [150, 116, 114, 230], 116: [288, 544, 115, 155], 117: [230, 114, 501, 385], 118: [120, 787, 121, 378], 119: [325, 120, 378, 328], 120: [119, 327, 11, 118], 121: [379, 118, 670, 441], 122: [123, 124, 125, 347], 123: [348, 482, 397, 122], 124: [394, 288, 122, 397], 125: [298, 122, 288, 155], 126: [127, 130, 129, 443], 127: [126, 287, 286, 128], 128: [127, 616, 167, 130], 129: [448, 447, 442, 126], 130: [548, 448, 126, 128], 131: [513, 717, 632, 168], 132: [133, 413, 159, 106], 133: [105, 607, 521, 132], 134: [136, 135, 6, 137], 135: [5, 134, 627, 626], 136: [134, 141, 628, 627], 137: [138, 141, 134, 13], 138: [140, 137, 139, 475], 139: [535, 138, 13, 14], 140: [138, 473, 588, 141], 141: [140, 602, 136, 137], 142: [56, 143, 358, 359], 143: [145, 142, 144, 146], 144: [56, 60, 364, 143], 145: [147, 358, 143], 146: [421, 147, 143, 364], 147: [146, 565, 149, 145], 148: [543, 149, 542], 149: [147, 563, 148], 150: [153, 155, 115, 151], 151: [150, 230, 594, 152], 152: [151, 323, 321, 153], 153: [154, 150, 152, 603], 154: [298, 155, 153, 295], 155: [150, 154, 125, 116], 156: [157, 159, 158, 595], 157: [609, 401, 156, 608], 158: [425, 680, 357, 156], 159: [132, 425, 156, 401], 160: [27, 597, 161, 43], 161: [250, 42, 160, 583], 162: [163, 164, 166, 517], 163: [531, 162, 70, 66], 164: [165, 162, 531, 548], 165: [452, 166, 164, 167], 166: [81, 162, 165, 432], 167: [548, 128, 590, 165], 168: [631, 436, 438, 131], 169: [630, 629, 588, 437], 170: [171, 589, 307, 85], 171: [170, 84, 283, 409], 172: [212, 174, 176, 208], 173: [176, 174, 175, 388], 174: [173, 172, 403, 524], 175: [387, 173, 524, 525], 176: [172, 173, 486, 210], 177: [47, 305, 306, 179], 178: [179, 456, 48, 47], 179: [177, 461, 464, 178], 180: [773, 772, 284, 181], 181: [180, 324, 281, 182], 182: [181, 601, 773], 183: [185, 284, 772, 771], 184: [186, 185, 771, 530], 185: [183, 184, 187, 188], 186: [195, 187, 184, 59], 187: [186, 193, 611, 185], 188: [285, 284, 185, 611], 189: [191, 192, 194, 242], 190: [191, 660, 248, 192], 191: [661, 190, 189, 249], 192: [190, 611, 193, 189], 193: [195, 194, 192, 187], 194: [193, 241, 240, 189], 195: [193, 186, 478, 241], 196: [197, 201, 381, 199], 197: [198, 223, 200, 196], 198: [199, 453, 218, 197], 199: [196, 384, 454, 198], 200: [204, 201, 197, 203], 201: [200, 451, 383, 196], 202: [206, 204, 203, 96], 203: [200, 223, 369, 202], 204: [451, 200, 202, 450], 205: [794, 356, 293], 206: [202, 207, 462, 450], 207: [533, 463, 206, 96], 208: [172, 210, 209, 211], 209: [504, 507, 331, 208], 210: [376, 504, 208, 176], 211: [330, 212, 208, 331], 212: [211, 402, 403, 172], 213: [215, 217, 518, 687], 214: [485, 518, 217, 538], 215: [213, 220, 221, 216], 216: [215, 370, 567, 217], 217: [214, 213, 216, 623], 218: [198, 371, 219, 223], 219: [218, 221, 220, 222], 220: [215, 687, 368, 219], 221: [370, 215, 219, 371], 222: [369, 223, 219, 368], 223: [222, 203, 197, 218], 224: [41, 37, 472, 262], 225: [113, 229, 511, 227], 226: [579, 113, 227, 552], 227: [617, 226, 225, 606], 228: [72, 229, 113, 75], 229: [512, 225, 228, 466], 230: [386, 151, 115, 117], 231: [232, 467, 439, 38], 232: [490, 231, 233, 493], 233: [503, 232, 38, 389], 234: [236, 237, 239, 329], 235: [329, 325, 328, 236], 236: [286, 287, 234, 235], 237: [287, 304, 238, 234], 238: [237, 305, 334, 239], 239: [618, 234, 238, 607], 240: [242, 194, 584, 340], 241: [194, 195, 359, 584], 242: [249, 189, 240, 339], 243: [244, 246, 245, 723], 244: [390, 243, 596, 604], 245: [724, 243, 574, 725], 246: [573, 574, 243, 390], 247: [60, 58, 768, 653], 248: [659, 285, 611, 190], 249: [191, 242, 430, 662], 250: [45, 161, 470, 251], 251: [253, 250, 252, 111], 252: [470, 469, 112, 251], 253: [110, 546, 45, 251], 254: [679, 255, 527], 255: [526, 254, 256, 418], 256: [561, 255, 679, 257], 257: [560, 256, 12], 258: [456, 682, 681, 48], 259: [533, 682, 456, 463], 260: [41, 262, 261, 388], 261: [486, 260, 377, 374], 262: [260, 224, 476, 377], 263: [278, 277, 738, 265], 264: [265, 625, 505, 278], 265: [264, 263, 266, 54], 266: [53, 265, 738, 599], 267: [67, 69], 268: [68, 67], 269: [273, 271, 270, 272], 270: [7, 275, 276, 269], 271: [269, 496, 494, 7], 272: [375, 374, 269, 276], 273: [377, 496, 269, 374], 274: [275, 277, 278, 276], 275: [755, 274, 270, 756], 276: [274, 622, 272, 270], 277: [274, 755, 754, 263], 278: [263, 264, 622, 274], 279: [108, 822, 280, 595], 280: [292, 457, 608, 279], 281: [601, 181, 282, 656], 282: [559, 657, 281, 324], 283: [171, 678, 407], 284: [183, 188, 324, 180], 285: [188, 248, 559, 324], 286: [127, 236, 328, 616], 287: [127, 443, 237, 236], 288: [125, 124, 395, 116], 289: [727, 63, 499, 728], 290: [18, 581, 614, 17], 291: [523, 597, 292, 821], 292: [291, 458, 280, 822], 293: [205, 522, 523, 821], 294: [298, 295, 593, 297], 295: [294, 154, 603, 296], 296: [92, 593, 295, 322], 297: [294, 547, 343, 347], 298: [347, 125, 154, 294], 299: [302, 300, 301, 500], 300: [639, 581, 299, 640], 301: [581, 18, 497, 299], 302: [640, 299, 303, 641], 303: [500, 502, 541, 302], 304: [306, 305, 237, 443], 305: [238, 304, 177, 333], 306: [461, 177, 304, 442], 307: [309, 311, 170, 308], 308: [307, 589, 362, 555], 309: [555, 312, 310, 307], 310: [309, 313, 427, 311], 311: [307, 310, 86, 85], 312: [313, 309, 650, 649], 313: [648, 428, 310, 312], 314: [315, 317, 719, 718], 315: [314, 717, 513, 514], 316: [720, 719, 317, 422], 317: [551, 316, 314, 514], 318: [322, 321, 319, 488], 319: [320, 510, 512, 318], 320: [610, 319, 321, 323], 321: [320, 318, 603, 152], 322: [318, 94, 296, 603], 323: [152, 594, 573, 320], 324: [282, 181, 284, 285], 325: [235, 326, 327, 119], 326: [404, 405, 325, 329], 327: [120, 325, 405, 562], 328: [286, 235, 119, 380], 329: [235, 234, 618, 326], 330: [402, 211, 103, 104], 331: [103, 211, 209, 506], 332: [506, 568, 107, 103], 333: [520, 334, 305, 47], 334: [607, 238, 333, 521], 335: [337, 336, 465, 424], 336: [338, 335, 509, 339], 337: [665, 509, 335, 341], 338: [340, 98, 465, 336], 339: [242, 340, 336, 430], 340: [99, 338, 339, 240], 341: [454, 666, 337, 424], 342: [454, 384, 666], 343: [345, 348, 297, 344], 344: [418, 417, 343, 547], 345: [343, 417, 419, 346], 346: [345, 426, 482, 348], 347: [298, 297, 348, 122], 348: [343, 346, 123, 347], 349: [672, 352, 373, 350], 350: [349, 480, 799], 351: [672, 485, 538, 352], 352: [349, 351, 353], 353: [543, 373, 352], 354: [586, 355, 479, 585], 355: [792, 354, 558, 356], 356: [205, 793, 355, 522], 357: [158, 796, 108, 595], 358: [142, 145, 360], 359: [478, 142, 360, 241], 360: [584, 359, 358, 459], 361: [363, 365, 652, 367], 362: [420, 363, 367, 308], 363: [364, 361, 362, 421], 364: [144, 365, 363, 146], 365: [361, 364, 60, 653], 366: [481, 647, 646, 554], 367: [362, 361, 651, 555], 368: [686, 95, 222, 220], 369: [95, 96, 203, 222], 370: [221, 372, 100, 216], 371: [453, 372, 221, 218], 372: [465, 370, 371, 424], 373: [620, 480, 349, 353], 374: [376, 261, 273, 272], 375: [272, 622, 504, 376], 376: [374, 375, 210, 486], 377: [537, 273, 261, 262], 378: [379, 380, 119, 118], 379: [378, 121, 556, 615], 380: [615, 616, 328, 378], 381: [196, 383, 667, 384], 382: [667, 383, 398], 383: [400, 382, 381, 201], 384: [342, 199, 381], 385: [61, 386, 117, 498], 386: [385, 65, 594, 230], 387: [41, 388, 175, 389], 388: [486, 173, 387, 260], 389: [233, 40, 387, 525], 390: [246, 244, 605, 610], 391: [69, 392], 392: [391, 70, 79, 393], 393: [392, 80], 394: [395, 124, 553, 643], 395: [288, 394, 396, 544], 396: [545, 395, 643, 642], 397: [554, 553, 124, 123], 398: [382, 400, 399, 410], 399: [487, 398, 612, 415], 400: [398, 383, 451, 612], 401: [159, 157, 104, 106], 402: [31, 212, 330, 609], 403: [31, 28, 174, 212], 404: [618, 569, 406, 326], 405: [327, 326, 406, 52], 406: [404, 568, 55, 405], 407: [283, 677, 408, 409], 408: [564, 407, 440, 563], 409: [407, 564, 589, 171], 410: [398, 487], 411: [425, 50, 412, 680], 412: [797, 411, 51], 413: [425, 132, 521, 50], 414: [415, 416, 32, 36], 415: [414, 68, 399, 576], 416: [414, 576, 508, 33], 417: [345, 344, 561, 87], 418: [344, 528, 255, 561], 419: [426, 345, 87, 86], 420: [564, 421, 362, 589], 421: [420, 565, 146, 363], 422: [316, 551, 549, 423], 423: [422, 613, 721, 720], 424: [335, 372, 453, 341], 425: [413, 411, 158, 159], 426: [427, 481, 346, 419], 427: [426, 86, 310, 428], 428: [647, 481, 427, 313], 429: [527, 532], 430: [249, 339, 509, 663], 431: [434, 734, 468, 433], 432: [433, 166, 452, 434], 433: [81, 432, 431, 571], 434: [557, 435, 431, 432], 435: [434, 556, 735, 734], 436: [437, 534, 439, 168], 437: [631, 169, 587, 436], 438: [439, 467, 513, 168], 439: [436, 39, 231, 438], 440: [676, 542, 408, 677], 441: [556, 121, 736, 735], 442: [129, 446, 306, 443], 443: [287, 126, 442, 304], 444: [445, 778, 80], 445: [444, 78, 516, 669], 446: [461, 442, 447, 566], 447: [446, 129, 33, 508], 448: [129, 130, 35, 33], 449: [450, 477, 612, 451], 450: [519, 449, 204, 206], 451: [201, 204, 449, 400], 452: [432, 165, 590, 557], 453: [424, 371, 198, 454], 454: [342, 341, 453, 199], 455: [503, 30, 43, 44], 456: [178, 464, 259, 258], 457: [458, 26, 572, 280], 458: [27, 457, 292, 597], 459: [360, 101, 99], 460: [462, 464, 461, 566], 461: [446, 460, 179, 306], 462: [206, 463, 460, 519], 463: [462, 207, 259, 464], 464: [179, 460, 463, 456], 465: [100, 372, 335, 338], 466: [229, 72, 93, 488], 467: [490, 515, 438, 231], 468: [732, 571, 431, 733], 469: [558, 76, 252, 471], 470: [583, 471, 252, 250], 471: [522, 469, 470, 523], 472: [475, 476, 224, 474], 473: [140, 475, 474, 587], 474: [534, 473, 472, 37], 475: [473, 138, 535, 472], 476: [535, 537, 262, 472], 477: [449, 519, 508, 576], 478: [359, 195, 59, 56], 479: [354, 792, 532], 480: [673, 350, 373], 481: [366, 482, 426, 428], 482: [481, 554, 123, 346], 483: [484, 604, 596, 25], 484: [721, 613, 624, 483], 485: [671, 214, 351, 23], 486: [176, 388, 261, 376], 487: [410, 399, 68], 488: [318, 512, 466, 94], 489: [490, 493, 492, 591], 490: [232, 489, 491, 467], 491: [591, 592, 515, 490], 492: [44, 45, 546, 489], 493: [503, 44, 489, 232], 494: [21, 271, 495, 711], 495: [496, 536, 598, 494], 496: [271, 273, 537, 495], 497: [498, 500, 301, 499], 498: [64, 385, 501, 497], 499: [497, 18, 289, 64], 500: [497, 501, 303, 299], 501: [500, 498, 117, 502], 502: [501, 114, 545, 303], 503: [525, 455, 493, 233], 504: [375, 505, 209, 210], 505: [504, 622, 264, 507], 506: [332, 331, 507, 621], 507: [625, 506, 209, 505], 508: [566, 447, 416, 477], 509: [664, 430, 336, 337], 510: [605, 511, 319, 610], 511: [512, 510, 606, 225], 512: [319, 511, 229, 488], 513: [315, 131, 438, 515], 514: [317, 315, 515, 592], 515: [491, 514, 513, 467], 516: [20, 710, 445, 570], 517: [70, 162, 81, 79], 518: [671, 688, 213, 214], 519: [477, 450, 462, 566], 520: [521, 333, 46, 50], 521: [520, 413, 133, 334], 522: [293, 356, 558, 471], 523: [471, 583, 291, 293], 524: [28, 30, 175, 174], 525: [30, 503, 389, 175], 526: [255, 528, 91, 527], 527: [526, 90, 429, 254], 528: [526, 418, 547, 529], 529: [528, 593, 92, 91], 530: [58, 59, 184, 770], 531: [164, 163, 34, 35], 532: [479, 429, 90, 585], 533: [97, 683, 259, 207], 534: [474, 39, 436, 587], 535: [139, 536, 476, 475], 536: [535, 14, 495, 537], 537: [496, 377, 476, 536], 538: [623, 351, 214], 539: [638, 637, 540, 582], 540: [636, 635, 614, 539], 541: [545, 642, 641, 303], 542: [148, 563, 440, 675], 543: [148, 675, 620, 353], 544: [395, 545, 114, 116], 545: [544, 396, 541, 502], 546: [591, 492, 253, 580], 547: [344, 297, 593, 528], 548: [167, 164, 35, 130], 549: [613, 422, 550, 552], 550: [549, 551, 578, 577], 551: [550, 422, 317, 592], 552: [577, 226, 617, 549], 553: [645, 644, 394, 397], 554: [645, 397, 482, 366], 555: [309, 308, 367, 650], 556: [441, 435, 557, 379], 557: [434, 452, 615, 556], 558: [355, 586, 469, 522], 559: [659, 658, 282, 285], 560: [561, 257, 82, 87], 561: [417, 418, 256, 560], 562: [52, 600, 11, 327], 563: [149, 565, 408, 542], 564: [408, 565, 420, 409], 565: [147, 421, 564, 563], 566: [446, 508, 519, 460], 567: [623, 216, 100, 101], 568: [621, 406, 569, 332], 569: [619, 107, 568, 404], 570: [78, 571, 732, 516], 571: [77, 433, 468, 570], 572: [31, 609, 608, 457], 573: [610, 323, 575, 246], 574: [245, 246, 575, 19], 575: [573, 594, 65, 574], 576: [612, 477, 416, 415], 577: [580, 579, 552, 550], 578: [550, 592, 591, 580], 579: [226, 577, 110, 109], 580: [577, 578, 546, 110], 581: [301, 300, 582, 290], 582: [639, 539, 614, 581], 583: [470, 161, 597, 523], 584: [240, 241, 360, 99], 585: [354, 532, 89, 74], 586: [74, 76, 558, 354], 587: [437, 588, 473, 534], 588: [602, 140, 587, 169], 589: [420, 308, 170, 409], 590: [452, 167, 616, 615], 591: [546, 578, 491, 489], 592: [514, 491, 578, 551], 593: [294, 296, 529, 547], 594: [575, 323, 151, 386], 595: [357, 279, 608, 156], 596: [722, 483, 244, 723], 597: [458, 291, 583, 160], 598: [14, 712, 711, 495], 599: [9, 600, 266, 737], 600: [562, 53, 599, 10], 601: [820, 182, 281, 655], 602: [141, 588, 629, 628], 603: [295, 153, 321, 322], 604: [605, 244, 483, 624], 605: [390, 604, 606, 510], 606: [511, 605, 624, 227], 607: [133, 619, 239, 334], 608: [157, 595, 280, 572], 609: [104, 157, 572, 402], 610: [573, 390, 510, 320], 611: [248, 188, 187, 192], 612: [449, 576, 399, 400], 613: [549, 617, 484, 423], 614: [290, 582, 540, 634], 615: [557, 590, 380, 379], 616: [590, 128, 286, 380], 617: [613, 552, 227, 624], 618: [239, 619, 404, 329], 619: [607, 105, 569, 618], 620: [673, 373, 543, 674], 621: [625, 55, 568, 506], 622: [505, 375, 276, 278], 623: [538, 217, 567], 624: [606, 604, 484, 617], 625: [621, 507, 264, 54], 626: [135, 690, 689, 806], 627: [135, 136, 691, 690], 628: [136, 602, 692, 691], 629: [602, 169, 693, 692], 630: [169, 631, 715, 693], 631: [437, 168, 632, 630], 632: [131, 716, 715, 631], 633: [63, 727, 726, 16], 634: [614, 635, 17], 635: [540, 694, 634], 636: [540, 637, 695, 694], 637: [539, 697, 696, 636], 638: [539, 639, 698, 697], 639: [582, 300, 699, 638], 640: [300, 302, 700, 699], 641: [302, 541, 701, 700], 642: [541, 396, 702, 701], 643: [396, 394, 644, 702], 644: [553, 704, 703, 643], 645: [553, 554, 646, 704], 646: [366, 705, 761, 645], 647: [366, 428, 648, 705], 648: [313, 649, 763, 647], 649: [312, 706, 764, 648], 650: [312, 555, 651, 706], 651: [367, 652, 765, 650], 652: [361, 653, 766, 651], 653: [365, 247, 767, 652], 654: [820, 655, 774], 655: [601, 656, 775, 654], 656: [281, 657, 776, 655], 657: [282, 658, 777, 656], 658: [559, 707, 657], 659: [559, 248, 660, 707], 660: [190, 661, 708, 659], 661: [191, 662, 660], 662: [249, 663, 661], 663: [430, 664, 662], 664: [509, 665, 663], 665: [337, 666, 664], 666: [341, 342, 665], 667: [381, 382], 668: [669, 709], 669: [778, 445, 710, 668], 670: [121, 787, 752, 736], 671: [518, 485], 672: [351, 349, 22, 23], 673: [480, 620], 674: [620, 675], 675: [543, 542, 676, 674], 676: [440, 675], 677: [440, 407], 678: [283, 84, 12], 679: [256, 254], 680: [158, 411, 797, 796], 681: [49, 258], 682: [258, 259, 683], 683: [533, 684, 682], 684: [97, 685, 683], 685: [95, 686, 684], 686: [368, 687, 685], 687: [220, 213, 688, 686], 688: [518, 687], 689: [626, 714], 690: [626, 627, 808, 714], 691: [627, 628, 809, 808], 692: [628, 629, 810, 809], 693: [629, 630, 811, 810], 694: [635, 636, 729], 695: [636, 696, 729], 696: [637, 695], 697: [637, 638], 698: [638, 699], 699: [639, 640, 757, 698], 700: [640, 641, 730, 757], 701: [641, 642, 731, 730], 702: [642, 643, 703, 731], 703: [644, 760, 759, 702], 704: [644, 645, 761, 760], 705: [646, 647, 763, 762], 706: [649, 650, 765], 707: [658, 659, 708], 708: [660, 707], 709: [668, 710, 779], 710: [669, 516, 2, 709], 711: [494, 598, 739], 712: [598, 713, 790, 739], 713: [14, 13, 791, 712], 714: [689, 690, 807], 715: [630, 632, 812, 811], 716: [632, 717, 813, 812], 717: [131, 315, 718, 716], 718: [314, 740, 813, 717], 719: [314, 316, 741, 740], 720: [316, 423, 742, 741], 721: [423, 484, 25, 742], 722: [25, 596, 743, 817], 723: [596, 243, 724, 743], 724: [245, 745, 744, 723], 725: [245, 19, 16, 745], 726: [15, 633], 727: [633, 289, 746], 728: [289, 18, 17, 746], 729: [694, 695], 730: [700, 701, 758], 731: [701, 702, 759, 758], 732: [570, 468, 747, 20], 733: [468, 734, 748, 747], 734: [431, 435, 749, 733], 735: [435, 441, 750, 749], 736: [441, 670, 751, 750], 737: [599, 738, 753, 8], 738: [266, 263, 754, 737], 739: [711, 712], 740: [718, 719, 815, 814], 741: [719, 720, 816, 815], 742: [720, 721, 24, 816], 743: [722, 723, 744], 744: [724, 818, 743], 745: [724, 725, 15, 818], 746: [727, 728, 4], 747: [732, 733, 780, 3], 748: [733, 749, 781, 780], 749: [734, 735, 782, 748], 750: [735, 736, 783, 782], 751: [736, 752, 784, 783], 752: [670, 786, 785, 751], 753: [737, 754], 754: [738, 277, 788, 753], 755: [277, 275, 789, 788], 756: [275, 7, 789], 757: [699, 700], 758: [730, 731], 759: [731, 703], 760: [703, 704], 761: [704, 646, 762], 762: [705, 761], 763: [705, 648, 764], 764: [649, 763], 765: [706, 651, 766], 766: [652, 767, 765], 767: [653, 768, 766], 768: [247, 769, 767], 769: [58, 770, 768], 770: [530, 771, 819, 769], 771: [184, 183, 800, 770], 772: [183, 180, 800], 773: [180, 182], 774: [654, 775], 775: [655, 776, 774], 776: [656, 777, 775], 777: [657, 776], 778: [444, 669], 779: [709, 2, 801], 780: [747, 748, 802], 781: [748, 782], 782: [749, 750, 781], 783: [750, 751], 784: [751, 785], 785: [752, 803, 784], 786: [752, 787, 10, 803], 787: [670, 118, 11, 786], 788: [754, 755], 789: [755, 756], 790: [712, 791], 791: [713, 6, 804, 790], 792: [479, 355, 793], 793: [356, 794, 792], 794: [205, 793], 795: [108, 796], 796: [357, 680, 824, 795], 797: [680, 412, 824], 798: [], 799: [350], 800: [771, 772, 819], 801: [779, 1], 802: [3, 780, 0], 803: [785, 786, 9, 805], 804: [791, 5], 805: [803, 8], 806: [5, 626], 807: [714, 808], 808: [690, 691, 825, 807], 809: [691, 692, 826, 825], 810: [692, 693, 827, 826], 811: [693, 715, 828, 827], 812: [715, 716, 829, 828], 813: [716, 718, 814, 829], 814: [740, 813], 815: [740, 741], 816: [741, 742], 817: [24, 722], 818: [744, 745], 819: [770, 800], 820: [601, 654], 821: [293, 291, 822], 822: [292, 279, 823, 821], 823: [108, 822], 824: [796, 797], 825: [808, 809], 826: [809, 810], 827: [810, 811], 828: [811, 812], 829: [812, 813]}
# adj_lists = {0: [], 1: [497, 456], 2: [68, 144, 497], 3: [11, 494, 484, 16], 4: [200, 421], 5: [496], 6: [487], 7: [496, 489, 179], 8: [488, 487, 161], 9: [401, 432, 492], 10: [493, 12], 11: [299, 258, 493, 3], 12: [203, 485, 10, 414], 13: [387, 34, 483], 14: [27, 28, 477], 15: [20, 471, 482, 476], 16: [21, 299, 3, 478], 17: [203, 308, 479, 485], 18: [318, 257, 19, 480], 19: [22, 465, 481, 18], 20: [15, 470, 304, 302], 21: [16, 464, 317, 300], 22: [443, 19, 257, 256], 23: [395, 354], 24: [49, 161, 487, 469], 25: [381, 382], 26: [339, 403], 27: [14, 461, 313, 208], 28: [215, 462, 14, 208], 29: [275, 122, 460, 439], 30: [86, 440, 462, 215], 31: [49, 169, 210, 161], 32: [117, 410, 413, 116], 33: [304, 470, 386, 75], 34: [305, 495, 13, 35], 35: [214, 323, 34, 387], 36: [340, 85], 37: [441, 343, 331, 291], 38: [309, 183, 344, 445], 39: [159, 40, 382, 381], 40: [39, 160, 196, 41], 41: [382, 40, 195, 334], 42: [229, 162, 43, 47], 43: [42, 44, 45, 310], 44: [43, 162, 163, 46], 45: [303, 43, 46, 279], 46: [44, 104, 280, 45], 47: [310, 314, 230, 42], 48: [453, 361, 64, 50], 49: [50, 31, 24, 453], 50: [48, 66, 169, 49], 51: [54, 57, 56, 52], 52: [51, 81, 80, 53], 53: [52, 226, 223, 54], 54: [51, 53, 91, 55], 55: [218, 57, 54, 93], 56: [81, 51, 192, 189], 57: [219, 192, 51, 55], 58: [62, 60, 61, 95], 59: [60, 236, 266, 61], 60: [58, 92, 287, 59], 61: [59, 326, 94, 58], 62: [92, 58, 63, 93], 63: [95, 272, 217, 62], 64: [358, 66, 48, 65], 65: [64, 361, 360, 359], 66: [357, 170, 50, 64], 67: [380, 127, 159, 381], 68: [219, 2, 69, 192], 69: [158, 191, 68], 70: [74, 73, 312, 71], 71: [337, 151, 70, 273], 72: [239, 73, 74, 274], 73: [75, 70, 72, 242], 74: [70, 151, 336, 72], 75: [73, 292, 33, 312], 76: [77, 78, 349, 348], 77: [165, 181, 182, 76], 78: [76, 182, 224, 225], 79: [80, 81, 352, 351], 80: [79, 350, 226, 52], 81: [52, 56, 82, 79], 82: [352, 81, 189, 353], 83: [86, 84, 89, 88], 84: [83, 87, 307, 329], 85: [440, 86, 88, 36], 86: [85, 30, 87, 83], 87: [306, 84, 86, 215], 88: [90, 340, 85, 83], 89: [83, 329, 330, 90], 90: [89, 331, 145, 88], 91: [93, 54, 223, 92], 92: [60, 62, 91, 227], 93: [217, 55, 91, 62], 94: [95, 61, 222, 220], 95: [94, 96, 63, 58], 96: [221, 272, 95, 220], 97: [100, 98, 247, 101], 98: [97, 102, 246, 99], 99: [98, 333, 248, 247], 100: [153, 154, 102, 97], 101: [147, 153, 97, 213], 102: [244, 98, 100, 173], 103: [105, 107, 325, 245], 104: [163, 325, 107, 46], 105: [106, 103, 243, 216], 106: [201, 107, 105, 200], 107: [104, 103, 106, 280], 108: [272, 364, 143, 217], 109: [418, 417, 110, 254], 110: [364, 272, 221, 109], 111: [126, 113, 112, 132], 112: [238, 111, 114, 424], 113: [111, 127, 115, 114], 114: [112, 113, 283, 425], 115: [113, 250, 251, 283], 116: [370, 177, 32, 179], 117: [32, 177, 211, 371], 118: [119, 173, 172, 120], 119: [366, 365, 282, 118], 120: [130, 121, 366, 118], 121: [368, 367, 120, 131], 122: [461, 29, 276, 313], 123: [125, 124, 198, 355], 124: [123, 202, 171, 170], 125: [354, 184, 202, 123], 126: [111, 128, 159, 127], 127: [250, 113, 126, 67], 128: [133, 160, 126, 132], 129: [132, 131, 233, 133], 130: [172, 233, 131, 120], 131: [129, 238, 121, 130], 132: [128, 111, 238, 129], 133: [129, 298, 197, 128], 134: [293, 149, 137, 136], 135: [136, 298, 284, 293], 136: [135, 134, 240, 241], 137: [242, 240, 134, 148], 138: [343, 342, 145, 331], 139: [375, 140, 141, 142], 140: [164, 372, 139, 374], 141: [372, 371, 211, 139], 142: [212, 376, 139, 211], 143: [108, 363, 144, 218], 144: [219, 143, 415, 2], 145: [340, 90, 138, 278], 146: [149, 147, 301, 150], 147: [101, 214, 146, 155], 148: [137, 149, 150, 292], 149: [155, 146, 148, 134], 150: [146, 302, 304, 148], 151: [74, 71, 437, 436], 152: [154, 153, 293, 284], 153: [155, 152, 100, 101], 154: [173, 100, 152, 172], 155: [293, 153, 147, 149], 156: [202, 158, 157, 171], 157: [210, 156, 362, 455], 158: [156, 190, 69, 362], 159: [126, 160, 39, 67], 160: [197, 40, 159, 128], 161: [31, 454, 8, 24], 162: [294, 295, 44, 42], 163: [104, 44, 295, 324], 164: [429, 140, 373, 430], 165: [166, 167, 77, 348], 166: [346, 183, 165, 347], 167: [165, 183, 309, 181], 168: [282, 365, 216, 243], 169: [50, 170, 171, 31], 170: [198, 124, 169, 66], 171: [124, 156, 210, 169], 172: [130, 118, 154, 284], 173: [102, 154, 118, 282], 174: [176, 175, 178, 251], 175: [212, 211, 177, 174], 176: [174, 237, 378, 212], 177: [117, 116, 178, 175], 178: [174, 177, 370, 281], 179: [7, 428, 116, 413], 180: [234, 182, 181, 256], 181: [77, 167, 271, 180], 182: [180, 288, 78, 77], 183: [311, 38, 167, 166], 184: [190, 125, 353, 189], 185: [188, 255, 277, 186], 186: [201, 187, 185, 279], 187: [188, 186, 199, 420], 188: [185, 187, 419, 252], 189: [56, 191, 184, 82], 190: [191, 158, 202, 184], 191: [69, 190, 189, 192], 192: [56, 57, 68, 191], 193: [240, 194, 196, 241], 194: [274, 195, 193, 239], 195: [41, 196, 194, 335], 196: [193, 195, 40, 197], 197: [196, 160, 133, 241], 198: [357, 356, 123, 170], 199: [200, 187, 201], 200: [4, 199, 106, 216], 201: [199, 186, 280, 106], 202: [190, 156, 124, 125], 203: [204, 205, 17, 12], 204: [414, 321, 319, 203], 205: [326, 308, 203, 319], 206: [209, 207, 296, 297], 207: [215, 208, 206, 306], 208: [207, 28, 27, 296], 209: [294, 306, 206, 295], 210: [31, 171, 157, 454], 211: [175, 142, 141, 117], 212: [175, 176, 377, 142], 213: [323, 214, 101, 247], 214: [213, 35, 301, 147], 215: [28, 207, 87, 30], 216: [200, 105, 168, 421], 217: [108, 218, 93, 63], 218: [55, 217, 143, 219], 219: [68, 57, 218, 144], 220: [96, 94, 286, 285], 221: [285, 254, 110, 96], 222: [319, 286, 94, 326], 223: [91, 53, 224, 227], 224: [223, 226, 78, 288], 225: [226, 350, 349, 78], 226: [224, 53, 80, 225], 227: [288, 287, 92, 223], 228: [229, 231, 329, 307], 229: [42, 230, 228, 294], 230: [229, 47, 315, 231], 231: [232, 228, 230, 317], 232: [330, 329, 231, 290], 233: [129, 130, 284, 298], 234: [180, 235, 287, 288], 235: [257, 236, 234, 256], 236: [59, 287, 235, 265], 237: [250, 379, 176, 251], 238: [112, 368, 131, 132], 239: [240, 242, 72, 194], 240: [239, 193, 136, 137], 241: [298, 136, 193, 197], 242: [73, 239, 137, 292], 243: [105, 245, 244, 168], 244: [282, 243, 246, 102], 245: [332, 246, 243, 103], 246: [245, 333, 98, 244], 247: [249, 213, 97, 99], 248: [99, 268, 276, 249], 249: [247, 248, 275, 323], 250: [237, 115, 127, 380], 251: [237, 174, 281, 115], 252: [254, 255, 188, 418], 253: [262, 255, 254, 285], 254: [221, 253, 252, 109], 255: [252, 253, 260, 185], 256: [235, 180, 271, 22], 257: [265, 235, 22, 18], 258: [11, 259, 321, 414], 259: [316, 322, 258, 299], 260: [255, 262, 289, 277], 261: [262, 264, 328, 289], 262: [261, 260, 253, 263], 263: [286, 264, 262, 285], 264: [263, 320, 322, 261], 265: [236, 257, 318, 266], 266: [265, 308, 326, 59], 267: [268, 269, 313, 276], 268: [248, 333, 270, 267], 269: [296, 267, 270, 297], 270: [268, 332, 324, 269], 271: [256, 181, 309, 443], 272: [63, 96, 110, 108], 273: [71, 312, 339, 338], 274: [336, 335, 194, 72], 275: [276, 29, 305, 249], 276: [248, 267, 122, 275], 277: [260, 303, 279, 185], 278: [341, 145, 342], 279: [45, 280, 186, 277], 280: [279, 46, 107, 201], 281: [283, 251, 178, 369], 282: [244, 173, 119, 168], 283: [281, 426, 114, 115], 284: [233, 172, 152, 135], 285: [263, 253, 221, 220], 286: [220, 222, 320, 263], 287: [234, 236, 60, 227], 288: [227, 224, 182, 234], 289: [260, 261, 327, 303], 290: [317, 464, 291, 232], 291: [290, 442, 37, 330], 292: [242, 148, 304, 75], 293: [152, 155, 134, 135], 294: [229, 307, 209, 162], 295: [209, 297, 163, 162], 296: [206, 208, 313, 269], 297: [269, 324, 295, 206], 298: [133, 233, 135, 241], 299: [259, 11, 16, 300], 300: [315, 316, 299, 21], 301: [387, 302, 146, 214], 302: [150, 301, 471, 20], 303: [310, 45, 277, 289], 304: [20, 33, 292, 150], 305: [275, 439, 34, 323], 306: [207, 209, 307, 87], 307: [84, 306, 294, 228], 308: [266, 318, 17, 205], 309: [444, 271, 167, 38], 310: [47, 43, 303, 327], 311: [345, 344, 183, 346], 312: [70, 75, 386, 273], 313: [267, 296, 27, 122], 314: [316, 315, 47, 327], 315: [230, 314, 300, 317], 316: [314, 328, 259, 300], 317: [315, 21, 290, 231], 318: [479, 308, 265, 18], 319: [320, 222, 205, 204], 320: [321, 264, 286, 319], 321: [320, 204, 258, 322], 322: [328, 264, 321, 259], 323: [213, 249, 305, 35], 324: [163, 297, 270, 325], 325: [103, 104, 324, 332], 326: [222, 61, 266, 205], 327: [314, 310, 289, 328], 328: [322, 316, 327, 261], 329: [228, 232, 89, 84], 330: [291, 331, 89, 232], 331: [90, 330, 37, 138], 332: [333, 245, 325, 270], 333: [99, 246, 332, 268], 334: [41, 335], 335: [195, 274, 435, 334], 336: [274, 74, 436, 435], 337: [71, 338, 383, 437], 338: [273, 385, 384, 337], 339: [273, 386, 26, 385], 340: [88, 145, 341, 36], 341: [278, 340], 342: [278, 138, 388], 343: [138, 37, 388], 344: [311, 389, 446, 38], 345: [311, 391, 390, 389], 346: [311, 166, 412, 391], 347: [166, 348, 392, 412], 348: [165, 76, 393, 347], 349: [76, 225, 394, 393], 350: [225, 80, 351, 394], 351: [79, 447, 350], 352: [79, 82, 395, 447], 353: [82, 184, 354, 395], 354: [125, 355, 23, 353], 355: [123, 356, 354], 356: [198, 396, 355], 357: [198, 66, 358, 396], 358: [64, 359, 397, 357], 359: [65, 399, 398, 358], 360: [65, 451, 450, 399], 361: [65, 48, 452, 451], 362: [157, 158, 456], 363: [143, 364, 416, 415], 364: [108, 110, 417, 363], 365: [168, 119, 422, 421], 366: [119, 120, 367, 422], 367: [121, 423, 366], 368: [121, 238, 424, 423], 369: [281, 370, 427, 426], 370: [178, 116, 428, 369], 371: [117, 141, 400, 410], 372: [141, 140, 429, 400], 373: [164, 374, 432, 401], 374: [140, 375, 373], 375: [139, 376, 374], 376: [142, 377, 375], 377: [212, 378, 376], 378: [176, 379, 433, 377], 379: [237, 380, 434, 378], 380: [250, 67, 402, 379], 381: [67, 39, 25, 402], 382: [39, 41, 25], 383: [337, 384, 438], 384: [338, 383], 385: [338, 339], 386: [339, 312, 33, 403], 387: [471, 301, 35, 13], 388: [342, 343], 389: [344, 345, 404], 390: [345, 405, 404], 391: [345, 346, 405], 392: [347, 393], 393: [348, 349, 392], 394: [349, 350], 395: [352, 353, 23], 396: [356, 357, 397], 397: [358, 398, 396], 398: [359, 406, 397], 399: [359, 360, 407, 406], 400: [371, 372], 401: [430, 373, 9, 431], 402: [380, 381, 434], 403: [26, 386, 470, 475], 404: [389, 390], 405: [390, 391], 406: [398, 399, 408], 407: [399, 450, 409, 408], 408: [406, 407, 411], 409: [407, 449, 448, 411], 410: [32, 371], 411: [408, 409, 468, 467], 412: [346, 347], 413: [179, 32, 496], 414: [493, 258, 204, 12], 415: [144, 363, 497], 416: [363, 417], 417: [364, 109, 457, 416], 418: [109, 252, 419, 457], 419: [188, 420, 418], 420: [187, 419], 421: [216, 365, 4], 422: [365, 366], 423: [367, 368], 424: [368, 112, 425], 425: [114, 426, 424], 426: [283, 369, 458, 425], 427: [369, 428, 458], 428: [370, 179, 489, 427], 429: [372, 164], 430: [164, 401], 431: [401, 492, 459], 432: [373, 9], 433: [378, 434], 434: [379, 402, 433], 435: [335, 336], 436: [336, 151], 437: [151, 337, 438], 438: [383, 437], 439: [305, 29, 495], 440: [85, 30], 441: [37, 442], 442: [291, 464, 463, 441], 443: [271, 444, 465, 22], 444: [309, 445, 466, 443], 445: [38, 446, 444], 446: [344, 445], 447: [351, 352], 448: [409, 468], 449: [409, 450], 450: [407, 360, 449], 451: [360, 361], 452: [361, 453], 453: [48, 49, 469, 452], 454: [161, 210, 455, 488], 455: [157, 456, 454], 456: [362, 1, 455], 457: [417, 418], 458: [426, 427], 459: [431, 474], 460: [29, 461], 461: [122, 27, 477, 460], 462: [30, 28], 463: [442, 478], 464: [442, 290, 21, 478], 465: [443, 466, 19], 466: [444, 465], 467: [411, 472], 468: [411, 448, 473, 472], 469: [453, 24], 470: [476, 403, 33, 20], 471: [15, 302, 387, 483], 472: [467, 468, 486], 473: [468, 486], 474: [459, 492, 491, 490], 475: [403, 476], 476: [470, 15, 475], 477: [461, 14], 478: [463, 464, 16, 484], 479: [318, 480, 17], 480: [18, 481, 479], 481: [19, 480], 482: [15, 483], 483: [471, 13, 482], 484: [478, 3], 485: [17, 12], 486: [472, 473], 487: [24, 8, 6], 488: [454, 8], 489: [428, 7], 490: [474], 491: [474], 492: [474, 431, 9], 493: [494, 11, 414, 10], 494: [493, 3], 495: [439, 34], 496: [7, 5, 413], 497: [1, 2, 415]}
# list of vertices (mesh faces) on the border - for these we don't care whether they are matched
border_vertices = [0, 4, 8, 12, 15, 21, 22, 23, 24, 49, 101, 145, 148, 149, 182, 205, 254, 257, 267, 268, 283, 342, 350, 352, 353, 358, 382, 384, 391, 393, 410, 412, 429, 444, 459, 479, 480, 487, 538, 623, 634, 635, 654, 658, 661, 662, 663, 664, 665, 666, 667, 668, 671, 673, 674, 676, 677, 678, 679, 681, 682, 683, 684, 685, 686, 688, 689, 694, 695, 696, 697, 698, 706, 707, 708, 709, 711, 714, 726, 727, 729, 730, 739, 743, 744, 746, 753, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782, 783, 784, 785, 788, 789, 790, 792, 793, 794, 795, 797, 798, 799, 800, 801, 802, 804, 805, 806, 807, 814, 815, 816, 817, 818, 819, 820, 821, 823, 824, 825, 826, 827, 828, 829]
# force the connectivity
# forced_pairs = [(346, 412), (311, 344), (339, 273), (71,151),
# (445, 38), (183, 166), (347, 392),
# (403, 386), (312, 70), (74, 336),
# (19, 22), (466, 444), (49, 24),
# (470, 476), (301, 146), (48, 361),
# (102, 100),(152, 154), (147, 155), (101, 97),
# (94, 220), (61, 58), (300, 315), (243, 244),
# (254,252), (188, 187), (199, 200), (96, 221), (286, 263), (285, 253),
# (59, 266), (494, 3), (69, 158), (63, 272),
# (124, 170), (66, 64), (65, 360), (408, 411), (468, 473),
# (174, 175), (139, 140), (212, 142), (474, 490), (164, 430)]
forced_pairs = [# left_bottom_corner, parallel
# vertical
(458, 292), (821, 291), (523, 583),
# vertical down
(534, 587), (823, 822), (712, 790),(711, 739),
# horringbone left
(159, 132), (558, 586), (89, 88), (585, 74), (91, 526), (205, 293),
(417, 561), (793, 794), (701, 730), (482, 481), (394, 643),
(426, 427), (419, 345), (348, 123), (347, 297), (343, 344),
(313, 428), (418, 255), (553, 397), (366, 647),
(646, 645), (644, 703), (761, 762), (706, 765), (766, 767), (768, 769),
(635, 634), (729, 694), (746, 727), (705, 763),
# horizontal right
(357, 595), (51, 46), (50, 413), (540, 636), (614, 290),
(258, 48), (178, 47), (179, 461), (130, 548), (166, 81),
(748, 780), (0, 802), (1, 801),
(202, 206), (200, 204), (519, 477), (451, 449), (400, 383),
(576, 415), (398, 399), (68, 268), (8, 805), (782, 781),
# left top
(84, 82), (85, 170), (247, 653), (145, 147), (563, 542),
(309, 310), (772, 800),
# right top
(203, 223), (218, 371), (368, 95), (202, 206), (336, 335),(194, 240),
(101, 459), (623, 538), (351, 672), (662, 663), (664, 665), (666, 342),
(384, 381), (667, 382),
# middle
(349, 350), (675, 674), (543, 148), (283, 678),
]
edges = set()
# a dictionary whose key is the node(mesh face)
# value is the edge(two adjacent mesh faces)
edges_by_vert = defaultdict(set)
for a in adj_lists.keys():
for b in adj_lists[a]:
e = ordered_pair(a, b)
edges.add(e)
edges_by_vert[a].add(e)
edges_by_vert[b].add(e)
print(len(adj_lists), 'Vertexes')
print('Edges:', edges)
try:
# initiate the model
m = gp.Model("optimal_bricks")
# add variables, all the edges are variables
edges_picked_vars = m.addVars(edges, vtype=GRB.BINARY, lb = 0, ub = 1)
def count_neighbors(v):
return sum([edges_picked_vars[e] for e in edges_by_vert[v]])
# force some pairs if needed
for (u, v) in forced_pairs:
e = ordered_pair(u, v)
m.addConstr(edges_picked_vars[e] == 1)
# add constraint, every node can only be connected once
for a in edges_by_vert.keys():
m.addConstr(count_neighbors(a) <= 1, str(a))
vertices_not_on_border = set(adj_lists.keys()).difference(border_vertices)
cnt_vertices_not_on_border_with_neighbor = sum(count_neighbors(a) for a in vertices_not_on_border)
# Find pairs of edges which are directly next to each other and parallel, e.g. (a,b) and (c,d), and (a,c) and (b,d):
# a-b
# | |
# c-d
# We want to avoid such combination of edges because it is undesirable to have bricks next to each other like this.
# The code below finds the pair (a,b) & (c,d)
edge_neighbors = set()
for a in adj_lists.keys():
for b in adj_lists[a]:
for c in adj_lists[a]:
if b != c:
for d in adj_lists[c]:
if d in adj_lists[b]:
e1 = ordered_pair(a, b)
e2 = ordered_pair(c, d)
edge_neighbors.add(ordered_pair(e1, e2))
parallel_brick_pairs_vars = []
for e1, e2 in edge_neighbors:
edge_str = str(f"({e1})+({e2})")
edge_pair_exists = m.addVar(lb=0, ub=1, name=edge_str)
m.addConstr(edge_pair_exists >= edges_picked_vars[e1] + edges_picked_vars[e2] - 1, "constr_" + edge_str)
parallel_brick_pairs_vars.append(edge_pair_exists)
print(len(parallel_brick_pairs_vars))
# It seems more important to minimize the number of irregular bricks, so we assign a 5x higher weight to this part of
# the objective function
m.setObjective(cnt_vertices_not_on_border_with_neighbor / 2 - .2 * sum(parallel_brick_pairs_vars), GRB.MAXIMIZE)
m.optimize()
print('Obj: %g' % m.ObjVal)
bricks_cnt = sum(int(v.X) for v in edges_picked_vars.values())
print(f"{bricks_cnt} bricks, {len(adj_lists) - bricks_cnt*2} unconnected vertex(es)")
parallel_bricks_cnt = sum(round(v.X) for v in parallel_brick_pairs_vars)
print(f"{parallel_bricks_cnt} pair(s) of parallel bricks")
chosen_edges = []
for e in edges_picked_vars.keys():
if edges_picked_vars[e].X == 1:
chosen_edges.append(e)
print(chosen_edges)
with open(o_file, 'wb') as file:
pickle.dump(chosen_edges, file, protocol=2)
except gp.GurobiError as e:
print('Error code ' + str(e.errno) + ': ' + str(e))
except AttributeError:
print('Encountered an attribute error')