11 March 2023 8:57:31.747 PM graph_dist_test(): FORTRAN90 version graph_dist() implements graph algorithms. graph_dist_all_test(): graph_dist_all() computes the distance between all pairs of nodes. Immediate node distance matrix: Columns 1 2 3 4 5 Row 1 0.0 2.00000 6.00000 1.00000 1000.00 2 2.00000 0.0 3.00000 4.00000 1000.00 3 6.00000 3.00000 0.0 1000.00 1000.00 4 1.00000 4.00000 1000.00 0.0 5.00000 5 1000.00 1000.00 1000.00 5.00000 0.0 Total node distance matrix: Columns 1 2 3 4 5 Row 1 0.0 2.00000 5.00000 1.00000 6.00000 2 2.00000 0.0 3.00000 3.00000 8.00000 3 5.00000 3.00000 0.0 6.00000 11.0000 4 1.00000 3.00000 6.00000 0.0 5.00000 5 6.00000 8.00000 11.0000 5.00000 0.0 Note that "infinity" is represented by 1000.00 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: Columns 1 2 3 4 5 Row 1 0.0 100.000 125.000 120.000 110.000 2 100.000 0.0 40.0000 65.0000 60.0000 3 125.000 40.0000 0.0 45.0000 55.0000 4 120.000 65.0000 45.0000 0.0 50.0000 5 110.000 60.0000 55.0000 50.0000 0.0 The minimal spanning tree: 1 1 2 100.000 2 2 3 40.0000 3 3 4 45.0000 4 4 5 50.0000 The length of the minimal tree is 235.000 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.0000 2 2 4 152.000 3 3 19 80.0000 4 4 34 205.000 5 5 41 207.000 6 6 36 216.000 7 7 11 186.000 8 8 41 444.000 9 9 38 155.000 10 10 30 111.000 11 11 53 110.000 12 12 10 106.000 13 13 55 268.000 14 14 8 101.000 15 15 37 135.000 16 16 53 57.0000 17 17 45 170.000 18 18 22 116.000 19 19 42 200.000 20 20 46 498.000 21 21 13 242.000 22 22 10 109.000 23 23 31 213.000 24 24 2 316.000 25 25 26 149.000 26 26 54 63.0000 27 27 16 84.0000 28 28 31 139.000 29 29 47 405.000 30 30 17 125.000 31 31 34 222.000 32 32 9 91.0000 33 33 15 253.000 34 34 17 160.000 35 35 23 187.000 36 36 39 92.0000 37 37 54 167.000 38 38 50 73.0000 39 39 3 97.0000 40 40 29 390.000 41 41 37 390.000 42 42 1 105.000 43 43 48 176.000 44 44 56 263.000 45 45 25 128.000 46 46 8 458.000 47 47 43 669.000 48 48 49 288.000 49 49 20 322.000 50 50 45 101.000 51 51 25 140.000 52 52 24 200.000 53 53 18 110.000 54 54 57 139.000 55 55 51 181.000 56 56 3 38.0000 The length of the minimal tree is 10835.0 graph_dist_min_span_tree2_test(): graph_dist_min_span_tree2() finds a minimum spanning tree. The graph: Columns 1 2 3 4 5 Row 1 0.0 100.000 125.000 120.000 110.000 2 100.000 0.0 40.0000 65.0000 60.0000 3 125.000 40.0000 0.0 45.0000 55.0000 4 120.000 65.0000 45.0000 0.0 50.0000 5 110.000 60.0000 55.0000 50.0000 0.0 The minimal spanning tree: 1 2 3 40.0000 2 3 4 45.0000 3 4 5 50.0000 4 2 1 100.000 The length of the minimal tree is 235.000 graph_dist_min_span_tree3_test() graph_dist_min_span_tree3() finds a minimum spanning tree. The graph: Columns 1 2 3 4 5 Row 1 0.0 100.000 125.000 120.000 110.000 2 100.000 0.0 40.0000 65.0000 60.0000 3 125.000 40.0000 0.0 45.0000 55.0000 4 120.000 65.0000 45.0000 0.0 50.0000 5 110.000 60.0000 55.0000 50.0000 0.0 The minimal spanning tree: 1 1 2 100.000 2 2 3 40.0000 3 3 4 45.0000 4 4 5 50.0000 The length of the minimal tree is 235.000 graph_dist_one_test(): graph_dist_one() computes the distance from one node to all others in a graph. Edge Distance Matrix: Columns 1 2 3 4 5 Row 1 0.0 1.00000 3.00000 1000.00 1000.00 2 2.00000 0.0 1.00000 1000.00 2.00000 3 1000.00 1000.00 0.0 2.00000 3.00000 4 1000.00 1000.00 1.00000 0.0 1000.00 5 1.00000 3.00000 1000.00 6.00000 0.0 The starting node is 5 Node Distance Path Idad 1 1.00000 2 5 2 2.00000 3 1 3 3.00000 4 2 4 5.00000 5 3 5 0.00000 1 5 Note that "infinity" is represented by 1000.00 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.500000E-01 Maximum number of steps = 10 X range is 0.00000 to 10.0000 Y range is 3.00000 to 5.00000 Initial black node coordinates: I Black X Y 1 1 6.35010 3.95003 2 2 8.13256 3.01607 3 3 3.93441 3.31124 4 4 4.24701 4.42787 5 5 4.79046 3.72396 6 6 2.76873 4.56184 7 7 4.43101 3.60218 8 8 7.41402 3.45491 9 9 5.81422 4.40280 10 10 8.87537 4.16551 11 11 6.94735 4.12589 12 12 2.71034 4.17333 13 13 1.04100 3.64735 14 14 3.18382 3.84048 15 15 0.976034 3.80015 Initial red node coordinates: I Red X Y 1 1 0.796705 4.31274 2 2 4.92791 3.86535 3 3 2.88044 3.14748 4 4 7.40281 4.92823 5 5 0.961124 4.43299 6 6 9.70211 3.06804 7 7 9.24869 3.96104 8 8 3.62608 4.77487 9 9 4.02870 4.63262 10 10 2.74415 3.33552 11 11 4.51419 4.08458 12 12 5.29972 3.58867 13 13 9.57080 4.06638 14 14 2.73552 3.20728 15 15 6.09141 3.87753 Initial pairing of nodes: I Black Red Distance 1 1 1 5.56522 2 2 2 3.31527 3 3 3 1.06662 4 4 4 3.19522 5 5 5 3.89442 6 6 6 7.09247 7 7 7 4.83102 8 8 8 4.01133 9 9 9 1.80025 10 10 10 6.18714 11 11 11 2.43351 12 12 12 2.65457 13 13 13 8.54009 14 14 14 0.775837 15 15 15 5.11596 Total discrepancy of initial pairing = 60.4789 On step 1 discrepancy = 18.4833 Swaps made was 57 On step 2 discrepancy = 12.5229 Swaps made was 15 On step 3 discrepancy = 12.2135 Swaps made was 1 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.247058E-01 which is less than the tolerance TOL = 0.500000E-01 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 6.35010 3.95003 2 2 8.13256 3.01607 3 3 3.93441 3.31124 4 4 4.24701 4.42787 5 5 4.79046 3.72396 6 6 2.76873 4.56184 7 7 4.43101 3.60218 8 8 7.41402 3.45491 9 9 5.81422 4.40280 10 10 8.87537 4.16551 11 11 6.94735 4.12589 12 12 2.71034 4.17333 13 13 1.04100 3.64735 14 14 3.18382 3.84048 15 15 0.976034 3.80015 Final red node coordinates: I Red X Y 1 15 0.796705 4.31274 2 6 4.92791 3.86535 3 3 2.88044 3.14748 4 9 7.40281 4.92823 5 2 0.961124 4.43299 6 8 9.70211 3.06804 7 11 9.24869 3.96104 8 7 3.62608 4.77487 9 12 4.02870 4.63262 10 13 2.74415 3.33552 11 4 4.51419 4.08458 12 10 5.29972 3.58867 13 5 9.57080 4.06638 14 14 2.73552 3.20728 15 1 6.09141 3.87753 Final pairing of nodes: I Black Red Distance 1 1 15 0.268651 2 2 6 1.57041 3 3 3 1.06662 4 4 9 0.299309 5 5 2 0.197198 6 6 8 0.883412 7 7 11 0.489514 8 8 7 1.90320 9 9 12 0.963078 10 10 13 0.702468 11 11 4 0.922600 12 12 10 0.838489 13 13 5 0.789696 14 14 14 0.775837 15 15 1 0.543057 Total discrepancy of final pairing = 12.2135 Reversing NODER! Initial black node coordinates: I Black X Y 1 1 6.35010 3.95003 2 2 8.13256 3.01607 3 3 3.93441 3.31124 4 4 4.24701 4.42787 5 5 4.79046 3.72396 6 6 2.76873 4.56184 7 7 4.43101 3.60218 8 8 7.41402 3.45491 9 9 5.81422 4.40280 10 10 8.87537 4.16551 11 11 6.94735 4.12589 12 12 2.71034 4.17333 13 13 1.04100 3.64735 14 14 3.18382 3.84048 15 15 0.976034 3.80015 Initial red node coordinates: I Red X Y 1 1 0.796705 4.31274 2 14 4.92791 3.86535 3 5 2.88044 3.14748 4 10 7.40281 4.92823 5 4 0.961124 4.43299 6 13 9.70211 3.06804 7 12 9.24869 3.96104 8 7 3.62608 4.77487 9 11 4.02870 4.63262 10 8 2.74415 3.33552 11 2 4.51419 4.08458 12 9 5.29972 3.58867 13 3 9.57080 4.06638 14 6 2.73552 3.20728 15 15 6.09141 3.87753 Initial pairing of nodes: I Black Red Distance 1 1 1 5.56522 2 2 14 5.40043 3 3 5 3.17786 4 4 10 1.85791 5 5 4 2.87657 6 6 13 6.82009 7 7 12 0.868814 8 8 7 1.90320 9 9 11 1.33841 10 10 8 5.28454 11 11 2 2.03617 12 12 9 1.39608 13 13 3 1.90615 14 14 6 6.56390 15 15 15 5.11596 Total discrepancy of initial pairing = 52.1113 On step 1 discrepancy = 31.0928 Swaps made was 70 On step 2 discrepancy = 16.6434 Swaps made was 31 On step 3 discrepancy = 13.5939 Swaps made was 9 On step 4 discrepancy = 12.2135 Swaps made was 5 On step 5 discrepancy = 12.2135 Swaps made was 0 graph_dist_pairing_greedy(): Warning: The relative change in the discrepancy was only 0.00000 which is less than the tolerance TOL = 0.500000E-01 Bailing out of the iteration. Final black node coordinates: I Black X Y 1 1 6.35010 3.95003 2 2 8.13256 3.01607 3 3 3.93441 3.31124 4 4 4.24701 4.42787 5 5 4.79046 3.72396 6 6 2.76873 4.56184 7 7 4.43101 3.60218 8 8 7.41402 3.45491 9 9 5.81422 4.40280 10 10 8.87537 4.16551 11 11 6.94735 4.12589 12 12 2.71034 4.17333 13 13 1.04100 3.64735 14 14 3.18382 3.84048 15 15 0.976034 3.80015 Final red node coordinates: I Red X Y 1 15 0.796705 4.31274 2 6 4.92791 3.86535 3 3 2.88044 3.14748 4 9 7.40281 4.92823 5 2 0.961124 4.43299 6 8 9.70211 3.06804 7 11 9.24869 3.96104 8 7 3.62608 4.77487 9 12 4.02870 4.63262 10 13 2.74415 3.33552 11 4 4.51419 4.08458 12 10 5.29972 3.58867 13 5 9.57080 4.06638 14 14 2.73552 3.20728 15 1 6.09141 3.87753 Final pairing of nodes: I Black Red Distance 1 1 15 0.268651 2 2 6 1.57041 3 3 3 1.06662 4 4 9 0.299309 5 5 2 0.197198 6 6 8 0.883412 7 7 11 0.489514 8 8 7 1.90320 9 9 12 0.963078 10 10 13 0.702468 11 11 4 0.922600 12 12 10 0.838489 13 13 5 0.789696 14 14 14 0.775837 15 15 1 0.543057 Total discrepancy of final pairing = 12.2135 graph_dist_test(): Normal end of execution. 11 March 2023 8:57:31.749 PM