guohanghui/graph-theory
0
1from time import process_time2from collections import defaultdict3from graph import Graph4from tests.test_graph import graph5x55 6from graph.traffic_scheduling_problem import jam_solver, UnSolvable, NoSolution, Timer7from graph.traffic_scheduling_problem import State8from graph.traffic_scheduling_problem import check_user_input, path_to_moves9from graph.traffic_scheduling_problem import moves_to_synchronous_moves10 11 12def test_data_loading():13 """ Checks the two acceptable data formats - happy path. """14 g = Graph(from_list=[15 (1, 2, 1.0), (2, 3, 0.2), (3, 4, 0.1), (4, 5, 0.5),16 (2, 7, 1.0), (2, 8, 0.5), (8, 9, 10)17 ])18 19 loads_as_list = [20 {'id': 1, 'start': 1, 'ends': 3}, # keyword prohibited is missing.21 {'id': 2, 'start': 2, 'ends': [3, 4, 5], 'prohibited': [7, 8, 9]},22 {'id': 3, 'start': 3, 'ends': [4, 5], 'prohibited': [2]}, # gateway to off limits.23 {'id': 4, 'start': 8}24 ]25 list_of_loads1 = list(check_user_input(g, loads_as_list).values())26 27 loads_as_dict = {28 1: (1, 3), # start, end, None29 2: (2, [3, 4, 5], [7, 8, 9]), # start, end(s), prohibited30 3: (3, [4, 5], [2]),31 4: (8,)32 }33 list_of_loads2 = list(check_user_input(g, loads_as_dict).values())34 35 assert list_of_loads1 == list_of_loads236 37 38def is_sequence_valid(sequence, graph):39 """ helper to verify that the suggested path actually exists."""40 41 d = defaultdict(list)42 for item in sequence:43 for k, t in item.items():44 if k not in d:45 d[k].extend(t)46 elif d[k][-1] == t[0]:47 d[k].append(t[-1])48 else:49 raise ValueError50 51 return all(graph.has_path(p) for k, p in d.items())52 53 54def is_matching(a, b):55 """ Helper to check that the moves in A are the same as in B."""56 g1 = Graph()57 for d in a:58 for k,v in d.items():59 g1.add_edge(*v, bidirectional=True)60 g2 = Graph()61 for d in b:62 for k,v in d.items():63 g2.add_edge(*v, bidirectional=True)64 return g1 == g265 66 67def test_check_concurrent_moves():68 A = [{2: (3, 4), 1: (1, 2)}, {2: (4, 1), 1: (2, 3)}]69 B = [{2: (3, 2), 1: (1, 4)}, {1: (4, 3), 2: (2, 1)}]70 assert is_matching(A, B)71 72 73def test_check_moves():74 A = [{2: (3, 4)}, {1: (1, 2)}, {2: (4, 1)}, {1: (2, 3)}]75 B = [{2: (3, 2)}, {1: (1, 4)}, {1: (4, 3)}, {2: (2, 1)}]76 assert is_matching(A, B)77 78 79def test_state_class():80 State(loads=(('A', 1), ('B', 2)))81 82 83def test_compact_bfs_problem():84 """85 [4]-->----+86 | |87 [1]--[2]--[3] v88 | |89 [5]--<----+90 91 find the shortest path for the collision between load on [1] and load on [2]92 """93 g = Graph(from_list=[(1, 2, 1), (2, 3, 1), (4, 2, 1), (2, 5, 1), (4, 5, 3)])94 # edge 4,5 has distance 3, which is longer than path [4,2,5] which has distance 2.95 96 moves = jam_solver(g, loads={1: [1, 3], 2: [4, 5]})97 assert is_matching(moves, [{1: (1, 2)}, {1: (2, 3)}, {2: (4, 2)}, {2: (2, 5)}])98 99 100def test_hill_climb():101 """102 [1]<--->[2]<--->[3]103 \\ /104 +->[4]->+ single direction!105 """106 g = Graph()107 for s, e in [(1, 2), (2, 3)]:108 g.add_edge(s, e, 1, bidirectional=True)109 for s, e in [(1, 4), (4, 3)]:110 g.add_edge(s, e, 1, bidirectional=False)111 112 loads = {1: [1, 3], 2: [3, 1]}113 moves = jam_solver(g,loads, synchronous_moves=True)114 expected = [{1: (1, 4), 2: (3, 2)}, {2: (2, 1), 1: (4, 3)}]115 assert is_matching(moves, expected), moves116 117 118def test_hill_climb_with_edge_weights():119 """ 1 1120 [1]<--->[2]<--->[3]121 \ 3 1 /122 <->[4]<->123 All edges are weight 1, except 1<->4 which has weight 3.124 """125 g = Graph()126 for sed in [(1, 2, 1), (2, 3, 1),127 (1, 4, 3), # <-- 3!128 (4, 3, 1)]:129 g.add_edge(*sed, bidirectional=True)130 131 loads={1: [1, 3], 2: [3, 1]}132 133 moves = jam_solver(g,loads)134 is_sequence_valid(moves, g)135 expected = [{2: (3, 4)}, {1: (1, 2)}, {2: (4, 1)}, {1: (2, 3)}]136 assert is_matching(moves, expected)137 138 concurrent_moves = jam_solver(g, loads, synchronous_moves=True)139 expected_conc_moves = [{2: (3, 4), 1: (1, 2)}, {2: (4, 1), 1: (2, 3)}]140 assert is_matching(concurrent_moves, expected_conc_moves)141 142 143def test_hill_climb_with_edge_different_weights():144 """ Same test as the previous, but this time edge 1<-->3 has weight 3,145 whilst the rest have weight 1.146 147 3 1148 [1]<--->[2]<--->[3]149 \\1 1 /150 <->[4]<->151 """152 g = Graph()153 for sed in [(1, 2, 3), # <-- 3!154 (2, 3, 1), (1, 4, 1), (4, 3, 1)]:155 g.add_edge(*sed, bidirectional=True)156 157 loads = {1: [1, 3], 2: [3, 1]}158 moves = jam_solver(g, loads)159 expected_moves = [{2: (3, 4)}, {1: (1, 2)}, {2: (4, 1)}, {1: (2, 3)}] # reverse of previous test.160 assert is_matching(moves, expected_moves)161 162 concurrent_moves = jam_solver(g, loads, synchronous_moves=True)163 expected = [{2: (3, 4), 1: (1, 2)}, {2: (4, 1), 1: (2, 3)}]164 assert is_matching(concurrent_moves, expected)165 166 167def test_hill_climb_with_restrictions():168 """ Same problem as the previous, except that all weights are 1,169 and edge [1,4] and [4,3] are not bidirectional.170 and the only restriction is that load 1 cannot travel over node 2.171 172 1 1173 [1]<--->[2]<--->[3]174 \ 1 1 /175 -->[4]-->176 """177 g = Graph()178 for s, e in [(1, 2), (2, 3)]:179 g.add_edge(s, e, 1, bidirectional=True)180 for s, e in [(1, 4), (4, 3)]:181 g.add_edge(s, e, 1, bidirectional=False)182 183 loads = {1: (1, [3], [2]), # restriction 1 cannot travel over 2184 2: [3, 1]}185 186 sequence = jam_solver(g, loads)187 188 expected_seq = [{2: (3, 2)}, {1: (1, 4)}, {1: (4, 3)}, {2: (2, 1)}]189 assert is_matching(sequence, expected_seq)190 191 concurrent_moves = jam_solver(g, loads, synchronous_moves=True)192 expected_conc_moves = [{1: (1, 4), 2: (3, 2)},{1: (4, 3), 2: (2, 1)}]193 assert is_matching(concurrent_moves, expected_conc_moves)194 195 196def test_hill_climb_with_restrictions_bidirectional():197 """ Same problem as the previous, except that all weights are 1,198 and the only restriction is that load 1 cannot travel over node 2.199 200 1 1201 [1]<--->[2]<--->[3]202 \\1 1 /203 <->[4]<->204 """205 g = Graph()206 for s, e in [(1, 2), (2, 3), (1, 4), (4, 3)]:207 g.add_edge(s, e, 1, bidirectional=True)208 209 loads = {1: (1, [3], [2]), # restriction 1 cannot travel over 2210 2: (3, 1)}211 212 sequence = jam_solver(g, loads)213 expected_seq = [{2: (3, 2)}, {1: (1, 4)}, {1: (4, 3)}, {2: (2, 1)}]214 assert is_matching(sequence, expected_seq)215 216 concurrent_moves = jam_solver(g, loads, synchronous_moves=True)217 assert concurrent_moves == [{1: (1, 4), 2: (3, 2)}, {2: (2, 1), 1: (4, 3)}]218 219 220def test_energy_and_restrictions_2_loads():221 """ See chart in example/images/tjs_problem_w_distance_restrictions.png222 223 NB: LENGTHS DIFFER FROM IMAGE!224 """225 g = Graph()226 for sed in [227 (1, 2, 1),228 (3, 5, 2), # dead end.229 (1, 3, 7), # this is the most direct route for load 2, but it is 7 long.230 (3, 4, 1), (4, 6, 1), # this could be the shortest path for load 1, but231 # load 1 cannot travel over 4. If it could the path [2,3,4,6] would be 3 long.232 (2, 3, 1), (3, 6, 3), # this is the shortest unrestricted route for load 1: [2,3,6] and it is 4 long.233 (2, 6, 8), # this is the most direct route for load 1 [2,6] but it is 8 long.234 ]:235 g.add_edge(*sed, bidirectional=True)236 237 loads = {1: (2, [6], [4]), # restriction load 1 cannot travel over 4238 2: (3, 1)}239 240 moves = jam_solver(g, loads, synchronous_moves=False)241 242 expected= [243 {2: (3, 4)}, # distance = 1, Load2 moves out of Load1's way.244 {1: (2, 3)}, # distance = 1245 {1: (3, 6)}, # distance = 3246 {2: (4, 3)}, # distance = 1, Load2 moves back onto it's starting point.247 {2: (3, 2)}, # distance = 1248 {2: (2, 1)} # distance = 1249 ] # total distance = (1+3)+(1+1+1+1) = 8250 assert is_matching(moves, expected)251 252 253def test_energy_and_restrictions_3_loads():254 """ See chart in example/images/tjs_problem_w_distance_restrictions.png255 NB: Lengths differ from image!256 """257 g = Graph()258 for sed in [259 260 (1, 2, 1),261 (3, 5, 2), # dead end.262 (1, 3, 7), # this is the most direct route for load 2, but it is 7 long.263 (3, 4, 1), (4, 6, 1), # this could be the shortest path for load 1, but264 # load 1 cannot travel over 4. If it could the path [2,3,4,6] would be 3 long.265 (2, 3, 1), (3, 6, 3), # this is the shortest unrestricted route for load 1: [2,3,6] and it is 4 long.266 (2, 6, 8), # this is the most direct route for load 1 [2,6] but it is 8 long.267 ]:268 g.add_edge(*sed, bidirectional=True)269 270 loads = {1: (2, [6], [4]),271 2: (3, 1),272 3: (5, 3)}273 274 moves = jam_solver(g, loads, synchronous_moves=False)275 assert is_sequence_valid(moves, g)276 assert len(moves) == 7277 expected_moves = [278 {2: (3, 4)}, # distance 1279 {1: (2, 3)}, # distance 1280 {1: (3, 6)}, # distance 3281 {2: (4, 3)}, # distance 1282 {2: (3, 2)}, # distance 1283 {2: (2, 1)}, # distance 1284 {3: (5, 3)} # distance 2285 ] # total distance = (1+3)+(1+1+1+1)+(2) = 10286 assert is_matching(moves, expected_moves), moves287 288 289def test_energy_and_restrictions_3_loads_b():290 """ See chart in example/images/tjs_problem_w_distance_restrictions.png291 NB: Lengths differ from image!292 """293 g = Graph()294 for sed in [295 (1, 2, 1),296 (3, 5, 2), # dead end.297 (1, 3, 7), # this is the most direct route for load 2, but it is 7 long.298 (3, 4, 1), (4, 6, 1), # this could be the shortest path for load 1, but299 # load 1 cannot travel over 4. If it could the path [2,3,4,6] would be 3 long.300 (2, 3, 1), (3, 6, 3), # this is the shortest unrestricted route for load 1: [2,3,6] and it is 4 long.301 (2, 6, 8), # this is the most direct route for load 1 [2,6] but it is 8 long.302 ]:303 g.add_edge(*sed, bidirectional=True)304 305 loads = {1: (2, [6], [4]),306 2: (3, 1),307 3: (4, 3)} # Load 3 blocks load two from moving in here.308 309 moves = jam_solver(g, loads, synchronous_moves=False)310 atomic_moves = [311 {1: (2, 6)}, # 8312 {2: (3, 2)}, # 1313 {2: (2, 1)}, # 1314 {3: (4, 3)} # 1315 ] # total distance 11316 317 assert is_matching(moves, atomic_moves)318 # if load 2 would move to 5, the extra cost is 4, but load 1 could travel via [2,3,6] at cost 4.319 # However the distance LEFT for load 2 would be longer, whereby it is the lesser preferred solution.320 321 322def test_energy_and_restrictions_3_loads_c():323 """ See chart in example/images/tjs_problem_w_distance_restrictions.png324 NB: Lengths differ from image!325 """326 g = Graph()327 for sed in [328 (1, 2, 1),329 (3, 5, 1), # dead end.330 (1, 3, 7), # this is the most direct route for load 2, but it is 7 long.331 (3, 4, 1), (4, 6, 1), # this could be the shortest path for load 1, but332 # load 1 cannot travel over 4. If it could the path [2,3,4,6] would be 3 long.333 (2, 3, 1), (3, 6, 3), # this is the shortest unrestricted route for load 1: [2,3,6] and it is 4 long.334 (2, 6, 8), # this is the most direct route for load 1 [2,6] but it is 8 long.335 ]:336 g.add_edge(*sed, bidirectional=True)337 338 loads = {1: (2, [6], [4]),339 2: (3, 1),340 3: (4, 3)} # Load 3 blocks load two from moving in here.341 342 moves = jam_solver(g, loads, synchronous_moves=False)343 344 expected = [345 {2: (3, 5)}, # load 2 moves out of the way at cost 1346 {1: (2, 3)}, {1: (3, 6)}, # load 1 takes shortest permitted path.347 {2: (5, 3)}, {2: (3, 2)}, {2: (2, 1)}, # load 2 moves to destination.348 {3: (4, 3)} # load 3 moves to destination.349 ] # total distance 9350 assert is_matching(moves, expected), moves351 352 353def test_energy_and_restrictions_2_load_high_detour_costs():354 """ See chart in example/images/tjs_problem_w_distance_restrictions.png """355 g = Graph()356 for sed in [357 (1, 2, 1),358 (1, 3, 70), # this is the most direct route for load 2, but it is 70 long.359 (3, 5, 2), # 5 is a dead end at higher cost than going (3,4)360 (3, 4, 1), (4, 6, 1), # this could be shortest path for load 1, but361 # load 1 cannot travel over 4. If it could the path [2,3,4,6] would be 3 long.362 (2, 3, 1), (3, 6, 3), # this is the shortest unrestricted route for load 1: [2,3,6] and it is 4 long.363 (2, 6, 50), # this is the most direct route for load 1 [2,6] but it is 50 long.364 ]:365 g.add_edge(*sed, bidirectional=True)366 367 loads = {"A": (2, [6], [4]),368 "B": (3, 1)}369 370 moves = jam_solver(g, loads, synchronous_moves=False, return_on_first=False)371 assert is_sequence_valid(moves, g)372 assert len(moves) == 6373 expected = [374 {"B": (3, 4)}, # 2 moves into the dead end.375 {"A": (2, 3)}, # 1 moves into where 2 was.376 {"A": (3, 6)}, # 1 moves onto destination.377 {"B": (4, 3)}, # 2 moves back to origin along path [4,3,2,1]378 {"B": (3, 2)},379 {"B": (2, 1)}380 ]381 assert is_matching(moves, expected), moves382 383 384def test_simple_reroute():385 """ to loads on a collision path. """386 g = Graph()387 for s, e in [(1, 2), (2, 3)]:388 g.add_edge(s, e, 1, bidirectional=True)389 for s, e in [(1, 4), (4, 3)]:390 g.add_edge(s, e, 1, bidirectional=False)391 392 loads = {1: [1, 3], 2: [3, 1]}393 394 concurrent_moves = jam_solver(g, loads, synchronous_moves=True)395 expected = [{1: (1, 4), 2: (3, 2)}, {1: (4, 3), 2: (2, 1)}]396 assert is_matching(concurrent_moves, expected), concurrent_moves397 398 399def test_simple_reroute_2():400 """ to loads on a collision path.401 402 [1]<-->[2]<-->[3]<-->[4]403 | ^404 +---->[5]-->[6]------+405 """406 g = Graph()407 for s, e in [(1, 2), (2, 3), (3, 4)]:408 g.add_edge(s, e, 1, bidirectional=True)409 for s, e in [(1, 5), (5, 6), (6, 4)]:410 g.add_edge(s, e, 1, bidirectional=False)411 412 loads = {1: [1, 4], 2: [4, 1]}413 414 sequence = jam_solver(g, loads, synchronous_moves=False)415 416 atomic_sequence = [{1: (1, 5)}, {1: (5, 6)}, {2: (4, 3)}, {1: (6, 4)}, {2: (3, 2)}, {2: (2, 1)}]417 assert is_matching(sequence, atomic_sequence)418 assert is_sequence_valid(sequence, g)419 420 421def test_simple_reroute_3():422 """ Loop with 6 nodes:423 1 <--> 2 <--> 3 <--> 4 <-- 5 <--> 6 <--> (1)424 """425 g = Graph()426 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)]427 for s, e in edges:428 g.add_edge(s, e, 1, bidirectional=True)429 g.del_edge(4, 5)430 431 loads = {1: [1, 3], 2: [3, 1]}432 433 sequence = jam_solver(g, loads, synchronous_moves=False)434 435 expected = [{1: (1, 6)}, {1: (6, 5)}, {1: (5, 4)}, {2: (3, 2)}, {1: (4, 3)}, {2: (2, 1)}]436 assert is_matching(sequence, expected)437 assert is_sequence_valid(sequence, g)438 439 440def test_shuffle():441 g = Graph()442 edges = [(1, 2), (2, 3), (3, 5), (3, 6), (5, 6), (6, 7), (7, 8)]443 for s, e in edges:444 g.add_edge(s, e, 1, bidirectional=True)445 446 loads = {447 1: (1, 7),448 2: (2, [2, 5]),449 3: (8, [8, 5])450 }451 sequence = jam_solver(g, loads, synchronous_moves=False)452 453 expected = [454 {2: (2, 3)},455 {2: (3, 5)},456 {1: (1, 2)},457 {1: (2, 3)},458 {1: (3, 6)},459 {1: (6, 7)}]460 461 assert is_matching(sequence, expected), sequence462 463 464def test_shuffle2():465 g = Graph()466 edges = [(1, 2), (2, 3), (3, 5), (3, 6), (5, 6), (6, 7), (7, 8)]467 for s, e in edges:468 g.add_edge(s, e, 1, bidirectional=True)469 loads = {470 1: (1, 7),471 2: (2, g.nodes()),472 3: (8, g.nodes())473 }474 475 sequence = jam_solver(g, loads, synchronous_moves=False, return_on_first=True)476 477 expected = [478 {2: (2, 3)},479 {2: (3, 5)},480 {1: (1, 2)},481 {1: (2, 3)},482 {1: (3, 6)},483 {1: (6, 7)}]484 485 assert is_matching(sequence, expected), sequence486 487 488def test_simple_reroute_4():489 """490 1491 / \\492 6---2493 / \\/ \\494 5 - 4 - 3495 """496 g = Graph()497 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (2, 6), (2, 4), (6, 2)]498 for s, e in edges:499 g.add_edge(s, e, 1, bidirectional=True)500 g.del_edge(4, 5)501 502 loads = {1: [1, 4],503 3: [3, 1],504 6: [6, 2]}505 506 sequence = jam_solver(g, loads, synchronous_moves=False)507 assert sequence == [{1: (1, 2)}, {1: (2, 4)}, {3: (3, 2)}, {3: (2, 1)}, {6: (6, 2)}]508 509 g.del_edge(2, 4)510 511 sequence = jam_solver(g, loads, synchronous_moves=False)512 513 expected = [{1: (1, 2)}, {3: (3, 4)}, {1: (2, 3)}, {3: (4, 2)}, {3: (2, 1)}, {6: (6, 2)}, {1: (3, 4)}]514 assert is_matching(sequence, expected)515 516 517def test_clockwise_rotation():518 """ A simple loop of 4 locations, where 3 loads need to move519 clockwise. """520 g = Graph()521 edges = [(1, 2), (2, 3), (3, 4), (4, 1), ]522 for s, e in edges:523 g.add_edge(s, e, 1, bidirectional=True)524 525 loads = {1: [1, 2], 2: [2, 3], 3: [3, 4]} # position 4 is empty.526 527 sequence = jam_solver(g, loads, synchronous_moves=False)528 529 expected = [{3: (3, 4)}, # first move.530 {2: (2, 3)}, # second move.531 {1: (1, 2)}] # last move.532 assert is_matching(sequence, expected), sequence533 534 535def test_small_gridlock():536 """ a grid lock is given, solver solves it."""537 g = Graph()538 edges = [539 (1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (5, 6), (4, 7), (5, 8), (6, 9), (7, 8), (8, 9)540 ]541 for s, e in edges:542 g.add_edge(s, e, 1, bidirectional=True)543 544 loads = {'a': [2, 1], 'b': [5, 2], 'c': [4, 3], 'd': [8], 'e': [1, 9]}545 546 results = []547 548 # TRIAL - 1549 start = process_time()550 moves = jam_solver(g, loads)551 e = process_time() - start552 concurrent = jam_solver(g, loads, synchronous_moves=True)553 d = sum(len(d) for d in moves)554 results.append((e, d, len(concurrent)))555 556 assert d == 11, d557 expected = [{'b': (5, 6), 'c': (4, 5), 'e': (1, 4)},558 {'b': (6, 3), 'c': (5, 6), 'e': (4, 5), 'a': (2, 1)},559 {'b': (3, 2), 'c': (6, 3), 'e': (5, 6)},560 {'e': (6, 9)}]561 assert all(m in expected for m in moves), moves562 563 assert len(concurrent) == 4564 565 # TRIAL - 2566 start = process_time()567 moves = jam_solver(g, loads)568 e = process_time() - start569 concurrent = jam_solver(g, loads, synchronous_moves=True)570 d = sum(len(d) for d in moves)571 results.append((e, d, len(concurrent)))572 573 for e, d, c in results:574 print("duration:", round(e, 4), "| distance", d, "| concurrent moves", c)575 results.clear()576 577 578def test_snake_gridlock():579 """580 A bad route was given to train abcd, and now the train has gridlocked itself.581 582 9 - 10 - 11 - 12583 |584 1 - 2 - 3 - 4 - 5d-> 6c585 ^ |586 | v587 8a - 7b588 589 :return:590 """591 g = Graph()592 edges = [(a, b) for a, b in zip(range(1, 12), range(2, 13)) if (a, b) != (8, 9)]593 for s, e in edges:594 g.add_edge(s, e, 1, bidirectional=True)595 g.add_edge(8, 5, 1, bidirectional=True)596 g.add_edge(5, 9, 1, bidirectional=True)597 598 loads = {'a': [8, 12], 'b': [7, 11], 'c': [6, 10], 'd': [5, 9]}599 sequence = jam_solver(g, loads, synchronous_moves=False, return_on_first=False)600 601 sync_moves = moves_to_synchronous_moves(sequence, check_user_input(g, loads))602 603 expected = [{'d': (5, 4)}, # d goes one step back.604 {'a': (8, 5)}, # a moves forward towards its destination.605 {'b': (7, 8)}, # b moves forward to it's destination.606 {'a': (5, 9)},607 {'b': (8, 5)},608 {'a': (9, 10)},609 {'b': (5, 9)},610 {'c': (6, 5)}, # c moves forward.611 {'a': (10, 11)},612 {'b': (9, 10)},613 {'c': (5, 9)},614 {'d': (4, 5)},615 {'a': (11, 12)},616 {'b': (10, 11)},617 {'c': (9, 10)},618 {'d': (5, 9)}] # d does a left turn (shortcut).619 assert is_matching(sequence, expected)620 621 expected = [{'d': (5, 4), 'a': (8, 5), 'b': (7, 8)},622 {'a': (5, 9), 'b': (8, 5)},623 {'a': (9, 10), 'b': (5, 9), 'c': (6, 5)},624 {'a': (10, 11), 'b': (9, 10), 'c': (5, 9), 'd': (4, 5)},625 {'a': (11, 12), 'b': (10, 11), 'c': (9, 10), 'd': (5, 9)}]626 assert is_matching(expected, sync_moves), sync_moves627 628 629def test_5x5_graph():630 g = graph5x5()631 loads = {'a': [6], 'b': [11, 1], 'c': [16, 2], 'd': [17, 4], 'e': [19, 5], 'f': [20, 3]}632 633 sequence = jam_solver(g, loads, return_on_first=True, timeout=30_000)634 assert is_sequence_valid(sequence, g)635 636 637def test_2_trains():638 """639 two trains of loads are approaching each other.640 train 123 going from 1 to 14641 train 4567 going from 14 to 1.642 643 At intersection 4 train 123 can be broken apart and644 buffered, so that train 4567 can pass.645 646 The reverse (buffering train 4567) is not possible.647 648 [1]--[2]--[3]--[4]--[5]--[9]--[10]--[11]--[12]--[13]--[14]649 +---[6]---+650 +---[7]---+651 +---[8]---+652 """653 g = Graph()654 edges = [655 (1, 2),656 (2, 3),657 (3, 4),658 (4, 5), (4, 6), (4, 7), (4, 8),659 (5, 9), (6, 9), (7, 9), (8, 9),660 (9, 10),661 (10, 11),662 (11, 12),663 (12, 13),664 (13, 14),665 ]666 for s, e in edges:667 g.add_edge(s, e, 1, bidirectional=True)668 669 loads = {670 41: [1, 12],671 42: [2, 13],672 43: [3, 14],673 44: [11, 1],674 45: [12, 2],675 46: [13, 3],676 47: [14, 4],677 }678 679 sequence = jam_solver(g, loads, return_on_first=True, timeout=180_000)680 assert is_sequence_valid(sequence, g)681 expected = [{43: (3, 4)}, {43: (4, 6)}, {42: (2, 3)}, {42: (3, 4)}, {42: (4, 7)}, {41: (1, 2)},682 {41: (2, 3)}, {41: (3, 4)}, {41: (4, 5)}, {44: (11, 10)}, {44: (10, 9)}, {44: (9, 8)},683 {44: (8, 4)}, {44: (4, 3)}, {44: (3, 2)}, {44: (2, 1)}, {45: (12, 11)}, {45: (11, 10)},684 {45: (10, 9)}, {45: (9, 8)}, {45: (8, 4)}, {45: (4, 3)}, {45: (3, 2)}, {46: (13, 12)},685 {46: (12, 11)}, {46: (11, 10)}, {46: (10, 9)}, {46: (9, 8)}, {46: (8, 4)}, {46: (4, 3)},686 {47: (14, 13)}, {47: (13, 12)}, {47: (12, 11)}, {47: (11, 10)}, {47: (10, 9)}, {47: (9, 8)},687 {47: (8, 4)}, {43: (6, 9)}, {43: (9, 10)}, {43: (10, 11)}, {43: (11, 12)}, {43: (12, 13)},688 {43: (13, 14)}, {42: (7, 9)}, {42: (9, 10)}, {42: (10, 11)}, {42: (11, 12)}, {42: (12, 13)},689 {41: (5, 9)}, {41: (9, 10)}, {41: (10, 11)}, {41: (11, 12)}]690 assert is_matching(expected, sequence), sequence691 692 693def test_3_trains():694 """695 Two trains (abc & d) are going east. One train is going west (efgh).696 697 a-b-c--0-0-0--d--0--e-f-g-h698 \\--0---/ \\0-/699 700 1-2-3--4-5-6--7--8---9-10-11-12701 \\--13--/ \\14-/702 703 The solution is given by side stepping abc (on 4,5,6) & d (on 8)704 and letting efgh pass on (12, 11, 10, 9, 14, 7, 13, 3, 2, 1)705 """706 g = Graph()707 edges = [708 (3, 13), (13, 7), (7, 14), (14, 9)709 ]710 for a, b in zip(range(1, 12), range(2, 13)):711 edges.append((a, b))712 for s, e in edges:713 g.add_edge(s, e, 1, bidirectional=True)714 715 loads = {716 'a': [1, 10], 'b': [2, 11], 'c': [3, 12], 'd': [8, 9], # east bound717 'e': [9, 1], 'f': [10, 2], 'g': [11, 3], 'h': [12, 4] # west bound718 }719 720 sequence = jam_solver(g, loads, return_on_first=True,timeout=40_000)721 assert sequence is not None722 723 724def test_loop_9():725 g = Graph(726 from_list=[(a, b, 1) for a, b in zip(range(1, 8), range(2, 9))] + [(8, 1, 1)]727 )728 loads = {1: [1, 2], 2: [3, 4], 3: [5, 6], 4: [7, 8]}729 solution = jam_solver(g, loads, return_on_first=True)730 731 assert is_sequence_valid(solution, g)732 expected = [{4: (7, 8), 3: (5, 6), 2: (3, 4), 1: (1, 2)}]733 assert solution == expected734 735 sync_moves = jam_solver(g, loads, return_on_first=True, synchronous_moves=True)736 assert sync_moves == [{4: (7, 8), 3: (5, 6), 2: (3, 4), 1: (1, 2)}]737 738 739def test_loop_52():740 g = Graph(741 from_list=[742 (52, 1, 1), (1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 5, 1), (5, 6, 1), (6, 7, 1), (7, 8, 1), (8, 9, 1),743 (9, 10, 1), (10, 11, 1), (11, 12, 1), (12, 13, 1), (13, 14, 1), (14, 15, 1), (15, 16, 1), (16, 17, 1),744 (17, 18, 1), (18, 19, 1), (19, 20, 1), (20, 21, 1), (21, 22, 1), (22, 23, 1), (23, 24, 1), (24, 25, 1),745 (25, 26, 1), (26, 27, 1), (27, 28, 1), (28, 29, 1), (29, 30, 1), (30, 31, 1), (31, 32, 1), (32, 33, 1),746 (33, 34, 1), (34, 35, 1), (35, 36, 1), (36, 37, 1), (37, 38, 1), (38, 39, 1), (39, 40, 1), (40, 41, 1),747 (41, 42, 1), (42, 43, 1), (43, 44, 1), (44, 45, 1), (45, 46, 1), (46, 47, 1), (47, 48, 1), (48, 49, 1),748 (49, 50, 1), (50, 51, 1), (51, 52, 1)749 ]750 )751 752 loads = {753 98: [52, 1], 55: [2, 3], 56: [3, 4], 57: [4, 5], 58: [5, 6], 59: [6, 7], 60: [7, 8], 61: [9, 10], 62: [10, 11],754 63: [11, 12], 64: [12, 13], 65: [14, 15], 66: [15, 16], 67: [16, 17], 68: [17, 18], 69: [18, 19], 70: [19, 20],755 71: [21, 22], 72: [22, 23], 73: [23, 24], 74: [24, 25], 75: [25, 26], 76: [26, 27], 77: [28, 29], 78: [29, 30],756 79: [30, 31], 80: [31, 32], 81: [32, 33], 82: [33, 34], 83: [35, 36], 84: [36, 37], 85: [37, 38], 86: [38, 39],757 87: [39, 40], 88: [40, 41], 89: [42, 43], 90: [43, 44], 91: [44, 45], 92: [45, 46], 93: [46, 47],758 94: [47, 48], 95: [49, 50], 96: [50, 51], 97: [51, 52]759 }760 761 solution = jam_solver(g, loads, return_on_first=True, timeout=1_000)762 assert is_sequence_valid(solution, g)763 764 loads2 = check_user_input(g, loads)765 concurrent_moves = moves_to_synchronous_moves(solution, loads2)766 assert concurrent_moves == [767 {98: (52, 1), 60: (7, 8), 59: (6, 7), 58: (5, 6), 57: (4, 5), 56: (3, 4), 55: (2, 3), 64: (12, 13),768 63: (11, 12), 62: (10, 11), 61: (9, 10), 70: (19, 20), 69: (18, 19), 68: (17, 18), 67: (16, 17), 66: (15, 16),769 65: (14, 15), 76: (26, 27), 75: (25, 26), 74: (24, 25), 73: (23, 24), 72: (22, 23), 71: (21, 22), 82: (33, 34),770 81: (32, 33), 80: (31, 32), 79: (30, 31), 78: (29, 30), 77: (28, 29), 88: (40, 41), 87: (39, 40), 86: (38, 39),771 85: (37, 38), 84: (36, 37), 83: (35, 36), 94: (47, 48), 93: (46, 47), 92: (45, 46), 91: (44, 45), 90: (43, 44),772 89: (42, 43), 97: (51, 52), 96: (50, 51), 95: (49, 50)}773 ], "something is wrong. All moves CAN happen at the same time."774 775 776def test_simple_failed_path():777 """ two colliding loads with no solution """778 g = Graph()779 for s, e in [(1, 2), (2, 3)]:780 g.add_edge(s, e, 1, bidirectional=True)781 782 loads = {1: [1, 3], 2: [3, 1]}783 784 try:785 _ = jam_solver(g, loads, return_on_first=True, timeout=200)786 assert False, "The problem is unsolvable."787 except NoSolution:788 assert True789 790 791def test_incomplete_graph():792 """ two loads with an incomplete graph making the problem unsolvable """793 g = Graph()794 for s, e in [(1, 2), (2, 3)]:795 g.add_edge(s, e, 1, bidirectional=True)796 g.add_node(5)797 798 loads = {1: [1, 5], 2: [5, 1]}799 800 try:801 _ = jam_solver(g, loads, timeout=200)802 assert False, "There is no path."803 except UnSolvable as e:804 assert str(e) == 'load 1 has no path from 1 to 5'805 806def test_timeout():807 """ Timeout prevents all end states from being recorded, ensure that a solution is still found """808 edges = {1: {2: 1, 41: 2, 63: 2},809 41: {42: 1, 1: 2, 63: 2},810 65: {1: 2, 41: 2, 63: 2},811 2: {1: 1, 3: 1},812 3: {2: 1, 4: 1},813 4: {3: 1, 5: 1},814 5: {4: 1},815 42: {41: 1, 43: 1},816 43: {42: 1, 44: 1},817 44: {43: 1, 45: 1},818 45: {44: 1},819 63: {'pseudo_L48': 1, 'pseudo_L33': 1, 'pseudo_L35': 1, 'pseudo_L55': 1}}820 821 subgraph_2 = Graph(from_dict=edges)822 823 loads_for_jam_solver = {'L23': (41, [3, 4, 41, 44, 1, 2]),824 'L48': (42, ['pseudo_L48']),825 'L33': (43, ['pseudo_L33']),826 'L8': (44, [3, 4, 41, 44, 1, 2]),827 'L35': (45, ['pseudo_L35']),828 'L5': (3, [3, 4, 41, 44, 1, 2]),829 'L15': (4, [3, 4, 41, 44, 1, 2]),830 'L55': (5, ['pseudo_L55'])}831 832 moves = jam_solver(graph=subgraph_2, loads=loads_for_jam_solver, timeout=5000, synchronous_moves=False)833 834 expected_moves = [{'L23': (41, 1)}, {'L48': (42, 41)}, {'L48': (41, 63)}, {'L48': (63, 'pseudo_L48')},835 {'L33': (43, 42)}, {'L33': (42, 41)}, {'L33': (41, 63)}, {'L33': (63, 'pseudo_L33')},836 {'L5': (3, 2)}, {'L15': (4, 3)}, {'L55': (5, 4)}, {'L23': (1, 41)}, {'L5': (2, 1)},837 {'L15': (3, 2)}, {'L55': (4, 3)}, {'L23': (41, 42)}, {'L23': (42, 43)}, {'L5': (1, 41)},838 {'L15': (2, 1)}, {'L55': (3, 2)}, {'L5': (41, 42)}, {'L15': (1, 41)}, {'L55': (2, 1)},839 {'L55': (1, 63)}, {'L55': (63, 'pseudo_L55')}, {'L15': (41, 1)}, {'L5': (42, 41)},840 {'L23': (43, 42)}, {'L15': (1, 2)}, {'L5': (41, 1)}, {'L23': (42, 41)}, {'L8': (44, 43)},841 {'L35': (45, 44)}, {'L8': (43, 42)}, {'L35': (44, 43)}, {'L15': (2, 3)}, {'L5': (1, 2)},842 {'L15': (3, 4)}, {'L5': (2, 3)}, {'L23': (41, 1)}, {'L23': (1, 2)}, {'L8': (42, 41)},843 {'L35': (43, 42)}, {'L8': (41, 1)}, {'L35': (42, 41)}, {'L35': (41, 63)},844 {'L35': (63, 'pseudo_L35')}]845 846 for index in range(5):847 assert moves[index] == expected_moves[index]848