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 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.
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
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
marvel.MarvelPaths (create the file yourself:
that reads the Marvel data from a file (
marvel.tsv), builds a graph, and finds paths between
characters in the graph.
As you complete this assignment, you may need to modify the implementation and/or the specification of your Graph
ADT. Briefly document any changes you made and why in a PDF file (no more
than 1-2 sentences per change). If you made no changes, state that explicitly. You don't need to track and
cosmetic and other minor changes, such as renaming a variable - we are only interested in substantial changes to
your API or implementation, such as adding a public method or using a different data structure. Describe logical
changes rather than precisely how each line of your code was altered. For example, “I switched the data
structure for storing all the nodes from a ___ to a ___ because ___” is more helpful than, “I
changed line 27 from
nodes = new ___(); to
nodes = new ____();.” Submit this
file to Gradescope when you're done with the assignment.
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
Before you get started, look at the file with the Marvel data:
A TSV (“tab-separated value”) file consists of human-readable data delineated by tabs, and can be
opened in your favorite text editor, spreadsheet, or IntelliJ. Each line in
marvel.tsv is of the
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 tab (
The first step in your program is to parse the provided tsv files. We have provided a starter file
and you must implement it using the OpenCSV package. You probably want to use the demo of the OpenCSV package
from section to get started.
We've provided enough code to get a
BufferedReader that's pointing to a particular TSV file - then
you can pass that reader to the
CsvToBeanBuilder, as seen in the demo. When you call the
method, you just give it the simple filename of the TSV file and it'll take care of looking in the correct
directory. For example:
parseData("marvel.tsv"). If you write any parsing code elsewhere in this
course, you should write code similar to the example code here to ensure that it works across
projects/assignments and in testing. See the comments in
parseData 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
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 CSV 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
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. Below is a general BFS pseudocode algorithm to find the shortest path between two nodes in a graph G. For readability, you should use more descriptive variable names in your actual code:
start = starting node dest = destination node Q = queue, or "worklist", of nodes to visit: initially empty M = map from nodes to paths: initially empty. // Each key in M is a visited node. // Each value is a path from start to that node. // A path is a list; you decide whether it is a list of nodes, or edges, // or node data, or edge data, or nodes and edges, or something else. Add start to Q Add start-> to M (start mapped to an empty list) while Q is not empty: dequeue next node n if n is dest return the path associated with n in M for each edge e=〈n,m〉: if m is not in M, i.e. m has not been visited: let p be the path n maps to in M let p' be the path formed by appending e to p add m->p' to M add m to Q // If the loop terminates, then no path exists from start to dest. // The implementation should indicate this to the client. Note that // BFS returns the path with the fewest number of edges.
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 BFS algorithm above can be easily modified to support this ordering: in the for-each loop, visit edges in increasing order of m's character name, with edges to the same character visited in increasing order of comic book title. This is not meant to imply that your graph should store data in this order; it is merely a convenience for grading. Note that normally it wouldn't be a great idea to "specialize" BFS like this, where it requires a sort-able input, but it's fine to modify the BFS itself to achieve this sorting behavior for this assignment and our use-case.
Because this search is specific to this particular application, you should implement your BFS algorithm 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
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
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.
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
*.expected files as before, you will write
in the format defined for
marvel.tsv to test your parser. All the
*.tsv files used for testing should be placed in the
directory. Place your test scripts in
You should create a class named
MarvelTestDriver that runs tests in the same way that
did. We have provided a starter file in
hw-marvel/src/test/java/marvel/scriptTestRunner with method
and a small amount of starter code, but you can replace it. You have two choices for your approach:
graph/src/test/java/graph/scriptTestRunner/GraphTestDriver.javasource 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. This is probably the easier option, and is highly recommended.
MarvelTestDriverclass that extends the
GraphTestDriverand reuses some of its code. This approach is potentially more elegant but requires some care to do properly. You will need to edit your
GraphTestDriverto make it more extensible — in particular, by making some of its methods and/or fields protected instead of private. Also, static methods may not have the inheritance properties you want. You may find it easiest to copy the
GraphTestDriverand change the references from Graph to Marvel. Regardless of how you decide to change
GraphTestDriver, it must continue to work correctly for the previous assignment(s) and the graph script tests there (so rerun your Graph tests after doing this and make sure they still work).
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.
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
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.
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.
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
Mac/Linux users should run the following from the IntelliJ Terminal window:
Windows users should run the following:
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.tsv
Creates a new graph named graphName from file.tsv, where file.tsv is a data file of
the format defined for
marvel.tsv 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.tsv 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.tsv is a simple filename;
FindPath graphName node_a node_b
Find the shortest path from node_a to node_b in the graph using your breadth-first search algorithm. For this command only, underscores in node names should be converted to spaces before being passed into any methods external to the test driver. For example, "node_a" would become "node a". This is to allow the test scripts to work with the full Marvel dataset, where many character names contain whitespace (but none contain underscores). Anywhere a node is printed in the output for this command, the underscores should be replaced by spaces, as shown below.
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 N: no path found
If a character name CHAR was not in the original dataset, print:
unknown character CHAR
where, as before, any underscores in the name are replaced by spaces. 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 character C" output, including printing it twice, since "both" characters could not be found.
Several sample test files demonstrating the new commands are provided in
.expected files should also go in this directory alongside the
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
/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
Note that your
.expected files should be in 'src/test/...' as usual, it's
.tsv 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:
hashCodeif you overrode
checkRepmethod? 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).
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:
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, if any.]
hw-marvel/src/main/java/marvel/*.java[Other classes you create, if any (there may be none!).]
hw-marvel/src/main/resources/data/*.tsv[Any tsv files you create for testing or running.]
hw-marvel/src/test/java/marvel/junitTests/*Test.java[Other JUnit test classes you create, if any.]
Don't forget to submit your written answers to Gradescope, in addition to submitting the code through GitLab. Note that if you didn't make any changes to your graph code in this assignment, you should still submit a file to Gradescope that says "I didn't make any changes to my graph code." Everyone should have something submitted to Gradescope.