LEDA Assignment 1: Hello, LEDA!
LEDA, a Library of Efficient Data Structures and Algorithms, was developed by Naher and Mehlhorn of the Max-Planck-Institut fur Informatik, Germany. LEDA is done in C++ and includes a vast library and multiple implementations of most of the common basic and some advanced data structures studied in this course. It also includes library of many of the combinatorial and graph algorithms covered in the course.
LEDA helps to make it more painless to incorporate advanced data structures into C++ applications.
Your task is to run Dijkstra's algorithm for computing shortest path in a graph using seven different heap implementations. The purpose of this exercise is to give you a feel of how your choice of data structures may affect the performances of Dijkstra's algorithm.
All the files needed for this assignment can be found in this leda1.zip archive.
In this assignment, you are given a LEDA program LEDAdijkstra.cpp (also an automated version, LEDAdijkstra2.cpp that contains four different implementations of Dijkstra's algorithm for shortest path in a graph. This program will first create a random directed weighted graph G and then ask the user to choose an implementation of Dijkstra's algorithm among four implementations -- 1:f_heap 2:k_heap 3:m_heap 4:list_pq
All the files needed for this assignment is found in leda1.zip. We recommend working on your assignment in the UNIX environment. After logging in to the UNIX environment on sunfire, you can download the archive using the wget program as follows:
wget http://www.comp.nus.edu.sg/~cs5206/2010/LEDA/leda1.zip
You can then extract the contents using the unzip program as follows:
unzip leda1.zip
This will create a directory named leda1 containing the files for this assignment.
Compile LEDAdijkstra (make LEDAdijkstra) and run it a few times to get familiar with the interface of the program. After you get a hang of it, compile the automated version of this program (make LEDAdijkstra2) for your performance evaluation. Besides being non-interactive, the automated version also generates 100 graphs so that an averaged value for each data structure can be obtained.
Edit LEDAdijkstra2.cpp to include three more heap implementations -- p_heap, r_heap and bin_heap. In total, LEDAdijkstra2 should automatically run Dijkstra's algorithm using seven different heap implementations.
Compare the performance of Dijkstra's algorithm for each of the seven heap implementations on graph of different sizes -- n=2000, 4000, 8000, 16000, 32000. For each n, run it on different edge sparsity -- m=10n, 15n, 20n, 25n, 30n. For all graphs, you can use the same max-edge-cost M=1,000,000).
Note that this exercise is also about experimental research methods. There are several problem paramemters you are dealing with:
You have to figure out how to deal with these multiple dimensions and to present tables/graphs that allows you to draw meaningful conclusions (well supported by data/graphs/tables). Often, you will also need to combine theory and practice in making different conclusions or explaining the conclusions/observations.
Minimally, you should plot running time (t) versus number of node (n) for each edge sparsity and running time (t) versus number of edges (m) for each value of n. Where necessary, you may also want to run more experiments (what I specify is a baseline) to test out certain hypotheses of your own.
Write a brief report on your comparisons and observations. Submit your comparison graphs together with your report (you don't have to include the data tables in the report).
[Note: Part of your grade will also be one how well organized
your report is, how well you have done your comparisons, and your
comments and conclusions drawn from your comparative study.]
Please put these two files one folder/directory called CS5206-LEDA-[your-name]. Then zip the folder/directory into a file called CS5206-LEDA-[your-name].zip.
Submit this zip file to CS5206 IVLE workbin called "CS5206-LEDA".
LEDA provides many implementations of priority queues. The implementations include Fibonacci heaps (f_heap), pairing heaps (p_heap), k-nary heaps (k_heap) and binary heaps (bin_heap), redistributive heaps (r_heap), lists (list_pq) and buckets (b_heap) [See Note], and monotone heaps (m_heap). Fibonacci heaps are the default implementation and other implementations acan be selected using the implementation parameter mechanism. Following is a list of related biography
Note: In the list implementation the items of the queue are stored as an unordered list. This makes delete_min and find_min linear time process (linear search through the entire list) and trivalizes all other operations. In the bucket implementation we have an array of linear lists; the list with index i contains all items whose priority is equal to i. This scheme requires the priorities to be integers from a prespecified range.