CMPT **7 / 777 Formal Verification
Programming Assignment 1
This assignment is due by 11:59pm PT on Wednesday Oct 2, 2024. Please submit it to Canvas. Late policy:
Suppose you can get n (out of 100) points based on your code and report
• If you submit before the deadline, you can get all n points.
• If you submit between 11:59pm PT Oct 2 and 11:59pm PT Oct 3, you get n − 10 points. • If you submit between 11:59pm PT Oct 3 and 11:59pm PT Oct 4, you get n − 20 points. • If you submit after 11:59pm PT Oct 4, you get 0 points.
Problem Description
(100 points) A solution to a graph coloring problem is an assignment of colors to vertices such that no two adjacent vertices have the same color. Formally, a finite graph G = (V,E) consists of vertices V = {v1,...,vn} and edges E = {(vi1,wi1),...,(vik,wik)}. The finite set of colors is given by C = {c1,...,cm}. A problem instance is given by a graph and a set of colors: the problem is to assign each vertex v ∈ V a color(v) ∈ C such that for every edge (v,w) ∈ E, color(v) ̸= color(w). Clearly, not all instances have solutions.
Please write a Java program with Z3 APIs to solve the graph coloring problem. The input is a file in the following format
NM
vi1 wi1
vi2 wi2
...
vik wik
where the first line contains two positive integers: N is the number of vertices, and M is the number of colors (separated by a space). Without loss of generality, we can assume V = {1,...,N} and C = {1,...,M}. Each of the rest line contains two positive integers vij and wij that are no more than N, which corresponds to an edge (vij , wij ).
The output is also a file. If an instance does not have a solution, write “No Solution” in the output file. Otherwise, write an assignment of colors to vertices in the following format.
v1 c1
v2 c2
...
vm ck
where vi denotes the vertex and ci denotes its color, i.e., color(vi) = ci, separated by a space.
You might want to use the following hints for encoding: • Introduce a boolean variable pv,c for color(v) = c.
• Describe the formula asserting every vertex is colored.
1
• Describe the formula asserting every vertex has at most one color.
• Describe the formula asserting that no two connected vertices have the same color.
2 Sample Input and Output
Suppose we have an input file input.txt that contains the following six lines
which represents the following graph
43 12 13 14 24 34
12
34
After running the program, we can get a file with the following lines (not unique)
11 22 ** 43
It means the colors of vertices v1, v2, v3, v4 are c1, c2, c2, c3, respectively. 3 Compilation and Execution
Compilation. The provided codebase uses the Maven build system. After you enter the verif-sat direc- tory, the project can be easily compiled with one command
$ mvn package
Then you should be able to see the message “BUILD SUCCESS”. A directory called target will be created
and a jar file called verif-sat-1.0.jar will be generated inside the target.
Execution. In the verif-sat directory, you can execute the program using the following command (use ;
instead of : on Windows)
$ java -cp lib/com.microsoft.z3.jar:target/verif-sat-1.0.jar sat.GraphColoring <in-path> <out-path>
where <in-path> is the path to the input file and <out-path> is the path to the output file. For example, you can run
$ java -cp lib/com.microsoft.z3.jar:target/verif-sat-1.0.jar sat.GraphColoring input.txt output.txt
You will see a runtime exception with message “To be implemented”, because the program is not imple- mented yet. After you finish the implementation, you should see a file named output.txt with the content as shown in Section 2.
2
4 Deliverable
A zip file called P1 SFUID.zip (SFUID is replaced with your 9-digit student ID number) that contains the followings:
• The verif-sat directory that contains your Java program. You can have multiple source files if you want, but you need to make sure the project can be built and executed in the way described in Section 3.
• A short report called P1 SFUID.pdf that describes your encoding and explains the design choices, features, issues (if any), and anything else that you want to explain about your program.
3
請(qǐng)加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
