Home  |   Notes  |   Languages  |   Programs  |   Homework
Program Assignment 3

75 Points
Due: 10/30/00 at 5:00PM

 Problem: Directed Graphs in Prolog

In this programming assignment, you will implement some predicates in Prolog related to directed graphs. Recall that, mathematically, a directed graph G is an ordered pair G=(N,A), where N is a set of nodes and A is a set of arcs. In turn, an arc is always an ordered pair (u,v) of nodes in N, indicating that the arc goes from u to v. For example,

G1 = ({u,v,x,y},{(v,u),(x,y),(y,u),(u,v),(x,u)}

is a directed graph having 4 nodes and 5 edges. It is easy to represent a directed graph using Prolog lists; just replace the brackets and parentheses in the previous example with square brackets, yielding this representation of G1:

You are to implement the following Prolog predicates:

 Implementation Language

For this assignment, your program must be written in Prolog.

Your solution will consist of a file of Prolog facts and rules that implement the predicates in the problem statement above. Of course, you are free to implement "helper" predicates beyond those specified.

 Input Format

Input to your program will be a file of Prolog facts and rules about one or more particular directed graphs. All facts and rules in this file are written using only the predicates described above.

 Output Format

You do not have to think about output explicitly, as the queries given to the Prolog engine to test your program will automatically return all solutions to the query.

 Testing Your Program

Before submitting your file of Prolog facts and rules, you must test it thoroughly. To do this, you should devise a set of tests of your own that you believe exhaustively test your Prolog program.

The GTA will devise a set of tests and will post a sample of those tests here, along with the expected output. The remaining tests will be held back for grading purposes. Please be certain that your Prolog program passes at least the posted test before submitting it.

 Submitting Your Program

Your Prolog program must be in a single file named <pid>.pl, where <pid> must be replaced by your Virginia Tech PID. That file and any auxiliary files, such as test results, must be packaged as a zip file (or tar file) named <pid>_project3.zip, which is attached to email sent to the class account, cs3304@courses.cs.vt.edu. The subject of the mail must be "Program assignment 3" - without quotes.

For example, the GTA's submission will be a Prolog file: derao.pl along with the input file containing the test cases and their output, packaged in a zip file: derao_project3.zip. Further, derao_project3.zip will be mailed to cs3304@courses.cs.vt.edu with subject Program assignment 3.

Your Prolog implementation is to be organized in a single file. The comments at the beginning of the file should identify the assignment and should give your name. Every Prolog predicate should be preceded by comments explaining its purpose and implementation.

Be sure to follow the Program Submission Guidelines in preparing your report to turn in. In accordance with these guidelines, you will need to develop a set of test cases for your program that tests both positive and negative cases. For test cases that you are unable to run, be sure to indicate "Unable to perform test" in the corresponding test result within your report.

NOTE: Failure to follow the submission guidelines may result in a grade penalty.

Home  |   Notes  |   Languages  |   Programs  |   Homework

copyright © 2000 Virginia Tech, ALL RIGHTS RESERVED
Last modified: October 29, 2000, 05:31:20 EST, by Lenwood S. Heath <heath@cs.vt.edu>