Sat Feb 15 19:18:17 2025 graph_dist_test(): python version: 3.10.12 numpy version: 1.26.4 Test graph_dist(), which implements graph algorithms. graph_dist_all_test(): graph_dist_all() computes the distance between all pairs of nodes. Immediate node distance matrix: [[ 0. 2. 5. 1. inf] [ 2. 0. 3. 4. inf] [ 6. 3. 0. inf inf] [ 1. 4. inf 0. 5.] [inf inf inf 5. 0.]] Total node distance matrix: [[ 0. 2. 5. 1. 6.] [ 2. 0. 3. 3. 8.] [ 5. 3. 0. 6. 11.] [ 1. 3. 6. 0. 5.] [ 6. 8. 11. 5. 0.]] graph_dist_check_test(): graph_dist_check() checks a distance matrix. The distance matrix passed all tests. graph_dist_min_span_tree_test(): graph_dist_min_span_tree() finds a minimum spanning tree. The graph: [[ 0. 100. 125. 120. 110.] [100. 0. 40. 65. 60.] [125. 40. 0. 45. 55.] [120. 65. 45. 0. 50.] [110. 60. 55. 50. 0.]] The minimal spanning tree: 0 0 1 100 1 1 2 40 2 2 3 45 3 3 4 50 The length of the minimal tree is 235.0 graph_dist_min_span_tree_alternate_test() graph_dist_min_span_tree() finds a minimum spanning tree. Read distance data for 57 cities from file. The weighted tree: 0 0 10 33 1 1 3 152 2 2 18 80 3 3 33 205 4 4 40 207 5 5 35 216 6 6 10 186 7 7 40 444 8 8 37 155 9 9 29 111 10 10 52 110 11 11 9 106 12 12 54 268 13 13 7 101 14 14 36 135 15 15 52 57 16 16 44 170 17 17 21 116 18 18 41 200 19 19 45 498 20 20 12 242 21 21 9 109 22 22 30 213 23 23 1 316 24 24 25 149 25 25 53 63 26 26 15 84 27 27 30 139 28 28 46 405 29 29 16 125 30 30 33 222 31 31 8 91 32 32 14 253 33 33 16 160 34 34 22 187 35 35 38 92 36 36 53 167 37 37 49 73 38 38 2 97 39 39 28 390 40 40 36 390 41 41 0 105 42 42 47 176 43 43 55 263 44 44 24 128 45 45 7 458 46 46 42 669 47 47 48 288 48 48 19 322 49 49 44 101 50 50 24 140 51 51 23 200 52 52 17 110 53 53 56 139 54 54 50 181 55 55 2 38 The length of the minimal tree is 10835.0 graph_dist_min_span_tree2_test(): graph_dist_min_span_tree() finds a minimum spanning tree. The graph: [[ 0. 100. 125. 120. 110.] [100. 0. 40. 65. 60.] [125. 40. 0. 45. 55.] [120. 65. 45. 0. 50.] [110. 60. 55. 50. 0.]] The minimal spanning tree: 0 1 2 40 1 2 3 45 2 3 4 50 3 1 0 100 The length of the minimal tree is 235 graph_dist_min_span_tree3_test(): graph_dist_min_span_tree3() finds a minimum spanning tree. The graph: [[ 0. 100. 125. 120. 110.] [100. 0. 40. 65. 60.] [125. 40. 0. 45. 55.] [120. 65. 45. 0. 50.] [110. 60. 55. 50. 0.]] The minimal spanning tree: 0 0 1 100 1 1 2 40 2 2 3 45 3 3 4 50 The length of the minimal tree is 235.0 graph_dist_one_test(): graph_dist_one() computes the distance from one node to all others in a graph. Edge Distance Matrix: [[ 0. 1. 3. inf inf] [ 2. 0. 1. inf 2.] [inf inf 0. 2. 3.] [inf inf 1. 0. inf] [ 1. 3. inf 6. 0.]] The starting node is 4 Node Distance Path Idad 0 1 1 4 1 2 2 0 2 3 3 1 3 5 4 2 4 0 0 4 Here are the paths for each node: 0 4 1 0 4 2 1 0 4 3 2 1 0 4 4 graph_dist_pairing_greedy_test(): graph_dist_pairing_greedy() tries to minimize the total distance in a pairing of black and red nodes. Try to find a pairing of two sets of nodes with a low discrepancy. Relative tolerance for step decrease = 0.05 Maximum number of steps = 10 X range is 0.0 to 10.0 Y range is 3.0 to 5.0 Initial black node coordinates: I Black X Y 0 0 6.00458 3.30019 1 1 9.53858 4.13953 2 2 5.17503 4.10094 3 3 8.53885 3.59908 4 4 0.982837 3.64061 5 5 1.87384 3.89341 6 6 7.90854 3.63316 7 7 2.56906 4.4317 8 8 0.200746 4.6681 9 9 6.86558 4.9437 10 10 3.7376 4.87511 11 11 8.3068 4.55083 12 12 7.17214 3.9702 13 13 4.14405 3.08127 14 14 5.37091 3.55022 Initial red node coordinates: I Red X Y 0 0 9.86432 4.69268 1 1 6.33104 3.52551 2 2 8.35237 3.95377 3 3 4.53269 3.61072 4 4 9.20457 4.57629 5 5 8.95484 3.61441 6 6 6.68491 4.3349 7 7 6.09511 3.95807 8 8 8.44204 4.76688 9 9 5.60735 3.71838 10 10 7.13787 3.78296 11 11 8.55535 4.94173 12 12 3.06498 4.10716 13 13 0.365085 4.98402 14 14 5.54986 3.35129 Initial pairing of nodes: I Black Red Distance 0 0 0 4.10324 1 1 1 3.26578 2 2 2 3.18075 3 3 3 4.00617 4 4 4 8.2748 5 5 5 7.0865 6 6 6 1.41057 7 7 7 3.55772 8 8 8 8.24188 9 9 9 1.75629 10 10 10 3.57136 11 11 11 0.463233 12 12 12 4.10945 13 13 13 4.23096 14 14 14 0.267577 Total discrepancy of initial pairing = 57.5262893321093 On step 0 discrepancy = 22.406690771281752 Swaps made was 31 On step 1 discrepancy = 21.85573224323659 Swaps made was 10 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.02458901823875369 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 0 0 6.00458 3.30019 1 1 9.53858 4.13953 2 2 5.17503 4.10094 3 3 8.53885 3.59908 4 4 0.982837 3.64061 5 5 1.87384 3.89341 6 6 7.90854 3.63316 7 7 2.56906 4.4317 8 8 0.200746 4.6681 9 9 6.86558 4.9437 10 10 3.7376 4.87511 11 11 8.3068 4.55083 12 12 7.17214 3.9702 13 13 4.14405 3.08127 14 14 5.37091 3.55022 Final red node coordinates: I Red X Y 0 1 9.86432 4.69268 1 0 6.33104 3.52551 2 7 8.35237 3.95377 3 2 4.53269 3.61072 4 3 9.20457 4.57629 5 12 8.95484 3.61441 6 5 6.68491 4.3349 7 6 6.09511 3.95807 8 13 8.44204 4.76688 9 11 5.60735 3.71838 10 8 7.13787 3.78296 11 4 8.55535 4.94173 12 10 3.06498 4.10716 13 14 0.365085 4.98402 14 9 5.54986 3.35129 Final pairing of nodes: I Black Red Distance 0 0 1 0.396664 1 1 0 0.641935 2 2 7 0.931108 3 3 2 0.400722 4 4 3 3.54998 5 5 12 1.21017 6 6 5 1.04646 7 7 6 4.11699 8 8 13 0.35611 9 9 11 1.68977 10 10 8 4.70568 11 11 4 0.898128 12 12 10 0.190352 13 13 14 1.43151 14 14 9 0.290145 Total discrepancy of final pairing = 21.85573224323659 Try reversing NODER! Initial black node coordinates: I Black X Y 0 0 6.00458 3.30019 1 1 9.53858 4.13953 2 2 5.17503 4.10094 3 3 8.53885 3.59908 4 4 0.982837 3.64061 5 5 1.87384 3.89341 6 6 7.90854 3.63316 7 7 2.56906 4.4317 8 8 0.200746 4.6681 9 9 6.86558 4.9437 10 10 3.7376 4.87511 11 11 8.3068 4.55083 12 12 7.17214 3.9702 13 13 4.14405 3.08127 14 14 5.37091 3.55022 Initial red node coordinates: I Red X Y 0 9 9.86432 4.69268 1 14 6.33104 3.52551 2 10 8.35237 3.95377 3 4 4.53269 3.61072 4 8 9.20457 4.57629 5 11 8.95484 3.61441 6 13 6.68491 4.3349 7 6 6.09511 3.95807 8 5 8.44204 4.76688 9 12 5.60735 3.71838 10 3 7.13787 3.78296 11 2 8.55535 4.94173 12 7 3.06498 4.10716 13 0 0.365085 4.98402 14 1 5.54986 3.35129 Initial pairing of nodes: I Black Red Distance 0 0 9 0.576778 1 1 14 4.06586 2 2 10 1.98843 3 3 4 1.18242 4 4 8 7.54375 5 5 11 6.76326 6 6 13 7.66345 7 7 6 4.11699 8 8 5 8.81728 9 9 12 3.89158 10 10 3 1.49361 11 11 2 0.598793 12 12 7 1.0771 13 13 0 5.9429 14 14 1 0.960452 Total discrepancy of initial pairing = 56.68264435303149 On step 0 discrepancy = 33.044641949212405 Swaps made was 96 On step 1 discrepancy = 21.575876399884947 Swaps made was 19 On step 2 discrepancy = 21.37233248832812 Swaps made was 3 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.00943386529401482 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 0 0 6.00458 3.30019 1 1 9.53858 4.13953 2 2 5.17503 4.10094 3 3 8.53885 3.59908 4 4 0.982837 3.64061 5 5 1.87384 3.89341 6 6 7.90854 3.63316 7 7 2.56906 4.4317 8 8 0.200746 4.6681 9 9 6.86558 4.9437 10 10 3.7376 4.87511 11 11 8.3068 4.55083 12 12 7.17214 3.9702 13 13 4.14405 3.08127 14 14 5.37091 3.55022 Final red node coordinates: I Red X Y 0 1 9.86432 4.69268 1 0 6.33104 3.52551 2 7 8.35237 3.95377 3 5 4.53269 3.61072 4 3 9.20457 4.57629 5 12 8.95484 3.61441 6 2 6.68491 4.3349 7 6 6.09511 3.95807 8 13 8.44204 4.76688 9 11 5.60735 3.71838 10 8 7.13787 3.78296 11 4 8.55535 4.94173 12 10 3.06498 4.10716 13 14 0.365085 4.98402 14 9 5.54986 3.35129 Final pairing of nodes: I Black Red Distance 0 0 1 0.396664 1 1 0 0.641935 2 2 7 0.931108 3 3 5 0.416272 4 4 3 3.54998 5 5 12 1.21017 6 6 2 0.547515 7 7 6 4.11699 8 8 13 0.35611 9 9 11 1.68977 10 10 8 4.70568 11 11 4 0.898128 12 12 10 0.190352 13 13 14 1.43151 14 14 9 0.290145 Total discrepancy of final pairing = 21.37233248832812 graph_dist_test(): Normal end of execution. Sat Feb 15 19:18:17 2025