You may work together on these programming assignments, in teams of up to 3 people. If you work in a team, e-mail only one copy of the program and submit only one printout with all the team members' names on them.

Introduction: Graph coloring

When coloring maps, one often wants to color adjacent regions different colors, to show clearly that the two regions are different. For example, in a map of North America, the US and Canada should be colored two different colors, because they are next to each other. The US and Mexico should also be two different colors, because they are also next to each other. However, if the mapmaker is running out of colors, it is acceptable to color Canada and Mexico the same color, because they do not share a border.

One can represent the adjacency information as a graph: Each node represents a map region, and if two regions are adjacent on the map, then their two nodes are connected by an edge in the graph. Our map of North America would then be represented by this graph:

"Coloring" this graph means assigning a color to each node in the graph, so that no two adjacent nodes have the same color. For example, here is an acceptable coloring of our North America graph:

To keep things simple for writing programs, the nodes in our graphs will usually have abstract names A, B, C, ..., and the colors will be represented by consecutive positive integers 1, 2, 3, ....

Here is another example, using this abstract format. Our graph to color is:

One acceptable coloring of this graph is:

Note that there can be more than one acceptable coloring; for example,

This, however, is not an acceptable coloring, because B and D are adjacent, and they both have color 3.

Two programming problems arise out of the concept of graph coloring:

1. Given a graph and a proposed coloring, decide whether the coloring is acceptable.

   This problem will be the main homework problem this semester.

2. Given a graph and a number of colors k, find a way to color the graph using no more than k colors (or report that such a coloring is impossible).

   This problem will be an extra credit homework problem this semester.

You will solve these problems in each of four programming languages during the semester. The language-specific details of the assignments are described below.

In each of these four language-specific programming assignments, the main homework problem will be graded out of a total of 100 points. You may earn up to 25 additional points on each assignment by solving the extra credit problem.

Testing suggestion:

Since the input for this problem is lengthy and prone to typing errors, you will not want to type the input by hand every time you run the program. Instead, create a file containing the test data, and then use either cut-and-paste with the mouse or input redirection to run the test examples.

I will test your program on the input examples listed on this handout as well as on additional input known only to me. I guarantee that the test data will be properly formatted, but your program should be prepared for any legal input.

1. Imperative-language assignment

