03 March 2022 05:47:10 PM FLOYD_TEST C++ version Test the FLOYD library. TEST01 I4MAT_FLOYO uses Floyd's algorithm to find the shortest distance between all pairs of nodes in a directed graph, starting from the initial array of direct node-to-node distances. In the initial direct distance array, if A(I,J) = -1, this indicates there is NO directed link from node I to node J. In that case, the value of of A(I,J) is essentially "infinity". Initial direct distance array: Col: 1 2 3 4 5 6 Row 1 0 2 5 -1 -1 -1 2 -1 0 7 1 -1 8 3 -1 -1 0 4 -1 -1 4 -1 -1 -1 0 3 -1 5 -1 -1 2 -1 0 3 6 -1 5 -1 2 4 0 In the final shortest distance array, if A(I,J) = -1, this indicates there is NO directed path from node I to node J. Final shortest distance array: Col: 1 2 3 4 5 6 Row 1 0 2 5 3 6 9 2 -1 0 6 1 4 7 3 -1 15 0 4 7 10 4 -1 11 5 0 3 6 5 -1 8 2 5 0 3 6 -1 5 6 2 4 0 TEST02 R8MAT_FLOYO uses Floyd's algorithm to find the shortest distance between all pairs of nodes in a directed graph, starting from the initial array of direct node-to-node distances. In the initial direct distance array, if A(I,J) = -1, this indicates there is NO directed link from node I to node J. In that case, the value of of A(I,J) is essentially "infinity". Initial direct distance array: Col: 1 2 3 4 5 Row 1 0 2 5 -1 -1 2 -1 0 7 1 -1 3 -1 -1 0 4 -1 4 -1 -1 -1 0 3 5 -1 -1 2 -1 0 6 -1 5 -1 2 4 Col: 6 Row 1 -1 2 8 3 -1 4 -1 5 3 6 0 In the final shortest distance array, if A(I,J) = -1, this indicates there is NO directed path from node I to node J. Final shortest distance array: Col: 1 2 3 4 5 Row 1 0 2 5 3 6 2 -1 0 6 1 4 3 -1 15 0 4 7 4 -1 11 5 0 3 5 -1 8 2 5 0 6 -1 5 6 2 4 Col: 6 Row 1 9 2 7 3 10 4 6 5 3 6 0 TEST03 Test I4MAT_FLOYD on the MOD(I,J) matrix. The work is roughly N^3. N Time (seconds) Time/N^3 1 1e-06 1 2 0 0 4 1e-06 0.015625 8 5e-06 0.00976563 16 3.2e-05 0.0078125 32 0.000281 0.00857544 64 0.001995 0.00761032 128 0.014456 0.00689316 256 0.107559 0.00641102 512 0.851892 0.00634709 1024 6.80539 0.00633801 2048 54.3608 0.00632843 TEST04 Start with a triangulation, and use R8_FLOYD to determine the pairwise distance matrix. Distance matrix Col: 1 2 3 4 5 Row 1 0 1 2 3 4 2 1 0 1 2 3 3 2 1 0 1 2 4 3 2 1 0 1 5 4 3 2 1 0 6 5 4 3 2 1 7 6 5 4 3 2 8 7 6 5 4 3 9 1 1.41421 2.41421 3.41421 4.41421 10 2 1 1.41421 2.41421 3.41421 11 3 2 1 1.41421 2.41421 12 4 3 2 1 1.41421 13 5 4 3 2 1 14 6 5 4 3 2 15 7 6 5 4 3 16 8 7 6 5 4 17 2 2.41421 2.82843 3.82843 4.82843 18 3 2 2.41421 3.41421 4.41421 19 8 7 6 5 4 20 9 8 7 6 5 21 3 3.41421 3.82843 4.82843 5.82843 22 4 3 3.41421 4.41421 5.41421 23 9 8 7 6 5 24 10 9 8 7 6 25 4 4.41421 4.82843 5.82843 6.82843 26 5 4 4.41421 5.41421 6.41421 27 10 9 8 7 6 28 11 10 9 8 7 29 5 5.41421 5.82843 6.82843 7.82843 30 6 5 5.41421 6.41421 7.41421 31 11 10 9 8 7 32 12 11 10 9 8 33 6 6.41421 6.82843 7.82843 8.82843 34 7 6 6.41421 7.41421 8.41421 35 8 7 7.41421 8.41421 9.41421 36 9 8 8.41421 9.41421 10.4142 37 14 13 12 11 10 38 13 12 11 10 9 39 12 11 10 9 8 40 13 12 11 10 9 41 7 7.41421 7.82843 8.82843 9.82843 42 8 7 7.41421 8.41421 9.41421 43 9 8 8.41421 9.41421 10.4142 44 10 9 9.41421 10.4142 11.4142 45 14.4142 13.4142 12.4142 11.4142 10.4142 46 13.4142 12.4142 11.4142 10.4142 9.41421 47 13 12 11 10 9 48 14 13 12 11 10 Col: 6 7 8 9 10 Row 1 5 6 7 1 2 2 4 5 6 1.41421 1 3 3 4 5 2.41421 1.41421 4 2 3 4 3.41421 2.41421 5 1 2 3 4.41421 3.41421 6 0 1 2 5.41421 4.41421 7 1 0 1 6.41421 5.41421 8 2 1 0 7.41421 6.41421 9 5.41421 6.41421 7.41421 0 1 10 4.41421 5.41421 6.41421 1 0 11 3.41421 4.41421 5.41421 2 1 12 2.41421 3.41421 4.41421 3 2 13 1.41421 2.41421 3.41421 4 3 14 1 1.41421 2.41421 5 4 15 2 1 1.41421 6 5 16 3 2 1 7 6 17 5.82843 6.82843 7.82843 1 1.41421 18 5.41421 6.41421 7.41421 2 1 19 3 2 2.41421 7 6 20 4 3 2 8 7 21 6.82843 7.82843 8.82843 2 2.41421 22 6.41421 7.41421 8.41421 3 2 23 4 3 3.41421 8 7 24 5 4 3 9 8 25 7.82843 8.82843 9.82843 3 3.41421 26 7.41421 8.41421 9.41421 4 3 27 5 4 4.41421 9 8 28 6 5 4 10 9 29 8.82843 9.82843 10.8284 4 4.41421 30 8.41421 9.41421 10.4142 5 4 31 6 5 5.41421 10 9 32 7 6 5 11 10 33 9.82843 10.8284 11.8284 5 5.41421 34 9.41421 10.4142 11.4142 6 5 35 10.4142 11.4142 12.4142 7 6 36 11.4142 12.4142 13.4142 8 7 37 9 8 8.41421 13 12 38 8 7 7.41421 12 11 39 7 6 6.41421 11 10 40 8 7 6 12 11 41 10.8284 11.8284 12.8284 6 6.41421 42 10.4142 11.4142 12.4142 7 6 43 11.4142 12.4142 13.4142 8 7 44 12.4142 13.4142 14.4142 9 8 45 9.41421 8.41421 8.82843 13.4142 12.4142 46 8.41421 7.41421 7.82843 12.4142 11.4142 47 8 7 7.41421 12 11 48 9 8 7 13 12 Col: 11 12 13 14 15 Row 1 3 4 5 6 7 2 2 3 4 5 6 3 1 2 3 4 5 4 1.41421 1 2 3 4 5 2.41421 1.41421 1 2 3 6 3.41421 2.41421 1.41421 1 2 7 4.41421 3.41421 2.41421 1.41421 1 8 5.41421 4.41421 3.41421 2.41421 1.41421 9 2 3 4 5 6 10 1 2 3 4 5 11 0 1 2 3 4 12 1 0 1 2 3 13 2 1 0 1 2 14 3 2 1 0 1 15 4 3 2 1 0 16 5 4 3 2 1 17 2.41421 3.41421 4.41421 5.41421 6.41421 18 2 3 4 5 6 19 5 4 3 2 1 20 6 5 4 3 2 21 3.41421 4.41421 5.41421 6.41421 7.41421 22 3 4 5 6 7 23 6 5 4 3 2 24 7 6 5 4 3 25 4.41421 5.41421 6.41421 7.41421 8.41421 26 4 5 6 7 8 27 7 6 5 4 3 28 8 7 6 5 4 29 5.41421 6.41421 7.41421 8.41421 9.41421 30 5 6 7 8 9 31 8 7 6 5 4 32 9 8 7 6 5 33 6.41421 7.41421 8.41421 9.41421 10.4142 34 6 7 8 9 10 35 7 8 9 10 11 36 8 9 10 11 12 37 11 10 9 8 7 38 10 9 8 7 6 39 9 8 7 6 5 40 10 9 8 7 6 41 7.41421 8.41421 9.41421 10.4142 11.4142 42 7 8 9 10 11 43 8 9 10 11 12 44 9 10 11 12 13 45 11.4142 10.4142 9.41421 8.41421 7.41421 46 10.4142 9.41421 8.41421 7.41421 6.41421 47 10 9 8 7 6 48 11 10 9 8 7 Col: 16 17 18 19 20 Row 1 8 2 3 8 9 2 7 2.41421 2 7 8 3 6 2.82843 2.41421 6 7 4 5 3.82843 3.41421 5 6 5 4 4.82843 4.41421 4 5 6 3 5.82843 5.41421 3 4 7 2 6.82843 6.41421 2 3 8 1 7.82843 7.41421 2.41421 2 9 7 1 2 7 8 10 6 1.41421 1 6 7 11 5 2.41421 2 5 6 12 4 3.41421 3 4 5 13 3 4.41421 4 3 4 14 2 5.41421 5 2 3 15 1 6.41421 6 1 2 16 0 7.41421 7 1.41421 1 17 7.41421 0 1 7.41421 8.41421 18 7 1 0 7 8 19 1.41421 7.41421 7 0 1 20 1 8.41421 8 1 0 21 8.41421 1 1.41421 8.41421 9.41421 22 8 2 1 8 9 23 2.41421 8.41421 8 1 1.41421 24 2 9.41421 9 2 1 25 9.41421 2 2.41421 9.41421 10.4142 26 9 3 2 9 10 27 3.41421 9.41421 9 2 2.41421 28 3 10.4142 10 3 2 29 10.4142 3 3.41421 10.4142 11.4142 30 10 4 3 10 11 31 4.41421 10.4142 10 3 3.41421 32 4 11.4142 11 4 3 33 11.4142 4 4.41421 11.4142 12.4142 34 11 5 4 11 12 35 12 6 5 12 13 36 13 7 6 13 14 37 7.41421 13.4142 13 6 6.41421 38 6.41421 12.4142 12 5 5.41421 39 5.41421 11.4142 11 4 4.41421 40 5 12.4142 12 5 4 41 12.4142 5 5.41421 12.4142 13.4142 42 12 6 5 12 13 43 13 7 6 13 14 44 14 8 7 14 15 45 7.82843 13.8284 13.4142 6.41421 6.82843 46 6.82843 12.8284 12.4142 5.41421 5.82843 47 6.41421 12.4142 12 5 5.41421 48 6 13.4142 13 6 5 Col: 21 22 23 24 25 Row 1 3 4 9 10 4 2 3.41421 3 8 9 4.41421 3 3.82843 3.41421 7 8 4.82843 4 4.82843 4.41421 6 7 5.82843 5 5.82843 5.41421 5 6 6.82843 6 6.82843 6.41421 4 5 7.82843 7 7.82843 7.41421 3 4 8.82843 8 8.82843 8.41421 3.41421 3 9.82843 9 2 3 8 9 3 10 2.41421 2 7 8 3.41421 11 3.41421 3 6 7 4.41421 12 4.41421 4 5 6 5.41421 13 5.41421 5 4 5 6.41421 14 6.41421 6 3 4 7.41421 15 7.41421 7 2 3 8.41421 16 8.41421 8 2.41421 2 9.41421 17 1 2 8.41421 9.41421 2 18 1.41421 1 8 9 2.41421 19 8.41421 8 1 2 9.41421 20 9.41421 9 1.41421 1 10.4142 21 0 1 9.41421 10.4142 1 22 1 0 9 10 1.41421 23 9.41421 9 0 1 10.4142 24 10.4142 10 1 0 11.4142 25 1 1.41421 10.4142 11.4142 0 26 2 1 10 11 1 27 10.4142 10 1 1.41421 11.4142 28 11.4142 11 2 1 12.4142 29 2 2.41421 11.4142 12.4142 1 30 3 2 11 12 2 31 11.4142 11 2 2.41421 12.4142 32 12.4142 12 3 2 13.4142 33 3 3.41421 12.4142 13.4142 2 34 4 3 12 13 3 35 5 4 13 14 4 36 6 5 14 15 5 37 14.4142 14 5 5.41421 15.4142 38 13.4142 13 4 4.41421 14.4142 39 12.4142 12 3 3.41421 13.4142 40 13.4142 13 4 3 14.4142 41 4 4.41421 13.4142 14.4142 3 42 5 4 13 14 4 43 6 5 14 15 5 44 7 6 15 16 6 45 14.8284 14.4142 5.41421 5.82843 15.8284 46 13.8284 13.4142 4.41421 4.82843 14.8284 47 13.4142 13 4 4.41421 14.4142 48 14.4142 14 5 4 15.4142 Col: 26 27 28 29 30 Row 1 5 10 11 5 6 2 4 9 10 5.41421 5 3 4.41421 8 9 5.82843 5.41421 4 5.41421 7 8 6.82843 6.41421 5 6.41421 6 7 7.82843 7.41421 6 7.41421 5 6 8.82843 8.41421 7 8.41421 4 5 9.82843 9.41421 8 9.41421 4.41421 4 10.8284 10.4142 9 4 9 10 4 5 10 3 8 9 4.41421 4 11 4 7 8 5.41421 5 12 5 6 7 6.41421 6 13 6 5 6 7.41421 7 14 7 4 5 8.41421 8 15 8 3 4 9.41421 9 16 9 3.41421 3 10.4142 10 17 3 9.41421 10.4142 3 4 18 2 9 10 3.41421 3 19 9 2 3 10.4142 10 20 10 2.41421 2 11.4142 11 21 2 10.4142 11.4142 2 3 22 1 10 11 2.41421 2 23 10 1 2 11.4142 11 24 11 1.41421 1 12.4142 12 25 1 11.4142 12.4142 1 2 26 0 11 12 1.41421 1 27 11 0 1 12.4142 12 28 12 1 0 13.4142 13 29 1.41421 12.4142 13.4142 0 1 30 1 12 13 1 0 31 12 1 1.41421 13.4142 13 32 13 2 1 14.4142 14 33 2.41421 13.4142 14.4142 1 1.41421 34 2 13 14 2 1 35 3 14 15 3 2 36 4 15 16 4 3 37 15 4 4.41421 16.4142 16 38 14 3 3.41421 15.4142 15 39 13 2 2.41421 14.4142 14 40 14 3 2 15.4142 15 41 3.41421 14.4142 15.4142 2 2.41421 42 3 14 15 3 2 43 4 15 16 4 3 44 5 16 17 5 4 45 15.4142 4.41421 4.82843 16.8284 16.4142 46 14.4142 3.41421 3.82843 15.8284 15.4142 47 14 3 3.41421 15.4142 15 48 15 4 3 16.4142 16 Col: 31 32 33 34 35 Row 1 11 12 6 7 8 2 10 11 6.41421 6 7 3 9 10 6.82843 6.41421 7.41421 4 8 9 7.82843 7.41421 8.41421 5 7 8 8.82843 8.41421 9.41421 6 6 7 9.82843 9.41421 10.4142 7 5 6 10.8284 10.4142 11.4142 8 5.41421 5 11.8284 11.4142 12.4142 9 10 11 5 6 7 10 9 10 5.41421 5 6 11 8 9 6.41421 6 7 12 7 8 7.41421 7 8 13 6 7 8.41421 8 9 14 5 6 9.41421 9 10 15 4 5 10.4142 10 11 16 4.41421 4 11.4142 11 12 17 10.4142 11.4142 4 5 6 18 10 11 4.41421 4 5 19 3 4 11.4142 11 12 20 3.41421 3 12.4142 12 13 21 11.4142 12.4142 3 4 5 22 11 12 3.41421 3 4 23 2 3 12.4142 12 13 24 2.41421 2 13.4142 13 14 25 12.4142 13.4142 2 3 4 26 12 13 2.41421 2 3 27 1 2 13.4142 13 14 28 1.41421 1 14.4142 14 15 29 13.4142 14.4142 1 2 3 30 13 14 1.41421 1 2 31 0 1 14.4142 14 15 32 1 0 15.4142 15 16 33 14.4142 15.4142 0 1 2 34 14 15 1 0 1 35 15 16 2 1 0 36 16 17 3 2 1 37 3 3.41421 17.4142 17 18 38 2 2.41421 16.4142 16 17 39 1 1.41421 15.4142 15 16 40 2 1 16.4142 16 17 41 15.4142 16.4142 1 1.41421 2.41421 42 15 16 2 1 1.41421 43 16 17 3 2 1 44 17 18 4 3 2 45 3.41421 3.82843 17.8284 17.4142 18.4142 46 2.41421 2.82843 16.8284 16.4142 17.4142 47 2 2.41421 16.4142 16 17 48 3 2 17.4142 17 18 Col: 36 37 38 39 40 Row 1 9 14 13 12 13 2 8 13 12 11 12 3 8.41421 12 11 10 11 4 9.41421 11 10 9 10 5 10.4142 10 9 8 9 6 11.4142 9 8 7 8 7 12.4142 8 7 6 7 8 13.4142 8.41421 7.41421 6.41421 6 9 8 13 12 11 12 10 7 12 11 10 11 11 8 11 10 9 10 12 9 10 9 8 9 13 10 9 8 7 8 14 11 8 7 6 7 15 12 7 6 5 6 16 13 7.41421 6.41421 5.41421 5 17 7 13.4142 12.4142 11.4142 12.4142 18 6 13 12 11 12 19 13 6 5 4 5 20 14 6.41421 5.41421 4.41421 4 21 6 14.4142 13.4142 12.4142 13.4142 22 5 14 13 12 13 23 14 5 4 3 4 24 15 5.41421 4.41421 3.41421 3 25 5 15.4142 14.4142 13.4142 14.4142 26 4 15 14 13 14 27 15 4 3 2 3 28 16 4.41421 3.41421 2.41421 2 29 4 16.4142 15.4142 14.4142 15.4142 30 3 16 15 14 15 31 16 3 2 1 2 32 17 3.41421 2.41421 1.41421 1 33 3 17.4142 16.4142 15.4142 16.4142 34 2 17 16 15 16 35 1 18 17 16 17 36 0 19 18 17 18 37 19 0 1 2 3 38 18 1 0 1 2 39 17 2 1 0 1 40 18 3 2 1 0 41 3.41421 18.4142 17.4142 16.4142 17.4142 42 2.41421 18 17 16 17 43 1.41421 19 18 17 18 44 1 20 19 18 19 45 19.4142 1 1.41421 2.41421 3.41421 46 18.4142 2 1 1.41421 2.41421 47 18 3 2 1 1.41421 48 19 4 3 2 1 Col: 41 42 43 44 45 Row 1 7 8 9 10 14.4142 2 7.41421 7 8 9 13.4142 3 7.82843 7.41421 8.41421 9.41421 12.4142 4 8.82843 8.41421 9.41421 10.4142 11.4142 5 9.82843 9.41421 10.4142 11.4142 10.4142 6 10.8284 10.4142 11.4142 12.4142 9.41421 7 11.8284 11.4142 12.4142 13.4142 8.41421 8 12.8284 12.4142 13.4142 14.4142 8.82843 9 6 7 8 9 13.4142 10 6.41421 6 7 8 12.4142 11 7.41421 7 8 9 11.4142 12 8.41421 8 9 10 10.4142 13 9.41421 9 10 11 9.41421 14 10.4142 10 11 12 8.41421 15 11.4142 11 12 13 7.41421 16 12.4142 12 13 14 7.82843 17 5 6 7 8 13.8284 18 5.41421 5 6 7 13.4142 19 12.4142 12 13 14 6.41421 20 13.4142 13 14 15 6.82843 21 4 5 6 7 14.8284 22 4.41421 4 5 6 14.4142 23 13.4142 13 14 15 5.41421 24 14.4142 14 15 16 5.82843 25 3 4 5 6 15.8284 26 3.41421 3 4 5 15.4142 27 14.4142 14 15 16 4.41421 28 15.4142 15 16 17 4.82843 29 2 3 4 5 16.8284 30 2.41421 2 3 4 16.4142 31 15.4142 15 16 17 3.41421 32 16.4142 16 17 18 3.82843 33 1 2 3 4 17.8284 34 1.41421 1 2 3 17.4142 35 2.41421 1.41421 1 2 18.4142 36 3.41421 2.41421 1.41421 1 19.4142 37 18.4142 18 19 20 1 38 17.4142 17 18 19 1.41421 39 16.4142 16 17 18 2.41421 40 17.4142 17 18 19 3.41421 41 0 1 2 3 18.8284 42 1 0 1 2 18.4142 43 2 1 0 1 19.4142 44 3 2 1 0 20.4142 45 18.8284 18.4142 19.4142 20.4142 0 46 17.8284 17.4142 18.4142 19.4142 1 47 17.4142 17 18 19 2 48 18.4142 18 19 20 3 Col: 46 47 48 Row 1 13.4142 13 14 2 12.4142 12 13 3 11.4142 11 12 4 10.4142 10 11 5 9.41421 9 10 6 8.41421 8 9 7 7.41421 7 8 8 7.82843 7.41421 7 9 12.4142 12 13 10 11.4142 11 12 11 10.4142 10 11 12 9.41421 9 10 13 8.41421 8 9 14 7.41421 7 8 15 6.41421 6 7 16 6.82843 6.41421 6 17 12.8284 12.4142 13.4142 18 12.4142 12 13 19 5.41421 5 6 20 5.82843 5.41421 5 21 13.8284 13.4142 14.4142 22 13.4142 13 14 23 4.41421 4 5 24 4.82843 4.41421 4 25 14.8284 14.4142 15.4142 26 14.4142 14 15 27 3.41421 3 4 28 3.82843 3.41421 3 29 15.8284 15.4142 16.4142 30 15.4142 15 16 31 2.41421 2 3 32 2.82843 2.41421 2 33 16.8284 16.4142 17.4142 34 16.4142 16 17 35 17.4142 17 18 36 18.4142 18 19 37 2 3 4 38 1 2 3 39 1.41421 1 2 40 2.41421 1.41421 1 41 17.8284 17.4142 18.4142 42 17.4142 17 18 43 18.4142 18 19 44 19.4142 19 20 45 1 2 3 46 0 1 2 47 1 0 1 48 2 1 0 FLOYD_TEST Normal end of execution. 03 March 2022 05:48:12 PM