Lab 8: Graphs (100 pts)
Due Monday, March 4 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: Writing The Graph Class (65 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 4 when you implement this Lab 4.

  • 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<List<Integer> > adj;
    private ArrayList<Character> color;
    private ArrayList<Integer> distance;
    private ArrayList<Integer> 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 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 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
     */
    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, v <= vertices
     * 
     */
    public 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: <space separated list of adjacent vertices>
     */
    @Override public String toString() {
        String result = "";
        return result;
    }
   
   
   
    /**
     * 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() {
        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
     * is not a vertex in the graph
     */

    public void BFS(Integer source) throws IllegalStateException, IndexOutOfBoundsException {
       
    }
   
    /**
     * 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
     */
   
    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<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.


    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 (13 pts)

    • 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


    Part 3: File I/O and WriteGraph.java (22 pts)

    • Save two 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.
    • The input file will be in two parts. The first part will begin with a line consisting of a single integer n giving the number of vertices in the graph.
      • You will pass this value n into your Graph constructor, setting the numVertices to be this value n.
    • Each subsequent line will represent an undirected edge by a pair of distinct numbers in the range 1 to n, separated by a space.
      • These numbers are the end vertices of the corresponding edge.
    • The first part of the input file defines the graph, and will be terminated by a dummy line containing “0 0”. After these lines are read, your program will print the adjacency list representation of the graph to the output file.
    • The second part of the input file will consist of a number of lines, each consisting of a pair of integers in the range 1 to n, separated by a space.
      • Each line specifies a pair of vertices in the graph; a starting point (or source) and a destination.
    • The second part of the input file will also be terminated by the dummy line “0 0”.
    • For each source-destination pair your program will do the following:
      • Perform a Breadth First Search (BFS) from the given source vertex. This assigns a parent vertex (which may be 0, indicating that there is no parent) to every vertex in the graph.
      • Use the results of BFS to print out the distance from the source vertex to the destination vertex, then use the parent pointers to print out a shortest path from source to destination.


    Example Input File:

    7
    1 3
    1 4
    1 5
    2 6
    3 5
    4 5
    5 7
    0 0
    1 7
    2 6
    3 3
    4 6
    0 0


    Example Output File:

    1: 3 4 5
    2: 6
    3: 1 5
    4: 1 5
    5: 1 3 4 7
    6: 2
    7: 5
    The distance from 1 to 7: 2
    A shortest path from 1 to 7: 1 5 7
    The distance from 2 to 6: 1
    A shortest path from 2 to 6: 2 6
    The distance from 3 to 3: 0
    A shortest path from 3 to 3: 3
    The distance from 4 to 6: -1
    No path from 4 to 6 exists.


    • If there is no path from source to destination (which may happen if the graph is disconnected), then your program should print a message to that effect.
    • Note that there may be more than one shortest path joining a given pair of vertices.
    • The particular path discovered by BFS depends on the order in which it steps through the vertices in each adjacency list.
    • We adopt the convention in this assignment that vertices are always processed in sorted order, i.e. by increasing labels.

    Input File:

    8
    1 2
    2 3
    2 4
    2 5
    2 6
    3 8
    6 7
    7 8
    0 0
    2 7
    4 7
    5 8
    0 0


    Output File:

    1: 2
    2: 1 3 4 5 6
    3: 2 8
    4: 2
    5: 2
    6: 2 7
    7: 6 8
    8: 3 7
    The distance from 2 to 7: 2
    A shortest path from 2 to 7: 2 6 7
    The distance from 4 to 7: 3
    A shortest path from 4 to 7: 4 2 6 7
    The distance from 5 to 8: 3
    A shortest path from 5 to 8: 5 2 3 8



    WriteGraph.java (22 points)

    • Your WriteGraph.java should work identically to the sample output below.
    • It should prompt a user for the name of a file and then use a loop to report an error if the file name is not found in the directory.
    • It should read in the contents of the file specified by the user
      • Note that the user should be able to name the input and output files anything they want. Do not assume the names of the files will be input.txt and output.txt
    • Next, it will call BFS on the graph for each source vertex, and then calculate the path from source to destination.
    • It should then prompt the user for the name of an output file and print the information as shown in the sample output files above into the output file:


    Welcome to WriteGraph!

    Enter the name of the file containing the graph information: asdkshjkdshljkdsf
    Invalid file name!

    Please enter the name of the file: input
    Invalid file name!

    Please enter the name of the file: input.txt

    ***Reading from input.txt***

    Please enter the name of the output file: output.txt
    Thank you! Your Graph is now written to output.txt!



    How You Will Be Graded
    • 5 points for each correct Graph method
    • 13 points for the GraphTest.java, as well as the JUnit test files specified above
    • 22 points for a WriteGraph.java which can replicate the results of all 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, WriteGraph.java, GraphTest.java, and JUnitTest files 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).
    • Please do not add any additional import statements to the provided Graph.java or you will not received credit for this Lab.