Assignment - COP 3530, Fall 2007

Assignment 12 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Have your name, UFID, and discussion session number as comments at the top of your code.
ONLY SOFT copy is REQUIRED.
Jar all the files directly WITHOUT the dataStructures folder.
For coding problems, put the complexity analysis and other non-coding parts of THIS question (if it has) in comments at the beginning of your code.
For pen-paper questions, we only accept the following format file: Plain TEXT, PDF and DOC. Plain TEXT format is preferred. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
Getting correct results for the given test cases does not necessarily mean your implementation does not have any bugs; your code will be tested with additional test cases during grading.
Grading rules of coding problems are available.
Please download and check your jar file after your submission. Make sure the submission is correct.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial. If you have trouble with the classpath settings you could try reading this tutorial.
Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
super();
}

public ALLExtended( int n ){
super(n);
}

A path with no repeated vertices is called a simple path, and a cycle with no repeated vertices aside from the start/end vertex is a simple cycle.
In this assignment, you will extend the LinkedDigraph class to support several additional functions related to simple paths and simple cycles.

PLEASE put all your solutions in one single java file. Name this file MyLinkedDigraph.java.

a): Suppose you have a directed graph G=(V,E), develop a new method FindPathLen(int i,int j,int k), which will print the simple path between vertex i and j, whose length is k. If there are multiple such paths, just print one of them.
For example, if MyLinkedDigraph g equals to:

When g.FindPathLen(2,3,4) is called, the output should be "2->5->4->1->3".
When g.FindPathLen(2,3,3) is called, the output should be "No path exists."
b): Develop a new method FindAllPaths(int i,int j), which will print all simple paths between vertex i and j.
For example, for the graph g above,
when g.FindAllPaths(4,5) is called, the output should be:
4->1->3->2->5
4->1->3->5
4->1->2->5

You are NOT allowed to call any method of the LinkedDigraph class. Calling one of these methods can cost up to 100% of the question grade.

The template is:

package dataStructures;

      

      

      public class MyLinkedDigraph extends LinkedDigraph {

      

          int nodeNumber_;

      

          //Add any member here when necessary

          public MyLinkedDigraph(int n)

          {

              super(n);

              nodeNumber_ = n;

          }

      

          void FindPathLen(int i,int j,int k)

          {

              //Your code goes here

          }

      

          void FindAllPaths(int i,int j)

          {

              //Your code goes here

          }

      

      

          // Please use the test code as follows.

          public static void main(String[] args) {

      

              MyLinkedDigraph g = new MyLinkedDigraph(5);

              g.putEdge(new Edge(1, 2));

              g.putEdge(new Edge(3, 4));

              g.putEdge(new Edge(5, 4));

              g.putEdge(new Edge(3, 5));

              g.putEdge(new Edge(1, 3));

              g.putEdge(new Edge(4, 1));

              g.putEdge(new Edge(3, 2));

              g.putEdge(new Edge(2, 5));

      

              System.out.println("Part (a)");

              g.FindPathLen(2,3,4);

              g.FindPathLen(2,3,3);

      

              System.out.println("Part (b)");

              g.FindAllPaths(4,5);

      

      

          }

      

      }