Looking for Help with Assignments?
-RUCats has 80 hours of tutoring available online and in-person. Check the tutoring tab in Canvas!
-Instructors and Lead TAs have a combined 10 hours of Office Hours, open to all sections. See times/locations here.
-Piazza (found in the Canvas sidebar) provides fast support from Course Staff and other Students. Be sure to search to see if someone has asked a similar question!
-If you need a computer to complete work on, iLab machines can be found in the CSL (Hill 252) and surrounding rooms.
RUMaps – 100 course points
This assignment will take MORE time to complete than previous assignments.
Start your assignment early! You need time to understand the assignment and to answer the many questions that will arise as you read the description and the code provided. You CANNOT use a token on this assignment; plan to submit early.
Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.
- See this video on how to import the project into VSCode and how to submit into Autolab.
The assignment has two components:
- Coding (97 points) submitted through Autolab.
- Reflection (3 points) submitted through a form.
- Submit the reflection AFTER you have completed the coding component.
- Be sure to sign in with your RU credentials! (netid@scarletmail.rutgers.edu)
- You cannot resubmit reflections but you can edit your responses before the deadline by clicking the Google Form link, signing in with their netid, and selecting “Edit your response”
Overview
You will design a navigation system to model the street layout of Rutgers-New Brunswick. You’ll work with intersections where two streets intersect, as well as blocks which are parts of streets that lead to some intersection, and you’ll create an adjacency list in order to represent the relationships between blocks and their intersections.
We will be using an adjacency list implementation of an undirected graph (for any edge a -> b, we also have an edge b -> a). Moreover, edges have various associated attributes, including names and traffic.
- Intersections are our vertices; they connect blocks or lead to an end. Intersections are stored within a parallel array of Intersection objects.
- Blocks are edges that lead to one (or two) intersections; in the real world, they are city blocks or are part of larger roads. Blocks are stored inside an array of linked lists called adj[], where adj[i] is the reference to the front of a linked list.
- NOTE: this structure differs from what you’ve seen in class. You can search for a vertex in the intersections array, and then access adj[i] to access its incident edges (stored in a linked list).
Implementation
Overview of files provided
- Driver.java is used to test your methods interactively. Follow the prompts in the terminal to use the driver. Feel free to edit this file, as it is provided only to help you test your code. It is not submitted and it is not used to grade your code. Do not submit to Autolab.
- MapPanel.java: Provides visuals and updates information upon user interaction. Do not submit to Autolab.
- RUMaps.java: The RUMaps class contains all methods needed to represent the Rutgers steet network and return any relevant information. Edit the empty methods with your solution, but DO NOT edit the provided ones or the method signatures of any method. You will submit this file to Autolab.
- Coordinate.java: Cartesian coordinates (x, y). Used to keep track of the points where blocks and intersections lie. Intersections are defined by a single coordinate; blocks are defined by a list of Coordinates representing points. Don’t edit or submit to Autolab.
- Block.java: The edges of the graph. Represents a street block. Made up of mutiple coordinates/points that make a path. Don’t edit or submit to Autolab.
- path – for GUI/driver
- points – list of coordinates making the block
- roadSize – width of the block (purely for GUI/driver)
- firstEndpoint – starting (can also be considered end) point of the block
- lastEndpoint – ending (can also be considered start) point of the block
- length – length of the block
- trafficFactor – traffic factor of the block
- traffic – traffic of the block
- streetName – name of the street block is on
- blockNumber – number of the block
- next – a reference to the next node this block points to
- copy() – this method creates a deep copy of the block and returns a new Block object with the same attributes.
- other(Intersection intersection) – finds the other intersection of a Block.
- Intersection.java: The vertices/nodes of the graph. Represents an intersection between 2 or more streets or the end of a street.. Do not edit or submit to Autolab.
- Stores a coordinate – location of the intersection on the map.
- Network.java: The map/graph itself. Contains all the information needed to set up a graph and initialize vertices and edges. Don’t edit or submit to Autolab.
- Instance variables:
- intersections: stores an array of vertices.
- adj: stores ONLY the edges for a vertex, whose index is given by its position in the intersections array
- nextIndex: stores the next index at which you can add an intersection, used by the addIntersection method
- Methods:
- findIntersection method: returns the index of an intersection, given its x, y coordinates.
- adj(index) method: returns the edges incident to a vertex, given the index of an intersection
- addEdge method: adds a Block to the END of the list whose index is given in parameters.
- Instance variables:
- StdIn (to handle input and reading files), StdOut (to handle printing output), and StdRandom (to create random variables). Neither of these classes should be edited or submitted.
- Busch/AllCampuses.in: The data to construct the Rutgers Network — the blocks that make up the streets, and the coordinates that make up the blocks. More information on how to read this file is provided below.
- Busch.in is a smaller file that only has Busch campus. It has 29 vertices.
- AllCampuses.in is a larger input file that covers all campuses, and it has 120 vertices.
RUMaps.java
- DO NOT add new import statements; you may only use packages in java.util.*.
- DO NOT change any of the method’s signatures.
RUMaps constructor (provided)
This constructor initializes a MapPanel (so that the driver can reference your solution), and reads the number of intersections and streets, followed by a newline.
Then, it initializes a Network with the mapPanel and number of intersections, then calls initializeBlocks and initializeIntersections to create blocks + intersections from those blocks. Finally, it initializes block lengths, traffic factors, and block traffic for each block.
The constructor is designed to work incrementally to make the driver work – the driver won’t work in full until you implement both initializeBlocks AND initializeIntersections. Then, for additional features like pathfinding, you’ll have to implement the latter methods.
IMPORTANT, before you submit: make sure that lines 30-32 of the constructor contain “ptr” instead of “block” in parameters.
Methods to be implemented by you: (look below for provided methods + helpful Java classes)
1. initializeBlocks
Submit RUMaps.java with this method AND initializeIntersections completed under early submission to receive extra credit. We will not make exceptions if you forget to implement initializeIntersections.
The initializeBlocks method reads street and block data from the file parameter provided and initializes and returns an ArrayList of Blocks. course’s academic integrity
Here’s how to implement this method – the input file format is specified after these steps:
- Create an ArrayList of blocks.
- For each street:
- Read the street name and its number of blocks.
- For each block:
- Read its block number (as an int), number of points (as an int), and road size (as a double), and initialize a Block object.
- For each point, read its x and y coordinates and create a new Coordinate object. If this is the first point, call block.startPoint on the coordinate; if it’s not, call block.nextPoint on the coordinate.
- If StdIn.readInt is followed by StdIn.readLine, read the remaining newline character (as .readInt() leaves trailing newline characters unread).
- Then, add the block to the resulting blocks ArrayList.
- Return the ArrayList of blocks that now stores all blocks you read from the input file.
The input file is formatted as follows:
- One line containing the number of intersections (this is read for you in the constructor)
- One line containing the number of streets (this is read for you in the constructor).
- For each street:
- One line containing the street name (may contain spaces, as a string).
- One line containing the number of blocks (as an int).
- For each block:
- One line containing the block number (as an int)
- One line containing the number of points (as an int)
- One line containing the road size (as a double)
- For each point: One line containing an x and y coordinate (as integers, space-separated)
Later, we’ll examine each Block and then take start and end points to create a vertex.
The driver won’t work yet, so here’s what you can do to test this method:
- Write a JUnit test for this method and verify that:
- the size of this ArrayList is 34 for Busch.in (there are 34 incident edges)
- the block coordinate points and data match what you see below:
- Alternatively, you can use the debugger to verify the ArrayList size and the first few blocks (shown below for Busch.in. Place a breakpoint on the initializeBlocks line in the constructor, and then “step over” that line of code so that it executes. Then, take a look at the blocks list. You may have to hit an “eye” icon to make an object visible. Remember to run in Debug mode.
2. initializeIntersections
Submit RUMaps.java with initializeBlocks AND initializeIntersections completed under early submission to receive extra credit.
This method takes in the list of Blocks you created using initializeBlocks, and then for each block examines it to find its endpoints (where intersections lie). It then creates an intersection out of the endpoints. Pay attention to how we’re creating vertices and edges, as this logic differs from class. Rather than being given the vertices and edges, you’ll use Block endpoints to create vertices and edges themselves.
Here’s how to complete this method:
- For each block, grab its starting point (given in index 0 of its coordinate list), and its ending point (given in index (size – 1) of its coordinate list).
- Identify if an intersection exists for BOTH the start and end points: use the findIntersection method on your network instance and pass in the start and end coordinates. It’ll return its index.
- If the starting intersection doesn’t exist, create a new Intersection object with the starting coordinate and set the block’s first endpoint to the intersection. Then, add the intersection to the network.
- If the ending intersection doesn’t exist (if any), create a new Intersection object with the ending coordinate and set the block’s LAST endpoint to the intersection. Then, add the intersection to the network.
- If an intersection DOES exist, find the intersection in the intersections array and update its first (OR last) endpoint accordingly.
- Use the index of the intersections you just added (or found) to determine the index its edges should go into – you can use findIntersection to do this. USE the block.copy() method in order to create a deep copy of the current block.
- Block a stores an edge from first -> last.
- Block b stores an edge from last -> first. You should REVERSE the endpoints from block a.
- Then, call addEdge to 1) add block A to its corresponding index, and 2) add block B to its corresponding index. There are TWO calls to addEdge.
Here is the resulting graph for Busch.in:
Submit RUMaps.java with initializeBlocks AND initializeIntersections completed under early submission to receive extra credit. We will not make exceptions if you forget to implement initializeIntersections.
3. blockLength
In this method, you’re given a block, and you’ll need to find the total length of this block (in terms of distance). Do not simply calculate the distance between vertex0 and vertex1 as this won’t give you an accurate representation of the length of a block (apart from straight lines) – USE the coordinateDistance method which takes in two coordinate objects.
Grab the block’s coordinate points, and then iterate through each pair of points. Sum the distance between each pair.
Then, return the total length of this block. This will be given in the driver (shown below for Busch.in) when you hover over an edge, as seen below. Sutphen Road is to the left of SHI Stadium and intersects with River Road (which isn’t on this input file).
The block length for Sutphen Road using Busch.in is 108.06. Test this method by hovering hover the block – this particular block is located on the bottom near SHI Stadium.
4. reachableIntersections
This method uses a DFS from a given source intersection to find the order of all vertices visited, starting from (and including the source). You’ll return the order of all intersections visited inside an ArrayList of Intersections.
Order matters since DFS produces a specific ordering. Implement this method recursively as discussed in class; you can use helper methods to do so provided that they are private.
In the driver, select an intersection and you’ll be able to see a list of coordinates. Hover over the list to see it in full, as it’s truncated in the driver.
The expected intersections for Scarlet Knight Way are in the second image (for Busch.in; the first shows you where Scarlet Knight Way is). This is a connected graph, so ALL vertices must be reached.
(228, 256) -> (206, 303) -> (108, 341) -> (260, 274) -> (308, 254) -> (313, 275) -> (337, 256) -> (207, 334) -> (298, 164) -> (269, 127) -> (281, 116) -> (293, 111) -> (279, 106) -> (247, 94) -> (240, 112) -> (231, 124) -> (214, 117) -> (204, 113) -> (167, 158) -> (57, 196) -> (155, 85) -> (176, 52) -> (228, 86) -> (322, 115) -> (310, 74) -> (378, 102) -> (410, 117) -> (373, 141) -> (306, 242)
5. minimizeIntersections
In this method, you’ll use a BFS search to find a path from the source intersection to a target intersection.
Use the edgeTo array to store predecessors of each vertex, as discussed in class. edgeTo[source] should be null, as there is no cycle.
To get the path, you will follow an algorithm similar to quick-union’s find() method, chasing up from the target until the source is in your path. See below.
Reverse the path so that it starts from the source — you can use Collections.reverse(___) to do this since the path is an ArrayList. DO NOT use other methods to reverse the ArrayList, as they may not exist in Java 17 which Autolab uses.
v = target path = [] while v is not null: add v to path v = edgeTo[v]; reverse path to start from source
From Scarlet Knight Way to the leftmost Davidson Road (take a look at the highlighted blue intersections) using Busch.in, here’s the expected path (if you see purple and you’ve implemented fastestPath, uncheck the fastest path box):
The driver will show the incident edges you’ve crossed in order to get to this path (it’ll take the intersections you’ve gathered and then reconstruct the path). The output is below:
Scarlet Knight Way (Block 124) -> Scarlet Knight Way (Block 125) -> Frelinghuysen Rd (Block 135) -> Allison Rd (Block 136) -> Bevier Rd (Block 137) -> Davidson Rd (Block 144)
6. fastestPath
This method takes in two vertices – a start intersection and an end intersection – and uses Dijkstra’s shortest path algorithm to find a minimal-cost path from the start to the end. You will return a path of Intersections, and you’ll use traffic to extract the lowest-distance vertex.
This is a modification of BFS, but rather than just picking out vertices in the order we see them, we’re making a decision based on cost (in this case, traffic).
Break ties by picking the earlier vertex in the fringe. For this reason, it’s best to use an ArrayList to implement the fringe; DO NOT use an unordered structure like a HashSet or HashMap.
Here’s an overview of Dijkstra’s algorithm along with pseudocode. w(m, w) is given by edge weight (use traffic for weights). The following slide deck has examples, and you can watch a video that goes through these examples here.
Remember that the expected output of this method is an ArrayList of Intersections. Use the path construction algorithm from before to create your path. pred replaces edgeTo.
v = target
path = []
while v is not null:
add v to path
v = pred(v);
reverse path to start from source
From Scarlet Knight Way to the leftmost Davidson Road (take a look at the highlighted blue intersections) using Busch.in, here’s the expected path (if you see purple and red and you’ve implemented minimizeIntersections, uncheck the minimize intersections box):
Scarlet Knight Way (Block 124) -> Scarlet Knight Way (Block 125) -> Frelinghuysen Rd (Block 135) -> Allison Rd (Block 136) -> Bevier Rd (Block 137) -> Davidson Rd (Block 144) total 6 intersections
NOTE: Getting a different result with nine intersections? Check your constructor, make sure lines 30-32 pass in (ptr) instead of (block) in parameters.
7. pathInformation
In this method, you will be given a path of Intersections – we are going from intersection to intersection. However, this involves traversing an edge (which adds on traffic and length to this path).
For each pair of intersections on this incident path:
- Remember that we can find where an intersection lies by accessing its first and last points. You can then use the .adj method to traverse.
- Find the incident edge that matches where this intersection lies, and increment the total length and total traffic.
- You’ll return an array of 3 doubles: index 0 stores the total length, index 1 the total traffic divided by the total length, and index 2 the total traffic.
NOTE: Getting 435.52 in red and 445.46 in blue for block length? Check your constructor, make sure lines 30-32 pass in (ptr) instead of (block) in parameters.
Provided methods
DO NOT edit these methods.
coordinateDistance: PROVIDED
The coordinateDistance method calculates the Euclidean distance between two coordinates.
Euclidean distance formula:
blockTraffic(Block block): PROVIDED
The blockTraffic method returns the traffic experienced by a rider on any block. This is calculated by the product of the block’s length and its traffic factor.
blockTrafficFactor(Block block): PROVIDED
The blockTrafficFactor method calculates and returns a randomized traffic factor for the block based on a Gaussian (normal) distribution.
This method generates a random traffic factor to simulate varying traffic conditions for each block:
< 1 for good (faster) conditions
= 1 for normal conditions
> 1 for bad (slower) conditions
The traffic factor is generated with a Gaussian distribution centered at 1 and a standard deviation of 0.2. The traffic factor is capped between a minimum of 0.5 and a maximum of 1.5 to avoid extreme values
Helpful Java Classes
Queue implements a FIFO structure.
- You can initialize an empty Queue named “name” which holds objects of type “Type” with Queue<Type> name = new Queue<>();
- For example, a Queue of integers named “q” is initialized with Queue<Integer> q = new Queue<>();
- You can add a new element of type “Type” to the back of your Queue in O(1) time with name.enqueue(newElement);
- You can get and delete the element at the front of the queue with name.dequeue()
The following are helpful classes you can use from java.util.*.
An ArrayList is an ordered array-like structure with no size limit, as it automatically resizes.
- You can initialize an empty ArrayList named “name” which holds objects of type “Type” with ArrayList<Type> name = new ArrayList<>();
- For example, an ArrayList of integers named “arrList” is initialized with ArrayList<Integer> arrList = new ArrayList<>();
- You can add a new element of type “Type” to the end of your ArrayList in average case O(1) time with name.add(newElement);
- You can get the element at some index of your ArrayList in O(1) time with name.get(index);
- You can set some index to some new element in O(1) time with name.set(index, newElement);
- You can check if the ArrayList contains some element (returns a boolean) in O(n) time with name.contains(element)
HashMap is an unordered data structure which stores and retrieves key value pairs.
- You can initialize an empty HashMap named “name” that maps objects of type “Key” to objects of type “Value” with HashMap<Key, Value> name = new HashMap<>();
- For example, a HashMap named “map” which maps strings to integers is initialized with HashMap<String, Integer> map = new HashMap<>();
- You can add a new key value pair, or update an existing key with a new value in average case O(1) time with name.put(key, value);
- You can check if the HashMap contains some key in average case O(1) time (returns a boolean) with name.containsKey(key)
- You can check the value of some key in the HashMap in average case O(1) time with name.get(key)
- You can iterate over all the keys in the HashMap with for (Key key : name.keySet()) where Key is the type of keys in the HashMap.
LinkedList is an ordered data structure.
- You can initialize an empty LinkedList named “name” which holds objects of type “Type” with LinkedList<Type> name = new LinkedList();
- You can add an element to the end of your linked list with name.add(item); and to the front with name.addFirst(item).
- You can get items using name.get(index), name.getFirst(), or name.getLast(), to get an item at a specific index, first index, or last index respectively.
- name.remove() removes the first element from the list, name.remove(index); removes an item at a specific index.
Implementation Notes
- YOU MAY only update the methods with the WRITE YOUR CODE HERE line.
- COMMENT all print statements you have written from RUMaps.java
- DO NOT add any instance variables to the RUMaps class.
- DO NOT add any public methods to the RUMaps class.
- DO NOT add/rename the project or package statements.
- DO NOT change the class RUMaps name.
- YOU MAY add private methods to the RUMaps class.
- YOU MAY use any of the libraries provided in the zip file.
- DO NOT use System.exit()
VSCode Extensions
You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:
Importing VSCode Project
- Download RUMaps.zip from Autolab Attachments.
- Unzip the file by double clicking.
- Open VSCode
- Import the folder to a workspace through File > Open
Executing and Debugging
- You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
- How to debug your code
- If you choose the Terminal:
- first navigate to RUMaps directory/folder
- to compile: javac -d bin src/rumaps/*.java
- to execute: java -cp bin rumaps.Driver
- first navigate to RUMaps directory/folder
Before submission
COMMENT all printing statements you have written from RUMaps.java
Collaboration policy. Read our collaboration policy here.
Submitting the assignment. Submit RUMaps.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.
Getting help
If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.
- Find instructors office hours here
- Find tutors office hours on Canvas -> Tutoring
- Find head TAs office hours here
- In addition to office hours we have the CSL in Hill 252, a community space staffed with community managers who are undergraduate students further along the CS major to answer questions.
By Vian Miranda and Anna Lu