Description
Part 1 of 4 (25 points):
Note: some LinkedList class methods you may need: add, remove, contains to add, delete and search for the given
item, size() to get the length of the list, and get(int x) to get the element at x index (indexing starts at 0).
1. Define a class DiGraph to implement a directed graph as an array of Adjacency Linked Lists.
Vertices are numbered by integers 0 through N-1 (N is the number of vertices in the graph).
DiGraph class contains one private instance variable, one constructor and 5 public methods:
a) One private instance variable: this is an array of linked lists (use Java’s LinkedList class).
b) A constructor with one int type parameter for N. This constructor creates and initializes the
instance variable-array.
c) A public method addEdge(int from, int to) where two parameters identify vertices representing the
edge that needs to be added to the graph (to vertex is added as from vertex’s neighbor).
Important: the edge should not be added if it already exists: needs to be checked before adding.
Attention: vertex-numbers are given in natural numbering (starting with 1) so you should “turn”
them to Java-indexing to reflect correct connection. No need for validity check.
d) A public method deleteEdge(int from, int to) where two parameters identify vertices representing
the edge that needs to be deleted from the graph (to vertex is removed as from vertex’s neighbor).
Note: nothing is done if such edge doesn’t exist (no error message or exception).
Attention: vertex-numbers are given in natural numbering (starting with 1) so you should “turn”
them to Java-indexing to reflect correct connection. No need for validity check.
e) A public method edgeCount(): computes and returns the number of edges in the graph.
f) A public method vertexCount(): returns the number of vertices in the graph (it’s the array’s length)
g) A public method print() that outputs the graph in the following format: for each vertex i (from 0 to
N-1) outputs a line: i is connected to: x1, …, xk where x1,…, xk are vertices that are adjacent to i.
Example: for some 5-vertex graph your output may look like this:
1 is connected to: 2, 4
2 is connected to:
3 is connected to: 2, 4, 1
4 is connected to: 3
5 is connected to: 3, 1
Attention: numbering of vertices in the output should be natural, i.e. starting with 1.
Important: Separate two neighbors with a comma; do NOT put comma after the last neighbor
2. Define an application class DiGraphTest. In main method of this class you need to do the following:
1. Define a scanner object for keyboard input (i.e. connect it to System.in). You must make a scanner
for System.in only once here and use it for all keyboard inputs in this main method. DON’T redefine this scanner or create a new scanner for System.in – it will cause problems in grading.
2. Prompt the user to enter the number of vertices.
3. Input the number of vertices and define an object of DiGraph class.
4. Output a menu to the user, listing the above mentioned 5 operations that your DiGraph class
provides. For example, your menu may look like this:
Choose one of the following operations:
– add edge (enter a)
– delete edge (enter d)
– edge count (enter e)
– vertex count (enter v)
– print graph (enter p)
– Quit (enter q)
Important: must use a, d, e, v, p, q letters for menu choices (do NOT change these letters)
Dr. Hasmik Gharibyan
CSC/CPE 349
2
5. For as long as the user does not choose to quit, do the following:
– Prompt the user to enter a menu choice (do NOT print the menu here; the menu should be output
only once, in step 3 above, before entering this loop).
– Input user’s choice and analyze it (you are recommended to use a switch statement with default
case which will be executed for invalid menu choices). Arrange the execution of the requested
operation; if input values are necessary (for add edge and delete edge menu choices), prompt the
user to enter two integers and input them (no need for validity check). For every request, after
executing it, output feedback: e.g. if you are adding/deleting an edge, output a message saying for
example that the edge (x, y) was added/deleted; if you are giving some returned answer (e.g.
number of edges), precede it with an informative message (e.g. “Number of edges is: ”); or before
printing the graph, output a sentence “The graph is the following:”
Note: in all communications with the user the vertex numbering is natural, i.e. starting with 1.
3. Edit, compile and execute DiGraphTest class, test it thoroughly. When running the program, first
provide the graph by inputting N (number of vertices) and then one by one adding vertices (with ‘a’
menu option). Extensively test the functionality of your program: request different menu choices and
check their execution; then add and delete edges to change the graph and repeat the testing for the
modified graph. Finish testing when you are absolutely sure all the functionality of the program is correct.
Part 2 of 4 (15 points):
1. Make additions in the DiGraph class to include the implementation of the Topological Sort
algorithm including a supporting routine for computing vertex indegrees.
Add the following content to the DiGraph class’s definition.
a) A private method indegrees: returns an array of integers representing the indegrees of all vertices in
the graph: the i-th integer in the resulting array is the indegree of the i-th vertex.
b) A public method topSort: returns an array containing the list of topologically sorted vertices (values
in the array should represent natural vertex-numbers, i.e. starting with 1).
Important: If the graph is cyclic, this method must throw IllegalArgumentException type exception
(read the note on top of the last page of your Topological Sort lecture handout).
Attention: In topSort you need a regular queue and NOT a priority queue. To implement a queue in
Java, you can simply use an object of LinkedList class (for integers). Your list will
function like a regular queue if you always add an element to the end using addLast
method, and delete an element from the front using removeFirst method.
2. Make additions to the DiGraphTest class’s main method to incorporate one additional service.
Add one new menu-choice for outputting the topologically sorted list of vertices of the graph and arrange
the execution of that new service.
Attention: 1. Use t letter for the new menu choice (t – topological sort).
2. Numbering of vertices in the output should be natural (starts with 1).
3. The list should be output on one line, with vertex-numbers separated by commas.
Important: there should NOT be a comma after the last vertex.
3. Edit, compile and execute DiGraphTest program, testing the new service very thoroughly.
DEMO: Under Project5 on Canvas there is a link to demo instructions. Run your program
according to these instructions, make sure all answers/outputs are correct, and then put
a request for me to come to your breakout room. I will visit you to check your work.
Attention: 1. Demo early (as soon as you finish the assignment) to avoid last-day commotion.
2. Make sure both partners are present at the time of the demo.
Part 3 of 4 (30 points): implementation of breadth-first-search and related routines
1. Make additions in the DiGraph class to include the implementation of the BFS algorithm and
related routines to allow determining shortest distances and paths between vertices of the graph.
Note: For the purpose of this assignment, we’ll implement the BFS algorithm as a private method.
Add the following content to the DiGraph class’s definition. Note that parameter vertices in c,d,e methods
are given via natural numbering: you need to manage adjustments with Java indexing (no validity check).
a) A private nested class VertexInfo with two int instance variables: one for the distance (or length of the
path), and the second for the predecessor/parent of a vertex.
b) A private method BFS(int s): returns an array of VertexInfo type objects containing data that can be
used to construct shortest paths from s vertex to all vertices in the graph that are reachable from s. This
is the BFS algorithm we discussed in class (see lecture handout).
Note: this is a private method so you can decide how s vertex is given (via natural numbering or not).
Attention: In BFS you need a regular queue (not a priority queue). To implement a queue, in Java you
can define an object of LinkedList class (the list is for integers). Your list will function like a
regular queue if you always add an element to the end of the list (addLast method) and
delete an element from the front of the list (removeFirst method).
c) A public method isTherePath(int from, int to): returns true if there is a path from from vertex to to
vertex, and false otherwise.
Hint: invokes BFS method and uses data in the returned array.
d) A public method lengthOfPath(int from, int to): returns an integer – the shortest distance of the to
vertex from the from vertex.
Hint: invokes BFS method and uses data in the returned array.
e) A public method printPath(int from, int to): arranges the output of the shortest path from from vertex
to to vertex if to is reachable from from (vertices of the path should be printed in natural numbering); it
outputs “There is no path” otherwise.
Hint: invokes BFS method and uses data in the returned array.
2. Make additions to the DiGraphTest class’s main method to incorporate three additional services.
Add three menu choices and arrange the execution of the following three new services:
– For given two vertices find out if there is a path going from the first vertex to the second.
– For given two vertices find the length of the shortest path going from the first vertex to the second.
– For given two vertices print the shortest path going from the first vertex to the second, if such path
exists; and output an informative message otherwise.
Attention: 1. You must use menu letters: i – is there a path, l – length of the path, and s – shortest path.
2. To execute each of these requests, you need to ask the user to enter 2 vertex numbers.
Note: vertices are given via natural numbering, i.e. starting with 1. No validity check.
3. For l menu choice, if the destination vertex is not reachable from the source vertex, you can
output -1 as the length of the path.
3. Edit, compile and execute DiGraphTest class, testing all new services very thoroughly.
Dr. Hasmik Gharibyan
CSC/CPE349
2
Part 4 of 4 (30 points): building and printing of the breadth-first-tree
Preface:
A general tree can be implemented as a linked structure of nodes where each node contains a value and a
link to a list of its children. Here is an illustration of the linked structure for the given graph:
a root a
b c d b c d
e f g h i e f g h i
j k l j k l
Notes: 1. List of children is more convenient to implement as a linked list.
2. In this example the list of children for c,e,g,i,j,k,l nodes is empty.
Assignment:
1. Make additions in the DiGraph class to include the implementation of routines that will allow to
print the breadth-first-tree of the graph for the given start vertex s.
Add the following members to the DiGraph class’s definition.
a) A private nested class TreeNode with two instance variables: an int type variable to hold the vertexnumber and a LinkedList type list to hold TreeNode type objects representing this vertex’s children.
b) A private method buildTree(int s): returns the root of the breadth-first-tree for the given s sourcevertex. The tree can be built based on the data in the array returned by the BFS method.
Note: this is a private method so you can decide how s vertex is given (via natural numbering or not).
Hint: Create TreeNode type objects for every graph-vertex and link them using the array returned by the
BFS method, namely, using the predecessor values in this array (all you need to do is go through
the array and make arrangement to include each vertex into its parent’s list of children).
c) A public method printTree(int s): this method prints the breadth-first-tree for a given source vertex s.
Vertex s is given via natural numbering: manage adjustments with Java indexing. No validity check.
Hint: invoke buildTree method and obtain the breadth-first-tree (more precisely, its root-node). Then
arrange the printing of this tree in the required format (vertices must be naturally numbered)
Format of the tree: the tree should be printed in this commonly used formats (see the picture below)
where levels are depicted vertically (with 0-level as the leftmost “column”); elements on each level are
depicted in a “column” in the same order (with the leftmost element of the level depicted as the highest
one). You are required to implement the proper indentation, i.e. each level of the tree, compared to
the previous level, needs to be indented to the right by few spaces (e.g. 4 spaces).
a a
b
b c d e
f
j
e f g h i c
d
j k l g
h
k
l
i
Attention: Printing of the tree is easily implemented with recursion. You can have this public method
obtain the tree and initiate the recursion, and then include a private method to carry the recursive work.
Dr. Hasmik Gharibyan
CSC/CPE349
3
2. Make additions to the DiGraphTest class’s main method to incorporate one new service.
Add one new menu choices and arrange the execution of the following new service:
– for the given start vertex print the breadth-first-tree.
Attention: 1. Must use menu letter b for this new option: print breadth-first-tree.
2. To execute this request, you need to ask the user to enter a source vertex number (natural
number). There is no need for validity check.
3. Edit, compile and execute DiGraphTest class testing this new service very thoroughly.
Submitting your work:
Turn in DiGraph and DiGraphTest source files electronically via “handin” procedure by the
deadline (see the top of the first page of this document for the due date and time):
The account id is: hg-cpe103
The name of the assignment is: Project5
The name of the assignment for late submissions is: Project5_late.
Important requirements:
1. Your programs must compile and run from command line on our departmental
servers. So, before submitting, make sure your programs compile and run on lab machines.
2. Do not create packages for your source code, do not zip, and do not use folders for your
submission – all these complicate the automated grading process.
3. Each file must have a comment-header which should include both authors’ names and ids
(as in id@calpoly.edu), as well as the date and the assignment name (e.g. Project 5).
Reminder: only one submission needs to be made for a pair/team.
4. The header of each file must start at the first line (no empty lines or import statements
before it) and should be followed by at least one empty line before the first line of the code.
