~o=39 ~?i&32768 ~o=24 ~$>end_of_copyright ~/!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ~/Copyright (C) Isabelle Constantin, INRO Consultants Inc., 1995. ~/ ~/The right to use this macro is granted to all EMME/2 users, provided the ~/following conditions are met: ~/ 1) The macro cannot be sold for a fee (but it can be used and ~/ distributed without charge within consulting projects). ~/ 2) The user is aware that this macro is not a part of the EMME/2 ~/ software licence, and that there is no explicit or implied ~/ warranty or support provided with this macro. ~/ 3) The comments in this macro must not be removed. ~/ 4) Any addition or modification must be identified as such, and give ~/ at least date, name and the reason of the modification. ~/!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ~:end_of_copyright ~/*********** FLOYD - 1.5 (I. Constantin, INRO Consultants Inc.) *********** ~/ ~/FLOYD - a macro that implements a Floyd-Warshall type of algorithm ~/ ~/This macro implements a Floyd-Warshall type of shortest path algorithm. ~/It checks, iteratively, if the distance for each O-D pair can be reduced ~/through the use of an intermediate zone. The resulting distance matrix ~/satisfies the triangle inequality. ~/ ~/Usage: ~ ~/ ~/where: Dpq distance matrix to be used (input) ~/ Spq shortest path distance matrix (output) ~/ Tpq full matrix used temporarily by this macro (output) ~/ const constant to be added (default is 0) ~/ ~/Notes: - This macro must be started at the main menu level ~/ - It needs Release 7.0 or later of the EMME/2 system ~/ - Scalar matrix ms99 is used temporarily by this macro ~/ - Reports are appended to the file floyd.rep ~/************************************************************************ ~x=%m% / test if started from main menu ~x+%q% ~?x>0 ~$>end_of_macro ~x=%0% / test if enough parameters are provided ~?x<3 ~$>end_of_macro ~t0=%t0% 0 ~z=%4% ~p=2005 ~t1=%p% ~/ ~/Macro FLOYD was called with the following parameters: ~/ Dpq distance matrix to be used %1% ~/ Spq shortest path distance matrix %2% ~/ Tpq full matrix used temporarily by this macro %3% ~/ const constant to be added %4% ~/ ~/Computations: reports=floyd.rep ~y=0 ~/ ~/Initialization ~/..... copying distance matrix (in 3.12) 3.12 4 / matrix copy 1 / simple copy %1% / copy from ~+|%2%|y|Spq|distance of shortest path for %1%|~?q=1|y|0 / copy to n / no submatrix q ~:loop ~y+1 ~/ ~/Iteration %y% ~/..... performing the Floyd-type operation (in 3.23, progress is shown below) 3.23 1 / matrix convolution %2% / operand matrix 1 + / combination operator %2% / operand matrix 2 n / not transposed .min. / contraction operator %3% / result matrix ~?y=1 ~+|y|fltmp|matrix used temporarily by macro floyd|~?q=1|y|0 ~?y>1 n / argmin matrix n / no submatrix ~o-1 / no constraint ~o+1 ~+|y|2|q|~/yes (report appended to file floyd.rep)|~/ 3.21 ~/..... computing no. of O-D pairs for which distance improved (in 3.21) 1 / matrix calculation y / save result ~+|ms99|y|fimp|number of cells with improved distance|~?q=1|y|0 ~?z=0 (%3% - %2%) < 0. ~?!z=0 (%3% + %4% - %2%) < 0. / no constraint n / no submatrix + / aggregation over origins + / aggregation over destinations 2 / send report to printer ~/ => improvement for %ms99% O-D pairs ~x=%ms99% ~?x=0 ~+|q|~$>stop ~/..... computing the shortest distance (in 3.21) 1 / matrix calculation y / save result %2% n / do not change header ~?z=0 %3% .min. %2% ~?!z=0 (%3% + %4%) .min. %2% / no constraint n / no submatrix 2 / send report to printer q ~$loop ~:stop reports=^ ~+|~p=2005|~y=%%%p%%%|~y-%t1%|~y/10 ~/ ~/Macro FLOYD terminated normally, after %y% CPU seconds. ~/========================================================================== ~:end_of_macro ~o=6