Priority Queue Tests -- Dijkstra Problems

Here's what you have to do to run the Dijkstra problems for Priority Queue tests in DIMACS Challenge 5. These files form a subset of Andrew Goldberg's SPLIB library of shortest-paths programs; they were modified for use in Challenge 5 by C. McGeoch.

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

• Get the splib compressed tar file. You will also need an extra graph generator program that is compatible with SPLIB.

  NOTE: In May 2003 the ftp site was relocated. Here are the new locations for the splib compressed tar file and the graph generator program .

• First compile the necessary SPLIB files and move to the input directory.

     uncompress splib_pq.tar     (if your browser hasn't already )
     tar -xf splib_pq.tar        
     cd splib_pq 
     make bin/dikh
     make bin/sprand
     make bin/spgrid
     cd inputs
     

• Now, typing dimacs_rand_4 dikh will cause 15 priority queue trace files to appear in the directory ../results. These represent 5 random trials at each of 3 problem sizes (2^18, 2^19, 2^20). These graphs produce relatively small queue sizes.

  Note: Problem size here is the number of nodes in the graph. This equals the number of inserts and deletes in the priority queue trace file, and in addition there are many decrease-keys. If you can't handle problems this large, edit the file rand_4 to get the 3 largest problem sizes you can handle.

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

• Typing dimacs_grid_slong will cause 15 more priority queue trace files to appear in ../results. Again, there are 5 random trials at each of 3 problem sizes (2^17, 2^18, 2^19). You can edit grid_slong to get smaller problems: here the graph size is found by multiplying the first two integers on the command line.

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

• The other tar file contains an extra graph input generator. These graphs maximize the number of decrease-key operations performed by Dijkstra's algorithm. Copy dikh from your splib_pq directory so you can use it here. Type

       uncompress hard_sp.tar    (if your browser hasn't already)
       tar -xf hard_sp.tar
       gcc -04 -o spbad spbad.c -lm
       dimacs_spbad 
       

  This generates 15 priority queue trace files, representing 5 random trials at each of 3 problem sizes (2^9, 2^10, 2^11). As before, problem size equals the number of inserts and deletes in the trace files. The largest files (2048 inserts/deletes) will have around 9500 decrease-keys. When the dimacs_spbad 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.