Graph Coloring Problem

CS 320 Data Structures and Analysis of Algorithms Programming 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