06-Nov-2024 17:46:50 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 7.98755 4.88579 2 2 6.93399 4.43071 3 3 6.95934 4.53244 4 4 8.02592 3.41271 5 5 1.86817 3.23245 6 6 4.98276 3.60803 7 7 0.829545 3.05568 8 8 5.73222 4.19272 9 9 1.25563 3.1672 10 10 5.20853 4.07286 11 11 2.64094 3.56328 12 12 2.65534 3.55146 13 13 1.18498 3.26756 14 14 2.14477 3.11453 15 15 0.204171 3.22061 Initial red node coordinates: I Red X Y 1 1 0.712831 4.29938 2 2 6.07577 3.61565 3 3 7.74265 4.36365 4 4 9.86258 4.01324 5 5 3.47078 3.42169 6 6 5.68325 4.31983 7 7 9.92087 4.41104 8 8 3.1673 4.2156 9 9 4.07148 3.88305 10 10 0.267277 4.49449 11 11 8.70591 3.2959 12 12 2.09401 3.9043 13 13 9.16946 4.69834 14 14 5.5566 4.45455 15 15 5.77646 3.4785 Initial pairing of nodes: I Black Red Distance 1 1 1 7.29831 2 2 2 1.18358 3 3 3 0.801293 4 4 4 1.93234 5 5 5 1.61374 6 6 6 0.998674 7 7 7 9.1918 8 8 8 2.56501 9 9 9 2.90541 10 10 10 4.95921 11 11 11 6.07086 12 12 12 0.66301 13 13 13 8.11166 14 14 14 3.66555 15 15 15 5.57825 Total discrepancy of initial pairing = 57.5387 On step 1 discrepancy = 33.0725 Swaps made was 89 On step 2 discrepancy = 27.0062 Swaps made was 16 On step 3 discrepancy = 27.0062 Swaps made was 0 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 7.98755 4.88579 2 2 6.93399 4.43071 3 3 6.95934 4.53244 4 4 8.02592 3.41271 5 5 1.86817 3.23245 6 6 4.98276 3.60803 7 7 0.829545 3.05568 8 8 5.73222 4.19272 9 9 1.25563 3.1672 10 10 5.20853 4.07286 11 11 2.64094 3.56328 12 12 2.65534 3.55146 13 13 1.18498 3.26756 14 14 2.14477 3.11453 15 15 0.204171 3.22061 Final red node coordinates: I Red X Y 1 13 0.712831 4.29938 2 3 6.07577 3.61565 3 7 7.74265 4.36365 4 11 9.86258 4.01324 5 5 3.47078 3.42169 6 2 5.68325 4.31983 7 1 9.92087 4.41104 8 4 3.1673 4.2156 9 8 4.07148 3.88305 10 6 0.267277 4.49449 11 14 8.70591 3.2959 12 9 2.09401 3.9043 13 12 9.16946 4.69834 14 15 5.5566 4.45455 15 10 5.77646 3.4785 Final pairing of nodes: I Black Red Distance 1 1 13 1.19669 2 2 3 0.811438 3 3 7 2.96402 4 4 11 0.689943 5 5 5 1.61374 6 6 2 1.09304 7 7 1 1.24917 8 8 4 4.13426 9 9 8 2.18028 10 10 6 0.535127 11 11 14 3.04884 12 12 9 1.45444 13 13 12 1.10985 14 14 15 3.64989 15 15 10 1.27544 Total discrepancy of final pairing = 27.0062 Reversing NODER! Initial black node coordinates: I Black X Y 1 1 7.98755 4.88579 2 2 6.93399 4.43071 3 3 6.95934 4.53244 4 4 8.02592 3.41271 5 5 1.86817 3.23245 6 6 4.98276 3.60803 7 7 0.829545 3.05568 8 8 5.73222 4.19272 9 9 1.25563 3.1672 10 10 5.20853 4.07286 11 11 2.64094 3.56328 12 12 2.65534 3.55146 13 13 1.18498 3.26756 14 14 2.14477 3.11453 15 15 0.204171 3.22061 Initial red node coordinates: I Red X Y 1 10 0.712831 4.29938 2 15 6.07577 3.61565 3 12 7.74265 4.36365 4 9 9.86258 4.01324 5 14 3.47078 3.42169 6 6 5.68325 4.31983 7 8 9.92087 4.41104 8 4 3.1673 4.2156 9 1 4.07148 3.88305 10 2 0.267277 4.49449 11 5 8.70591 3.2959 12 11 2.09401 3.9043 13 7 9.16946 4.69834 14 3 5.5566 4.45455 15 13 5.77646 3.4785 Initial pairing of nodes: I Black Red Distance 1 1 10 7.73018 2 2 15 1.49886 3 3 12 4.90571 4 4 9 3.98232 5 5 14 3.88562 6 6 6 0.998674 7 7 8 2.6097 8 8 4 4.13426 9 9 1 1.25558 10 10 2 0.980382 11 11 5 0.841829 12 12 11 6.05596 13 13 7 8.81041 14 14 3 5.73556 15 15 13 9.08626 Total discrepancy of initial pairing = 62.5113 On step 1 discrepancy = 29.8884 Swaps made was 72 On step 2 discrepancy = 31.9885 Swaps made was 19 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only -0.0702637 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 7.98755 4.88579 2 2 6.93399 4.43071 3 3 6.95934 4.53244 4 4 8.02592 3.41271 5 5 1.86817 3.23245 6 6 4.98276 3.60803 7 7 0.829545 3.05568 8 8 5.73222 4.19272 9 9 1.25563 3.1672 10 10 5.20853 4.07286 11 11 2.64094 3.56328 12 12 2.65534 3.55146 13 13 1.18498 3.26756 14 14 2.14477 3.11453 15 15 0.204171 3.22061 Final red node coordinates: I Red X Y 1 13 0.712831 4.29938 2 4 6.07577 3.61565 3 3 7.74265 4.36365 4 11 9.86258 4.01324 5 6 3.47078 3.42169 6 15 5.68325 4.31983 7 1 9.92087 4.41104 8 5 3.1673 4.2156 9 8 4.07148 3.88305 10 2 0.267277 4.49449 11 14 8.70591 3.2959 12 9 2.09401 3.9043 13 12 9.16946 4.69834 14 7 5.5566 4.45455 15 10 5.77646 3.4785 Final pairing of nodes: I Black Red Distance 1 1 13 1.19669 2 2 4 2.95819 3 3 3 0.801293 4 4 11 0.689943 5 5 6 3.96702 6 6 15 0.804204 7 7 1 1.24917 8 8 5 2.38927 9 9 8 2.18028 10 10 2 0.980382 11 11 14 3.04884 12 12 9 1.45444 13 13 12 1.10985 14 14 7 7.88345 15 15 10 1.27544 Total discrepancy of final pairing = 31.9885 graph_dist_test(): Normal end of execution. 06-Nov-2024 17:46:50