Project 2: Travel Planner

--- tags: projects, spr22 --- # Project 2: Travel Planner **Gear-up:** Sunday, March 13 at 3pm ET at [this link](https://brown.zoom.us/j/8258308411)! **Design Check:** March 14-16, 2022 **Due Date**: Thursday, March 24, 2022 at 11:59pm ET :::warning **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](https://youtu.be/C-dvTjK_07c?t=172)) to plan travel routes that meet their needs (though it's likely he's already [been there, done that](https://youtu.be/bTXJQ5ql5Fw?t=239)). 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. :::spoiler 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](https://hackmd.io/io7Gock2TZqC6UnBwpjP2w). ## 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. :::info **Note:** The end of each sub-section in the [Implementation Details](https://hackmd.io/FDY8JfHVRRWrg2st8T4lHg?view#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: ![](https://i.imgur.com/MMf582L.png) 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: ```java= 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`): ```java= 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: ```java= 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 ``` :::info **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](https://commons.apache.org/proper/commons-csv/apidocs/org/apache/commons/csv/CSVParser.html) 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. ```java= 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: ```java 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](https://hackmd.io/MTKTpCnhQrebbzKEvcSV9Q) 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](https://www.gradescope.com/courses/344946/assignments/1917574/). 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:  ![](https://i.imgur.com/7ahExfh.png)  :::warning See the [notes from Lecture 4 of the 111/17/19 track](https://brown-csci0200.github.io/assets/lectures/04fp/04notes.pdf) 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. :::warning **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! ::: ```java= 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")) ``` :::info 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: ```java= 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). :::spoiler Hint How can you ensure that `newProvBus` and `provBosBus` both point to the same "Providence" City in the heap? ::: <br> **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](https://byteboard.dev/) 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. ![](https://i.imgur.com/qgwSpU7.png?1) **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._ :::spoiler 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 ::: <br> **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. :::spoiler 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](https://brown-csci0200.github.io/assets/lectures/18dfsbfs/dfsbfs-notes.pdf) (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?  :::spoiler 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. ::: <br> **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? :::spoiler Hint Think through the way you select an edge weight to compute on. How exactly will you use `Function` objects and comparators here? ::: <br> **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. :::info **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. ::: :::success 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](https://hackmd.io/oTbF1IUuRs27VgVJF4z2rA). 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](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Comparator.html). 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 `Function`s (see more in the sections above about `Function`s). You can write different `Function`s 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](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*