Contents:
In this assignment, you will put the graph you designed in the graph homework to use by modeling the Marvel Comics universe. By trying out your Graph ADT in a client application, you will be able to test the usability of your design as well as the correctness, efficiency, and scalability of your implementation.
This application builds a graph containing thousands of nodes and edges. The size of the graph might expose
performance issues that weren't revealed by your unit tests on smaller graphs. With a well-designed
implementation, your program will run in a matter of seconds. Bugs or suboptimal data structures can increase
the runtime to anywhere from several minutes to 30 minutes or more. If this is the case, you may you will need to go back
and revisit your graph implementation from earlier. Remember that different graph representations have widely
varying time complexities for various operations and this, not a coding bug, may explain the slowness.
This Marvel dataset was also used by researchers at Cornell University, who published a research paper showing that the graph is strikingly similar to “real-life” social networks.
On top of this, you will start building a TypeScript version of the popular puzzle Connect the Dots using React. This part isn't related to any other parts of this assignment, but will help you in future assignments.
In this application, your graph models a social network among characters in Marvel comic books. Each node in the
graph represents a character, and an edge 〈Char1,Char2〉
indicates that Char1
appeared in a comic book that Char2
also appeared in. There should be a separate edge for every
comic book any two characters appear in, labeled with the name of the book. For example, if Zeus and Hercules
appeared in five issues of a given series, then Zeus would have five edges to Hercules, and Hercules would have
five edges to Zeus.
You will write a class MarvelPaths
(create the file yourself: MarvelPaths.java
)
that reads the Marvel data from a file (marvel.csv
), builds a graph, and finds paths between
characters in the graph.
As you complete this assignment, you may you will need to modify the implementation and/or the specification of your Graph
ADT. You are welcome to do this - you're not "locked in" to any of your previous decisions. We encourage you to
think carefully about any changes you might make, and use the same thought process you used when originally creating
your design to evaluate any potential changes.
Leave your graph in the graph
package where it was originally written, even if you modify it for
this assignment. There is no need to copy files nor duplicate code! You can just import
and use it
in this assignment. If you do modify your graph
code, be sure to commit those changes your
repository.
For the summer 2021 offering of the course, we will also provide you with an api that computes the shortest path between two superheros using the Breadth-first search (BFS) algorithm for part 3. Additionally, there is no part 5 for this offering of the course.
Before you get started, look at the file with the Marvel data: hw-marvel/src/main/resources/data/marvel.csv
.
A CSV (“comma-separated values”) file consists of human-readable data delineated by commas, and can be
opened in your favorite text editor, spreadsheet, or IntelliJ. Each line in marvel.csv
is of the
form
character,book
where character is the name of a character, book is the title of a comic book that the
character appeared in, and the two fields are separated by a comma (,
).
The first step in your program is to parse the provided csv files. We have provided a starter file
MarvelParser.java
and you must complete the implementation.
We've provided a helper method readLines
that returns a List<String>
where
each element in the list is one line of the file that has been opened. You can use this method to read in
the raw data in the file and then process it according to the format of the file. You'll need to complete
the implementation of parseData
to parse the data from the file into some useful data structure(s)
and return them to your main program (in MarvelPaths.java) to be assembled into your graph. We have provided a
CSV parser demo here to help you get started.
Note: When the readLines
method is called (such as in the provided code), we can just pass it the
simple filename of the file and it'll take care of looking in the correct directory (src/resources/data/).
For example: readLines("marvel.csv")
. If you write any parsing code elsewhere in this
course (this is unlikely for most students), you should write code similar to the
implementation of readLines
here to ensure that it works across projects/assignments and in
testing. See the comments in readLines
for more info.
The next step in your program is to construct your graph of the Marvel universe from a data file. Once you have
completed MarvelParser.parseData
, you need to convert the data from it into a Graph. This will be
specific to your implementation of a Graph, but most likely will involve looping through all the data returned
by the parser and calling methods on your Graph class(es) to construct nodes/edges and link them together
appropriately. Remember that, for each comic book relationship between Character A and Character B, there should
be two edges: one from Character A to Character B, and one the other way around, from Character B to Character
A.
Note: You should not create edges from a character to themself as part of this process.
At this point, it's a good idea to test the parsing and graph-building operation in isolation. Verify that your program builds the graph correctly before continuing by completing the relevant parts of Part 4.
The real meat of MarvelPaths
is the ability to find paths between two characters in the graph. Given
the name of two characters, MarvelPaths
should search for and return a path through the graph
connecting them. How the path is subsequently used, or the format in which it is printed out, depends on the
requirements of the particular application using MarvelPaths
, such as your test driver (see below).
Your program should return the shortest path found via breadth-first search (BFS). A BFS from node u to node v visits all of u's neighbors first, then all of u's neighbors' neighbors, then all of u's neighbors' neighbors' neighbors, and so on until v is found or all nodes with a path from u have been visited. For this offering of CSE331, we are providing you with a library containing a method that computes the shortest path using BFS for you. The BFS method provided to you handles the sorting feature for you. You just need to make sure not to re-sort the results in a different order. However, you should still be able to check whether the results returned to you is correct by writing appropriate and sufficient tests. You may reference section 6 material for the BFS algorithm.
Many character pairs will be connected by multiple shortest paths with the same length. For grading purposes, your program should return the lexicographically (alphabetically) least path. More precisely, it should pick the lexicographically first character at each next step in the path, and if those characters appear in several comic books together, it should print the lexicographically least title of a comic book that they both appear in. The library provided to you handles the sorting feature for you. You just need to make sure not to re-sort the results in a different order.
Because this search is specific to this particular application, you should implement your BFS wrapper method in
MarvelPaths
rather than directly in your graph, as other hypothetical applications that might need
BFS probably would not need this special ordering. Furthermore, other applications using the graph ADT might
need to use a different search algorithm, so we don't want to hard-code a particular search algorithm in the
graph ADT itself.
Using the full Marvel dataset, your program must be able to construct the graph and find a path in less than 30
seconds on attu. ScriptFileTests
, the provided class used to run your script tests, is set
to put a 30000 ms (30 second) timeout for each test. (For reference, the staff solution took around 5 seconds to
run on attu).
If your Graph ADT has a particularly thorough or expensive checkRep
function, it is possible that it
could take too long to load the Marvel dataset when all checks are performed. A good checkRep
function should include some way to disable particularly expensive checks by setting a compile-time or run-time
variable. You must disable the expensive checkRep
tests in the version you submit for
grading so it will pass all tests in the allotted time. It's recommended to simply disable the
entire checkRep
.
Here are the steps you need to take to implement our library:
StringGraphNeighbors
interface provided by us,
by adding implements StringGraphNeighbors
after
public class [your graph class name]
in your graph implementation. This will initially create
an error as IntelliJ will notice that you need to implement the outgoingEdges
method which is
missing from your class. You will address this in the next step.outgoingEdges
from the StringGraphNeighbors
interface using its
documentation. You may find the documentation under docs/javadoc/index.html
in your repository.
Note that you will have to translate the edges returned from your implementation to
be of type StringGraphNeighbors.Edge
Paths.shortestStringPath()
. Note that you will have to translate the edges returned from our
implementation back to edges in your implementation.Note that the above interfaces/classes/methods in our library have a sufficient documentation. As a part of this assignment you need to read and understand the documentation in order to figure out how you need to use the provided code in your implementation.
Because the Marvel graph contains thousands of nodes and hundreds of thousands of edges, you should not use it for correctness testing (such as ensuring that your code computes the correct path between two characters), because it will be too hard to determine the correct path in most cases. By contrast, the full data set is useful for scalability testing or to detect corner cases, after you have performed correctness testing using much smaller graphs that you create. Additionally, it is important to be able to test your parsing/graph-building and BFS operations in isolation and separately from each other. For these reasons, you should use a test driver to verify the correctness of both your parser and BFS algorithm on much smaller graphs.
Note: all of your hw-graph tests still exist, so there's no need to re-create any of those tests for hw-marvel. Your hw-marvel tests should be focused on the behavior your MarvelPaths (and related) code has.
You should write script tests using test scripts similar to those you wrote in the graph homework. The
format is defined in the test file format section below. In addition to
writing *.test
and *.expected
files as before, you will write *.csv
files
in the format defined for marvel.csv
to test your parser. All the
*.csv
files used for testing should be placed in the hw-marvel/src/main/resources/data
directory. Place your test scripts in hw-marvel/src/test/resources/testScripts/
.
You should create a class named MarvelTestDriver
that runs tests in the same way that GraphTestDriver
did. We have provided a starter file in hw-marvel/src/test/java/marvel/scriptTestRunner
with method
stubs and a small amount of starter code, but you can replace it. You may copy your
graph/src/test/java/graph/scriptTestRunner/GraphTestDriver.java
source file
to hw-marvel/src/test/java/marvel/scriptTestRunner/MarvelTestDriver.java
, change it to package
marvel.scriptTestRunner
, and revise it to match this assignment's file format
specification. This will cause duplicated code between the two assignments, but avoids some tricky issues
with subclassing (especially when trying to subclass test classes).
Your script tests will most likely cover the bulk of your testing. You may need to test additional
behaviors specific to your implementation, such as handling of edge cases. If so, write these tests in a regular
JUnit test class or classes in the marvel.junitTests
package. If your data fails to load in your
JUnit tests, see the File Paths section for information about resource files.
Be sure to run validation on attu with ./gradlew hw-marvel:validate
to verify that the data files
are still found successfully under the configuration in which we will run your tests. (And to make sure that
your test run in a reasonable amount of time.)
To run your tests, we recommend using the IntelliJ JUnit testing integration. Make sure you've set up your
IntelliJ to properly run tests using gradle - see the Editing/Compiling/Running/Testing handout for more setup
instructions. Once you've done so, you can right-click on any of your JUnit tests and choose "Run <filename>"
to run the tests in that file. To run all the tests in a folder, you can right click a folder and choose "Run
Tests in <folder>". The script tests (.test and .expected files) are run by ScriptFileTests
,
so right-click and run that file to run all of your script tests.
You can also always use the gradle hw-marvel:test
target in the gradle window to run all tests.
(Under cse331 > hw-marvel > Tasks > verification > test in the IntelliJ gradle window).
Please be extra sure that your IntelliJ is properly configured to use the gradle test runner before trying to run tests using any of these methods. (See the editing/compiling handout if you haven't already done this.) Running tests with the IntelliJ runner instead of the Gradle runner will likely result in "no tests found" when trying to run your script tests. This requires extra work to undo beyond just fixing the settings after the first test run, as IntelliJ will remember the original settings you had when you ran the tests the first time, even if you change them later. If you find yourself in this situation, please contact the staff for instructions on fixing IntelliJ so it will always use the Gradle runner.
This part is omitted for the summer 2021 offering of the class.
Do not implement a main method as it would prevent our validation scripts from performing correctly.A surprising number of students forget to do this part of the assignment. Please don't let that be you!
Add a main
method to MarvelPaths
that allows a user to interact with your program from
the command line (i.e., your code should read user input from System.in
). The program should read
pairs of character names and then print to the console the path between those two characters if any, or else
print a suitable message (your code should write to System.out
). There is no rigid specification
here for input or output formats, but especially creative ones may receive a small amount of extra credit.
At a minimum, your program should make it clear to the user how they are supposed to input the character names, and there should be some reasonable way to quit the program when they are done (that doesn't involve just crashing).
To run your program, a user would run the hw-marvel:runMarvel
gradle task. For this task in
particular, it is highly recommended that you run the gradle task using gradlew
from the command
line, as we've experienced bugs with IntelliJ's built-in grade task runner when reading input from System.in
.
Mac/Linux users should run the following from the IntelliJ Terminal window:
./gradlew hw-marvel:runMarvel
Windows users should run the following:
gradlew.bat hw-marvel:runMarvel
You will start writing a User Interface(UI) to let users run a version of a Connect the Dots drawing puzzle.
You will start writing the UI in *.tsx
files under hw-dots/src
. You may create additional
files as needed and may edit provided files. Each file may contain no more than a single React class/component.
Be sure to add any new files to your repository as you commit your changes. You may also add .ts
files if you choose to write any other code (i.e. helper functions) that aren't a part of a specific component.
(You aren't required to have separate .ts files if you don't want to.)
The interface provided by the staff has the following elements:
Much of the functionality in this starter code is only half-written, often with hard-coded values instead of actual interactivity. The code is full of unused variables and half-implemented functions for you to complete. For example, the “edges” text box currently can't be edited at all. It's your job to read and modify the provided code to complete the functionality of the application.
The starter code is half-written. This means you will need to add, change, or remove props, state, and functions in the components. You are not required to keep our existing code - please change it if you can think of a better design. Here is a demo you can reference when you are finishing this part of the assignment.
cd hw-dots npm install
It's not uncommon for this installation to take 15+ minutes, depending on the speed of your network connection
and your computer, so don't worry if it seems to be taking a while. You may get a few warnings and messages, but
nothing particularly tragic should be printed to the screen. You'll only need to do this installation once for
each place you have your repository cloned. To test your installation, run npm start
. This will run
your React application, which currently only has the starter code that we provided. When it's done starting up,
a browser window will automatically open the website.
If the browser didn't automatically open, or the wrong browser opened, you can manually navigate to http://localhost:3000
to view your site. Now that the React server is up and running, you can edit the code and the website will
auto-reload without you having to stop and re-start the React server. When you're done with development, you can
stop the running react server by clicking in the terminal window where it's running and pressing
Control-C
.
GridSizePicker
is able to be edited. The actual number that
was entered into the text box is stored in the state of App, in state.gridSize
. A string
version of it is passed down to be displayed by the GridSizePicker
through its
value
prop, and a callback function that updates the state is passed into the GridSizePicker
through the onChange
prop. Whenever the text field has a change, the
GridSizePicker
's onInputChange
method is called, which parses the text inside the
text field into an integer, then calls the onChange
function it got as a prop from
App
to tell it about the new data. (This is similar to the standard “fully-controlled
component”
model described in the Advanced User Interface section of the React handout.) The current value of the grid
size is also passed as a prop to Grid
, so it can be used when rendering the grid onto the
canvas. It's your job to make use of that information so the Grid
component automatically
changes the way it's displayed based on the current grid size.render
method in Grid
to make sure the “Current Grid
Size: X” text properly displays the current value of the gridSize
prop.getCoordinates
method in Grid
so that it dynamically calculates
the coordinates of all the points that need to be drawn by redraw
, and returns those
points in the same format as getCoordinates
already does. If the current
gridSize
is 5, it should return an array of 25 2-element arrays, each with an x and y
coordinate representing the location of one of the 25 points in a 5x5 grid. The exact spacing and
arrangement of the grid is your choice, but it should be centered, and fill a reasonable amount of
space on the image (i.e. not be tiny, but also fit completely within the canvas). Note that the
drawCircle
function already takes care of making the circles smaller or bigger
depending on how many there are, though you're welcome to modify this behavior if you have a better
idea. :)Grid
component should react (get it? React? :P) immediately to the changing text
field, no button presses or other user action should be required. (Understanding the React lifecycle
methods will be helpful here.) Note: Most students will not need to
modify their code after completing 2b to meet this requirement - this is just listed here to make
sure everyone understands what the requirements are for their final product.toString
on App's gridSize state.) For example, you could have a piece of state (a string) in GridSizePicker
that keeps track of the current string in the text box, and then use the App state to track the
current grid size, as it's already doing. That way, you could have App's current grid size be zero,
for example, while the GridSizePicker's displayed string is the empty string.Grid
component complete. We will finish the rest
of the UI in Part 2.
It can be tempting, when the TypeScript compiler is complaining about something, to simply add the
any
annotation to whatever is causing your problem to get the compiler to be quiet. There are
plenty of reasonable uses for any
, but you should always carefully evaluate whether you are simply
masking a bug before you use it.
For example, it's generally fine (in this course) to replace complex names that come from React or HTML with
any
to keep the code simple. There's a trade-off here - the code may be somewhat simpler, but (a)
you get less help from the TypeScript compiler, since it can't catch bugs that it can't see, and (b) you get
less help from IntelliJ, since it doesn't know what kind of object it's dealing with. It's up to you to make a
choice about what types you want to write out, and what types you'll leave as any
. TypeScript is a
tool - the more you use it, the more it will help you.
At a minimum, you should attempt to use explicit types for the following:
One note - some TypeScript compiler errors can be long or confusing. When you encounter errors like this, resist the urge to randomly change the code in the hopes that it will go away. By not understanding the error behind what you wrote, you are making yourself more likely to make the same mistake in the future, and you're robbing yourself the opportunity to understand why the compiler said what it said, and why the code that was there had a problem. When you're faced with an error you don't understand, here are some tips for figuring out what's going on:
The format of the test file is similar to the format described in the graph assignment. As before, the test driver manages a collection of named graphs and accepts commands for creating and operating on those graphs.
Each input file has one command per line, and each command consists of whitespace-separated words, the first of which is the command name and the remainder of which are arguments. Lines starting with # are considered comment lines and should be echoed (copied) to the output when running the test script. Lines that are blank should cause a blank line to be printed to the output.
The behavior of the testing driver on malformed input command files is not defined; you may assume the input files are well-formed.
In addition to all the same commands (and the same output) as in the graph assignment, the test driver for this homework accepts the following new commands:
LoadGraph graphName file.csv
Creates a new graph named graphName from file.csv, where file.csv is a data file of
the format defined for marvel.csv
and is located in the
src/main/resources/data/
directory of your project. The command's output is
loaded graph graphName
You may assume file.csv is well-formed; the behavior for malformed input files is not defined.
Filenames supplied to the LoadGraph command should be simple, meaning they do not include the directory
in which they are located. For example, marvel.csv
is a simple filename; src/main/resources/data/marvel.csv
is not.
FindPath graphName Char_1 Char_N
Find the shortest path from Char_1 to Char_2 in the graph using your breadth-first search algorithm.
Paths should be chosen using the lexicographic ordering described in Part 3. If a path is found, the command prints the path in the format:
path from CHAR_1 to CHAR_N: CHAR_1 to CHAR_2 via BOOK 1 CHAR_2 to CHAR_3 via BOOK 2 ... CHAR_N-1 to CHAR_N via BOOK N-1
where CHAR_1 is the first node listed in the arguments to FindPath, CHAR_N is the second node listed in the arguments, and BOOK K is the title of a book that CHAR_K and CHAR_K+1 appeared in.
It is possible that given two character names there is no path in the data between them. If the user gives two valid node arguments CHAR_1 and CHAR_2 that have no path in the specified graph, print:
path from CHAR_1 to CHAR_2: no path found
If a character name CHAR was not in the original dataset, print:
unknown: CHAR
If neither character is in the original dataset, print the line twice: first for CHAR 1, then for CHAR N (even if they are the same character). These should be the only lines your program prints in this case — i.e., do not print the regular "path not found" output, and do not print the "path from CHAR 1 to CHAR N" output.
What if the user asks for the path from a character in the dataset to itself? Print:
path from C to C:
but nothing else. (Hint: a well-written solution requires no special handling of this case.)
This applies only to characters in the dataset: a request for a path from a character that is not in the dataset to itself should print the the usual "unknown: C" output, including printing it twice, since "both" characters could not be found.
Several sample test files demonstrating the new commands are provided in hw-marvel/src/test/resources/testScripts/
.
Your .test
and .expected
files should also go in this directory alongside the
examples.
Since your parsing code will likely always be using the CSV reader in MarvelParser
, and that class
is declared in src/main
, it will always look for data files in src/main/resources/data/
instead of src/test/resources/data/
. This might seem a little odd, since
some of your testing files (the data files) will be in 'main' instead of 'test.' We've done this to greatly
simplify the infrastructure required for getting these files to work across projects (as you start using your
parsing code for future assignments.)
In an industry setting, you'd have a separate parsing system capable of finding files only in 'src/test', but
for 331 you should have all your data files in src/main/resources/data
.
Note that your .test
and .expected
files should be in 'src/test/...' as usual, it's
just any .csv
files you create that should go in 'src/main/...'.
If your program takes an excessively long time to construct the graph for the full Marvel dataset, first make sure that it parses the data and builds the graph correctly for a very small dataset. If it does, here are a few questions to consider:
hashCode
if you overrode equals
?
checkRep
method? Does performance improve if you comment it
out or disable expensive checks?
Be aware that machine specs affect not only how fast your program runs but also how much memory it is allowed to use (more precisely, the maximum heap size).
ReactDOM.render
in your application. Only index.tsx
(which you do not
need to edit) should call ReactDOM.render
. The Document Object Model (DOM) is a representation
of HTML and XML documents and is the data object a JavaScript program manipulates to interact with a
browser. The DOM represents the document as nodes and objects. A JavaScript program can change the DOM,
which changes what the user sees in the browser. Using React allows React to manage the webpage and is more
efficient because React does not need to keep communicating with the DOM. Calling
ReactDOM.render
will require React to communicate with the DOM which affects performance and
defeats the purpose of React, which normally updates the page without re-rendering all of it.
document.getElementById
that “go around React”
are not permitted.
As always, remember to:
Refer to the Assignment Submission Handout and closely follow the steps listed to submit your assignment. Do not forget to double check your submission as described in that handout - you are responsible for any issues if your code does not run when we try to grade it.
Use the tag name hw6-final for this assignment. To verify your assignment on attu,
use the gradle task: hw-marvel:validate
.
For Part 6, ./gradlew validate
will not validate your homework assignment. The staff
strongly recommends you use the latest, standard version of Google Chrome to test your code. Your UI must load
when we use Google Chrome to visit http://localhost:3000 after running
npm start
from hw-dots/
. For this part, there are no new files that you must submit as part of the assignment, unless you add any new files yourself.
Make sure to commit any changes and additional files you create. Don't forget to note any additional
functionality in extras.txt
.
Your TA should be able to find the following in your repository:
hw-graph/src/main/java/graph/*.java
[Changes you made to your graph class.]
hw-marvel/src/main/java/marvel/MarvelPaths.java
hw-marvel/src/main/java/marvel/MarvelParser.java
hw-marvel/src/main/java/marvel/*.java
[Other classes you create, if any (there may be
none!).]hw-marvel/src/main/resources/data/*.csv
[Any csv files you create for testing or
running.]hw-marvel/src/test/java/marvel/scriptTestRunner/MarvelTestDriver.java
hw-marvel/src/test/resources/testScripts/*.test
hw-marvel/src/test/resources/testScripts/*.expected
hw-marvel/src/test/java/marvel/junitTests/*Test.java
[Other JUnit test classes you create,
if
any.]hw-dots/src/App.tsx
hw-dots/src/Grid.tsx
hw-dots/src/GridSizePicker.tsx
hw-dots/src/EdgeList.tsx
hw-dots/src/index.tsx
hw-dots/src/App.css
hw-dots/src/extras.txt