Skip to Main Content

Data Structures

Computer Science Department

Flight Path Graph - 10 Course Points

The purpose of this assignment is to learn how to build and use Adjacency Lists, with an array of Singly Linked Lists.

The assignment has one component: Coding (10 points) submitted through Autolab.

Overview

To represent a graph, we can write it as a list of its unique vertices, each with a list of vertices of its own (representing that vertex’s edges). 

 

The above graph has 5 unique vertices. We can store vertices as a Linked List node, with a name and a next reference (next nodes are NOT necessarily graph edges).

We use a similar structure as to a hash table in order to store the graph. We use an array of Linked List nodes, where each index of the array represents one of the unique vertices. Since we store these as nodes, each index is also the head of a linked list. So, any node AFTER the first node in each list represents edges incident to the first node (the vertex). 

For example, in the above graph the vertex A points to one other node (D), so at index 0 in the corresponding array, we find A, then after is only D. Representing that A has an edge to D.

C has an edge to E, and so we find a node containing E in C’s linked list. E also has an edge to C, so we see also a node containing C inside E’s linked (edge) list.

 

Directions

  • DO NOT add new import statements.
  • DO NOT add any new class attributes
  • DO NOT change any of the method’s signatures.
  • DO NOT modify the given constructor.

To complete this Lab, you will implement the FlightPathGraph() constructor, addEdge(), and removeEdge() methods for the graph of cities (strings). Each vertex in this graph representation is a City, which is a simple linked list node with a name and a next.

The method signatures are already given, do not modify these or add any new ones.

There is one class attribute provided for you in FlightPathGraph.java:

  • “flightPaths” which is a reference to an adjacency list for the graph
    • This is not initialized. You will initialize this in the constructor with the given vertices, and then you will use this in addEdge() and removeEdge().

FlightPathGraph(String[] cities) (constructor)

This method initializes the graph with the given list of String names. Each name is a unique vertex which you should add to the graph.

First, initialize the flightPaths adjacency list array to the same size as the parameter cities array. Then, for each index in flightPaths, initialize it to a new City node, with the corresponding name from the same index in the input array.

In the FlightPathGraphTest.java file, you are provided a completed test for this method.

addEdge(String departure, String arrival)

This method adds a new directed edge from the departure vertex to the arrival vertex. If an edge already exists, do nothing.

Do NOT add loops (edges from a vertex to itself, i.e. u -> u). You can’t take a flight from an airport to the same airport. So addEdge(“a”, “a”) should NOT add an edge.

To add an edge, you should first find the index in flightPaths with the departure City. Remember, that index is actually the head of a linked list. If the arrival city is NOT already in that linked list (aka edge list for the departure city), then add it to the end of the list.

Once you complete this method, the drivers addEdge button will start to function. Select two different cities, then add an edge to draw a line between those vertices. If your code correctly adds a directed edge, then the edges will appear as red. Undirected edges are represented by black lines, and will appear if you add a symmetric edge (i.e. u -> v AND v -> u).

Here is the graph from above after a call to addEdge(“D”,”E”)

removeEdge(String departure, String arrival)

This method removes the DIRECTED edge between the departure vertex and arrival vertex. If the edge doesn’t exist or either the departure or arrival vertex doesn’t exist, do nothing.

CLARIFICATION 11/20: Do NOT remove the edge from arrival -> departure, disregard any comment in the FlightPathGraph.java file that says this.

Search the adjacency list (flightPaths) for the departure city, and if you find it search its corresponding linked list for the arrival city (and remove that node if you find it).

Here is what the graph AFTER addEdge(“D”,”E”) would look like after performing removeEdge(“B”,”C”), then removeEdge(“E”,”C”).

Autolab Hints

Similar to other assignments, autolab will compare your created data structure to the reference solution and output and mismatching nodes.

For this assignments, these messages will look like “Student flightPaths[x] at list index y is A, Should contain B”. This means that flightPaths at index x has an incorrect linked list. The node containing A should actually contain B. The list index starts at 0 (so flightPaths[x] is the node at index 0 for that linked list).

You should test your code with generic cases (any unique vertices), with many combinations of edges for addEdge and removeEdge. Ensure each method works properly before moving onto the next.

Driver

Once you implement your code, you can run the FlightPathGraph.java file and interact with the driver. It will show a visualization of predetermined city vertices in a graph. You can use the “addEdge” button to add a line (edge) between the chosen (distinct) vertices. You can also use the “removeEdge” button to remove any edges from the graph. 

If you insert edges correctly as directed, they will appear in the driver as red. This is correct – a single call to addEdge should create a DIRECTED edge.

You can use this Driver to test your code, but it is still useful to write JUnit test cases, in case the driver does not catch all cases.

Testing Your Code

We can test this adjacency list code using a test class, since the City nodes can contain any String.

In the main project folder, there exists a “test” folder inside the “src” folder. This contains JUnit tests, which can run and test pieces of your code. To compile and run these tests, you must install the JUnit package. See the Assignment FAQ for more info on VScode extensions.

You are provided with a premade JUnit test class for FlightPathGraph. Within this test class there is a COMPLETED test for the constructor and INCOMPLETE test stubs for addEdge()/removeEdge().

You should implement the two blank tests using JUnit tests (assertTrue(), assertFalse(), assertEquals()) in order to test your code as you write it. You do NOT need to submit this test file.

See the JUnit Testing Guide to learn more about JUnit tests. See the Debugging Guide to learn more about debugging.

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. (You’ll know if you have the Oracle Java extension if you see a “Run Configuration” option on the bottom-left corner of your VS Code window. Remember that you must fill in the tests for addEdge()/removeEdge().

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download FlightPathGraph.zip from Autolab Attachments.
  2. Unzip the file by double-clicking.
  3. Open VSCode
    • Import the folder to a workspace through File > Open Folder

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to FlightPathGraph directory/folder
      • to compile: javac -d bin src/graph/*.java
      • to execute: java -cp bin graph.FlightPathGraph
      • NOTE: if you have FlightPathGraph (2) -> FlightPathGraph or CS112 -> FlightPathGraph in VS Code, open the INNERMOST FlightPathGraph through File -> Open Folder.

Before submission

COMMENT all printing statements you have written from FlightPathGraph .java 

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit FlightPathGraph.java separately via the web submission system called Autolab. To do this, click the Labs and Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • Find head TAs office hours here
  • In addition to office hours we have the Coding and Social Lounge (CSL) , a community space staffed with ilab assistants which are undergraduate students further along the CS major to answer questions.

By Colin Sullivan