Home License -- for personal use only. Not for government, academic, research, commercial, or other organizational use. 06-Nov-2024 16:36:15 graph_dist_test(): MATLAB/Octave version 9.11.0.2358333 (R2021b) Update 7 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 8.14724 4.41209 2 2 9.05792 3.06367 3 3 1.26987 3.55385 4 4 9.13376 3.09234 5 5 6.32359 3.19426 6 6 0.975404 4.64692 7 7 2.78498 4.38966 8 8 5.46882 3.6342 9 9 9.57507 4.90044 10 10 9.64889 3.06889 11 11 1.57613 3.87749 12 12 9.70593 3.76312 13 13 9.57167 4.53103 14 14 4.85376 4.5904 15 15 8.0028 3.37375 Initial red node coordinates: I Red X Y 1 1 1.41886 3.97953 2 2 4.21761 3.89117 3 3 9.15736 4.29263 4 4 7.92207 4.41873 5 5 9.59492 4.50937 6 6 6.55741 3.55205 7 7 0.357117 4.35941 8 8 8.49129 4.3102 9 9 9.33993 3.32522 10 10 6.78735 3.238 11 11 7.5774 3.99673 12 12 7.43132 4.91949 13 13 3.92227 3.68077 14 14 6.55478 4.17054 15 15 1.71187 3.44762 Initial pairing of nodes: I Black Red Distance 1 1 1 6.74226 2 2 2 4.91053 3 3 3 7.92201 4 4 4 1.79652 5 5 5 3.52578 6 6 6 5.68836 7 7 7 2.42805 8 8 8 3.09715 9 9 9 1.59267 10 10 10 2.86653 11 11 11 6.00245 12 12 12 2.55167 13 13 13 5.71303 14 14 14 1.75207 15 15 15 6.29137 Total discrepancy of initial pairing = 62.8805 On step 1 discrepancy = 15.564 Swaps made was 50 On step 2 discrepancy = 13.3733 Swaps made was 5 On step 3 discrepancy = 13.3247 Swaps made was 1 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.00363431 which is less than the tolerance TOL = 0.05 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 8.14724 4.41209 2 2 9.05792 3.06367 3 3 1.26987 3.55385 4 4 9.13376 3.09234 5 5 6.32359 3.19426 6 6 0.975404 4.64692 7 7 2.78498 4.38966 8 8 5.46882 3.6342 9 9 9.57507 4.90044 10 10 9.64889 3.06889 11 11 1.57613 3.87749 12 12 9.70593 3.76312 13 13 9.57167 4.53103 14 14 4.85376 4.5904 15 15 8.0028 3.37375 Final red node coordinates: I Red X Y 1 12 1.41886 3.97953 2 11 4.21761 3.89117 3 15 9.15736 4.29263 4 4 7.92207 4.41873 5 6 9.59492 4.50937 6 7 6.55741 3.55205 7 13 0.357117 4.35941 8 14 8.49129 4.3102 9 8 9.33993 3.32522 10 9 6.78735 3.238 11 1 7.5774 3.99673 12 3 7.43132 4.91949 13 5 3.92227 3.68077 14 2 6.55478 4.17054 15 10 1.71187 3.44762 Final pairing of nodes: I Black Red Distance 1 1 12 0.877485 2 2 11 1.75001 3 3 15 0.454583 4 4 4 1.79652 5 5 6 0.427411 6 6 7 0.681866 7 7 13 1.34013 8 8 14 1.21119 9 9 8 1.23408 10 10 9 0.401444 11 11 1 0.187471 12 12 3 0.762438 13 13 5 0.0317797 14 14 2 0.945303 15 15 10 1.22301 Total discrepancy of final pairing = 13.3247 Reversing NODER! Initial black node coordinates: I Black X Y 1 1 8.14724 4.41209 2 2 9.05792 3.06367 3 3 1.26987 3.55385 4 4 9.13376 3.09234 5 5 6.32359 3.19426 6 6 0.975404 4.64692 7 7 2.78498 4.38966 8 8 5.46882 3.6342 9 9 9.57507 4.90044 10 10 9.64889 3.06889 11 11 1.57613 3.87749 12 12 9.70593 3.76312 13 13 9.57167 4.53103 14 14 4.85376 4.5904 15 15 8.0028 3.37375 Initial red node coordinates: I Red X Y 1 10 1.41886 3.97953 2 2 4.21761 3.89117 3 5 9.15736 4.29263 4 3 7.92207 4.41873 5 1 9.59492 4.50937 6 9 6.55741 3.55205 7 8 0.357117 4.35941 8 14 8.49129 4.3102 9 13 9.33993 3.32522 10 7 6.78735 3.238 11 6 7.5774 3.99673 12 4 7.43132 4.91949 13 15 3.92227 3.68077 14 11 6.55478 4.17054 15 12 1.71187 3.44762 Initial pairing of nodes: I Black Red Distance 1 1 10 1.79661 2 2 2 4.91053 3 3 5 8.37971 4 4 3 1.20052 5 5 1 4.96719 6 6 9 8.46831 7 7 8 5.70686 8 8 14 1.21119 9 9 13 5.78288 10 10 7 9.38096 11 11 6 4.9919 12 12 4 1.90052 13 13 15 7.93412 14 14 11 2.7876 15 15 12 1.648 Total discrepancy of initial pairing = 71.0669 On step 1 discrepancy = 16.3081 Swaps made was 51 On step 2 discrepancy = 13.1626 Swaps made was 12 On step 3 discrepancy = 13.1626 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 8.14724 4.41209 2 2 9.05792 3.06367 3 3 1.26987 3.55385 4 4 9.13376 3.09234 5 5 6.32359 3.19426 6 6 0.975404 4.64692 7 7 2.78498 4.38966 8 8 5.46882 3.6342 9 9 9.57507 4.90044 10 10 9.64889 3.06889 11 11 1.57613 3.87749 12 12 9.70593 3.76312 13 13 9.57167 4.53103 14 14 4.85376 4.5904 15 15 8.0028 3.37375 Final red node coordinates: I Red X Y 1 4 1.41886 3.97953 2 11 4.21761 3.89117 3 15 9.15736 4.29263 4 8 7.92207 4.41873 5 6 9.59492 4.50937 6 7 6.55741 3.55205 7 13 0.357117 4.35941 8 14 8.49129 4.3102 9 12 9.33993 3.32522 10 9 6.78735 3.238 11 1 7.5774 3.99673 12 3 7.43132 4.91949 13 5 3.92227 3.68077 14 2 6.55478 4.17054 15 10 1.71187 3.44762 Final pairing of nodes: I Black Red Distance 1 1 4 0.225261 2 2 11 1.75001 3 3 15 0.454583 4 4 8 1.37693 5 5 6 0.427411 6 6 7 0.681866 7 7 13 1.34013 8 8 14 1.21119 9 9 12 2.14383 10 10 9 0.401444 11 11 1 0.187471 12 12 3 0.762438 13 13 5 0.0317797 14 14 2 0.945303 15 15 10 1.22301 Total discrepancy of final pairing = 13.1626 graph_dist_test(): Normal end of execution. 06-Nov-2024 16:36:17