How to use vaxrandom

How to use vaxrandom.c

Vaxrandom (now version 3.01) takes in a vax file of the standard format and creates a random perfect matching of the corresponding graph. An example of a file of the correct format is

#Creator: drawtiling.c
#Vax file
#Title: Fortress of order 4
8 16
     AAVVAA
    AVVAAVVA
 AAVVAAVVAAVVAA
AVVAAVVAAVVAAVVA
VAAVVAAVVAAVVAAV
 VVAAVVAAVVAAVV
    VAAVVAAV
     VVAAVV

All of the # lines are comments, ignored by vaxrandom but useful for reference. The first line under the comments contains the maximum number of rows and columns to allocate for the region. If these numbers are too small, vaxrandom will not allocate enough space for the matching and will return an error. If the numbers are larger than the number of rows and columns, it is fine with vaxrandom; vaxrandom will allocate more space than needed.

The VAX characters behave in the standard way. X matches all four directions, A all directions except up, V all directions except down, < all directions except left, and > all directions except right.

Vaxrandom uses the standard Propp-Wilson algorithm by first making a perfect matching using a breadth first search and a max-flow algorithm. It reports right away if the region does not permit a perfect matching. It then computes the maximum and minimum matchings of the region and finally it raises and lowers cycles in the matchings so that the two matchings coalesce. The algorithm starts with an initial number of timesteps (remembering the random coin flips it used), and if the lower and upper matchings didn't coalesce, it goes back twice as far into the past and tries again. It continues until it succeeds.

Options for vaxrandom

Vaxrandom excepts a number of command line arguments. Without any arguments, you just run it by typing "vaxrandom ", but it excepts options at the end. Note some of these options are debugging options.

-vax outputs a random perfect matching in ASCII form using brackets and AV to denote edges. This is the default.
-ps outputs a random perfect matching as a postscript file.
-height outputs a height function of a random perfect matching where the height of each vertex is the number of times a cycle with that vertex has been raised. The height at a vertex is -1 if the vertex is outside the region. This option is not used much anymore.
-seed [value] uses the specified value as the initial random seed. This allows for the reproducibility of experiments. One bit of caution though is the seed depends on what platform you are using.
-initial [value] starts the Propp-Wilson algorithm using [value] timesteps back in to the past. The default is 128.
-minonly doesn't compute a random matching; only outputs the minimum matching
-maxonly doesn't compute a random matching; only outputs the maximum matching
-showcycles doesn't compute a random matching; only outputs the index of each cycle of the graph. Used for debugging.
-report print a progress report of the Propp-Wilson algorithm giving output like
Starting at time -128, at time -32, max is 76, min is 22, difference is 54.
which shows the initial value of t, the current value of t, and the volume under the upper and lower height functions and their difference. The upper and lower matchings have coupled when their volumes are equal and the difference is 0. By looking at the report, we can see if the Propp-Wilson algorithm is close to finishing or if there is a long way to go. This is useful when computing random perfect matchings of large regions that are expected to take a long time.
-time Gives the time that the Propp-Wilson reached certain points in the computation. This is also useful for large regions that are expected to take a long time.
-bound [value] starts with the upper matching, randomly flips cycles for value time steps (not using Propp-Wilson) and outputs the final state of the matching. Note this does not yield a random perfect matching.
-version outputs the current working version of vaxrandom.
-help outputs a brief help message on how to use vaxrandom.

Example usage

For a simple example on how to use vaxrandom, create a region using drawtiling and then use vaxrandom. Here is an order 4 fortress.

athena% drawtiling -fortress 4 > fort4
athena% vaxrandom fort4
Matching    88 vertices                                     end mark V
......................................................................
This is vaxrandom version 3.01.
The initial seed was -1954326176.
Random matching generated after 128 time steps.
#Matching
#Creator: vaxrandom.c
#Platform: sun4
#Title: Fortress of order 4
#Seed: -1954326176
#Random matching made in 128 timesteps
8 16
     <><><>     
    A<>A<><>    
 A<>V<>V<>A<>AA 
AV<>A<>A<>V<>VVA
VA<>VAAV<><><>AV
 V<>AVVAA<>A<>V 
    V<>VVAAV    
     <><>VV

This output is a random matching of the fortess shown earlier.

If you have any questions or comments, send an email to mdblum@mit.edu .

-vax	outputs a random perfect matching in ASCII form using brackets and AV to denote edges. This is the default.
-ps	outputs a random perfect matching as a postscript file.
-height	outputs a height function of a random perfect matching where the height of each vertex is the number of times a cycle with that vertex has been raised. The height at a vertex is -1 if the vertex is outside the region. This option is not used much anymore.
-seed [value]	uses the specified value as the initial random seed. This allows for the reproducibility of experiments. One bit of caution though is the seed depends on what platform you are using.
-initial [value]	starts the Propp-Wilson algorithm using [value] timesteps back in to the past. The default is 128.
-minonly	doesn't compute a random matching; only outputs the minimum matching
-maxonly	doesn't compute a random matching; only outputs the maximum matching
-showcycles	doesn't compute a random matching; only outputs the index of each cycle of the graph. Used for debugging.
-report	print a progress report of the Propp-Wilson algorithm giving output like Starting at time -128, at time -32, max is 76, min is 22, difference is 54. which shows the initial value of t, the current value of t, and the volume under the upper and lower height functions and their difference. The upper and lower matchings have coupled when their volumes are equal and the difference is 0. By looking at the report, we can see if the Propp-Wilson algorithm is close to finishing or if there is a long way to go. This is useful when computing random perfect matchings of large regions that are expected to take a long time.
-time	Gives the time that the Propp-Wilson reached certain points in the computation. This is also useful for large regions that are expected to take a long time.
-bound [value]	starts with the upper matching, randomly flips cycles for value time steps (not using Propp-Wilson) and outputs the final state of the matching. Note this does not yield a random perfect matching.
-version	outputs the current working version of vaxrandom.
-help	outputs a brief help message on how to use vaxrandom.