Project 5 is worth 6% of your grade.

This project deals with graphs and the Four Color Theorem.

Four Color Theorem - given a planar graph, one can color the vertices of the graph so that

• no adjacent nodes have the same color
• at most 4 colors are used.

A graph is planar if it can be drawn in a plane so that no two edges cross.

A simple graph is one which contains no multiple edges or (self) loops.

A set is an associative container that stores keys (vertices).

• duplicate keys are not allowed
• the set container stores keys in ascending sorted order

This project teaches you about graphs. While it is effortless to draw and color a graph on paper, representing such a structure and working with a computer representation are less obvious. The goals of this project are to:

1. Understand planar graphs.
2. Be able to represent a graph as an adjacency list.
3. Manipulate graphs by coloring the vertices.
4. Determine and implement an algorithm that will color a planar graph with the fewest number of colors.
5. Implement an in-place heapsort on a set.
6. Write comments based on CMSC 214 Style Guide.

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Students are expected to write "clear and legible" code. Please review the following Style Guide which specifies how students in CMSC 214 are expected to lay out their code:

http://www.cs.umd.edu/class/fall2002/cmsc214/Projects/styleguide.txt

Answers to "frequently asked questions" will be posted via the main projects page. Prior to asking a question or submitting a project you should check the FAQ to see if any important information has been covered there. In addition to answers to FAQ's any important information pertaining to a project will be posted on it's FAQ.

For this project you will be required, among other things, to write the code for four classes:

class 1: Adjlist
class 2: Node
class 3: GNode
class 4: Graph

• No public functions or (public, protected, or private) data members may be added to the header files.
• Your output must match our output, an example of which is provided in output1.txt
• You may not change the input - as provided in input1.txt
• Adjlist must be a set of nodes adjacent to a particular vertex.
• A summary of set operations is provided in your text on pages 595-596
• The input will contain multiple edges and self loops
• You will strip out multiple extra edges and self loops so your graph will be a simple graph.
• There is no particular order to the nodes in the input files
• You must use the colors 'R', 'W', 'B', 'G'
• the printer() method in Graph should print after heapsort has been executed.
• Nodes with accompanying adjacency list will be in order by vertex degree (high to low)

After copying the header files Graph.h, GNode.h, Adjlist.h and Node.h into your account you should create the corresponding Graph.cpp, GNode.cpp, Adjlist.cpp and Node.cpp files and write the code that implements the member functions for these classes. Note: you may NOT change the public methods in the header files but may add private methods as needed. You may NOT add private, public or protected data members.

Note that Node is a base class and GNode is derived from Node. Neither of these classes is inherited by Graph. However, Graph CONTAINS a vector of GNodes. Node CONTAINS a set of Adjlist.

In each header file you will find the class with it's data member(s) and member function(s). There is a comment before/around each member function describing what it should do and you are to implement (aka write the code for) the member function so that it does what the comment states that it should do and nothing more.

Next you should write four unit test files to test each of your classes:

• AdjlistUnit.cpp
• NodeUnit.cpp
• GNodeUnit.cpp
• GraphUnit.cpp

A unit test file should be a main() that calls each public method and also tests the private methods. Note that when developing/writing code you should do so in pieces/parts and test them as you go (keeping backup copies!).

And finally you should write a:

main.cpp

Your main program should use the four classes created earlier to accomplish it's task and you may *not* write any other classes.

You may assume that

• the graph is planar
• the graph is an undirected graph
• the graph is connected
• the graph will become a simple graph once multiple edges and loops are removed
• the nodes will be labeled from 0 to N-1 where N is the total number of nodes in the graph
• the input file will contain
• a list of nodes adjacent to node i, and may include the node itself
• a list of N adjacency lists, in random order
• a carriage return at the end of each line in the file
• see the reader function in Graph.h for further description
• planar graphs imply 4 colors or less; 4 colors or less DOES NOT imply the graph is planar

You may assume:

• There are no blank lines in the input file.
• Each line terminates with a carriage return.
• The last line contains an EOF marker.
• The graph might not be asimple graph .

A primary input file and a primary output file are provided in the class posting accounts (in the appropriate directory). You should review these files. They will be named input1.txt and output1.txt respectively.

You should make sure your graph is simple - no self loops or multiple edges.

Input1.txt         meaning:
0 3 3 4              vertex 0 is adjacent to vertex 3, vertex 3, vertex 4
                          (ie. there are multiple edges between 0 and 3)
                          when these are inserted into a set, only one 3
                          will be inserted
1 2 4                 vertex 1 is adjacent to vertex 2, vertex 4
2 5 3 2 1           vertex 2 is adjacent to vertex 5,3,2 (self loop) and 1
                          you must check each time to remove possible self
                          loops of the starting vertex
                          your adjacency list should be {1,3,5}
3 2 0 0               vertex 3 is adjacent to vertex 2, vertex 0, vertex 0
4 5 4 0 1           vertex 4 is adjacent to vertex 0, 1, 4, 5
                          get rid of self loop (44)
                          your adjacency list should be {0,1,5}
5 2 4 4 2           vertex 5 is adjacent to 2,2,4,4
                          your adjacency list should be {2,4}

On secondary inputs, you will be given the data for a graph in the same format as input1.txt   Your program should generate the corresponding output similar to output1.txt

When your main program is compiled and run with input redirected so that it gets the contents of the primary input file (named input1.txt) as input, it should generate output that matches the primary output file. When we test your program we will diff your output (using diff -bwi) with that of the primary output and if it does not match, your program will be considered to not meet the minimum running standards and you will be unable to submit it.

In order for the coloring to contain the minimum number of colors, one must begin at the uncolored node with the highest degree each time a new color is chosen.

The coloring algorithm given in lab is a heuristic and will not necessarily always give the minimum number of colors for some types of graphs.

You may use a different coloring algorithm but it must be able to produce a minimal coloring of the graph.

You may NOT use a brute force method for the coloring

Some points will be deducted for answers that do not color a graph in the fewest possible colors but still color it in 4 colors or less.

Provide a Makefile that creates an executable file named p5

Tar up all necessary files, such as source code, including:

• all .cpp files
• all .h files
• your makefile

submit p5.tar 5

Submit will be ready by Dec 6 at the latest.
Look for the exact date and time in the motd of the posting account.