18  17L. Implementing Graphs

18.1 Project Overview

Here are the files in your project

.
├── src
│  ├── ADTs
│  │  ├── EdgeADT.java
│  │  ├── GraphADT.java
│  │  └── VertexADT.java
│  └── DataStructures
│     ├── DirectedEdge.java
│  >  ├── DirectedGraph.java           (Work here)
│     ├── DirectedWeightedEdge.java
│  >  ├── DirectedWeightedGraph.java   (Work here)
│     ├── UndirectedEdge.java  
│  >  ├── UndirectedGraph.java         (Work here)
│     ├── UndirectedWeightedEdge.java
│  >  ├── UndirectedWeightedGraph.java (Work here)
│     └── Vertex.java
└── test
   └── DataStructures
      ├── DirectedGraphTest.java
      ├── DirectedWeightedGraphTest.java
      ├── UndirectedGraphTest.java
      └── UndirectedWeightedGraphTest.java

18.2 Detailed Instructions

This project is about learning how to implement graphs in Java. 4 types of graphs will be implemented in this project:

  1. Directed Graph
  2. Undirected Graph
  3. Directed Weighted Graph
  4. Undirected Weighted Graph

Directed graphs are graphs where the edges have a direction. Undirected graphs are graphs where the edges do not have a direction. Weighted graphs are graphs where the edges have a weight. The weight can be used to represent the distance between two vertices. This distance can represent the cost of traveling between two vertices, or the cost can be the time it takes to travel between two vertices or the amount of money it costs to travel between two vertices, etc.

Instead of implementing everything from scratch, we will just be implementing four operations:

  1. addVertex()
  2. removeVertex()
  3. addEdge()
  4. removeEdge()

18.2.1 Getting Started

You should start by looking at this file. It explains everything you need to know about the files in this project.

18.2.2 Operations

18.2.2.1 addVertex(V vertex)

This operation adds a vertex to the graph. It takes a single argument, the vertex to be added, and returns a boolean value indicating whether the vertex has been added successfully.

Pseudocode:

For all types of graphs, the addVertex() operation is the same:

  1. Check if the vertex already exists in the graph.
  2. If it does, return false.
  3. Add the vertex to the graph and return true.

18.2.2.2 removeVertex(V vertex)

This operation removes a vertex from the graph. It takes a single argument, the vertex to be removed, and returns a boolean value indicating whether the vertex has been removed successfully.

Pseudocode:

  1. Check if the vertex exists in the graph.
  2. If it doesn’t, return false.
  3. Remove all edges connected to the vertex.
  4. Remove the vertex from the graph and return true.

18.2.2.3 addEdge(V vertex1, V vertex2)

This operation adds an edge to the graph. It takes two arguments, the vertices that the edge connects, and returns a boolean value indicating whether the edge has been added successfully.

Pseudocode:

18.2.2.3.1 For directed graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge already exists. If it does, return false.
  4. Add the edge from the first vertex to the second vertex and return true.
18.2.2.3.2 For undirected graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge already exists. If it does, return false.
  4. Add the edge between the first and second vertices (both ways) and return true.
18.2.2.3.3 For directed weighted graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge already exists. If it does, return false.
  4. Add the weighted edge from the first vertex to the second vertex and return true.
18.2.2.3.4 For undirected weighted graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge already exists. If it does, return false.
  4. Add the weighted edge between the first and second vertices (both ways) and return true.

18.2.2.4 removeEdge(V vertex1, V vertex2)

This operation removes an edge from the graph. It takes two arguments, the vertices that the edge connects, and returns a boolean value indicating whether the edge has been removed successfully.

Pseudocode:

18.2.2.4.1 For directed graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge exists. If it doesn’t, return false.
  4. Remove the edge from the first vertex to the second vertex and return true.
18.2.2.4.2 For undirected graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge exists. If it doesn’t, return false.
  4. Remove the edge between the first and second vertices (both ways) and return true.
18.2.2.4.3 For directed weighted graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge exists. If it doesn’t, return false.
  4. Remove the weighted edge from the first vertex to the second vertex and return true.
18.2.2.4.4 For undirected weighted graphs:
  1. Check if the vertices exist in the graph.
  2. If not, return false.
  3. Check if the edge exists. If it doesn’t, return false.
  4. Remove the weighted edge between the first and second vertices (both ways) and return true.

18.3 Rubric

  1. Project must compile, otherwise no grade.

  2. Unit tests for DirectedGraph must pass (15 points)

  3. Unit tests for DirectedWeightedGraph must pass (15 points)

  4. Unit tests for UndirectedGraph must pass (15 points)

  5. Unit tests for UndirectedWeightedGraph must pass (15 points)

18.4 Project Files

Download the project files here.

18.5 Opening Project in Visual Studio Code

  1. Download the project files from

  2. Unzip the files to preferably an ITSC 2214 folder for this class. You must have created this folder before for previous labs. Unzip_Location_ITSC_2214

  3. Launch Visual Studio Code. Go to File > Open Folder…, navigate and select the folder where you have extracted the zip file. Vs_code_extract_zip

18.6 Update the autograder

First, please update your autograder by running:

umm update

18.7 Checking Autograder Feedback

You can check your grade locally by following these steps:

  1. Open a terminal. To open a terminal in Visual Studio Code on different operating systems:

    • Windows: Press ” Ctrl + ` ” or ” Ctrl + Shift + ` ” to open the integrated terminal.

    • Mac: Press ” Cmd + ` ” or ” Cmd + Shift + ` ” to open the integrated terminal.

  2. Run the command:

    umm grade ./script.rhai

18.8 Submitting your Project

When you are ready to submit your assignment:

  1. Open a terminal. To open a terminal in Visual Studio Code on different operating systems:

    • Windows: Press ” Ctrl + ` ” or ” Ctrl + Shift + ` ” to open the integrated terminal.

    • Mac: Press ” Cmd + ` ” or ” Cmd + Shift + ` ” to open the integrated terminal.

  2. You can copy and run the umm create-submission command in the terminal, and that should create a zip file with a name similar to submission-2024-01-24-15-04-50.zip.

    umm create-submission

  3. Submit the submission-2024-... .zip file to Gradescope. The submission zip file will appear in the file explorer tab of VS Code. You can right click on this file and click on reveal in explorer (windows) or reveal in finder (mac) in order to find this file. then, you can drag and drop this to gradescope for submission.