Your task is to implement Prim's algorithm for undirected graphs,
using a binomial heap as
the basis for a priority queue.
Your program will process a file containing a description of a graph. A
graph description contains an arbitrary number of edge descriptions. An
edge description consists of two vertices (optionally followed
by a weight) followed by a semicolon.
A vertex is simply a
If a weight is omitted, a weight of 1 should be assumed.
A weight is a non-negative integer.
The file should be free format; whitespace may appear
Here a sample graph description:
1 5 ;
214 33 1
which is equivalent to:
1 5 ;
2 10 23 ;
214 33 1 ;
In this example
there are six vertices, named 1, 2, 5, 10, 33, and 214, and three
edges, 1 to 5, 2 to 10 and 214 to 33, with weights 1, 23, and 1,
The name of your executable must be prim
the name of the file describing the graph will be passed to your program as a
command line argument,
$ cat g1
1 2 1 ;
2 3 2 ;
3 1 3 ;
$ prim g1
[output appears here]
Your program should interpret the graph description
as an undirected graph and should report
the minimum spanning tree with the first vertex mentioned
in the graph description as the source
vertex. Any unconnected vertices are ignored.
The output of your program
should be a spanning tree,
displayed as a breadth-first traversal followed by the
Here is an example display:
$ cat g2
10 0 9 ;
6 7 11 ;
5 9 1 ;
4 8 7 ; 10 8 6 ;
11 12 2 ;
1 6 5 ;
0 6 10 ; 0 5 3 ; 0 4 8 ; 0 3 2 ; 0 1 4 ;
$ prim g2
4: 1(0)4 3(0)2 5(0)3
5: 6(1)5 9(5)1
Each level of the traversal starts
with the level number (level 0 is the first level),
followed by a colon, a space, and
space separated list of
A vertex description is the vertex
followed by its breadth-first-search predecessor (in parentheses) followed
by the weight of the edge from the predecessor to
the vertex in question.
The vertex descriptions in a level are to
be ordered by increasing vertex number.
You must follow the format exactly as diff will be
used to assess your output.
Your executable must handle a
-v option, as in previous assignments.
You must implement the your binomial heap as a separate module named
binomial.c and binomial.h
Likewise, you will need a vertex class
and an edge class
You may use my vertex and edge classes:
Modifications to existing classes
You will need to add the following methods to the DLL class:
You will also need to modify the insertDLL method to return the
newly created node holding the inserted value. Return the node as
void removeDLLall(DLL *) - sets the head and tail to null, the size to
zero. Only freeing of list nodes, not values, is to be done.
void *removeDLLnode(DLL *,void *) - removes the given node from the linked
list, return the value of the removed node
void firstDLL(DLL *) - start a DLL iterator, setting an object variable
to point to the head node
void lastDLL(DLL *) - start a DLL iterator, setting an object variable
to point to the tail node
int moreDLL(DLL *) - returns true if the current node is not null,
void nextDLL(DLL *) - moves the current node to the next node in the list
void prevDLL(DLL *) - moves the current node to the previous node
in the list
void *currentDLL(DLL *) - returns the value at the current node
void * pointer.
decreaseKey in time
In order to decrease the value of a vertex key quickly, the vertex object
needs to hold a pointer to the node in the binomial heap that holds
the vertex. Suppose that field in a vertex object is called owner.
Then, when inserting a vertex into the heap, one saves the return value
By saving this information, when the key of a vertex v is decreased,
the heap can be informed efficiently:
Also, when a decreaseKey operation is called, the vertex may bubble
up a subheap. In such cases, the binomial heap node holding the
vertex will change. To keep up with these changes, an update function
is passed to the binomial heap constructor:
update(void *v,void *n) //v is a vertex, n is a binomial heap node
VERTEX *p = v;
p->owner = n;
In order for your program to run on a randomly created graph, if an edge
is given more than once, ignore subsequent occurrences.
If a edge is given, also ignore edges,
since the presence of a edge implies the presence of a edge.
You must use an adjacency list for storing the graph.
You must be able to identify a duplicate edge in time.
You must be able to add a non-duplicative edge to the adjacency list
Use AVL trees to store edges and vertices to achieve these time bounds.
If more than one vertex is eligible to be added to the growing minimum
spanning tree at any given point,
chose the vertex with the larger vertex number.
You cannot use any fixed-sized data structures for storing information
You many not use built-in data structures (other than arrays for
sorting the display output).
All operations must run as efficiently as commonly expected.
When given an empty graph, the executable should display the
EMPTY followed by a newline.
You must implement your program in C.
Only the most foolish student
would not recompile and thoroughly test the implementation on a Linux
You must provide
a makefile which responds properly to the commands make,
make valgrind, and make clean. The make
must compile the prim executable no errors or warnings and it must
compile with the highest level of error checking (the
-Wextra options plus
The make test command should run your program through some test
files of your choosing. The make valgrind command should run
your tests through valgrind. The make clean command should remove
all intermediate files, including the executable prim.
All code you hand in should be attributed to its author. Comment
sparingly but well. Do explain the purpose of your program. Do not
explain obvious code. If code is not obvious, consider rewriting the
code rather than explaining what is going on through comments.
You must pass all tests for your program to be graded.
Handing in the application
For preliminary testing,
make clean and then
send me all the files in your directory by running the command:
submit cs201 lusth test3
For your final submission, run a
make clean and use the command:
submit cs201 lusth assign3
Again, your implementation may be developed on other hardware and
operating systems, but it must also compile and run cleanly and
correctly on a Linux system.