Contents:

Introduction

In this assignment, you will be implementing the directed labeled graph that you have written specifications, method stubs, and tests for in part 1 of this assignment. Unlike previous assignments, you must implement your Graph individually, following the specifications that you provided and incorporating any feedback that the staff have given you in previous assignments.

In addition, you will get started with Facebook's Javascript Framework React by making a small website with a form that takes your name and displays a greeting. This part will be completely independent from the previous parts (in the hw-react-starter folder rather than the hw-graph folder), and it will help you get familiar with React.

This assignment is the second part of a multi-part project, leading up to building a full application for getting directions to travel between two buildings on the UW campus.

Part 1: Choosing a representation

There are many ways to represent a graph. Here are a few:

Answer the following questions in the hw-graph/src/main/java/graph/answers-part2.txt file in your repo:

  1. In two or three sentences, explain an advantage and a disadvantage of each representation (for example, in terms of runtime complexity, space complexity, or ease of implementation).
  2. Which representation did you choose for your implementation?

Part 2: Abstraction functions and representation invariants

Place a proper abstraction function and representation invariant for your Graph data type (and any other ADTs you create) in your source code. Remember that abstraction functions and representation invariants are implementation details and shouldn't be visible to clients of your Graph, so they should be in a regular comment, not a javadoc comment. Also implement a private checkRep() method, which will help in finding errors in your implementation.

Be sure to call your checkRep() wherever it is appropriate.

Part 3: Implementation

Provide an implementation of your graph data type. We ask that you start off by focusing on style. Once you have well designed code, you can think more about efficiency.

Eventually, your path-finding application will create and operate on very large sized graphs (thousands of nodes and tens of thousands of edges), so the scalability of your Graph implementation will be important. We recommend that your graph building and manipulating operations should be reasonably efficient.

As your implementation will likely use classes in the Java Collections Framework, you should understand the computational complexity of classes such as HashMap and ArrayList.

Part 4: Additional tests and changes to specifications

Once you've finished your implementation, you should think about whether or not new tests are needed in addition to those you wrote before you started coding. If so, you should add these to your test suite. In the answers-part2.txt file from earlier, put a description of any new tests you added and why you added them, or why you feel that your original tests alone are sufficient.

Did you make any changes to your specifications as you were implementing your Graph? If so, describe your changes and why you made them in the answers-part2.txt file.

All of your answers in the answers-part2.txt file should be brief and to the point. Short bullet lists are fine. Excessive verbosity or irrelevant remarks should not be included and will not receive full credit.

Write the Test Driver for the Graph

The staff-supplied testing driver GraphTestDriver in the graph/scriptTestRunner package should read input from standard input or a specified file using the format described under the Test Script File Format section and print its results to standard output. We have provided a skeleton implementation that takes care of parsing the input file format. Complete this file by adding code where specified by TODO comments to perform the appropriate operations on your ADT. Please be sure to use the PrintWriter stored in the output field in the tester to print the desired output (i.e., when implementing the test driver, use output.println() instead of System.out.println()).

Test timeouts

If you have a bug, your program might run forever. To avoid such problems, you must add, to each JUnit test class, these two import statements: 

import org.junit.Rule;
import org.junit.rules.Timeout;
and this line within the class definition, at the top: 
@Rule public Timeout globalTimeout = Timeout.seconds(10); // 10 seconds max per method tested

Part 5: Getting Set Up to Develop with React

This part of the assignment does not depend on earlier parts. We recommend you use IntelliJ Ultimate as opposed to IntelliJ Community for this and the next assignment. IntelliJ Ultimate has much better IDE support for writing Javascript/TypeScript, and so likely will be more helpful for your development. There are free student licenses for IntelliJ Ultimate available, linked from the resources page for this course. Note that you can still complete this assignment with IntelliJ Community edition, it will simply be less helpful with auto-completing and error-checking.

