Subj: XVRFY: Program for Testing Coverings, t-Designs, Wheels - An Update Version 1.15beta A new version of the program XVRFY, a fast program for testing Coverings, Wheels, Steiner Systems and t-Designs, has been released. [For an intro and the exact mathematical definitions of such designs see the "Definitions" section of the text below belonging to the pgm] XVRFY is a command line program for quick testing of such designs, with an optional combinatorial compression feature which is even better than PKZIP and ARJ (no joke! C++ source included; now with a second, much more effective Binary Compression option). NEW in v1.09: - implemented a new algorithm for Binary Compression (-g2) - Converting a filled design with uservalues back to a based design scheme without gaps (-z) - Finding Design Params from Scratch (-z2) - and much more - Beware: some parameters have changed! (-b to -h2 etc.) NEW in v1.11: - corrected a reported bug: added multipass (see -Q and -q) NEW in v1.13: - -D didn't work with -g2: corrected. Binary compresed output can be put to files only, if necessary to a temp file... - Put S48_6_5.ZIP on WWW to demonstrate the strength of the -g2 compression - Reactivated l > 1 - Added a new filename scheme (-f2). Now 3 schemes avail. NEW in v1.15: - -y3 added: selectable redundancy analysis - Bugfix: Cut after 32767 blocks dumped corrected. - README.TXT of S48_6_5.ZIP corrected for uncompress of S(48,6,5) For details see Version History and Installation section. The archive contains also some interesting sample designs for testing, and lists of such designs with proven bounds; see below for the contents of the archive. Locations on the net: http://www.tuco.com/math1.htm ftp.tuco.com/pub/math/ Filename: XVRFY115.ZIP or higher (110 K) S48_6_5.ZIP optional (290 K) 32RTM.ZIP optional ( 98 K) Uenal Mutlu the author Below is the output of the command XVRFY -h2 -n -h -i -j -------------------------------------------------------- XVRFY v1.15beta/32 960918We - FAST! Wheel, Covering, and t-Design Checker Copyright (c) 1996 Uenal Mutlu, Istanbul/TR + Munich/GER XVRFY -h for help * THIS IS A BETA RELEASE FOR TESTING ONLY; USE IT AT YOUR OWN RISK! * PLEASE REPORT ANY BUGS FOUND TO THE AUTHOR. XVRFY is a general Verification and Redundancy Detection Program for Covering Designs, Steiner Systems, t-Designs and Wheels Cmdline: XVRFY -h2 -n -h -i -j XVRFY Mathematical Definitions (-n): ------------------------------------ A Covering Design C(v,k,t,m,l,=b) is a pair (V,B), where V is a set of v elements (called points) and B is a collection of b k-subsets of V (called blocks), such that every m-subset of V intersects at least l members of B in at least t points. It is required that v >= k >= t and m >= t. The case m > k is also a valid case. B can be a multiset. Valid designs have usually v >= k >= t >= 1, m >= t, l >= 1, b >= 1 (this implies that t never can exceed k, and that m never can be less than t, and that m indeed can exceed k. Confused? :-) The case t=m=k is trivial since it's the complete design. For coverings it's requested to optimize the value b; ie. the less blocks the better -> Set Covering Problem (SCP). A t-design t-(v,k,l,=b) is an exact Covering with m = t and the least possible number of blocks. t-Designs do and can exist for some admissable parameters only, where also some numerical neccessary conditions are met. Steiner System S(v,k,t,=b) is also a t-design with usually l=1. Wheel is another name for Covering. So, Covering Design, as defined here, is a generalization of all the others. The parameters can easily be converted back and forth... For further info and more references on this topic I recommend the following books and papers published in the last years: C.J.COLBOURN, J.H.DINITZ (eds.) "The CRC Handbook of Combinatorial Designs", 1995, CRC Press: - R.MATHON, A.ROSA "2-(v,k,l) Designs of Small Order" 3-40 - R.J.R.ABEL, M.GREIG "BIBDs with Small Block Size" 41-46 - D.L.KREHER "t-Designs, t >= 3" 47-65 - C.J.COLBOURN, R.MATHON "Steiner Systems" 66-74 - D.R.STINSON "Coverings" 260-265 - C.J.COLBOURN "Winning the lottery" 578-586 - E.S.KRAMER "t-Wise Balanced Designs" 484-489 - G.H.J.Van REES "(r,l)-Designs" 434-436 - P.B.GIBBONS "Computational Methods in Design Theory" 718-740 R.GRAHAM, M.GR™TSCHEL, L.LOVASZ (eds.) "Handbook of Combinatorics" Vol.1+2 1995, Elsevier Science: - Ch.14: A.E.BROUWER "Block Designs" 695-745 Most of the published results on Covering Designs have concerned the case m = t. A good discussion and references on general m >= t and l >= 1 designs can be found in the following paper, which IMHO can also be seen as a good survey paper on such general covering designs. It's also available online at http://saturn.hut.fi: K.J.NURMELA, P.R.J.™STERGARD "Upper Bounds for Covering Designs by Simulated Annealing", Congr.Numer. 96 (1993) 93-111 The following paper deals with m = t designs and is also available online at the AMS Preprint Server at http://www.ams.org/preprints : D.M.GORDON, O.PATASHNIK, G.KUPERBERG "New Constructions for Covering Designs" J.Combin.Designs 3.4 (1995) 269-284 For an update of the bounds given in the above paper, and on obtaining enumerated m = t designs via email look at http://sdcc12.ucsd.edu/~xm3dg/cover.html (for most uptodate proven bounds and lists you can also ask some combinatorics wizards in the newsgroups sci.math* and rec.gambling.lottery) Also a very good survey paper on m = t designs is contained in the book J.H.DINITZ and D.R.STINSON (eds.) "Contemporary Design Theory" 1992, John Wiley & Sons: - W.H.MILLS, R.C.MULLIN "Coverings and Packings" 371-400 Also visit my new WWW-page for some texts, lists, programs and pointers: http://www.tuco.com/math1.htm See also -h, -i, -j XVRFY Help (-h): ---------------- Usage: XVRFY [options] Options are cAsE sensitive and of the format '-|/variable[[[=|:]value]|-|+]' where '-' means 0 and '+' means 1, which is normally the default if not specified. Some vars are 'overloaded'. Valid variables and their meanings, ranges, current values: -v total numbers in the design (1..54=49) -k block size (1..7=6) -t min match t (t of m) (1..7=3) -m min match of m (t of m) (1..7=6) -l lambda (min l times t of m) (1..255=1) -b nbr of blocks (>0=0 will be filled from file) -V,-K,-T,-M,-L,-B: end values for v,k,t,m,l,b -a input base (0..201=1) -p output base (0..201=1) -s show summary [needs also -x] (=0) -o max losing lines (>0=1) -r max report lines (>0=15) -x show dupe t-sets list (=0) -d show redundancy list (=0) -O overwrite (cf. -c,-e), if same filename exists (=0) -D if can't create file, dump to stdout (=0) -w sort the new sysfile it's going to create [cf. -c, -e] (=0) -c create sysfile with ID if redund. blks found (=0) -e create sysfile with ID (ie. copy) [needs also -y] (=0) -y verify the design (default) [cf. -e, -c and -d] (=1) -h2 batch mode (no keyboard requests) (=1) -f0 oldstyle fnames for create (uses 'a' for compatibility) (=0) -f1 oldstyle fnames for create (uses val(l) instead of 'a') (=1) -f2 newstyle fnames for create (base-36 fname) (=0) -g compressed i/o [0=none,1=ctext,2=cbin] (0..2=0) -N use exp sign (^), ie. RLE, in compressed outputs (=1) -G set avg linelength for textcompression (-g1) (32..224=64) -A seperator line [0=none,1=top,2=bottom,3=both] (0..3=0) -y2 conditional verify [overrides -y- if redundants found] (=0) -z close gaps (ie. nbrs have gaps between them) (=0) -z2 find design params from scratch. -T and -M should be set too. (=0) -S skip complete designs, ie. m=t=k (=0) -Q skipperHigh (0..25=7) -q skipperLow (0...5=3 will be calcd if not given) -y3 no redundancy testing (=0) -i shows technical info: min, max, def settings and limits, and quits -j shows version history, and quits -n shows mathematical definitions and references, and quits -h,-H,-?,--h shows this help, and quits v,k,t,m,l should always be given if file does not have an ID line. (for files with an ID line it's sufficient to give the fname only) Examples: XVRFY file (tests a file with an ID line in it) XVRFY file -t3 -m4 -l1 (overrides t,m,l of a present ID line) XVRFY file -v49 -k6 -t3 -m6 -l1 -z (tests a file with no ID line) XVRFY file -e (copy uncompressed) XVRFY file -e -g1 (copy compressed text) XVRFY file -e -g2 (copy compressed binary) XVRFY -h2 -h -i -j -n (dump all info; can be redirected) To convert files without ID all design parameters and -e must be given: XVRFY file -v12 -k6 -t3 -m3 -l1 -a1 -e To test all files with ID, placed in an own directory, I use the command FOR %i IN (???????a.???) DO XVRFY -h2 -c -A1 %i >>MY.LOG and analyze MY.LOG later for any of the words "Err", "FAIL", "Warn"... To quick look for redundants in all files with ID, placed in an own directory: FOR %i IN (???????a.???) DO XVRFY -h2 -c -y- -y2 -A1 %i >>MY.LOG (this does the required testing (for -c) conditionally: ie. only in case of redundants; therefore it's faster...) If not much is known of the parameters, try the following: XVRFY file -z2 -A2 -S -T5 -M6 >MY.LOG (this will work downwards from 'highest' to 'lowest' T and M. But will NOT write the results it finds to files; do it yourself the normal way by giving the just found params...) To find the 'best' params for the file <1100663a.345>: XVRFY 1100663a.345 -z2 -A2 and further finetune with: XVRFY 1100663a.345 -z2 -A2 -M4 and further finetune with: XVRFY 1100663a.345 -z2 -A2 -T3 -M3 etc... (As you can see there are multiple satisfying params. You have to compare against known or expected bounds; cf. lists...) o To verify files with no ID line use the third example above (for the meaning of v,k,t,m,l see the mathem. definitions under -n). o Use -z2 if you want detect the best (highest) design parameters. also use this if nothing is known about the parameters of the design. Fine-tune with -T and -M (ie. re-run with lower -T, -M)... o Use -z to close gaps (ie. convert back to a based design scheme). o Use -f0, -f1 and -f2 to create 3 different filenames for the same design. o To use bases other than the default (=1) see -p and -a (but: for compressed output (-g) it uses always 1) o Overriding a present ID line can be done by giving the t,m,l options, or in case of textfile by simply removing or commenting out the ID line (not recommended!) and giving all params via cmdline. o Noncompressed text files must contain blocks with k nbrs / line, seperated by spaces or commas. o The input design does not need be sorted. The output files can be sorted with the -w option (not required if -g used). o Comment chars are: '#' and ';'. Everything after these and everything not being numeric and '^' will be ignored. o Redundant blocks will be detected and shown (see -d -c -i). o Fastest way to detect missing combinations: -Q25 o To skip full testing (for converting, compressing etc.) use -Q5 -q5 o Currently, best compression is achieved with -e -g2 -N o ReturnCodes: 0=success, else fail. See also -i, -j, -n XVRFY Technical Information (-i): --------------------------------- XVRFY is written in C++ and compiled with Borland C++ 4.52 for target 32bit-commandline-pgm to be run in DOS-Boxes under running W95 or NT (for plain DOS support see INSTALL.TXT). It was developed and tested under W95į. Version: v1.15beta/32 960918We (BETA RELEASE) Date of Compile: Sep 18 1996 16:43:14 Compiled limits: MAX_V=54 MAX_K=7 MAX_T=7 MAX_M=7 MAX_L=255 MAX_B=2147483647 MAX_N=255 Flags: 1 0 0 0 Current settings: v=49 k=6 t=3 m=6 l=1 b=0 V=54 K=7 T=7 M=7 L=255 B=0 a usInBase=1 p usOutBase=1 s fShowSummary=0 r ulMaxReport=15 o ulMaxLosing=1 y fDoTesting=1 x fShowDupeTSets=0 d fShowRedundants=0 c fWriteNonRedundantsToFile=0 e fWriteToNewFile=0 h2 fBatchMode=1 w fSortOutput=0 f fUseL_InOldStyleFNames=1 f2 fUseNewFNameScheme=0 g bCompressed=0 N fComprUseExp=1 G ulComprAvgLineLen=64 fDoIdCreate=1 A usMskSeperatorline=0 y2 fForceTestingIfRedund=0 z fCloseGaps=0 z2 fFindDesignParams=0 S fSkipCompleteDesigns=0 Q ulSkipperHigh=7 q ulSkipperLow=3 y3 fNoRedundTesting=0 New algorithms: Depending on k,t,m, internally 3 different algorithms will be used. Now with a unique output. C(49,6,3,6,1,=168) and other enclosed sample designs; see -j for the list: The enclosed file 4901683a.616 contains this covering for testing. Since it contains an ID line, it's sufficient to use "XVRFY 4901683a.616" A compressed version of this can be found in the file 4901683a.6a6 Speed: Although this version is fast, a very fast special version for t <= 3 is available. It's faster than any other program I've seen. Testing of the above C(49)-design takes 74 sec. on my old i486/66-DX2 under W95į and 25 sec. on a Pentium-100 machine under W95. The special version takes for the same design less than 2 sec. only on the above i486-machine! Due to one of the algorithms used, the testing of m = t designs is always faster than designs with m > t. ID Hdr and Filename Scheme: it can read from any text file, both with or without any ID Hdr in it (cf. the sample designs supplied). For automatic reading in of the design parameters from the file the "ID" line needs to be defined at top of the file (its structure is explained in the file C_DECODE.TXT; cf. also the sample design files) The old filename scheme it uses for creating new files (see -c, -e, -f) is or (depending on -f) where 'a' is always the letter 'a' or 'A', and the others represent v,k,t,m,l,b. This scheme can and probably will change in future versions. (People wondered why it creates such 'cryptic' fnames. The reason is that all parameters can be obtained without opening and scanning the file...) NEW: -f2 creates where all values are BASE-36 !!! Limits: v=1..1295, k,t,m=1..35, l=1..1295, b=1..46655, xFlags=1..35 Dual Output: even if output was redirected to file for capturing, some selected info will also be shown on the screen. Limitations: - Currently, create of new oldstyle files works only for v <= 99, k <= 9, t <= 9, m <= 9, l <= 9, b <= 9999; otherwise it can be dumped to stdout and redirected to a file of your own choice (option -e -c -D) or use the new -f2 option for newstyle fnames described above. Compressed Design Data in Textfiles (-g1 only): Compressed data (-g1) can be sent in emails and posted to newsgroups since they contain printable ascii chars only (mainly digits, comma and the exp sign '^'). Line length can be set individually (see -G). Consult the enclosed file C_DECODE.TXT for detailed info and source code. Most of the enclosed designs are now in compressed format. Use -j to see a note on decompressing these files. Binary Compressed Design Data in Binaryfiles (-g2): So far, this option produces the shortest files. Since the data is in a special binary packed format created by a new compression algorithm, it must NEVER be edited or manipulated by the user or other programs. Consult C_DECODE.TXT on which encoding schemes currently exist (cf. -g) and how to detect which one was used. To give an example: The file '48bin_5a.516' (get S48_6_5.ZIP) contains the Steiner System S(48,6,5) which has 285384 blocks with 6 nbrs ea. It is uncompressed more than 5.7 MB big in size. XVRFY -g2 compresses it down to 289 KB only. In contrast to that the packers ARJ and PKZIP produce more than 1.4 MB and BZIP about 850 KB ... Use 'XVRFY 48bin_5a.516 -e -D -O -y3 -Q5 -q5 >s48txt_5a.516' to uncompress it and try to achieve a better result with any other packer to beat XVRFY... The i/o routines are not yet optimized (ie. buffered) for speed. See also -h, -j, -n XVRFY Version History (-j): --------------------------- EndDate Vers r=released Changes 960808ThUM 0.00 Project started. Initially, it was based on three other programs of mine (SYSTST, TESTIT and FASTTST) and VRFY v1.10 of R.K.Lloyd . All of these are somehow limited and/or for some special cases only. XVRFY was planned to be general as much as possible to handle all these design types and parameters, and as fast as possible using sophisticated algorithms. 960819MoUM 1.00įr First public version released, but not announced on the net 960821WeUM 1.01į Added the case l > 1. Corrected some minor display bugs. Added more sample designs and the lists, more text. 960822ThUM 1.02įr Added -e, -w. Announced for the first time in various math newsgroups. 960828WeUM 1.03įr Redundancy Detection now for all types. Faster Analyse. Unique output for all algorithms. Added -f. Added -g -G -N -D -O. Added C_DECODE.TXT. 960830FrUM 1.05 r Missing sample design file 2521715a.716 added. Version numbering chgd: in future all odd versns are beta. -a enhanced and -p added: now different i/o bases possible; including 0. C_DECODE.TXT updated. v1.03b's testing routine has a bug, whereas v1.02b didn't had this bug. Corrected now. Don't use v1.03b any longer! Now runs also under plain DOS with Extender (see INSTALL.TXT). 960901SuUM 1.07 In C_DECODE.TXT the right ulMagicMod constant is used in the code, but another was mentioned in the text. Clearified. BEWARE: Parameters changed! Added -y2 -A -z -z2. Chgd -M to -N. -L now other meaning. -b changed to -h2. New: V,K,T,M,L,B. l>1 is disabled due to some problems; will be re-enabled in the next versions. 960907SaUM 1.09 r Implemented a new compression algorithm: added new option -g2 for Binary Compression. Most of the enclosed samples now compressed with that to conserve file space. 960909MoUM 1.11 r Serious bug in the testing routine reported. -> made it multipass (-Q -q added) 960912ThUM 1.13 r -D didn't work with -g2: corrected. Put S48_6_5.ZIP on WWW to demonstrate the strength of the -g2 compression. Reactivated l > 1. Added -f2 (newstyle fnames) 960918WeUM 1.15 -y3 added. Cut after 32767 blocks dumped corrected. README.TXT of S48_6_5.ZIP corrected. Known bugs and limitations in this and previous versions: v1.03: testing routine buggy. Don't use it. v1.05: l > 1 buggy. Use for l = 1 only. v1.07: l > 1 disabled. Also in v1.09-v1.11 disabled. v1.09: (1.05-1.09) Testing routine has a serious bug; thanks to evetss@azstarnet.com (Steve Greeno) 960904We Things planned for the next version(s): - Extracting Sub-Designs - Optimizing I/O; esp. BitIO - Isomorphism testing of nonisomorphic designs - Locating other programs on the market for extensive comparisons of speed and features. Send me your experiences, pointers, locations, copies. Suggestions, recommendations, bug reports, algorithms, research papers and pointers to them are welcome. I'm also interested in new designs, algorithms, formula and construction methods, and esp. in algorithms on data compression, group and design theory, all kinds of optimization methods, and in fast computing methods and algorithms. Please use the email adress given below. The distribution archive XVRFY115.ZIP contains the following files: INSTALL.TXT Installation Info XVRFY.EXE The 32-bit executable for W95, NT, and DOS+Extender XVRFY115.TXT DOC of the pgm w/AnnouncementHdr for the net C_DECODE.TXT TechDoc on the compression schemes used 4901683a.616 Covering Design C(49,6,3,6,1,=168) 4901683a.6a6 do. compressed 2470845a.516 Steiner System S(24,6,5,=7084) 1100663a.345 t-Design 3-(11,5,4,=66); example for l <> 1 1841406a.716 Covering Design C(18,6,6,7,1,=4140); example for m > k 2521715a.716 Covering Design C(25,6,5,7,1,=2171); example for m > k k3sys.txt List of Covering Designs for k=3 k4sys.txt List of Covering Designs for k=4 k5sys.txt List of Covering Designs for k=5 k6sys.txt List of Covering Designs for k=6 k7sys.txt List of Covering Designs for k=7 To decode compressed designs use the -e option, but since XVRFY can handle both types, it's normally not neccessary. See also -h, -i, -n XVRFY Copyright Notice: ----------------------- Copyright (c) 1996 by Uenal Mutlu. All rights reserved. For publicly accessible research results only. The use of this version in any commercial environment, governmental or military institutions is strictly prohibited, that's: verboten! Please ask for special conditions. If the use of this program was of any help, a reference to XVRFY and its author (Uenal Mutlu) should be made in the research results. The author can be contacted via Internet: bm373592@muenchen.org (Uenal Mutlu) Also check the following locations for new versions and other files http://www.tuco.com/math1.htm ftp://ftp.tuco.com/pub/math/ XVRFY Installation Procedure (INSTALL.TXT): ------------------------------------------- Make a new subdirectory (I think it's called "folder" nowadays :-) and unpack all files in the shipping archive into that directory. The 3 files mentioned below, if present, should be moved to a directory in your PATH, or deleted if not required (see below). WIN95 and NT users should NOT require the following: * For this program to be run under plain DOS copy the two files below to a directory listed in your PATH setting, but do so only if they aren't already on your system. They enable 32-bit DPMI programs developed with Borland C++ compiler to run under plain DOS: 32RTM.EXE DPMI32VM.OVL * If it does not run in DOS boxes under Windows, check your SYSTEM.INI file [386Enh] section: there should appear the loading of the file WINDPMI.386: device=C:\WINDPMI.386 If not, insert this line and put WINDPMI.386 to C:\ After changing SYSTEM.INI you need to make a reboot. These procedures COULD also be neccessary for using the program under OS/2, but I have no experience with that. And same applies if you have WIN95, but do not run the Desktop. If you need these files, and don't have them already somewhere on your system, and if they also weren't in the archive, get the file 32RTM.ZIP (98 K) from the following locations on the net: http://www.tuco.com/math1.htm ftp.tuco.com/pub/math/ Give XVRFY -h to see the help page of the program Give XVRFY 4901683a.616 to test this enclosed design file XVRFY Original Archive Contents (see above for the descriptions): ----------------------------------------------------------------- PKUNZIP (R) FAST! Extract Utility Version 2.04e 01-25-93 Copr. 1989-1993 PKWARE Inc. All Rights Reserved. Shareware Version PKUNZIP Reg. U.S. Pat. and Tm. Off. ž 80486 CPU detected. ž XMS version 3.00 detected. ž DPMI version 0.90 detected. Searching ZIP: XVRFY115.ZIP Length Method Size Ratio Date Time CRC-32 Attr Name ------ ------ ----- ----- ---- ---- -------- ---- ---- 1644 Implode 1004 39% 09-03-96 18:42 385e675c --w- INSTALL.TXT 22347 Implode 9878 56% 09-18-96 16:46 184e98e4 --w- XVRFY115.TXT 139264 Implode 74752 47% 09-18-96 16:43 78df4e0b --w- XVRFY.EXE 13225 Implode 4897 63% 09-11-96 00:42 86af0559 --w- C_DECODE.TXT 4232 Implode 1785 58% 09-07-96 15:19 142016f3 --w- 4901683A.616 507 Stored 507 0% 09-07-96 04:04 2612cb54 --w- 4901683A.6A6 7119 Stored 7119 0% 09-07-96 04:00 9d47fff1 --w- 2470845A.516 124 Stored 124 0% 09-11-96 00:34 d8ac64fc --w- 1100663A.345 3821 Implode 2851 26% 09-07-96 04:00 39fba1b8 --w- 1841406A.716 1166 Stored 1166 0% 09-07-96 04:01 b2367317 --w- 2521715A.716 7940 Implode 2513 69% 09-13-96 02:33 08aa6677 --w- K3SYS.TXT 10509 Implode 2979 72% 09-13-96 02:33 3591f99e --w- K4SYS.TXT 12395 Implode 3355 73% 09-13-96 02:33 05fecdbb --w- K5SYS.TXT 13631 Implode 3544 75% 09-13-96 02:33 ca523e7b --w- K6SYS.TXT 14250 Implode 3643 75% 09-13-96 02:33 82954ef6 --w- K7SYS.TXT ------ ------ --- ------- 252174 120117 53% 15 (XVRFY???.TXT can vary in size)