Programming Project 6

Due date: Mon 4/28 11:00 pm

Introduction

In this assignment you will handle simple data and list data with Prolog programs.

Paths on Graphs

In this part we work with labeled directed acyclic graphs using the following Prolog representation. The atom e(a,b) indicates that there is an edge from a to b in the graph. Each node in the graph is also given a single color using the appropriate predicates, as in the following example:
e(1,2).
e(2,3).
e(3,4).
e(4,5).
e(1,3).
e(2,5).

blue(1).
green(2).
black(3).
red(4).
black(5).

While we illustrate the requirements for the graph above your program should work for any graph given in this format.

Part I:

write a function path1(X,Y) that is true whenever there is a path from X to Y in the graph. For example
?- path1(1,5).
Yes
?- path1(1,3).
Yes
?- path1(3,5).
Yes
?- path1(3,1).
No

Part II:

write a function path2(X,Y) that is true whenever there is a path from X to Y in the graph which does not use an edge whose endpoints are colored red -> black. For example
?- path2(1,5).
Yes
?- path2(1,3).
Yes
?- path2(3,5).
No

Part III:

write a function path3(X,Y) that is true whenever there is a path from X to Y in the graph which does use an edge whose endpoints are colored red -> black. For example
?- path3(1,5).
Yes
?- path3(1,3).
No
?- path3(3,5).
Yes

Working with Lists

In this part you will work with a database capturing people and the CDs they own. Each CD is given a name and its main artist is listed. The data is given as a list in the following format:
[
[john,[cd1,clapton],[cd2,moody],[cd3,hip]],
[janet,[cd1,clapton],[cd3,hip],[cd4,moody],[cd5,u2]],
[beatrice,[cd6,doors],[cd7,clapton],[cd3,hip]],
[robert,[cd8,clapton],[cd3,hip],[cd6,doors]]
]
Each element of the main list represents a person. The person's name is the first element. Following elements are lists of length 2, each giving a CD name and the artist. As in the previous part we illustrate the requirements using this database but your programs should work for any database in this format.

Part I:

write a function similarTaste(Data,P1,P2) that is true when Data is a database as above and P1, P2 are two different people who own at least 2 different CDs in common. Notice that the 2 CDs do not need to appear in the same order in the lists. For the data above this holds for john and janet and for beatrice and robert. You do not need to worry about repeated answers.

You may want to break down the task into simpler tasks. For example you can define a function
ownsCD(Data,Person,CD) that is true when Person owns the CD. But this is up to you.

Part II:

write a function sameArtists(Data,P1,P2) that is true when Data is a database as above and P1, P2 are two different people who who have CDs by exactly the same artists. Again the CD lists do not need to be identical - they need to include the same set of elements. For the data above this holds only for beatrice and robert. You do not need to worry about repeated answers.

Here again the structure of the code is up yo you. A useful sub-task is a function
personArtists(Data,Person,Artists) that is true when Artists is the list of artists whose CDs are owned by Person.

Files

For your convenience a seed file for pp6.pl including the data given above is available at /comp/80/files/pp6/

Submitting your program

Put all the Prolog code in a file pp6.pl. Assuming your files are in the current directory on one of our Sun workstations or servers, you should submit by typing
provide comp80 pp6 pp6.pl

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation -no_images -dir TEMPHTML pp6.tex

The translation was initiated by Roni Khardon on 2008-04-17


Roni Khardon 2008-04-17