Writing The Graph Class Solved

Description

Part 1: Writing The Graph Class

We will be using the adjacency list representation of a Graph when we write the Graph data structure.

The heart of the Graph data structure will be an ArrayList of Lists, to store the adjacent vertices of each vertex in the Graph.

For this assignment, you could visualize the above Graph as shown in the diagram to its right.

1, 2, 3, 4 and 5 in the left hand column of the diagram are indices of the ArrayList (array).

Those values to their right are their adjacency lists which are stored as linked lists.

Specifically, for our purposes, we will be representing the Graph as an ArrayList of linked lists named “adj”

Thus, we could visualize storing the graph as depicted below for this assignment:

adj[0] (purposely left empty!)

adj[1] = 2 -> 3 -> 4 -> null //at index 1, we store the adjacency list of vertex 1

adj[2] = 3 -> null //at index 2, we store the adjacency list of vertex 2

adj[3] = 2 ->null //at index 3, we store the adjacency list of vertex 3, etc

adj[4] = 4 -> null

adj[5] = 2 -> null

Graph.java File

Copy the code below into a new file called Graph.java

Also, in the same project, copy and paste your List.java from Lab 4 into a new file called List.java

Lastly, create a test file called GraphTest.java to test your methods as you write them.

Note that you will also need to draw out some graphs on paper and trace BFS on them to test your code in GraphTest.java and verify that your methods are working correctly.

/**
* Graph.java
* @author
* @author
* CIS 22C, Lab 8
*/

import java.util.ArrayList;

public class Graph {
private int vertices;
private int edges;
private ArrayList > adj;
private ArrayList color;
private ArrayList distance;
private ArrayList parent;

/**Constructors*/

/**
* initializes an empty graph, with n vertices
* and 0 edges
* @param n the number of vertices in the graph
*/
public Graph(int n) {

}

/*** Accessors ***/

/**
* Returns the number of edges in the graph
* @return the number of edges
*/
public int getNumEdges() {
return -1;
}

/**
* Returns the number of vertices in the graph
* @return the number of vertices
*/
public int getNumVertices() {
return -1;
}

/**
* returns whether the graph is empty (no vertices)
* @return whether the graph is empty
*/
public boolean isEmpty() {
return false;
}

/**
* Returns the value of the distance[v]
* @param v a vertex in the graph
* @precondition 0 < v <= vertices
* @return the distance of vertex v
* @throws IndexOutOfBoundsException when
* the precondition is violated
*/
public Integer getDistance(Integer v) throws IndexOutOfBoundsException{

return -1;

}

/**
* Returns the value of the parent[v]
* @param v a vertex in the graph
* @precondition v <= vertices
* @return the parent of vertex v
* @throws IndexOutOfBoundsException when
* the precondition is violated
*/
public Integer getParent(Integer v) throws IndexOutOfBoundsException {

return 0;

}

/**
* Returns the value of the color[v]
* @param v a vertex in the graph
* @precondition 0< v <= vertices
* @return the color of vertex v
* @throws IndexOutOfBoundsException when
* the precondition is violated
*/
public Character getColor(Integer v) throws IndexOutOfBoundsException {
return ‘\0’;

}

/*** Manipulation Procedures ***/

/**
* Inserts vertex v into the adjacency list of vertex u
* (i.e. inserts v into the list at index u)
* @precondition, 0 < u, v <= vertices
* @throws IndexOutOfBounds exception when the precondition
* is violated
*/
void addDirectedEdge(Integer u, Integer v) throws IndexOutOfBoundsException {

}

/**
* Inserts vertex v into the adjacency list of vertex u
* (i.e. inserts v into the list at index u)
* and inserts u into the adjacent vertex list of v
* @precondition, 0 < u, v <= vertices
*
*/
void addUndirectedEdge(Integer u, Integer v) {

}

/*** Additional Operations ***/

/**
* Creates a String representation of the Graph
* Prints the adjacency list of each vertex in the graph,
* vertex:
*/
@Override public String toString() {
String result = “”;
return result;
}

/**
* Prints the current values in the parallel ArrayLists
* after executing BFS. First prints the heading:
* v c p d
* Then, prints out this information for each vertex in the graph
* Note that this method is intended purely to help you debug your code
*/
public void printBFS() {
System.out.println(“v\tc\tp\td”);

}

/**
* Performs breath first search on this Graph give a source vertex
* @param source
* @precondition graph must not be empty
* @precondition source is a vertex in the graph
* @throws IllegalStateException if the graph is empty
* @throws IndexOutOfBoundsException when the source vertex
*/

public void BFS(Integer source) throws IllegalStateException, IllegalArgumentException {

}

/**
* Recursive method to make a String containing the path

* from the source to the destination vertex
* @param source the source vertex when performing BFS
* @param destination the destination vertex
* @param a String containing the path
* @return a String containing the path
*/
//Prints to the console or to an output file given the ostream parameter
public String printPath(Integer source, Integer destination, String path) {

return “”;

}

}

