Project 2: Travel Planner

Gear-up: Sunday, March 13 at 3pm ET at this link!
Design Check: March 14-16, 2022
Due Date: Thursday, March 24, 2022 at 11:59pm ET

Note on stencil code: You'll receive invitations to join your repository with the stencil code shortly after project pairings are out.

Overview

In this project, you will be designing a system that will allow a user (e.g. Pitbull aka tall Mr. Worldwide) to plan travel routes that meet their needs (though it's likely he's already been there, done that). Specifically, users can load a travel graph, then request routes according to one of 3 priorities:

• Price, the route that costs the lowest amount of money
• Time, the route with the lowest total travel time
• Directness, the route with the fewest number of connections

Users will load graphs and request routes through text prompts in the IntelliJ console (we've written that part). Your code will compute routes, which our code will print back to users.

Learning Objectives

• Understanding code placement in model-view-controller
• Working with Function objects
• Working with Generics
• Implementing Data Structures
• Implementing and Debugging Algorithms
• Testing Data Structures and Algorithms

Style Expectations

For this and all future assignments, we expect your code to conform to the CS200 Java Style Guide.

Background

In lecture, we have talked about different algorithms for finding paths in graphs. Different algorithms are good for optimizing different aspects of paths. Sometimes, the same algorithm needs to be tailored to work on different pieces of information. This project has you combine what we've been learning about algorithms, software organization, and testing to develop a well-designed program for choosing and customizing algorithms. Concretely, you will:

• Fill in classes that represent travel graphs (using classes and interfaces that we will provide).
• Implement the BFS and Dijkstra's algorithms that we covered in lecture.
• Connect your code to a provided CSV parser and REPL to enable interaction with users.
• Make a debugging plan for your algorithm implementations.
• Create a good set of graphs for testing your project.

Note: The end of each sub-section in the Implementation Details section gives you a list of tasks you need to do to complete for each part of the project. The design check section walks you through some ways you might think about designing the code for these tasks.

Developing your Intuition: A Concrete Example

Let's say you have the following route data:

A few things to note:

• The data contain Cities and Transportation, corresponding to the vertices and edges of your graph.
• The graph is directed, meaning that transportation is not guaranteed to go both ways (i.e. there is a bus that goes from New York City to Providence but not the other way around).
• Each transportation contains information about its mode (train, bus, etc.), cost, and time.

If a user requests the fewest connections to get from New York City to Providence, they'll be given a direct route that costs $40 and takes 225 minutes. If instead they ask for the fastest such route, however, they'll be given a route that goes through Boston and takes a total of 130 minutes.

Here's an example of what the interface looks like for a user to load a graph and request a (fast) route. The valid commands at the prompt are load, fast, cheap, and direct. Note that we have to put "New York City" in quotes since its name is more than one word.

>>> load data/cities1.csv data/transport1.csv
Successfully loaded cities and transportation files.
>>> fast "New York City" Providence
================================================================================
Origin: New York City
Destination: Providence
--------------------------------------------------------------------------------
 -- New York City -> Boston, Type: plane, Cost: $267.0, Duration: 50.0 minutes
 -- Boston -> Providence, Type: train, Cost: $13.0, Duration: 80.0 minutes
================================================================================

If an error occurs, the interface should print an informative message such as

>>> load filedoesntexist filedoesntexist
Error parsing file: filedoesntexist

The cities and transit options between them are provided in CSV files. We have given you the CSV parser (TravelCSVParser.java) and the command-line interface code (REPL.java). The latter is associated with an interface ITravelController that requires the load, fast, cheap, and direct methods. You will flesh out a class that implements this interface, and you will write the classes for the underlying graph data structure and the route-finding algorithms.

Architecture

The classes for this project should be organized around a model-view-controller architecture.

• The model portion consists of the classes for your graph data structure and your implementations of the algorithms.
• The view portion consists of the CSV parser and the command-line REPL. This portion has been written for you!
• The controller handles communication between the view and the model. User requests to load graphs or compute routes will be sent from the view to the controller, the controller will call methods in the model to compute the routes and then pass those routes back to the view to display to the user.

Stencil Code

You will find the following classes in the src directory:

• A City class that you will use to represent the vertices of your graph
• An IBFS interface with the header for the method that performs BFS
• An IDijkstra interface with the header for the method that performs Dijkstra's lowest cost algorithm
• An IGraph interface with methods for creating and getting information from graphs
• An ITravelController interface with methods to load graphs from files and find routes with different priorities
• A Main class that you will use to run your project.
• A REPL class containing code to allow the user to interact with the program
• A Transport class that you will use to represent the edges of your graph
• A TransportType enum that defines an enumerated type (fixed set of values) for transit options, specifically plane, train, and bus
• A TravelCSVParser class to parse CSV files into Map objects that you can use to create graphs

You will find the following (initial) classes in the sol directory:

• A TravelController class that implements the ITravelController interface`
• A TravelGraph class that implements the IGraph interface
• A Dijkstra class that implements the IDijkstra interface
• A BFS class that implements the IBFS interface

You will find the following classes in the test directory:

• A simple package, containing:
  • A SimpleVertex class that represents a simple vertex
  • A SimpleEdge class that represents a simple edge
  • A SimpleGraph class that represents simple graph
• A GraphTest class, which you will use to test your graph methods
• A BFSTest class, which you will use to test your BFS
• A DijkstraTest class, which you will use to test your Dijkstra's

The data directory provides the CSV files for the sample we showed (cities1.csv and transport1.csv), as well as a second graph on 5 cities. You will create CSV files for your own graphs for testing in this directory.

The test/simple directory provides three basic classes for a vertex, edge, and graph. These don't have the city and transit details. We provide these so you can do basic tests of your BFS and Dijkstra's algorithms, but using these classes is not required and you will not be graded on tests using these classes.

Putting it together

Running the program (via the Main.java we provide) will call the run method in REPL.java.

The run method presents a prompt to the user (in your IntelliJ terminal window). At this point, the user can enter commands (load, fast, cheap, direct) as shown in the above interface demo. The REPL code will call the methods declared in the ITravelController interface to execute those commands (you will implement the underlying methods in one of your classes).

Your implementation of load (from ITravelController) will call methods in the TravelCSVParser class. Your implementations of fast, cheap, and direct in your TravelController will call the IBFS and IDijkstra methods that you've implemented.

There are different ways you could proceed with the design of this project. We outline two options near the bottom of the handout.

Concept: Functions as Arguments in Java

Your program needs to support finding routes based on combinations of time or cost. Fast routes look at time and ignore costs. Cheap routes look at cost and ignore time. One could also imagine more sophisticated weights based on factors like the cost per minute of travel time. This means that edge weights may vary depending on travel priorities. How do you implement Dijkstra's algorithm to account for differing edge weights from use to use?

You might imagine having your Dijkstra's implementation take a String as an argument that names which field to use. This is a weak approach (you'll think about why for your design check). Instead, you'll want to provide Dijsktra's with a function that indicates how to weigh an edge for that particular run of the algorithm. This is the kind of task that we used lambdas for in Racket and Pyret. How do we do this in Java?

Java provides an interface called Function that can be used to create a function with one parameter. Here's a brief example:

import java.util.function.Function;

class FunctionDemo {
    public static void main(String[] args) {
        Function<Integer, Boolean> isLarge = num -> num > 10;
   
        System.out.println("Checking whether 6 is large" );
        System.out.println(isLarge.apply(6));
    }
}

The Function interface takes two arguments: the input type and the output type. The notation for the function definition itself is

   input -> expression-using-input

You don't include return in this notation (the result of the expression gets returned automatically). An important exception to this rule is when you are writing a Function that returns Void. In this case, you must explicitly return null at the end of your function, even if it is a single-line function (i.e. making it a two-line function). Again, this is similar to lambdas in Pyret and Racket.

Sometimes, the body of a Function may need to perform multiple steps. Wrapping the body expression in curly braces allows this (note: in this case you need to include an explicit return):

Function<String, Boolean> isShort = 
   str -> { 
        len = str.length();
        return len < 5; 
    };
            
System.out.println(isShort.apply("functional"));

To use the Function object, we call its (built-in) apply method, giving it the input for the call. The second println in the below code thus calls testWithEight on the Integer 5.

Here's an example of a method that takes a Function as an input:

public Boolean testWithEight(Function<Integer, Boolean> checker) {
        return checker.apply(8);
}
System.out.println(testWithEight(num -> num == 5));

You should use Function objects to customize two parts of your code: tailoring edge weights in Dijkstra's algorithm and building your graph using the CSV parser. Details on both are below.

Implementation Details

There are three major programming steps, each detailed in its own labeled section below.

1. Choosing Data Structures and Classes for Graphs

Graphs can be represented and stored with a variety of built-in data structures (LinkedLists, ArrayLists, Maps, etc.) and classes that you define. You will use the City class to represent your vertices (as the parameterized V type) and the Transport class to represent your edges (as the parametrized E type). You will use these in a class called TravelGraph that implements the IGraph<V,E> interface.

Something you will need to think about inside your TravelGraph class is how you will get from a city name to the object in memory that represents the corresponding City. How can you store each City such that it is paired with the name of said city? The design check walks you through some scenarios where you might need to think about this.

Project tasks:

• Decide what data structures you want to use to keep track of the vertices (City) and/or edges (Transport) of a graph.
• Flesh out the TravelGraph class that implements IGraph<V,E>. You will use City as your V and Transport as your E. You may have to add additional methods for your TravelGraph beyond what is in IGraph! The design check walks you through thinking about this.

2. Creating Graphs from CSV Files

The contents of the graphs you will work with are given in pairs of CSV files. One file defines the cities, and another defines the transit options between them. Here are what those look like for the sample graph at the top of the handout:

data/cities1.csv

name
Boston
Providence
New York City

data/transport1.csv

origin,destination,type,price,duration
Boston,Providence,train,13,80
Boston,Providence,bus,7,150
Providence,Boston,train,13,80
Providence,Boston,bus,7,150
Boston,New York City,plane,267,50
New York City,Boston,plane,267,50
New York City,Providence,bus,40,225

Note: The first line of your cities file MUST be "name" and the first line of your transport file MUST be "origin,destination,type,price,duration". Our parser will not work if this is not the case

Creating a graph from the CSV files requires extracting the rows one at a time and using them to create vertices and edges in your data structures. The TravelCSVParser class that we provide does part of this work: it reads rows one at a time, turns each into a Map from column name (ex: "destination") to cell value (ex: "Providence"), then passes that row to a function that creates the vertex or edge data accordingly. This class uses a Java CSVParser library to transform the CSV information into Maps.

For instance, a Map for the 3rd row of data in the above transport1.csv file would look like this, with the first row representing the keys and the 2nd row representing the corresponding values:

"origin"	"destination"	"type"	"price"	"duration"
Providence	Boston	train	13	80

Specifically, TravelCSVParser provides two methods, one for reading each kind of file. Further details are provided in the header comments above the methods.

public void parseLocations(String locationFile, 
                           Function<Map<String, String>, Void> handleLoc) 
           throws IOException { ... }
           
public void parseTransportation(String transportationFile, 
                           Function<Map<String, String>, Void> handleTransport) 
           throws IOException { ... }

We have also provided a TransportType class that creates an enumerated type of known transportation types (BUS, TRAIN, PLANE). The following code converts a transit type string into an enumerated value:

TransportType.fromString(m.get("type"))

Project Tasks:

• Understand our example code that parses in the cities CSV file
• Plan out how reading in the information from a row of the transports CSV file should alter the data that is stored inside TravelGraph
• Write code to parse in the transports CSV file in TravelController

3. Implementing Route-Finding

To find the best route for the respective priorities, you will implement breadth-first search and Dijkstra's algorithm (both of which were covered in lecture). It is your job to figure out which algorithm is best fit for each of price, time, and directness. You will call the methods for these algorithms when appropriate in your ITravelController class to define the route-finding methods.

We have given you classes BFS and Dijkstra which implement the IBFS and IDijkstra interfaces, respectively. You can read about the methods for these classes in the Javadocs comments for IBFS and IDijkstra in the src directory.

Note that your implementation of Dijkstra's algorithm will require a PriorityQueue (or another data structure that stores things by priority). As a result, you will need to make a Comparator (refer to Lab 6 for how to do this). As this interface needs to be parameterized, you will need to consider what is being stored in your PriorityQueue and how it should be parametrized.

Note: Java's PriorityQueue does not automatically update when the priority of one of the vertices changes. As a result, if a vertex's priority changes, you must remove it and re-add it to the PriorityQueue.

Project Tasks:

• Implement breadth-first search in the getPath method of your BFS<V,E> class. We encourage you to use helper methods to make your code more readable!
  • Test your BFS extensively before moving on
• Implement Dijkstra's the getShortestPath method of you Dijkstra<V,E> class. Again, we encourage you to use helper methods!
  • Test your Dijkstra's extensively before moving on
• Call the appropriate methods inside of TravelPlanner.

Testing

For testing, we want you to:

1. identify interesting graph configurations to test
2. write a testing plan that describes these tests in brief prose, and
3. create JUnit tests to execute your plan. Your tests should use at least two graphs of your own (that are different from the ones we gave you).

You can (and should!) use the same graph for multiple individual tests (e.g., a fast route between two cities, a direct route between two different cites, etc).

A testing plan shows drawings of the graph to use for testing and a bulleted list of the cases to test in the graph and why. For example (again using our sample graph):

Testing Plan:

• Check for the fastest route from New York City to Providence because it requires taking a longer route
• …

You do not need to test every last method you wrote, but you should test the ones you deem critical. Even a small bit of testing can be a useful checkpoint on your work (and it can save you a lot of debugging time later).

Project tasks:

• Flesh out the testing plan you will have made for the design check to involve two separate graphs
• Create CSV files that represent the cities and transports of your two testing graphs
• Implement your tests in code in the following classes:
  • GraphTest.java
  • BFSTest.java
  • DijkstraTest.java

Design Check

There are four main goals for the design check: understanding the BFS and Dijkstra algorithms, understanding the starter code, considering the impacts of algorithm and design decisions, and planning the project.

Understanding the algorithms

Design Check Task: Work through an example of using Dijkstra's algorithm in the conceptual check Gradescope assignment. As you submit each question, Gradescope will tell you whether you are right or wrong, so that you can check your conception as you go. You can and should resubmit as many times as you need to. You may talk to your partner as you go through this task, but we expect both partners to submit (and get full points on) the assignment.

Design Check Task: Look at the example graph at the top of this handout and, by hand, compute BFS (assume neighbors are considered in alphabetical order) and Dijkstra (select an appropriate edge weight) for each of these routes (the first one is done for you, using cost as the edge weight):

Route	BFS route	Dijkstra route
NYC -> Boston	Plane(NYC -> Boston)	Bus(NYC -> Providence); Bus(Providence -> Boston)
NYC -> Providence
Boston -> Providence
Boston -> NYC
Providence -> Boston
Providence -> NYC

Design Check Task: Based on these results and your understanding of BFS/Dijkstra, identify which algorithm (BFS or Dijkstra) you should use for computing the:

1. Most direct route (route with fewest connections)
2. Fastest route
3. Cheapest route

Design Check Task: Because there are two algorithms and three priorities, you had to select the same algorithm for at least two of the goals (for example, at least two priorities need to be computed with Dijkstra, or at least two priorities need to be computed with BFS). Identify how the application of the algorithm changes for the two priorities. (e.g. if you chose Dijkstra for two of the priorities, what would cause the algorithm to come up with one answer for one priority and a potentially different answer for a different priority?)

Understanding starter code

Design Check Task: Look through the starter code and draw a containment/association diagram of how the classes fit together. You can ignore Main and REPL. We have started this for you:

See the notes from Lecture 4 of the 111/17/19 track for an example of a containment/association diagram.

Design Check Task: Practice connecting concepts in this handout to the code by answering the following questions:

1. Where in the code (which class/methods) do you expect to have to choose between Dijkstra and BFS? What inputs do the Dijkstra/BFS methods take? What does that tell you about what you need in the code at the point that calls those methods?
2. Where in the stencil code did we provide you an example of using functions as objects? Hint: when we described using functions as objects, we said we wanted to use them in two places: reading in the CSVs and deciding on what edge weight to use. Code that is meant to do that will be a good place to look. You should find a Function object defined in the code and also find where that object is passed in as an argument to another method.

Design Check Task: Draw out the way the following method calls will affect fields in the TravelGraph class and related classes. This means that you'll have to decide on the field(s)/data structure(s) that are contained in this class.

Note: The point of this task is to get you thinking about the data that TravelGraph needs to keep track of, by thinking through specific use cases of the graph. You may find that, after working through this and the next questions, you need to change some decisions you made. This is fine and the expected point of these tasks!

TravelGraph tg = new TravelGraph();

tg.addVertex(new City("Providence"))
tg.addVertex(new City("Boston"))
tg.addVertex(new City("New York City"))
tg.addVertex(new City("Newport"))

Draw out exactly how each new City looks in the heap, what your proposed field(s) are for tg, and draw arrows to indicate where the contents of these fields sit on the heap

Design Check Task: Now consider adding transit routes to tg. Say your transport CSV contains the following lines:

​​​​Newport, Providence, 10, 65
​​​​Providence, Boston, 15, 83

One way to try to add these routes to tg would be using the following method calls:

newProvBus = new Transport(new City("Newport"), new City("Providence"), TransportType.BUS, 10, 65)
provBosBus = new Transport(new City("Providence"), new City("Boston"), TransportType.BUS, 15, 83)
tg.addEdge(new City("Newport"), newProvBus)
tg.addEdge(new City("Providence"), provBosBus)

Adding to the previous diagram, draw out exactly how each new City and new Transport looks in the heap, list what your proposed field(s) are for tg, and draw arrows to indicate where the contents of the fields in newProvBus, provBosBus and tg sit on the heap

Design Check Task: Assess your work. Does this drawing make sense (i.e. are data that are supposed to be related actually related in the correct way in this diagram)? Why or why not? Hint: would you be able to compute a route between Newport and Boston using your graph?

If the answer is no, propose new fields(s) (and what types/data structures they are) and method(s) in TravelGraph that connect the relevant objects in the correct ways. Revise the method calls that instantiate and add newProvBus and provBosBus to tg to use your new method(s).

Hint

How can you ensure that newProvBus and provBosBus both point to the same "Providence" City in the heap?

Design Check Task: Based on your answers above, draw an updated association/containment diagram of how you want your classes to fit together. Also list any new fields and methods that you are proposing for the TravelGraph class.

Considering the impacts of algorithm and design decisions

You may have noticed that path-finding algorithms like Dijkstra’s and the Travel Planner bear a striking resemblance to other software with maps and navigation like Google Maps, Uber, or DoorDash. In Travel Planner, we offer the user a set of choices upon which to prioritize (time, price, directness), but there are often scenarios where a programmer may want to pick one prioritization (or at least a default) to reflect the needs of the application or just for simplicity’s sake.

Here you will be answering a software engineering (SWE) interview style question! When most people think of SWE interview questions, they may imagine being asked coding questions like how to reverse a linked list. However, many companies also ask more design-oriented questions that look for your understanding of tradeoffs and how to design software. This question in particular is inspired by a platform used by Lyft for their interviews. Even if you do not intend to do SWE interviews, this exercise is useful for reasoning through how and why you might make certain design decisions and the pros and cons of your decisions.

Note: For all the tasks in this section, you and your partner should work together and submit one answer as a group.

Design Check Task: Read through these two possible design proposals below for a food delivery app (think DoorDash, Postmates, UberEats, etc.). This app will feature local restaurants that customers can order from and have their food delivered to them by the app’s drivers. These proposals outline two different options for how the app will decide which routes and directions to give to delivery drivers.

Design Check Task: Pick one of the above proposals and defend it! Why is your chosen proposal better than the other one? How will your proposal benefit the application? Are there any concerns you have about your chosen proposal? List at least three reasons why you think yours makes the most sense and at least two hesitancies or concerns you have.

Note: If your hestancies and concerns apply to the other proposal as well, that’s fine!

---

One exercise that can be helpful when evaluating design decisions is creating a list of stakeholders. Stakeholders are people or groups of people who have an interest in or are affected by a system’s existence, operation, design, and impacts.

For example, stakeholders in CS200 include those directly involved in the class day-to-day: the professors, students, and TAs. Stakeholders also include those that aren’t directly involved in the class: the university, future CS students, others in the CIT during CS200 debugging and conceptual hours, etc. This list is not exhaustive, but it should give you a more concrete sense of what we mean when we say “stakeholders”.

Design Check Task: Create a list of stakeholders in the food delivery app! It will be helpful to think about both those who are directly involved and those who are not directly involved. Who will interact with the app? Who might be impacted by the app? Who might care about how the app operates?

After you have created your list take a look at the one we have made! It’s likely that neither our list nor yours is exhaustive, but pay attention to any differences. Is there anything that we have on ours that you do not? Is there anything you thought of that we didn’t?

Important Note: Please do not update your stakeholder list after reading ours. You will not be graded on the “correctness” or length of your list. As long as you’ve come up with at least a few examples of stakeholders on your own, you will receive full credit.

Our Stakeholder List (Please Only View After Coming Up With Your Own!)

• Drivers
• Drivers of competitor apps
• Non-automotive delivery people (e.g. people delivering on bikes)
• People ordering food
• Restaurants on the app
• Restaurants not on the app
• Restaurant Owners
• Restaurant Workers
  • Waiters/Waitresses
  • Cooks
  • Hostess/Cashier
• Non-app patrons dining at or ordering from the restaurants
• Software Engineers who designed the app
• Shareholders in the food delivery app
• Executives of the food delivery app
• Customer service representatives of the app
• Other people driving on the roads when order volume is high
• Pedestrians at intersections
• Residents of the neighborhood
• Owners/landlords of retail space in the neighborhood

Design Check Task: Write about any differences you observed between your stakeholder list and ours. Why might you or we not have thought of certain stakeholders? Are there any on the list that surprised you? Are there any you don’t understand or disagree with?

---

Often when we talk about prioritization and tradeoffs in programming we are also talking about stakeholders. Different design choices will almost always favor some stakeholders over others. This question of who to prioritize becomes even more complex when we consider power dynamics between stakeholders. Here we’ll define power dynamics as how different people or groups of people interact when one of them has more power than the other or power over the other.

Going back to our CS200 example, select a few stakeholders from the list and for each consider the power dynamics between them and the other stakeholders. Do any have direct power over the others? Who has more control over the existence, operation, and design of the course? You don’t need to write anything down for this, but do take a moment to discuss with your partner how these power dynamics could affect whose needs or wants are prioritized.

Design Check Task: Now that you have learned about stakeholders and power dynamics, return to the proposal you chose for the food delivery app’s routing and directions algorithm.

Which stakeholders does your chosen proposal prioritize? What role might power dynamics between stakeholders play in choosing what the routing and directions algorithm prioritizes? Are there any stakeholders who would be unhappy with both proposals? What kind of harm or social costs comes with these prioritizations?

Please write a reflection of at least 8-10 sentences considering the questions above.

Hint

If you can’t think of who may be harmed, consider what could happen if our algorithm determines that a particular street is almost always included in the optimal path.

Planning the project

Design Check Task: We have shown you how to read in the cities CSV in the code. Based on this example, propose a method call and helper function object that will help you read in the transports CSV and add the relevant transports to the graph (it might help to think through the design decisions you made above for adding the Newport-Providence and Providence-Boston bus routes).

Design Check Task: Take a look at the DFS code we wrote in class (3/9 lecture). What needs to change in this code to write a BFS implementation that takes in an IGraph? What data do you need to track at each step of BFS in order to make sure you're returning the correct output?

Hint

The code we wrote in class only tracked vertices, but in this project, we have both vertex (City) and edge (Transit) classes. How does that change the code we wrote in class? Think about the purpose of each step in the code, and think about how you will have to adapt it here.

In particular, think about the way we kept track of the path we went down for BFS/DFS (3/11 lecture). This algorithm worked because we assumed one possible edge going from one vertex to another. Does it make sense to use a HashMap from vertices to vertices for Travel Planner, or do you need to store something else to get back the exact edges? How would you use your chosen data structure to get back the route? It may help to draw out a concrete example here, just like we prompted you in the 3/11 handout/notes.

Design Check Task: Similarly, take a look at the Dijkstra pseudocode from class (3/11 lecture). What needs to be fleshed out in this pseudocode to make it compatible with an IGraph? What data do you need to track at each step of the algorithm in order to make sure you're returning the correct output?

Hint

Think through the way you select an edge weight to compute on. How exactly will you use Function objects and comparators here?

Design Check Task: Draw a small example graph and write out a testing plan for it, writing down the rationale for each test case as explained in the Testing section, above.

Note: While we are only requiring you to draw one example graph for the design check, we encourage you to draw a second one so that you can talk through it with your TA.

Please hand in your design check in the Project 2 - Design Check assignment in Gradescope before your design check.

Final Handin

Submit your final handin via Gradescope. Instructions on how to do so can be found in the Handing in Guide. When submitting with a partner, only one of you should submit the assignment and add your partner to the submission on Gradescope.

Make sure you submit your entire sol and test folders, which should contain your implementation and your tests. Specifically, sol must contain:

• BFS.java
• Dijkstra.java
• TravelController.java
• TravelGraph.java

and test must contain:

• GraphTest.java
• BFSTest.java
• DijkstraTest.java

If you write your own classes (which aren't in the stencil code), you must put those in sol as well.

Also, be sure to submit a .pdf of your testing plan along with the above files, as well as any custom .csv files you may have created.

Vocabulary

Segment: One section (edge/Transport) of a route. For example, if you go from New York City to Boston through Providence, there would be two segments, one from New York City to Providence, and one from Providence to Boston.

Source (of a segment): the city where the segment originates. For example, for the segment from Boston to Providence, Boston is the source.

Destination (of a segment): the city where the segment leads. For example, for the segment from Boston to Providence, Providence is the destination.

Route: An ordered sequence of segments, where the destination of one segment is the source of the subsequent segment. Saying "a route from New York to Providence" means that the first segment's source is New York and the last segment's destination is Providence.

FAQ

• What should I do first? You should start by thinking through the data structures and methods that you will need for your TravelGraph. The design check provides a starting point, and we have provided you with the SimpleEdge, SimpleVertex, and SimpleGraph classes in test/simple. You can use these classes to test your graph design before setting up CSV parsing. Make sure your graph construction is working the way you expect it to before moving on!

• Why does the ITravelController load method return a String? When using a REPL, all printing should be done within the actual REPL. Within the REPL code we provide, the load method you will override will be called, and the response that is returned will be printed. Therefore, you do not need to worry about printing at all, and instead, just return the response (whether that be an error or success message). The REPL also is in charge of transforming the paths that you compute in the other ITravelController methods to a string, so you never need to worry about formatting/printing your paths.

• Do I need to edit the files in the src folder? Nope! For all of the interfaces provided, you will need to flesh out classes that implement these interfaces and override all of the declared methods. REPL.java, TravelCSVParser.java, City.java, and Transport.java are fully written for you, but it might be helpful to take a look at the methods in these classes, as some of them will be useful to you when coding your project. Lastly, TransportType.java defines a helpful enum that you may use to represent the different types of transportation.

• For Dijkstra's, how does the PriorityQueue know how to order the vertices? The Java PriorityQueue class has a constructor that takes in a Comparator. Refer to the Comparators lab for a detailed example of how to define and pass in a comparator to be used in a PriorityQueue.

• How do I make the same algorithms work for different ways of determining edge weights? You want to be able to calculate paths based on price, speed, and number of connections, but you don't want to have to write more than one Dijkstra's/BFS method just because you need to use different methods of determining edge weights. A great solution is using Java Functions (see more in the sections above about Functions). You can write different Functions that get an edge's weight using different fields (price, time, etc.) and then pass the functions into your algo methods. This way, you can reuse the same methods for your different tasks.

• The autograder is failing but the program is working on my computer! Help! Make sure you haven't edited any of the files in the src folder, and make sure that you've implemented ALL methods from all of the provided interfaces in the classes you write. If you've done this and the autograder is failing to run but you think it should work, post on Ed / come to hours.

---

Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the anonymous feedback form.