Lab 6: Graphs (100 pts)

Due Friday, June 19th at 11:59pm on Canvas


Pair Programming Required or No Credit!

  • 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:
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 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;
private ArrayList<Character> color;
private ArrayList<Integer> distance;
private ArrayList<Integer> 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.
  • Important 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

Part 2: FriendNetwork.java (44 pts)

  • 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).


Example Input File:

10
1
Jiming Wu
2, 7, 10,
2
James Brown
1, 4, 5, 6,
3
Leanna Perez
6, 8, 9, 10,
4
Xing Li
2, 5, 6,
5
Stacey Cahill
2, 4,
6
Mohammed Abbas
2, 3, 4, 7,
7
Kumari Chakrabarti
1, 6,
8
Shakil Smith
3,
9
Jung Ahrin
3, 10,
10
Pedro Martinez
1, 3, 9,

Example Output 1:

Welcome to the Friend Recommender!

Enter the name of a file: friends.txt
Enter Your User Number Below:
1. Jiming Wu
2. James Brown
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez

Enter your choice: 3

Here are your current friends:
6. Mohammed Abbas
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
2. James Brown
4. Xing Li
5. Stacey Cahill
7. Kumari Chakrabarti

Enter the number of a friend to add or -1 to quit:
Enter your choice: 2

Here are your current friends:
2. James Brown
6. Mohammed Abbas
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
4. Xing Li
5. Stacey Cahill
7. Kumari Chakrabarti

Enter the number of a friend to add or -1 to quit:
Enter your choice: 7

Here are your current friends:
2. James Brown
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
4. Xing Li
5. Stacey Cahill

Enter the number of a friend to add or -1 to quit:
Enter your choice: -1

Goodbye!


Example Output 2:

Welcome to the Friend Recommender!

Enter the name of a file: friends

Invalid file name!
Enter the name of a file: friends.tx

Invalid file name!
Enter the name of a file: friends.txt

Enter Your User Number Below:
1. Jiming Wu
2. James Brown
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez

Enter your choice: 9

Here are your current friends:
3. Leanna Perez
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
2. James Brown
4. Xing Li
5. Stacey Cahill
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith

Enter the number of a friend to add or -1 to quit:
Enter your choice: 5

Here are your current friends:
3. Leanna Perez
5. Stacey Cahill
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
2. James Brown
4. Xing Li
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith

Enter the number of a friend to add or -1 to quit:
Enter your choice: 4

Here are your current friends:
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
2. James Brown
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith

Enter the number of a friend to add or -1 to quit:
Enter your choice: 8

Here are your current friends:
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
8. Shakil Smith
10. Pedro Martinez

Here are your recommended friends:
1. Jiming Wu
2. James Brown
6. Mohammed Abbas
7. Kumari Chakrabarti

Enter the number of a friend to add or -1 to quit:
Enter your choice: -1

Goodbye!

Example Input File:

13
1
Jiming Wu
2, 4,
2
James Brown
1, 4,
3
Leanna Perez
7, 8,
4
Xing Li
1, 2,
5
Stacey Cahill
7,
6
Mohammed Abbas
10,
7
Kumari Chakrabarti
3, 5,
8
Shakil Smith
3, 9,
9
Jung Ahrin
8,
10
Pedro Martinez
6, 12,
11
Abir Fadel
12, 13,
12
Brad Feinman
10, 11, 13,
13
Xiaohang Yue
11, 12,

Example Output 1:

Welcome to the Friend Recommender!

Enter the name of a file: friends2.txt
Enter Your User Number Below:
1. Jiming Wu
2. James Brown
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez
11. Abir Fadel
12. Brad Feinman
13. Xiaohang Yue

Enter your choice: 6

Here are your current friends:
10. Pedro Martinez

Here are your recommended friends:
11. Abir Fadel
12. Brad Feinman
13. Xiaohang Yue

Enter the number of a friend to add or -1 to quit:
Enter your choice: 11

Here are your current friends:
10. Pedro Martinez
11. Abir Fadel

Here are your recommended friends:
12. Brad Feinman
13. Xiaohang Yue

Enter the number of a friend to add or -1 to quit:
Enter your choice: 12

Here are your current friends:
10. Pedro Martinez
11. Abir Fadel
12. Brad Feinman

Here are your recommended friends:
13. Xiaohang Yue

Enter the number of a friend to add or -1 to quit:
Enter your choice: 13

Here are your current friends:
10. Pedro Martinez
11. Abir Fadel
12. Brad Feinman
13. Xiaohang Yue

Here are your recommended friends:
Sorry! We don't have any recommendations for you at this time.

Goodbye!


Sample Output 2:
Welcome to the Friend Recommender!

Enter the name of a file: friends2.txt
Enter Your User Number Below:
1. Jiming Wu
2. James Brown
3. Leanna Perez
4. Xing Li
5. Stacey Cahill
6. Mohammed Abbas
7. Kumari Chakrabarti
8. Shakil Smith
9. Jung Ahrin
10. Pedro Martinez
11. Abir Fadel
12. Brad Feinman
13. Xiaohang Yue

Enter your choice: 2

Here are your current friends:
1. Jiming Wu
4. Xing Li

Here are your recommended friends:
Sorry! We don't have any recommendations for you at this time.

Goodbye!


How You Will Be Graded
  • 3 points for each correct Graph method and 10 points for a correct BFS method (total of 46 points)
  • 10 points for the GraphTest.java, that tests each method thoroughly - including edge cases and preconditions. At a minimum, aim for two method calls per method.
  • 44 points for a FriendNetwork.java which can replicate the results of the example input and output files given for this assignment, plus any additional files with which the instructor may decide to test your code

What to Submit

  • Submit your List.java, Graph.java, FriendNetwork.java, and GraphTest.java to Canvas, as well as your pair programming contract for this lab.
  • Please do not use Queue.java or submit Queue.java in this Lab.
    • You must use List.java to represent the BFS queue.
  • Please submit each file separately (no zip files please -5 pts).
  • Please remove all package statements before submitting (-5 pts).
  • Missing pair programming contract (-5 pts).
  • Please do not add any additional import statements to the provided Graph.java or you will not received credit for this Lab.