Priority Queue Tests -- Nagomochi-Ibaraki Problems

Here's what you have to do to run the Nagomochi-Ibaraki problems for Priority Queue tests in DIMACS Challenge 5. This implementation of the Nagomochi-Ibaraki is joint work of C. Chekuri, A. Goldberg, D. Karger, M. Levine, and C. Stein (with modifications and additions by C. McGeoch.)

This is an intermediate version of the code which is made available only for Challenge 5 priority queue tests.

Send Cathy a note if you have questions or need help.

• Get the compressed tar file.

• Unbundle, compile and run it:

     uncompress mincut_pq.tar     (if your browser hasn't already)
     tar -xf mincut_pq.tar
     cd mincut_pq 
     make noigen
     make ni
     dimacs_tests
     

• The last command will cause 15 priority queue trace files to appear in the directory. These represent 5 random trials at each of 3 problem sizes (2^11, 2^12, 2^13).

  Note: problem size is the number of nodes in the graph for the min-cut algorithm. This is equal to the number of inserts and deletes in the priority queue trace file, and in addition there are many more increase-keys. If you can't handle problems this large, edit the file dimacs_tests to get the 3 largest problem sizes (powers of 2) you can handle.

• Nagomochi-Ibaraki uses max-priorities not min-priorities. To do min-priority tests, you'll have to convert these max files to min files. For each file nix.foo, type the following:

       findmax nix.foo             (Returns X, the max priority in the file. )
  
       maxtomin X ni.foo   
                                      (Subtracts all priorities from X+1, 
                                       changes "dmx" to "dmn", "icr" to "dcr",
                                       and removes "siz" lines.)
       

  Note: A prize will be awarded to the first participant who submits a Unix script to automate this. Or, if you have enough space to make the end-result files available to the public by anonymous ftp, please do so and send us a note giving their location.

  If you have a max-priority queue, then you can test it with the original files, but you'll have to modify the driver. (Just change "dmn" to "dmx" and "dcr" to "icr" in the driver specifications.)

• When the ni.foo trace files are ready, give them to your test driver to perform the priority queue tests .

Back to the Challenge.

Back to the Priority Queue Tests.