Parallel Arrays for the BFS Algorithm

Your Graph will store information not only about adjacent vertices, but also about the color, parent and the distance (from the source) of all the vertices in the Graph.

Inside your Graph class, there are four private ArrayLists:

private ArrayList > adj;
private ArrayList color;
private ArrayList distance;
private ArrayList parent;

These ArrayLists are in parallel to each other.

For example:

adj.get(1)
color.get(1)
distance.get(1)
parent.get(1)

All store information about vertex 1 of the Graph.

In other words, your Graph should contain:

An ArrayList of Lists whose ith element contains the neighbors of vertex i.

A ArrayList of Characters whose ith element is the color (white, gray, black) of vertex i.

A ArrayList of Integers whose ith element is the parent of vertex i.

A ArrayList of Integers whose ith element is the distance from the source to vertex i.

The Graph Constructor

Your graph constructor will take in a parameter for the number of vertices in the graph.

This parameter will define the size of the private parallel ArrayLists.

You will need to initialize all values in the parallel ArrayLists.

The color ArrayList should be initialized to ‘W’ (later updated to ‘G’ and ‘B’)

The distance ArrayList should be initialized to -1 (which we will use to indicate an infinite distance)

The parent ArrayList should be initialized to 0.

The adjacency list ArrayList should be initialized to an empty list at each index.

Note that your Graph constructor can be written using a single for loop to initialize all the ArrayLists.

Implementation of the BFS Algorithm

Use the pseudocode below to help you implement this method.

Note: Use your List.java class to stand in place of the Queue class in your implementation

BFS(G, s)

for all x in V(G)

color[x] = white

distance[x] = -1

parent[x] = Nil

color[s] = grey

distance[s] = 0

Enqueue(Q,s)

while(Q is not empty)

x = front of Q

Dequeue(Q,x)

for all y in adj[x]

if color[y] == white

color[y] = grey

distance[y] = distance[x] + 1

parent[y] = x

Enqueue(Q, y)

color[x] = black

Displaying Your Graph: toString() and printBFS()

Using the toString method for the Graph, we will create the Adjacency List Representation.

Thus, when we print the graph returned from toString(), we will print its adjacency list representation.

Below is an example of how to print a Graph g when the user System.out.println(g.toString()):

1: 2 5

2: 1 3 4

3: 2 4

4: 2 3 5

5: 1 4 5

In contrast, below is an example of what the printBFS() method’s output should look like:

v   c   p   d
1   B    0    0
2   B   1   1
3   B   2   2
4   B   2   2
5   B   1   1

Note that the printBFS() method is designed to be useful to you as the programmer in tracking down bugs as you are implementing the BFS method. It has no other purpose in this assignment.

The Print Path Algorithm

Once BFS has been called on a Graph, you will need a way to step through the parent ArrayList to find the shortest path from the source to the destination vertex.

We can use the recursive print path algorithm to help us.

Below is the recursive pseudocode for Print Path:

Print_Path(Graph, source, destination, path)

if destination == source

return source + path

else if parent[destination] == 0

return “No path from ” source “to ” destination ” exists”

else

return Print_Path(Graph, source, parent[destination], destination + path)

Part 2: Testing Your Graph

As you write each method, test your graph inside of GraphTest.java

When your Graph.java is complete, write a JUnit test file for each of the following methods, where you call assertEquals three times

Graph constructor

getNumEdges

getNumVertices

getParent

getDistance

getColor

BFS

printPath