CSC 4640: Project 8

Project 8:
Prolog XOR and Graphs

Assigned: Fri Mar 21 2025
Due: 11:59:00 PM on Wed Apr 02 2025
Team Size: 2
Language: SWI-Prolog
Out of: 100 points

In this project, you will write code to traverse graphs in Prolog. I have provided lots of examples. It's okay if your code doesn't print out the solutions in the same order that mine do, but you shouldn't repeat answers.

Part 0, 0 points: Look at the submission instructions below to set up your folder and source code file name.

Part 1, 10 points:

Write the procedure xor(A, B, C), which succeeds when A XOR B = C. Prolog uses 0 for false and 1 for true. This should succeed when any two of the three parameters are initialized. Here are some cases:

?- xor(0, 0, X).
X=0
?- xor(0, X, 1).
X=1

Part 2, 10 points:

Write the procedure xor(List, Value), which succeeds when List is a list of boolean values and Value is the total XOR of all those values. This should succeed when any of the two parameters are initialized; if the List is uninitialized, it should unify with the shortest possible list. Here are some cases:

?- xor([1, 0, 1], X).
X = 0
?- xor([1, 1, 1, 0, 1, 0, 1], X).
X = 1

Part 3, 30 points:

Assume we have a Directed Acyclic Graph (DAG) in Prolog defined by a set of facts such as: arc(a, b)., which means there is a directed edge from vertex a to vertex b. Write a functor, print_path(X,Y,S), that means there is a path in the graph between vertices X and Y, with S a description of that path as a string. You only need to worry about graphs without cycles, meaning there is no way for a path to loop back on itself. The third String parameter should contain the path between vertices with "->" delimiters between the vertex names showing the appropriate direction. If not, nothing should be printed. For example, if we have this set of facts:

arc(a, b).
arc(b, c).
arc(b, d).
arc(c, e).
arc(d, e).

We might get this behavior:

?- print_path(a, b, S).
S = "a->b"
?- print_path(b, a, S).
false
?- print_path(a, c, S).
S = "a->b->c"
?- print_path(b, e, S).
S = "b->c->e"
S = "b->d->e"
?- print_path(a, a, S).
S="a"

For this part, you only need to identify one of the paths. I think that you'll want to use the atom_string/2 predicate. (The labels of the arc facts are atoms.) E.g.:

?- atom_string(a, X).
X = "a"

Part 4, 10 points:

Update your print_path functor so that it gets strings of all paths, not just the first one you detect.

Part 5, 10 points:

Write another functor, path(X,Y,N), which means that a path between X and Y exists with length N. You should assume that all vertices have a path to themselves of length 0. First, make sure your code accepts full solutions appropriately, e.g., using the facts listed above:

?- path(a, b, 1).
 true
?- path(b, e, 1).
false
?- path(b, e, 2).
true

Part 6, 10 points:

Update your functor, path(X,Y,N), so that you don't need to specify N. E.g.:

?- path(a, b, N).
N=1
?- path(b, e, N).
N=2
N=2

Part 7, 5 points:

Update your functor, path(X,Y,N), so that you don't need to specify Y. E.g.:

?- path(a, V, 1).
V=b
?- path(b, V, 2).
V=e
V=e
?- path(a, V, 2).
V=c
V=d

Part 8, 5 points:

Update your functor, path(X,Y,N), so that you don't need to specify X. E.g.:

?- path(V, e, 1).
V=c
V=d

Part 9, 5 points:

Update your functor, path(X,Y,N), so that you don't need to specify both X and Y. E.g.:

?- path(V, W, 3).
V=a, W=e
V=a, W=e

Part 10, 5 points:

Update your functor, path(X,Y,N), so that you don't need to specify both X and N. E.g.:

?- path(V, c, N).
V=c, N=0
V=a, N=2
V=b, N=1

Part 11, 10 points (Bonus):

Write a new functor, advanced_path(X,Y,N), which is just like path(X,Y,N), except that it can be successfully run on graphs with cycles: it won't print out cycles as solutions. Test this functor both with and without N instantiated.

Submitting your Project: Put all your procedure definitions in one file named project8.pl in a folder named <TeamName>Project8 where <TeamName> has all team members' (last) names separated by 'and' in PascalCase. For example, if I had worked with Alyssa Borgin, my folder name would be: BorginAndBurkeProject8. The code file should be located directly in that folder. Zip the folder up (don't change the file name) and upload the zip file to the assignment in Canvas.