The commands and installation procedures for Node and NPM (which are what we're using to manage our React development environment) are the same for both Windows and macOS/Linux users. First, navigate to the Node.js homepage and install the "LTS" version of Node.js. This will also install the correct version of NPM automatically. Windows users should make sure that the “Add to PATH” option is enabled during the installation process.

macOS users running modern versions of macOS may get a warning about the installer not coming from a “verified developer.” To resolve this, open System Preferences and navigate to Security & Privacy > General. There, you'll be able to click “Open” to run the Node/NPM installer.

Once you have Node.js and NPM installed, restart IntelliJ (if it's open). Next, you need to install React and all of the other things that React needs to work correctly. We provided hw-react-starter/package.json, which tells NPM how to install React and where to find all the things it needs. All you need to do is run the installation. From the project root directory (which you can get to by opening the terminal window in IntelliJ), run the following two commands: 

cd hw-react-starter
npm install

The first navigates you to the hw-react-starter directory, which you'll need to run all your commands inside. The second tells NPM to read the package.json file and perform the installation for you. 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.

In addition to the steps above, we require that you use an up-to-date version of the Chrome web browser. Other browsers have varying compatibility and have the potential to complicate grading or cause your code to fail when being run in the grading environment.

We recommend using React Developer Tools, a Chrome Extension created by Facebook. Using this tool will help you debug your React code as you work on this assignment and the next assignment. It can help you view props and state of your components and trace how data is flowing between your components. It will also provide warnings in the console about common mistakes that it finds in your code.

Part 6: Simple Greeting Application

When you run the starter code, you should see a simple form with a text field that should take a name, and a submit button next to it. The text field accepts inputs, but submitting it doesn't do anything. This is because our starter code is half-written - you should fill the parts given by TODOs. In your complete version, submitting a name should make a text appear under the form, greeting the person with the name entered in the form. Also, your version should reset the text field when it is submitted, so that a new name could be written there. However, if the text field is empty when the submit button is clicked, no text should appear.

Looking at hw-react-starter/src/App.tsx, you should see that only a line in render() and handleSubmit should be filled, but you should understand all of the code before filling those parts - this will be helpful for you later, when we will ask you to implement more complicated user interfaces.

Part 7: Code Coverage

Before you start, note that this part is dependent on part 4. In this part, you will run your tests using code coverage and provide a screenshot of your code coverage statistics. To do so, Under the Gradle tasks tab, locate hw-graph > Tasks > verification. Right-click on the on test and select Run cse331… with Coverage. A tab with coverage for all the home project folders will appear in IntelliJ, which will look like the following picture (see the red box):

Note: In the above picture, the project containing hw5.2 implementation is named, but your project name might differ depending on your design. Navigate to where your Graph implementation files are by clicking on the package name. Once you see your project files, take a screenshot. The screenshot should contain your code coverage information for the classes in your graph ADT and look like this:

Save your image under hw-graph/src/main/java/graph/ as code-coverage.jpg or code-coverage.png
Remember to add the screenshot file to your git repository’s tracked files by right-clicking on it and choosing Git > Add. Otherwise, your screenshot may not get submitted, and you may not get graded on it.

Resources for Part 5-6

The Connect the Dots Graphical User Interface(GUI) is written using HTML and TypeScript, principally with the React framework.

To learn about HTML, see the W3 Schools HTML tutorial.

To learn about JavaScript (the basis for TypeScript), see the MDN JavaScript tutorial.

To learn about TypeScript (a superset of Javascript that adds type information), see the official TypeScript website.

We will not go deeply into either JavaScript/TS or HTML, so use these resources only to learn what you need and do not feel obligated to study them in depth.

We've created a React handout that explains some of the finer points of React and will guide you as you implement your applications in HW8 and HW9.

Hints

Abstraction function, representation invariant, and checkRep

Include an abstraction function, representation invariant, and private checkRep() method in all new classes you create that represent an ADT. If a class does not represent an ADT, place a comment that explicitly says so where the AF and RI would normally go. (For example, classes that contain only static methods and are never constructed usually do not represent an ADT — though you are unlikely to write any such classes for this assignment.) Please come to office hours if you feel unsure about what counts as an ADT and what doesn't.

Be conscious of how certain operations in checkRep(), particularly iterating over a large dataset, may affect the “big-O” runtime of your methods. If your program suffers performance problems in the next few homeworks, checkRep() is a good place to start looking for problems.

It is hard to balance the utility of the checkRep() method with how expensive it may be to run. A good approach is to call checkRep() as much as possible (generally at the beginning and end of every method), but to disable the checkRep() when you turn in your code so that our tests don't timeout. A good way to do this is to have a static final constant boolean in your class that is checked in your checkRep() such that it only runs when the constant variable is true. If your checkRep() function includes some expensive computations and some that are quick, you might want to selectively disable just the expensive ones. However be aware that when your code is evaluated, there will be a fairly short timeout on each staff test and an expensive checkRep() could easily cause tests to fail because do not terminate quickly enough. There will be enough time for the actual work needed, provided your code is straightforward and does not do excessive computation. As an example, you can create a DEBUG variable like in the example code below, and make sure that its value is false before turning in your assignment: 

class Graph {
    public static final boolean DEBUG = true;

    // other methods/constructors/fields in your class go here

    public void checkRep() {
         // Cheap tests go here
         if (DEBUG)  {
               // Expensive tests go here
         }
    }
}

A warning about equals and hashCode

You may find it useful to define a class or classes that implement method equals. If you do that, be sure to also provide a consistent definition of method hashCode, otherwise your objects may behave strangely if used in containers like HashMaps. There is a good discussion of the issues involved in Effective Java (item 11 in the 3rd edition). Remember that many data structures (HashMap and HashSet, to name a couple) have requirements on implementing methods like hashCode and equals before you can properly store objects in them. Be sure to read the documentation for data structures you use and understand the requirements for using them.

Node/NPM/React Installation Issues

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 hw5-part2-final for this assignment. To verify your assignment on attu, use the gradle task: hw-graph:validate to check for common errors such as your code not compiling or not passing tests. However, validation is not guaranteed to catch all errors in your code.

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