Stallmann, Brglez, Ghosh: Data Formats

The actual data used and generated to obtain the results reported in the paper can be reconstructed using the random number seeds in the file SEEDS_ISO (for isomorphic classes) or SEEDS_RND (for random graph classes). Each line of these files has the name of a class followed by the three 16-bit unsigned integers used to construct the seed for the IEEE 48-bit random number generator (rand48 library).

The data directory (after the desired bigraph classes are generated or the top-level directory in the other archive) contains a subdirectory for each bigraph class. These subdirectories are named as follows (using the organization of Table 2 in the paper). In all cases k is a two-digit encoding of the rank, padded with a 0 when needed.

• GB_a_rnd0_k - these are the directories for R(a,m), where a is expressed in decimal notation, with the letter p representing the decimal point, and m = 15 * 2^k - 10.
• GB_1_rndd_k - directories for R(1,m,d), where m is based on k as with GB_a_rnd0_k, and d is the dimension in decimal with p representing the decimal point.

• G_r_k - grid graphs G_r,k
• G_b_k - butterfly graphs G_b,k
• G_h_k - hypercubes G_h,k
• G_xy_k - VLSI graphs G_xy,k, where x is 0, 1, or 2 (meaning the density factor a is 1, 2, or 4), and y is 0 or 1 (meaning "easy or "hard")
• G_t_rnd0_k - rnd(X), where X is of rank k and type t, and t is one of b (butterfly), h (hypercube), r (grid), 0y (VLSI tree), 1y (VLSI graph with a=2), or 2y (VLSI graph with a=4); it does not make sense to distinguish between "easy" and "hard" here.

Before any experiments are executed, each class directory with name C contains two files for each subject, one is C_s.dot, where s is the subject sequence number, encoded in 4 digits padded with 0's, and the other is C_s.dot.ORD. The first describes the bigraph itself; the second describes the permutation of each layer. C_s.dot contains a description of the bigraph in simplified dot format (based on the paper by Gansner et al.; our parser can deal with more general formats, but will ignore any nonessential information about the geometry of nodes).

Dot format.

The expected format of our dot files is

digraph graph_name { statement ; ... statement ; }

layer0_node -> layer1_node

The graph name and node names must be legal C identifiers (begin with an alphabetic character, have any number of alphanumeric characters, and underscore counts as an alphabetic character). Arbitrary white space is allowed between and within statements. Comments delimited by /* ... */ count as white space.

Graphs generated by our programs always have a comment giving the three short integers of the rand48 seed right after the graph name. The graph name is usually the same as the file name (with the .dot extension).

Ord format.

layer_number { node ... node }

Anything between a # and the end of the line is interpreted as a comment. Arbitrary white space and/or comments can occur before the {, between nodes, or on either side of a layer description.

Other data files.

The program that executes our treatments generates an ord file with name graph_name_trt.ord where t is a 4-digit encoding of the treatment number. The execution scripts delete this file after it is no longer needed, but they can be edited to omit this step.

When a treatment is executed on subjects of a class, the execution scripts create a file TRt in the class directory, where t is a 2-digit encoding of the treatment number. The file has two columns (tab-separated), with graph names in the first column, and number of crossings after the treatment was applied in the second.

Summary files, created by the script sbg_summary, and containing summary information for a given class, have names of the form SUMMARY_class-directory. There are also files that record information about total time and number of iterations, called TIMING_SUMMARY_class-directory and ITR_SUMMARY_class-directory, respectively.

Files generated for comparison with the Jünger-Mutzel paper begin with the prefix GN_JM_. This is followed by S_size for the sparse graphs, where size is the number of nodes per layer, or 10_density for 10+10 graphs of increasing density. Similar graphs with prefix GC_JM_ are generated, as are most of our graphs, in such as way as to ensure connectedness.

There are also a few classes with prefix GN_ replacing the usual GB_ in the random classes. These, like the graphs used in the Jünger-Mutzel paper, use a simpler random-graph generation technique that does not ensure connectedness.