Graph Coloring Problem

CS 320 Data Structures and Analysis of AlgorithmsProgramming Project 4
Graph Coloring Problem
Due Date: Posted on the Blackboard web site for the course.
Project Name and What to Submit:
• Project Name MUST be CS320P04LastName. (Note there are no underscores.)
• Zipped file name must be named: CS320P04LastName.zip.
• Zipped file must contain the entire project folder containing your Visual Studio 2022 solutionproject for Project 4. Test cases (input and corresponding output) must be included in a Tests
subfolder in that zip file. Tests must include more than the samples given to you.
• Do not upload any files outside of the zip file.
• If your program does not work, please include a Word or notepad file explaining what works
and what doesn’t work.
Description: This project involves implementing a backtracking solution to the Graph Coloring
problem: Given an undirected graph, G = , with no self-loops, and a color palette, Colors,
of m > 0 colors find a coloring assignment, color: V → Colors, of all the vertices in V so that if
edge is in E, color(vi) ≠ color(vj). If there exists a (total function) color assignment, you
may use one that uses the minimum number of colors up to and including the ones that use all m
colors. If there is no color assignment possible, your program should indicate this.
Vertices must be named with non-negative integers: 0, 1, …, n-1 with |V|=n, where n >= 0.
Colors are named with positive integers 1, 2, …, m, where m > 0.
Input: First enter number of colors, m, then the number of vertices, n, then enter the sequence of
edges. Each edge must be entered in the following format: (vi vj). The sequence of edges must be
terminated with an edge whose first vertex is -1. So, (-1 -1), (-1 0), … etc. will work. All data
must be separated by white space (which are blank(s), tabs, or newlines). The edges need not be
separated with white space since parentheses are used as delimiters. Note that the parentheses are
syntactic sugar intended to make the input more readable.
Output:
• If there is a possible color assignment, print the color assignment by listing all vertices
with its respective color assignment. Start with vertex 0 and print the vertices in
increasing order (up to and including n-1). Put one vertex-color assignment per line.
Separate the vertex number from the color number with a colon character, ‘:’.
• If there is no color assignment, then print “No color assignment possible.”
Algorithm and Data Structure Constraints and Permissions:
• You must design a C++ Graph class with an appropriate interface.
• You must implement the Graph as an adjacency matrix or an adjacency list data structure.
• You may use any of the STL libraries, except graph, where appropriate.
• You must use the backtracking algorithm design, similar to the textbook’s description of
backtracking.
• You will be graded on appropriateness of your graph interface, graph implementation,
graph-coloring backtracking algorithm implementation, and number and relevance of
your tests. Many tests are good. Give screen shots of your tests. If you use files and
redirection at the command line, please show the contents of the input file and
corresponding output.
• Make sure the input statements correspond to correct order of input values and output
gives nothing more than what is required.
CS 320 Project 4
Page 1 of 2
Example 1:
0
1
3
2
To enter the above graph using only a two color palette the user should enter the
following:
2 4 (0 1)(1 2)(2 3)(3 0)(-1 -1)
Since there is a color assignment solution, a color assignment is printed, such as:
0:1
1:2
2:1
3:2
Note that if a 3-color palette was used (m=3), the same solution just given could be used
or an assignment such as the following could be used.
0:1
1:2
2:1
3:3
0
1
3
2
In other words, you can assign the minimum number of colors up to the maximum, m, to
the vertices.
■
Example 2: This illustrates what your program should print if no color assignment is
possible. Note this sequence has a redundant listing of an edge, namely, (1, 0). When a
user enters redundant edges, your program should not be affected adversely. In this
example either (0 1) or (1 0) could be the sole edge entered. With only one color in the
palette, it is impossible to color the graph so that no adjacent vertices have the same
color.
0
1
1 2 (0 1)(1 0)(-1 -1)
No color assignment possible.
Again, note that if two colors comprised the color palette, there would be two possible
solutions, 0 : 1, 1 : 2; or 0 : 2, 1 : 1. If there were three colors, one may choose any of the
three colors for the vertex 0 and any of the two remaining colors for the other vertex,
resulting in (3*2=) 6 possible solutions: ●●; ●●; ●●; ●●; ●●; ●●.
■
CS 320 Project 4
Page 2 of 2