15-May-2025 06:26:00 graph_dist_test(): MATLAB/Octave version 6.4.0 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 6 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: 1 1 2 100 2 2 3 40 3 3 4 45 4 4 5 50 The length of the minimal tree is 235 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: 1 1 11 33 2 2 4 152 3 3 19 80 4 4 34 205 5 5 41 207 6 6 36 216 7 7 11 186 8 8 41 444 9 9 38 155 10 10 30 111 11 11 53 110 12 12 10 106 13 13 55 268 14 14 8 101 15 15 37 135 16 16 53 57 17 17 45 170 18 18 22 116 19 19 42 200 20 20 46 498 21 21 13 242 22 22 10 109 23 23 31 213 24 24 2 316 25 25 26 149 26 26 54 63 27 27 16 84 28 28 31 139 29 29 47 405 30 30 17 125 31 31 34 222 32 32 9 91 33 33 15 253 34 34 17 160 35 35 23 187 36 36 39 92 37 37 54 167 38 38 50 73 39 39 3 97 40 40 29 390 41 41 37 390 42 42 1 105 43 43 48 176 44 44 56 263 45 45 25 128 46 46 8 458 47 47 43 669 48 48 49 288 49 49 20 322 50 50 45 101 51 51 25 140 52 52 24 200 53 53 18 110 54 54 57 139 55 55 51 181 56 56 3 38 The length of the minimal tree is 10835 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: 1 2 3 40 2 3 4 45 3 4 5 50 4 2 1 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: 1 1 2 100 2 2 3 40 3 3 4 45 4 4 5 50 The length of the minimal tree is 235 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 5 Node Distance Path Idad 1 1 2 5 2 2 3 1 3 3 4 2 4 5 5 3 5 0 1 5 Here are the paths for each node: 1 5 2 1 5 3 2 1 5 4 3 2 1 5 5 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 to 10 Y range is 3 to 5 Initial black node coordinates: I Black X Y 1 1 2.89863 4.66726 2 2 2.0972 3.01623 3 3 5.14697 3.42396 4 4 1.17208 4.06143 5 5 6.93629 3.82042 6 6 3.82132 3.84573 7 7 1.5147 3.67272 8 8 2.17081 4.36404 9 9 7.11492 3.96738 10 10 2.64326 3.92362 11 11 1.79376 3.1393 12 12 5.17534 4.17072 13 13 9.4856 4.2962 14 14 9.90279 4.76161 15 15 6.1551 4.76235 Initial red node coordinates: I Red X Y 1 1 0.288662 4.82271 2 2 4.68265 3.52711 3 3 9.47751 4.24469 4 4 3.9096 3.8167 5 5 7.06094 3.79806 6 6 7.30148 3.3781 7 7 5.67283 4.56588 8 8 8.86838 4.86788 9 9 7.70317 3.40733 10 10 5.73378 4.41675 11 11 9.14437 4.52724 12 12 2.17855 3.9382 13 13 6.04079 4.32613 14 14 0.415442 3.5637 15 15 3.79732 4.42183 Initial pairing of nodes: I Black Red Distance 1 1 1 2.61459 2 2 2 2.63544 3 3 3 4.40763 4 4 4 2.74843 5 5 5 0.126649 6 6 6 3.51144 7 7 7 4.25297 8 8 8 6.71649 9 9 9 0.812218 10 10 10 3.12961 11 11 11 7.4805 12 12 12 3.00579 13 13 13 3.44494 14 14 14 9.56267 15 15 15 2.38225 Total discrepancy of initial pairing = 56.8316 On step 1 discrepancy = 22.2317 Swaps made was 58 On step 2 discrepancy = 21.0122 Swaps made was 9 On step 3 discrepancy = 20.9536 Swaps made was 2 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.00279158 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 2.89863 4.66726 2 2 2.0972 3.01623 3 3 5.14697 3.42396 4 4 1.17208 4.06143 5 5 6.93629 3.82042 6 6 3.82132 3.84573 7 7 1.5147 3.67272 8 8 2.17081 4.36404 9 9 7.11492 3.96738 10 10 2.64326 3.92362 11 11 1.79376 3.1393 12 12 5.17534 4.17072 13 13 9.4856 4.2962 14 14 9.90279 4.76161 15 15 6.1551 4.76235 Final red node coordinates: I Red X Y 1 7 0.288662 4.82271 2 2 4.68265 3.52711 3 6 9.47751 4.24469 4 1 3.9096 3.8167 5 5 7.06094 3.79806 6 4 7.30148 3.3781 7 14 5.67283 4.56588 8 15 8.86838 4.86788 9 9 7.70317 3.40733 10 10 5.73378 4.41675 11 12 9.14437 4.52724 12 13 2.17855 3.9382 13 3 6.04079 4.32613 14 11 0.415442 3.5637 15 8 3.79732 4.42183 Final pairing of nodes: I Black Red Distance 1 1 7 2.77605 2 2 2 2.63544 3 3 6 2.155 4 4 1 1.16618 5 5 5 0.126649 6 6 4 0.0929259 7 7 14 1.10465 8 8 15 1.62754 9 9 9 0.812218 10 10 10 3.12961 11 11 12 0.886744 12 12 13 0.879291 13 13 3 0.0521486 14 14 11 0.793804 15 15 8 2.71532 Total discrepancy of final pairing = 20.9536 Reversing NODER! Initial black node coordinates: I Black X Y 1 1 2.89863 4.66726 2 2 2.0972 3.01623 3 3 5.14697 3.42396 4 4 1.17208 4.06143 5 5 6.93629 3.82042 6 6 3.82132 3.84573 7 7 1.5147 3.67272 8 8 2.17081 4.36404 9 9 7.11492 3.96738 10 10 2.64326 3.92362 11 11 1.79376 3.1393 12 12 5.17534 4.17072 13 13 9.4856 4.2962 14 14 9.90279 4.76161 15 15 6.1551 4.76235 Initial red node coordinates: I Red X Y 1 8 0.288662 4.82271 2 11 4.68265 3.52711 3 3 9.47751 4.24469 4 13 3.9096 3.8167 5 12 7.06094 3.79806 6 10 7.30148 3.3781 7 9 5.67283 4.56588 8 15 8.86838 4.86788 9 14 7.70317 3.40733 10 4 5.73378 4.41675 11 5 9.14437 4.52724 12 1 2.17855 3.9382 13 6 6.04079 4.32613 14 2 0.415442 3.5637 15 7 3.79732 4.42183 Initial pairing of nodes: I Black Red Distance 1 1 8 5.97312 2 2 11 7.20734 3 3 3 4.40763 4 4 13 4.8759 5 5 12 4.75919 6 6 10 1.99589 7 7 9 6.19417 8 8 15 1.62754 9 9 14 6.71163 10 10 4 1.27084 11 11 5 5.30822 12 12 1 4.92998 13 13 6 2.36924 14 14 2 5.36412 15 15 7 0.52076 Total discrepancy of initial pairing = 63.5156 On step 1 discrepancy = 36.3473 Swaps made was 55 On step 2 discrepancy = 21.7588 Swaps made was 44 On step 3 discrepancy = 20.9536 Swaps made was 10 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.0370084 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 2.89863 4.66726 2 2 2.0972 3.01623 3 3 5.14697 3.42396 4 4 1.17208 4.06143 5 5 6.93629 3.82042 6 6 3.82132 3.84573 7 7 1.5147 3.67272 8 8 2.17081 4.36404 9 9 7.11492 3.96738 10 10 2.64326 3.92362 11 11 1.79376 3.1393 12 12 5.17534 4.17072 13 13 9.4856 4.2962 14 14 9.90279 4.76161 15 15 6.1551 4.76235 Final red node coordinates: I Red X Y 1 7 0.288662 4.82271 2 2 4.68265 3.52711 3 6 9.47751 4.24469 4 1 3.9096 3.8167 5 5 7.06094 3.79806 6 4 7.30148 3.3781 7 14 5.67283 4.56588 8 15 8.86838 4.86788 9 9 7.70317 3.40733 10 10 5.73378 4.41675 11 12 9.14437 4.52724 12 13 2.17855 3.9382 13 3 6.04079 4.32613 14 11 0.415442 3.5637 15 8 3.79732 4.42183 Final pairing of nodes: I Black Red Distance 1 1 7 2.77605 2 2 2 2.63544 3 3 6 2.155 4 4 1 1.16618 5 5 5 0.126649 6 6 4 0.0929259 7 7 14 1.10465 8 8 15 1.62754 9 9 9 0.812218 10 10 10 3.12961 11 11 12 0.886744 12 12 13 0.879291 13 13 3 0.0521486 14 14 11 0.793804 15 15 8 2.71532 Total discrepancy of final pairing = 20.9536 graph_dist_test(): Normal end of execution. 15-May-2025 06:26:00