| Home | Notes | Languages | Programs | Homework |
| Program Assignment 3 |
| 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:
[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]]You are to implement the following Prolog predicates:
This predicate is true if its single parameter is a proper representation of a directed graph. From the previous example,
graph([[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])must be true. On the other hand,
graph([[u,v,x,y],[[v,u],[v,u]]])must be false, as there is a repeated arc in the list of arcs. Also,
graph([[u,v],[[v,x],[u,y]]])must be false, as there are nodes mentioned in the list of arcs that are not in the list of nodes.
This predicate is true if its second parameter represents a directed graph and its first parameter is a node of that directed graph. From the previous example,
node(v,[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])is true, while
node(tom,[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])is false.
This predicate is true if its second parameter represents a directed graph and its first parameter is a pair of nodes of that directed graph that is an arc of the graph. From the previous example,
arc([y,u],[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])is true, while
arc([u,u],[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])and
arc([u,x],[[u,v,x,y],[[v,u],[x,y],[y,u],[u,v],[x,u]]])are both false.
This predicate is true if (1) its third parameter represents a directed graph; (2) its first and second parameters (A and B) are nodes of that directed graph; and (3) there is a directed path in the graph from A to B. For example,
path(a,c,[[a,b,c],[[a,b],[b,c]]])is true, while
path(c,a,[[a,b,c],[[a,b],[b,c]]])is false. Note that there is always a directed path of length 0 from any node to itself.
This predicate is true if (1) its third parameter represents a directed graph; (2) its first and second parameters (A and B) are nodes of that directed graph; and (3) there is a directed path in the graph from A to B of length L (the fourth parameter). For example,
path(a,c,[[a,b,c],[[a,b],[b,c]]],2)is true, while
path(a,c,[[a,b,c],[[a,b],[b,c]]],4)is false.
This predicate is true if its first argument represents a directed graph that contains a directed cycle of length its second argument. For example,
hascycle([[a,b,c],[[a,b],[b,c],[c,a]]],3)is true, while
hascycle([[a,b,c],[[a,b],[b,c],[c,a]]],1)is false. Note that there is always a directed cycle of length 0 from any node to itself, so
hascycle([[a,b,c],[[a,b],[b,c],[c,a]]],0)is true.
| 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 |