Marvel Comics #1

Contents:

Introduction

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.

The MarvelPaths Application

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 marvel.MarvelPaths (create the file yourself: MarvelPaths.java) 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 document 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 repository.

Part 0: Understanding the Marvel Universe Data

Before you get started, look at the file with the Marvel data: hw-marvel/src/main/resources/data/marvel.tsv. 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 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 tab ('\t').

Part 1: Parsing the Data

The first step in your program is to parse the provided tsv files. We have provided a starter file marvel.MarvelParser.java 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 parseData 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.

Part 2: Building the Graph

The next step in your program is to construct your graph of the Marvel universe from a data file. Once you have written 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 A.

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.

Part 3: Finding Paths

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 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.

Part 4: Testing Your Solution

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.

Script Tests

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 *.tsv files in the format defined for marvel.tsv to test your parser. All the *.tsv 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 have two choices for your approach:

  1. 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. This is probably the easier option, and is highly recommended.
  2. Alternatively, you may choose to write a new MarvelTestDriver class that extends the GraphTestDriver and reuses some of its code. This approach is potentially more elegant but requires some care to do properly. You will need to edit your GraphTestDriver to 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 main method from GraphTestDriver and 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).

JUnit Tests

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.

Running 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 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.

Part 5: Running Your Solution From the Command Line

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.

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

Test script file format

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; src/main/resources/data/marvel.tsv is not.

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.

Sample testing files

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.

Paths to Files

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 .tsv files you create that should go in 'src/main/...'.

Hints

Performance

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:

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).

Miscellaneous

As always, remember to:

How to Turn In Your Homework

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:runMarvel.

Your TA should be able to find the following in your repository:

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.