<style>h3{border-bottom: 3px solid black} section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; } section.design { background-color: oklch(95% 0.01 180); border: 1px solid oklch(80% 0.01 180); color: oklch(40% 0.024 290); } section.idetails { background-color: oklch(95% 0.01 350); border: 1px solid oklch(80% 0.01 350); color: oklch(40% 0.024 290); } summary { text-decoration: underline; } summary:hover { font-weight: bold; } </style> # **Project 2: Travel Planner** 🚀 💫 **Gearup:** [Recording](https://drive.google.com/file/d/1Khd919vSTL9gRbS3jzwsGcwPebM2I9Kh/view?usp=sharing) + [Slides](https://docs.google.com/presentation/d/1VomO-9tHV5b0Vl2lQy1Qp9eYL9GnVfUa1nnZgWEUyzQ/edit?usp=sharing) **[Design checks](#Design-check)**: Wednesday, October 25 - Friday, October 27 **Final turn-in: Friday, November 3 at 11:59pm** :::danger **Looking for a stencil link?** See [here](#Stencil-Code)! You should wait to accept the assignment until after you have received your partner assignment. We will post an announcement on Ed once these emails have been sent out, so you can be sure you won't miss it. ::: :::warning **Important**: **This project involves using Dijkstra's algorithm, which we will cover in class on Monday, October 23.** If you want to get started and learn more about how this part works before Monday, see [this section](#Graph-algorithm-resources), which contains resources and notes (including a whole lecture recording) on how it works. ::: # Overview In this project, you will be designing a system that will allow a user to [plan](https://youtu.be/j0GZ3qSV9s0?t=78) travel routes that meet their needs. 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 - Working with complicated interactions between classes ## Style expectations For this and all future assignments, we expect your code to conform to the [CS200 Java Style Guide](https://docs.cs200.io/java-style-guide). # Grading This project will be graded as follows: - **Design check (30%)**: The design check includes the conceptual assignment (autograded so that you can check yourself), the written assignment (which includes SRC and design tasks and will be manually graded), and the design check meeting (graded on good-effort attendance). - **Implementation (Autograded) (35%)**: We will run autograder tests on your implementation. Due to the somewhat open-ended nature of the assignment, there is no wheat/chaff grading for testing.  - **Style checks (Autograded) (5%)**: We will check your code to ensure it complies with our <a href ="https://docs.cs200.io/java-style-guide"><b> Java style guide</b></a>, most especially on following our conventions for method naming and including Javadocs.  <b>Note</b>: On Gradescope, this part is counted with the autograder score for implementation. - **Design, testing, and code structure (30%)**: The TAs will manually grade your work according to some rubrics. To earn the points for this part of the project score: - Follow the design considerations for every task - Follow good OO design practices (i.e. if a computation is being done on the data that belongs to a certain class, that computation should be done in methods inside of that class) - Write thorough unit tests for each public method - Create and use your own datasets for system testing # Background In lecture, we 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. :::success ### How to read this handout (and how to get started) Like with Decision Tree, this handout is pretty long and contains a lot of information, but **you don't need to use or understand it all on your first reading**. Here's how to navigate the remainder of this document: 1. The [Travel graphs](#Travel-graphs-a-concrete-example) section outlines what we mean by a "travel graph" and how to use it to search for different routes 2. The [Stencil code](#Stencil-code-and-project-design) section describes how the stencil code is set up and what it will look like when you run the code. 3. The [Implementation details](#Implementation-Details) section breaks down the details of what you need to do in each part of the assignment. Each section has a summary of the most important tasks. 5. The [Design check](#Design-check) section has the set of tasks you'll need to complete for the design check The remaining sections have extra resources to consult as needed (how to hand in, FAQs, etc.)--see the table of contents for more info. **To get started, and to prepare for your design check**, read [Travel graphs](#Travel-graphs-a-concrete-example) in detail, then **skim over** the [Stencil code](#Stencil-code-and-project-design) and [Implementation details](#Implementation-Details) sections to get a sense of what you're going to need to do. Then, get started on the [Design check](#Design-check). ::: # Travel graphs: a concrete example Here's what a travel graph will look like. Let’s say you have the following route data:  **Let's break down what's in this graph**: - 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. :::success <details> <summary><b>Here’s an example of what the interface looks like for a user to load a graph and request a (fast) route.</b></summary> 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 </details> ::: 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. # Stencil code and project design The classes for this project are organized in 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 <!-- :::danger **Looking for a stancil link?** We will send a personalized link for you to clone the stencil when we assign your partner. Look for an email with 24-48 hours after the project is released--we will post an announcement on Ed after these emails have been sent, so you can be sure you won't miss it. ::: --> Once you receive your partner assignments, **[clone the stencil](https://classroom.github.com/a/7BE5sSdX)** from Github Classroom and create/join a team named as `[partner 1 brown login]-[partner 2 brown login]`. For instructions on how to download the stencil and set it up in IntelliJ, see our [Stencil Setup Guide](https://docs.cs200.io/s/java-stencil-setup-guide). <!-- **Please read:** If you have not received a partner assignment within a day of the project release date (Friday, October 20), please reach out to us via Ed or email (cs0200headtas\@lists.cs.brown.edu) ASAP! If you didn’t fill out the partner form, you probably weren’t assigned a partner: please fill out the form, and then reach out! --> #### Code overview Here's an overview of the files in the stencil code: <details><summary>Click to expand</summary> :::warning **There are a lot of files here, but don't worry!** The [Design check](#Design-check) is set up to help you get familiar with them step-by-step. ::: In the `src` directory: - An `IEdge` interface with methods one might use for the edges of a graph - An `IVertex` interface with methods one might use for the  vertices of a graph - An `ITransport` interface with methods to get information about the transport cost, time, and type - 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 `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 - A `Visualizer` class which uses your TravelController to parse CSV files and visualize them In the `sol` directory (initially): - 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 - A `City` class that you will use to represent the vertices of your graph. This implements `IVertex` - A `Transport` class that you will use to represent the edges of your graph. This implements `IEdge` and `ITransport`. In the `test` directory: - 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 Additionally, **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.** #### Extra testing resources The `test` directory also contains a directory called `simple` which has some basic classes for a vertex, edge, and graph, including: - A `SimpleVertex` class that represents a simple vertex - A `SimpleEdge` class that represents a simple edge - A `SimpleGraph` class that represents simple graph These don’t have the city and transit details, which may help as you build tests. **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.** </details> ## 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. # Implementation Details There are three major programming steps, each detailed in its own labeled section below. ### 1. Choosing Data Structures and Classes for Graphs As we discussed in class, Graphs can be represented and stored with a variety of built-in data structures (`LinkedList`s, `ArrayList`s, `Map`s, 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. :::info <details><summary><b>Note:</b> 'City'</summary> 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. </details> ::: <section class="idetails"> <br> **In this part, you will:** - Decide what data structures you want to use to keep track of the vertices (`City`) and/or edges (`Transport`) of a graph - Write tests for `City` and `Transport` while implementing those classes - 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`!  </section> The [design check](#Design-check) is designed to help you get started on making these decisions and thinking through the implementation. ### 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. :::info <details><summary>Here are what those look like for the sample graph at the top of the handout:</summary> **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 </details> ::: :::warning **_Warning:_** 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. :::info <details> <summary><b>Important Details</b></summary> 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")) ``` </details> ::: <section class="idetails"> <br> **In this part, you will:** - 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 </section> ### 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. <section class="idetails"> <br> **In this part, you will:** - 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 the `getShortestPath` method of your `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`. </section> 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. As a result, you will need to make a `Comparator` (refer to Lab 5 for how to do this). :::warning **_Warning:_** 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. ::: ## Testing For testing, you should: 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): > *"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). :::success **How to think about testing**: Just like you’ve been doing for the assignments up to this point, you should write tests as you go, to avoid debugging a big piece of untested code. You should write your testing plan with incremental, test-driven development in mind, so that, as you’re working on your project, you can finish one step of the testing plan and debug the corresponding code before moving to the next testing step and more development.  ::: :::warning **Important**: To help our TAs grade your tests, write detailed Javadocs for every test that you write, including: 1) the name of the method(s) that you are testing, and 2) a brief description of what your test is evaluating. This helps us when grading and is a good practice to help you think about what kinds of things you are testing! ::: <section class="idetails"> <br> **In this part, you will:** - 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 **as you code** the following classes: - `GraphTest.java` - `BFSTest.java` - `DijkstraTest.java` </section> ## Visualizer To help debug your project, we provide a `Visualizer` class in the `src/` directory. To use this Visualizer maker sure you have **completed writing** the `load` method in the TravelController class! To use the Visualizer set the `CITIES_FILEPATH` and `TRANSPORT_FILEPATH` to the path of the cities CSV and transport CSV you would like to parse. Set the `OUTPUT_FILEPATH` to where you’d like to save the output DOT file. Then, go to the [Travel Planner Vizualization website](https://brown-csci0200.github.io/TravelPlannerViz/) and drag-and-drop/open the output DOT file into the box to see your parsed graph! # 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. :::info **_Note:_** For the Design Check Tasks 1-\[letter], 2-\[letter], and 4-\[letter] that ask you to write something, put your answers in a document that you turn in in the Project 2 design check assignment on Gradescope. ::: ## Understanding the algorithms <section class="design"> ### **Design Check Task 1-A**: :::warning **This design check has you work through Dijkstra's algorithm, which we will cover Dijkstra's algorithm in class on Monday, October 23**. If you want to wait until then to get started, that's okay. Otherwise, take a look at [here](#Graph-algorithm-resources) for a list of resources on how Dijkstra's algorithm works (including a full lecture recording). ::: Work through an example of using Dijkstra’s algorithm in the conceptual check Gradescope assignment. Just like in Project 1, Gradescope will give you feedback about whether you are right or wrong, so you can resubmit as many times as 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. </section> <section class="design"> ### **Design Check Task 1-B**: 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 in the below table (the first one is done for you, using cost as the edge weight). Include a table like this in the document you hand in. | Route | BFS route | Dijkstra routes | | ------------------- | ---------------------- | --------------------------------------------------- | | NYC → Boston | 1. Plane(NYC → Boston) | 1. Bus(NYC → Providence)<br/>2. Bus(Providence → Boston) | | NYC → Providence | | | | Boston → Providence | | | | Boston → NYC | | | | Providence → Boston | | | | Providence → NYC | | | </section> <section class="design"> ### **Design Check Task 1-C**: Based on these results and your understanding of BFS/Dijkstra, write down the algorithm (BFS or Dijkstra) you should use for computing the: - Most direct route (route with fewest connections) - Fastest route - Cheapest route </section> <section class="design"> ### **Design Check Task 1-D**: 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). In writing, explain 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?) </section> ## Understanding the starter code <section class="design"> ### **Design Check Task 2-A**: Look through the starter code and draw a containment/association diagram of how the classes in the `src` and `sol` directories fit together. You can ignore `Main, TravelCSVParser,` and `REPL`. **While you do not have to draw out how the** `SimpleGraph` **and related classes in the test directory fit together, we _highly_ encourage you to examine these classes to see how the interfaces are implemented.** :::success **What to expect**: As you read the code, you might encounter some gnarly class definitions like this: ```java Dijkstra<V extends IVertex<E>, E extends IEdge<V>> implements IDijkstra<V, E> ``` <details><summary>What the heck does this even mean?! Click here to find out!</summary> Take a deep breath. It's going to be okay. Let’s break it down: You may notice that the `IEdge<V>` interface is parameterized with V, which means that an edge takes in the type of vertex it connects to. Similarly for `IVertex<E>`.Then you may notice that `IGraph` is written like `IGraph<V extends IVertex<E>, E extends IEdge<V>>`. It’s strange to use `extends` with an interface, but this is just a quirk of Java – it doesn’t let us use `implements` inside of generics, so we have to use `extends`. All this means is that `IGraph` has a generic parameter V that implements `IVertex<E>`, and a generic parameter E that implements `IEdge<V>`. The Dijkstra definition above just takes that idea one step further. Because we have an `IGraph` as an input for one of the methods in `IDijkstra`, we need to let Java know that the V and E parameters it takes in are edges and vertices to enforce the compatibility of all of these types. </details> ::: :::info **_Reminder:_** See the notes from [Lecture 4](https://brown-csci0200.github.io/assets/lectures/04fp/04notes.pdf) of the 111/17/19 track for an example of a containment/association diagram. ::: </section> <section class="design"> ### **Design Check Task 2-B**: Practice connecting concepts in this handout to the code by answering the following questions in writing: **Question 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? **Question 2**: In this project, we'll use new Java feature that allows us to use functions as objects. **Take a look at the section [Using functions as objects in Java](#Concept-Functions-as-Arguments-in-Java)**, which provides some conceptual background. Then, look at the stencil code: **Where in the stencil code did we provide you an example of using functions as objects?** :::success <details><summary><b>Hint</b></summary> 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, including the testing code we give you, will be a good place to look. Locate where the Function objects are defined in the code and also find where those objects are passed in as an argument to another method. </details> ::: </details> </section> <section class="design"> ### **Design Check Task 2-C**: Draw out a memory diagram for the following code. This means that you’ll have to decide on the field(s)/data structure(s) that are contained in `TravelGraph`, `City`, and any related class(es).  :::warning **Warning**: 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 okay--and it's the expected point of these tasks!** </details> ::: ```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")) ``` **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.** <details> <summary><b>More Information!</b></summary> One of the reasons that we set up the code in the way above (without naming variables for the `City` objects that we add to the graph) is because, for this project, you build the graph in two stages: one where you read in the cities file and add the `City` objects (like above), and one where you add transit routes. The next tasks guide you towards a helper method to help you connect the data from each step. </details> </section> <section class="design"> ### **Design Check Task 2-D**: 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 would be using these 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) ``` <br> 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. </section> <section class="design"> ### **Design Check Task 2-E**: 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? :::success <details><summary><b>Hint</b></summary> Would you be able to compute a route between Newport and Boston using your graph? </details> ::: 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 code that adds `newProvBus` and `provBosBus` to tg to use your new method(s). :::success <details><summary><b>Hint</b></summary> How can you ensure that `newProvBus` and `provBosBus` both point to the same “Providence” City in the heap? </details> ::: </section> <section class="design"> ### **Design Check Task 2-F**: 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`, `Transport`, and `City` classes. </section> ## Considering the impacts of algorithm and design decisions :::info **Note for submission:** Please submit responses to task **3-B, 3-C, 3-D, and 3-E** in a file called `written_responses.txt` or `written_responses.pdf` that you turn in to the Project 2 Design Check assignment on Gradescope. <br> **_Please do stick to the sentence limits in the following section. We are looking for concise answers that get to the point._**  ::: 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. :::info _Note: For all the tasks in this section, you and your partner should work together and submit one answer as a group._ ::: <section class="design"> ### **Design Check Task 3-A** 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.  </section> <section class="design"> ### **Design Check Task 3-B** Pick one of the above proposals and defend it! List three reasons why you think yours makes the most sense and at least two hesitancies or concerns you have. <details><summary><b>Hint</b></summary> Why is your chosen proposal better than the other one? How will your proposal benefit the application? Do you anticipate any shortcomings or scenarios where your proposal could create problems? :::info ***Note***: If your hesitancies and concerns apply to the other proposal as well, that’s fine! ::: </details> <br> </section> <section class="design"> ### **Design Check Task 3-C** :::info **Background**: 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”. ::: **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? (Include at least 4-5 people/groups of people in your list ). <details><summary><b>Expand this after you have created your list</b></summary> 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? <br> :::warning _Important Note: Please_ **_do not_** _make or 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._ ::: :::success <details><summary><b>Our Stakeholder List</b> (Please Only View After Coming Up With Your Own!)</summary> - 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 </details> ::: </details> </section> <section class="design"> ### **Design Check Task 3-D** 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? Summarize in not more than three sentences. :::info <details> <summary><b>Info:</b> Power Dynamics</summary> 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. </details> ::: </section> <section class="design"> ### **Design Check Task 3-E** 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 8-10 sentences considering the questions above.  :::success <details><summary><b>Hint!</b></summary> 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. </details> ::: </section> ## Planning the Project <section class="design"> ### **Design Check Task 4-A** Draw a small example graph and create a cities CSV and a transport CSV file for it. Include these CSV files in your submission to the design check assignment on Gradescope. **_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. </section> <section class="design"> ### **Design Check Task 4-B** Referencing your example graph from 4-A, write out a testing plan, writing down the rationale for each test case as explained in the [Testing ](#Testing)section, above. </section> <section class="design"> ### **Design Check Task 4-C** We have given you code that reads in the cities CSV. 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). </section> <section class="design"> ### **Design Check Task 4-D** Take a look at the `DFS` code we wrote in class. 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? :::info <details><summary><b>Note:</b> Tracking both vertices and edges</summary> 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. 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 did in the [handout/notes](#Graph-algorithm-resources). </details> ::: </section> <section class="design"> ### **Design Check Task 4-E** Similarly, take a look at the [Dijkstra pseudocode](#Graph-algorithm-resources) from the 3/10 lecture notes. 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? :::success <details><summary><b>Hint</b></summary> Think through the way you select an edge weight to compute on. How exactly will you use Function objects and comparators here? </details> ::: </section> # Final Handin After you’ve done your design check, you should implement your project! :::info **_Note:_** The bulleted lists in every [Implementation Details](#Implementation-Details) sub-section should give you a starting to-do list of tasks ::: Submit your final handin via Gradescope. 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, from `sol`, you must hand in: - BFS.java - City.java - Dijkstra.java - Transport.java - TravelController.java - TravelGraph.java and from `test`, you must hand in: - GraphTest.java - BFSTest.java - DijkstraTest.java **If you write your own classes (which aren’t in the stencil code), you must hand those in as well. Also include your test files.** :::danger ## :rotating_light: :rotating_light: Important submission reminder :rotating_light: :rotating_light: When you do your final submission, **make sure that your submission lists both you and your partner** if you are submitting as a group. This makes sure we know which submission to grade, out of any previous submissions from you and your partner. To check this, one member of your team should do the following (only necessary for your **final** submission): 1. Open up your submission on gradescope 2. Select **"Group Members"** at the bottom, which should look like this:  4. Type in your partner's name and select them from the list Only one member of your group needs to do this, and **you can do it after the deadline without being marked late**. **Please** be sure do to this, as it saves us a lot of time when grading and helps us get your grades back faster! :smile: ::: # Important resources ## Graph algorithm resources Take a look at the following links **We will cover Dijkstra's algorithm in class on Monday, October 23**. Until then, you can refer to the following notes and resources to learn how it works: - The **[lecture 19 handout](https://docs.google.com/document/d/196-TbKhFHkWOeh7ktBnjVgZ7Vr6yFXoAUp_bASfMKeo/edit?usp=sharing)** has templates for you to work through the algorithms as you watch the lecture recordings, as well as pesudocode - The **[lecture 19 class notes](https://brown-csci0200.github.io/assets/lectures/19dijkstra/Lec19_whiteboard.pdf)** have worked-out examples for BFS and DFS, as well as extra notes on Dijkstra's algorithm - The **[typed lecture notes from lecture 19](https://brown-csci0200.github.io/assets/lectures/19dijkstra/lec19bfsdijkstra_notes.pdf)** provide a detailed description of how Dijkstra's algorithm works. **Section 2.1 of this document has pseudocode for Dijkstra's algorithm.** - This **[lecture recording from last year](https://brown.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=55380f55-3973-4fd2-a7f1-b0a200e7c9c4)** steps through Dijkstra's algorithm in detail and talks about how it compares to BFS and DFS. Our lecture on 10/23 will be similar to this. ## 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. ## Concept: Functions as Arguments in Java :::success In two parts of the project, you will need to use Java's `Function` objects to pass functions as arguments, which help you customize your code to perform different functions. You will use this to tailoring edge weights in Dijkstra’s algorithm and building your graph using the CSV parser. **This section provides an overview of how to use `Function` objects in Java and when and why they're useful--read this section when you get to these parts!** ::: 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 Dijkstra'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 (for those of you who took CS15, we saw a very simple introduction of this concept when we used predicates for map and filter during the first two weeks of this course). How do we do this in Java? <details> <summary>Expand for details</summary> 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)); // prints false } } ``` 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). Again, this is similar to lambdas in Pyret and Racket. An important exception to this rule is when you are writing a Function whose return type is `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).**  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 _do_ need to include an explicit return**): ```java Function <String, Boolean> isShort = str -> { len = str.length(); return len < 5; }; System.out.println(isShort.apply("functional")); // prints false ``` 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 import java.util.function.Function; public Boolean testWithEight(Function<Integer, Boolean> checker) { return checker.apply(8); } System.out.println(testWithEight(num -> num == 5)); // prints false ``` To summarize: - If the body of your function takes multiple lines, you need to surround it in curly braces and include an explicit `return` at the end - If the body of your function has a return type of `void`, you need to surround it in curly braces and include an explicit `return` null at the end - Otherwise (if the body of your function is a single-line expression and returns something), you do not need to surround it in curly braces and you should not have a return at the end </details> # FAQ This section contains frequently-asked questions we have received in past versions of this assignment. For more FAQs, see the FAQ for this project on Ed. #### 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. See [this section](#Concept-Functions-as-Arguments-in-Java) for more info on how to use function objects. #### 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.