Write a program to solve the main homework problem described above, using one of the following languages: C, C++, or Java. (If you have another favorite language you'd prefer to use, talk to me.)

Optionally, for extra credit, you may also solve the extra credit homework problem described above, again using your choice of C, C++, or Java.

The input for the main homework problem will be in this format:

• A positive integer V on a line by itself, representing the number of vertices in the graph.
• Next, a sequence of V lines, each containing a single character, followed by a single space, followed by a positive integer. These lines represent a vertex followed by its proposed color assignment. No vertex will appear twice in this sequence.
• Next, a positive integer E on a line by itself, representing the number of edges in the graph.
• Next, a sequence of E lines, each containing a single character, followed by a single space, followed by a second single character. These lines represent the edges of the graph; each edge is specified by the two vertices it connects. Since the graph is undirected, vertex order is not significant; a b is the same edge as b a. No edge will appear twice in this sequence.

The output should be either the message This is an acceptable coloring or the message This is not an acceptable coloring.

The input for the extra credit homework problem will be in this format:

• A positive integer V on a line by itself, representing the number of vertices in the graph.
• Next, a sequence of V lines, each containing a single character, representing one vertex. No vertex will appear twice in this sequence.
• Next, a positive integer E on a line by itself, representing the number of edges in the graph.
• Next, a sequence of E lines, each containing a single character, followed by a single space, followed by a second single character. These lines represent the edges of the graph; each edge is specified by the two vertices it connects. Since the graph is undirected, vertex order is not significant; a b is the same edge as b a. No edge will appear twice in this sequence.
• Next, a positive integer k, representing the maximum number of colors to be used.

The output should be either a list of vertices with colors (if the graph can be colored in k colors) or the message The graph cannot be colored in k colors, where k is the input number indicating the maximum number of colors.

Main problem, example:

Input:

5
a 1
b 2
c 2
d 3
e 1
7
a b
a c
b d
c d
b e
d e
c e

Output:  This is an acceptable coloring.

Main problem, another example:

Input:

3
a 1
b 2
c 2
3
a b
a c
b c

Output:  This is not an acceptable coloring.

Extra credit problem, example:

Input:

3
a
b
c
2
a b
a c
2

Output: 
a 1
b 2
c 2

(or one of the other acceptable colorings)

Extra credit problem, another example:

Input:

4
a
b
c
d
6
a b
a c
a d
b c
b d
c d
3

Output: 
This graph cannot be colored in 3 colors.

Note: Please follow the input formats exactly. Do not add any extraneous I/O interactions, such as asking the user to "Enter 'y' to continue" or "Do you want to test another graph?" I will be grading your program by redirecting standard input from data files, and if you alter the input format, it makes grading more difficult.

If you wish to print a prompt for the user, print a single, short prompt at the beginning of the program (such as "Please enter the graph and coloring now"). Your program does not have to print a prompt at all. This terse style is not unusual for UNIX programs -- see bc and wc for two of many examples; the terseness allows for easier inclusion in pipes and easier redirection of input and output.

2. Scheme assignment

Write a Scheme program to solve the main homework problem described above: Define a function (coloring? VertexColorList EdgeList) which returns #T if the proposed coloring specified in VertexColorList is an acceptable coloring for the graph described in VertexColorList and EdgeList, and which returns #F if the proposed coloring is not acceptable. VertexColorList is a list of vertex-color pairs -- for example, ((a 1) (b 2) (c 1)). EdgeList is a list of edges, where each edge is specified as a pair of vertices -- for example, ((a b) (a c) (b c)). Each vertex will be represented by a single letter, and each color will be represented by a positive integer.

You may assume that VertexColorList and EdgeList will be in the correct format when the function is called; you do not have to error-check for incorrectly formed lists. In your program, you may write and call any additional functions that are helpful in the computation.

Optionally, for extra credit, write a Scheme program to solve the extra credit homework problem described above: Define a function (k-colorable? VertexList EdgeList K) which returns

• a list of vertex-color pairs, if the graph specified in VertexList and EdgeList can be colored in K colors.
• #F, if the graph cannot be colored in K colors.

You may assume that VertexColorList and EdgeList will be in the correct format when the function is called; you do not have to error-check for incorrectly formed lists. In your program, you may write and call any additional functions that are helpful in the computation.

Main problem, example:

(coloring? 
	'((a 1) (b 2) (c 2) (d 3) (e 1))
	'((a b) (a c) (b d) (c d) (b e) (d e) (c e))
)

Main problem, another example:

(coloring? 
	'((a 1) (b 2) (c 2))
	'((a b) (a c) (b c))
)

Extra credit problem, example:

(k-colorable?
	'(a b c)
	'((a b) (a c))
	2
)

Extra credit problem, example:

(k-colorable?
	'(a b c d)
	'((a b) (a c) (a d) (b c) (b d) (c d))
	3
)

3. Ada assignment

Write an Ada program to solve the main homework problem described above. Optionally, for extra credit, you may also solve the extra credit homework problem described above.

Use the same input/output format that was used for the imperative-language assignment.

4. Prolog assignment

Write a Prolog program to solve the main homework problem described above: Define a predicate coloring(+VertexColorList, +EdgeList) which succeeds if the proposed coloring specified in VertexColorList is an acceptable coloring for the graph described in VertexColorList and EdgeList, and which fails if the proposed coloring is not acceptable. VertexColorList is a list of vertex-color pairs -- for example, [[a, 1], [b, 2], [c, 1]]. EdgeList is a list of edges, where each edge is specified as a pair of vertices -- for example, [[a, b], [a, c], [b, c]]. Each vertex will be represented by a single letter, and each color will be represented by a positive integer.

You may assume that VertexColorList and EdgeList will be in the correct format when the predicate is called; you do not have to error-check for incorrectly formed lists. In your program, you may write and call any additional predicates that are helpful in the computation.

Optionally, for extra credit, write a Prolog program to solve the extra credit homework problem described above: Define a predicate k_colorable(+VertexList, +EdgeList, +K, -Coloring) which

• succeeds with Coloring set to a list of vertex-color pairs, if the graph specified in VertexList and EdgeList can be colored in K colors.
• fails if the graph cannot be colored in K colors.

You may assume that VertexColorList and EdgeList will be in the correct format when the predicate is called; you do not have to error-check for incorrectly formed lists. In your program, you may write and call any additional predicates that are helpful in the computation.

Main problem, example:

coloring(
	[[a, 1], [b, 2], [c, 2], [d, 3], [e, 1]],
	[[a, b], [a, c], [b, d], [c, d], [b, e], [d, e], [c, e]]
)

Main problem, another example:

coloring( 
	[[a, 1], [b, 2], [c, 2]],
	[[a, b], [a, c], [b, c]]
)

Extra credit problem, example:

k_colorable(
	[a, b, c],
	[[a, b], [a, c]],
	2,
	Coloring
)

Extra credit problem, example:

k_colorable(
	[a, b, c, d],
	[[a, b], [a, c], [a, d], [b, c], [b, d], [c, d]]
	3,
	Coloring
)

• A paper printout of the text of the program
• A paper printout of a sample run of the program (use script to capture the input and output)
• An e-mailed version of the program