Lab 7: 2D-Arrays, More While Loops, Methods, Input and Output
Due: 10pm Tuesday March 29
Purpose:
This lab will give you an opportunity to work with arrays; allocating
a fixed size array, setting its initial contents, changing the
contents, and examining the contents. You will also use while loops,
methods, the scanner class, and output.
In this lab in addition to learning about arrays, you will be using
language concepts you used in previous labs. Just like a learning a
foreign language, you need to remember just about everything you
learn. To help you remember and become more facile with the
programming concepts, you will use most of what you have already
learned again in each subsequent lab. Thus, you will form longer and
more complex programs which will give you practice and help improve
your programming skills.
You will write a program that creates and manipulates directed
graphs. Many computer programs use graphs as an abstraction of
problems such as network connectivity or legal resource allocation.
In this lab, you will represent and manipulate a directed graph, i.e.,
a graph with nodes and directed edges (tail -> head), as a
2-dimensional array.
Given a graph that contains N nodes and also contains some
directed edges (tail -> head) that connect some nodes to others. Then,
using a NxN 2D-array, we can represent the graph in the following way:
If node x is connected to
a node y through a
directed edge e =
(x->y) (in this case x is called the tail of the edge and y the head of the edge), with a
positive weight W, then the element [x][y] of the array is set to the weight, otherwise
it is set to a sentinel value, in this lab we choose -1. For this
lab, edge weights must be non-negative integer which can be used to
model for example the latency of a network link. An example directed
graph and its representation as a 2D-array is shown in the following
picture:
 |
|
0 |
1 |
2 |
3 |
| 0 |
-1 |
1
|
-1
|
-1
|
| 1 |
-1
|
5 |
2
|
3
|
| 2 |
-1
|
-1
|
-1
|
-1
|
| 3 |
-1
|
-1
|
-1
|
3
|
|
Your program will firstly construct a directed graph using information
that is contained in a text file, and then it will prompt the user to
ask several queries regarding the graph. The contents of the file that
contains the graph information will be of the following format:
n m
<------- n = number of nodes in the graph, m = number of
edges in the graph
a b w1 <------- edge from a to b with weight w1
....
x y w2 <------- edge from x to y with weight w2
We provide you with this sample.
The queries that the user can choose are:
- Check if an edge e = (x->y) exists.
- Print all the edges of the graph.
- Return the self-loops that exist in the graph (when a node x contains an edge e to itself (e = (x->x)), then node x is involved in a self-loop.
- Make a new inverse graph and print it. For every edge e = (x->y) that exists in
the initial graph, the inverse graph should contain an edge e1 = (y->x) instead.
- Check if a path (a,b,c...,y,w) exists in the graph and, if it does, calculate its total weight, that is the sum of the weights of the edges (a->b), (b->c), ....,(y->w)
You will write two classes: Graph.java which implements the directed
graph, and GraphTest.java which just contains the main method with the
code that creates the graph and executes the queries on it. Your Graph
class should use an int[][] to model the directed graph. We provide you
with the following templates (GraphTemplate.java, GraphTestTemplate.java) for the two classes. These files contain the signatures of all the constructors and methods you should define. You can also
add any helper methods you need for your implementation.
Your program will first ask the user to give the name of a file that
contains the data for populating the directed graph. While reading
information from the file (inside the constructor of Graph -- see the
templates above), you can assume that no errors will exist in the
given data. You must however implement the appropriate error checking
that relate to all the queries over the graph, and you must communicate
to the main method when a query fails to retrieve any information
through appropriate return values. You may choose whichever values
seem intuitively correct to you -- for example, if a specific path
does not exist in the graph, you can return -1 as the value of the
total weight of the path.
A sample execution of the program for the graph shown in the picture above, is provided here.
As part of this lab, you must provide an additional input graph in a
separate file, named "myGraph.txt". A large part of programming is
testing, and you should create multiple test files that help you get
your program correct. Turn in one of those interesting test files.
Submission and Grading:
Always include your names, slip days, and a comment at the top of
your file. Here is the template header for all the java files that you will create.
/**
* @author name 1: discussion section time:
* CS account user name:
* Section Unique Number:
* slip days used on this assignment: ??/4
* total slip days used: ??/6
*
* @author name 2: discussion section time:
* CS account user name:
* Section Unique Number:
* slip days used on this assignment: ??/4
* total slip days used: ??/6
*
* On our honor, we followed the pair programming rules of splitting
* keyboard time evenly and 80% or more joint development, and we have
* neither read nor copied code, nor have we shown or given our code to
* others.
*
* @version Date
*
* Extra Credit attempted (Yes/No):
*
* Describe what this program does, including any extra credit attempted.
*
*
*/
Submit your version of Graph.java, GraphTest.java and myGraph.txt using the turnin program . If you need help goto
turnin program help.
Your program should be internally correct (sound logic) and
externally correct (following Java style
guideline).
If you are submitting without a partner, please include your
initial partner and the email correspondence with the instructor or
with the TA in your header.