Homework #6 Solution



We discussed in class a predicate that finds the transitive closure of a

relation: transit(Rel, S, T) :- call(Rel, S, X), (X = T; transit(Rel, X, T)).

One may consider this a graph algorithm, where call(Rel, S, T) is true if an

arc exists from S to T, and transit(Rel, S, T) is true if a path exists from

S to T.

Unfortunately, this definition is only sound if Rel is acyclic. That is,

transit will try to find every path from S to T, and the number of paths is

potentially infinite.

For this assignment, write path/5, a relation that holds between a predicate,

two atoms, a path from the first atom to the second following that predicate,

and an integer that is the length of the path.

path(:Rel, ?Source, ?Target, ?Path, ?Length)

Path must have Source as its first element and Target as its last element.

The total number of elements in Path must be Length. Each successive pair of

elements in Path must have the Rel relation. Thus, Path=[a,b,c] and Rel=foo,

implies foo(a,b), foo(b,c).

Importantly, no element may occur in Path more than once. That is, path/5 must

avoid getting stuck in cycles.

There is no restriction on the type of elements that may occur in Path, beyond

those implied by Rel.

is_a(parallelogram, quadrilateral).

is_a(trapezoid, quadrilateral).

is_a(rhombus, parallelogram).

is_a(rectangle, parallelogram).

is_a(square, rhombus).

is_a(square, rectangle).

?- path(is_a, square, quadrilateral,

[square, rhombus, parallelogram, quadrilateral], 4).


?- path(is_a, square, parallelogram, [square, trapezoid, parallelogram], 3).


friend(alice, bob).

friend(bob, carol).

friend(carol, daniel).

friend(carol, eve).

friends(A,B) :- friend(A,B); friend(B,A).

?- path(friends, eve, bob, [eve, carol, bob], 3).


Your definition of path/5 should work in as many modes as possible. You will

receive partial credit for those modes which you are able to implement.

You will receive credit for implementing these modes:

A) path(+Rel, +S, +T, ++P, +N)

confirm that P is a path from S to T with length N (20 points)

B) path(+Rel, ?S, ?T, +P, ?N)

confirm that P is a path, find source, target, and length (20 points)

C) path(+Rel, +S, +T, ?P, +N)

find length-N paths from S to T (20 points)

D) path(+Rel, +S, +T, ?P, ?N)

find paths from S to T (20 points)

E) path(+Rel, ?S, ?T, ?P, +N)

find all length-N paths (10 points)

F) path(+Rel, ?S, ?T, ?P, ?N)

find all paths (10 points)

Indicate in your submission which modes you have attempted. We will not record

scores for those modes you have not attempted.

To receive full credit, your implementation should not exhibit universal or

existential non-termination for any mode you claim to support. If you have

implemented mode F, this query should terminate:

?- path(friends, _, _, _, _), false.


Where practical, your implementation should avoid leaving unnecessary choice


You will most likely want to use one or more helper predicates.


Your submission must be a single Prolog source file named “hw6.pl”.

Your submissions should be useable with SWI Prolog. If you plan to use

GNU Prolog for this assignment, you should speak with Prof. Menendez first.


You may use the unit tests provided in “hw6.plt” to test your program. Note

that these are necessary but not sufficient for correctness. We will be testing

with additional test cases not provided here.

The test cases use the Prolog unit-test package plunit. This should be included

with SWI Prolog installations by default, but is not available on the iLab

machines. To check whether plunit is available, use this command from the

SWI Prolog prompt:


If this fails, then copy the plunit.pl file to your directory.

To use these tests, copy “hw6.plt” to the same directory as your “hw6.pl” and

execute this command at the Unix prompt:

swipl -s hw6.pl -t “load_test_files([]), run_tests.”

If you are using the provided copy of plunit, use this command:

swipl -s hw6.pl -t “use_module(plunit), load_test_files([]), run_tests.”

Alternately, from the SWI Prolog prompt, you may do

?- load_test_files([]).


?- run_tests.

The test file contains six tests. To avoid infinite loops, all but the first

are disabled. As you complete modes, uncomment the lines implemented(mode_X)

to enable additional tests.