- Both partners fill in, sign and date the pair programming contract and BOTH partners submit.
- Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.
Part 1: The Graph Class (46 pts)- 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.
- Note that you must use your List.java from Lab 5 when you implement this Lab 5.
- 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:
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 5 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 6 */ import java.util.ArrayList; public class Graph { private int vertices; private int edges; private ArrayList<List<Integer> > adj; private ArrayList<Character> color; private ArrayList<Integer> distance; private ArrayList<Integer> parent; /**Constructor*/ /** * initializes an empty graph, with n vertices * and 0 edges, and intitializes all arraylists * to contain default values from indices 1 to n * @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 edges) * @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 0 < v <= vertices * @return the parent of vertex v * @throws IndexOutOfBoundsException when * the precondition is violated */ public Integer getParent(Integer v) throws IndexOutOfBoundsException { return -1; } /** * 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 null; } /** * Returns the List stored at index v * @param v a vertex in the graph * @return the adjacency List a v * @precondition 0 < v <= vertices * @throws IndexOutOfBoundsException when * the precondition is violated */ public List<Integer> getAdjacencyList(Integer v) throws IndexOutOfBoundsException { return null; } /*** 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 <= vertices, 0 < v <= vertices * @throws IndexOutOfBounds exception when the precondition * is violated */ public 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 <= vertices, 0 < v <= vertices * @throws IndexOutOfBounds exception when the precondition * is violated */ public void addUndirectedEdge(Integer u, Integer v) throws IndexOutOfBoundsException { } /*** Additional Operations ***/ /** * Creates a String representation of the Graph * Prints the adjacency list of each vertex in the graph, * vertex: <space separated list of adjacent vertices> */ @Override public String toString() { String result = ""; return ""; } /** * Prints the current values in the parallel ArrayLists * after executing BFS. First prints the heading: * v <tab> c <tab> p <tab> 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() { } /** * Performs breath first search on this Graph give a source vertex * @param source the source vertex * @precondition graph must not be empty * @precondition source is a vertex in the graph * @throws IllegalStateException if the graph is empty * @throws IndexOutOfBoundsException when vertex is * outside the bounds of the graph */ public void BFS(Integer source) throws IllegalStateException, IndexOutOfBoundsException { } } 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<List<Integer> > adj; - 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.
- 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.
**Important Note: Use your List.java class to stand in place of the Queue class in your implementation**
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
- 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
- Save two or more text files in the main project directory on Eclipse (right-click the name of the project and go to New->File) not in the src folder.
- Name your two text files using names of your choice.
- Note that I have named the files friends.txt and friends2.txt in the below example,
**but the user should be allowed to enter a file of any name.** - The first line of the input file specifies the number of vertices in the Graph
- Following this line, subsequent lines come in groups of 3, all of the information about one user:
- the user id
- the name of the user
- a comma separated list of friends of that user listed by id
- Note that you will need an array or ArrayList to store the associated user ids and user names, and a Graph to track the friend network and make friend recommendations (Hint: Call BFS)
- Since the Graph can only store integers, the array or ArrayList will allow you to associate names with user ids.
- Note that you can assume that the graph is undirected
- Your program should work *identically* to the sample output below, given the same input file.
- Note that the only input validation required is to check that the file name exists in the Eclipse folder of that project
- Friend recommendations should be made based on connections to the wider friend network (in other words, friends of friends or friends of their friends, or friends of friends of friends, etc). Not included should be current friends or a node with no connection to the wider friend network. (Hint: Call BFS).
10 |