Background:
This lab should provide more work on arrays, implementing methods and then using those methods in a client program to perform certain actions. Once you're done, you will use the Intro-CS Assignment Dropoff form to hand in your finished program.
What You'll Need
Download the lab5.zip file from the 15-111 course web site. Unzip
the file and you should see the following:
- Driver.java
- Graph.java
- graph.txt, the data file. This file is formatted in the following manner: the first line is the number of vertices in the graph. Each subsequent line is a triple of the form [origin-vertex destination-vertex cost]. Thus an entry of the form 0 1 10 means there is an edge of cost 10 from vertex 0 to vertex 1.
Assignment
You are to implement a Graph class using an adjacency matrix as discussed in lecture. As a reminder, an adjacency matrix is a two-dimensional array of values such that entry [i,j] is the cost of the edge from i to j, with a testable constant NO_EDGE as the value where no edge is present between two vertices.
You are to implement all of the stubbed member functions provided in Graph.java. In addition, I've started a Driver program to test various pieces of the Graph class. You should augment this in whatever way you need to make sure everything functions correctly (I will :-)). In addition to testing your Graph class, you will write additional client code in Driver to test your degree functions. As a reminder, the degree of a vertex is the number of edges incident to that vertex. For a directed graph, we defined the following terms:
- out-degree - the number of edges leaving the vertex
- in-degree - the number of edges entering the vertex
- degree - the number of edges entering and leaving
the vertex
After doing so and testing your implementation, you are to implement the
following client functions in Driver.java to exercise the 3 new member
functions:
- Max Out Degree - the maximal number of edges leaving any
single vertex
- Min Out Degree - the minimal number of edges leaving any
single vertex
- Max In Degree - the maximal number of edges entering any
single vertex
- Min In Degree - the minimal number of edges entering any
single vertex
- Max Degree - the maximal number of edges entering/leaving any
single vertex
- Min Degree - the minimal number of edges entering/leaving any
single vertex
For the sample file, graph.txt, the correct answers are
- Max Out Degree - 4
- Min Out Degree - 1
- Max In Degree - 4
- Min In Degree - 1
- Max Degree - 6
- Min Degree - 3
Extra Credit
You are to write a method that implements Dijkstra's algorithm for computing all-points shortest paths. Your client code should test this method by computing the shortest paths from node 0 to all the others. For extra-extra-credit, your output should not only include the lengths of the shortest paths, but the actual paths themselves, e.g.,
0 -> 3 length: 22 path: 0 -> 4 -> 3
Handing in your Solution
Your solution should be in the form of a .zip file. When we grade your solution
we will unzip the folder and execute the project.
Use the Intro Programming
dropoff form to submit your zip file.