tar xvf gens.tar
to unpack software.
make all
in directory gens. Modify the makefile in that directory if needed.
The script uses shell variables to pass values to scripts it calls. One can edit a corresponding script to set script-specific variable values if desired.
run-core L
For example, to get the data for programs h_prf and f_prf, run run-core h_prf f_prf. Program output appears in the gens/results directory.
One can run the main script on each maxflow program individually as well as on a list of programs. One can also run each auxiliary script individually. In this case, one needs to set the above-mentioned variables in the shell or edit the script and set the variables.
One also needs to edit the scripts to change problem parameters. In particular, one may need to change the range of network sizes to fit a test machine size and speed. Next we outline generators and problem families.
The generator has the following parameters:
genrmf a, b, c1, c2, seed
The core experiments include three GENRMF families defined by the following parameter values (for a network with 2^x vertices):
The default set of values for (a, b) pairs for the GENRMF-LONG family, used in the gens/scripts/rmg-long script, is {(8 64), (10 91), (11 128) (13 181) (16 256) (19 362) (23 512) (30 724)}. These values correspond to x ranging from 12 to 19.
The default set of values for b pairs for the GENRMF-LONGER family, used in the gens/scripts/rmg-longer script, is {1024, 2048, 4096, 8192, 16384, 32768}. These values correspond to x ranging from 12 to 17.
The default set of values for (a, b) pairs for the GENRMF-WIDE family, used in the gens/scripts/rmg-wide script, is {(28 5), (37 6), (49 7) (64 8) (85 9) (111 10) (147 12) (194 14)}. These values correspond to x ranging from 12 to 19.
washington function arg1 arg2 arg3 seed
where function specifies the desired graph type, seed is a seed for the pseudorandom number generator, and the remaining arguments are interpreted depending on the function type. We use function types two (random level graphs) and six (basic line graphs). In both cases, graph vertices correspond to points on a rectangular grid with arg1 rows and arg2 columns. In addition, there is a source, connected to every vertex in the first row, and a sink, to which every vertex in the last row connects.
For random level graphs, agr3 determines ranges from which arc capacities are chosen. For each column except for the last one, every vertex is connected to three randomly chosen vertices in the next column. Capacities of the connecting arcs are chosen uniformly at random from the range [1...arg3]. Capacities of the source and sink arcs are chosen independently at random from the range [1 ... 3*arg3].
For basic line graphs, arg3 determines vertex outdegrees. Vertices of a basic line graph can be thought of as points on a line, numbered from 0 (source) to arg1 * arg2 + 1 (sink). Other arcs are generated as follows. For every vertex i other then the source and the sink, pick a random subset of size arg3 from the set {1,...,arg2*arg3}. Then for each j in this set, if k = i + j < sink, then we connect i to k by an arc with capacity chosen uniformly at random from the range [1...1,000,000]. The source and the sink arc capacities are chose independently at random from the interval [1 ... arg3*1,000,000].
The core experiments include three WASHINGTON families defined by the following parameter values (for a network with 2^x vertices):
The default set of values for arg2 in the WASHINGTON-RLG-LONG problem family, used in gens/scripts/wash-rlg-long script, is {128, 256, 512, 1024, 2048, 4096, 8192, 16384}.
The default set of values for arg1 in the WASHINGTON-RLG-WIDE problem family, used in gens/scripts/wash-rlg-wide script, is {128, 256, 512, 1024, 2048, 4096, 8192, 16384}.
The default set of values for the (arg1, arg3) pair in the WASHINGTON-LINE-MODERATE problem family, used in gens/scripts/wash-line-moderate script, is {(1024 16) (2048 23), (4096 32), (8192 45), (16384 64)}.
ac n capacity seed
The generator produces a complete acyclic graph with n vertices by connecting every vertex to all higher-numbered vertices. Arc capacities are picked uniformly at random from the interval [1...capacity]. Pseudorandom number generator is seeded with seed. Vertex 1 is the source and vertex n is the sink.
We call the family of problems produced by this generator ACYCLIC-DENSE. This family has capacity set to 1,000,000, and n = 2^x for consequtive integers x. The default set of values of n, used in gens/scripts/ac-dense script, is {256, 512, 1024, 2048}.
AK n
where n is the number of vertices. Note that the generator is fully deterministic and does not use a random numer generator.
The core experiments include one AK family with n = 2^x. The default values of x are {1024, 2048, 4096, 8192, 16384, 32768}