Contents:

Introduction

This assignment lays the groundwork for the application you will build in Homeworks 8 and 9 called Campus Paths. Using your graph as the underlying data structure, Campus Paths generates directions between buildings on campus.

This assignment has two parts. In the first part, you will make your graph class(es) generic. In the second part, you will implement a different pathfinding algorithm for graphs known as Dijkstra's algorithm. These parts are not directly related to each other, but both are necessary for Homework 8.

Augmenting Your Graph and Marvel Paths

Problem 1: Making Your Graph Generic [30 points]

In Campus Paths, your mission is to find the shortest walking route between points on the UW campus. A graph is an excellent representation of a map, and luckily you have already specified and implemented a graph. Unfortunately, your graph stores only Strings, whereas Campus Paths needs to store other data in the nodes and edges, such as coordinate pairs and physical distances. More generally, your graph would be much more widely useful if the client could choose the data types stored in nodes and edges. Herein lies the power of generics!

Your task is to convert your graph ADT to a generic class. Rather than always storing the data in nodes and edge labels as Strings, it should have two type parameters representing the data types to be stored in nodes and edges. Directly modify your existing classes under hw5 — there is no need to copy or duplicate code.

When you are done, your previously-written HW5 and HW6 tests and test driver and MarvelPaths will no longer compile. Modify these classes to construct and use graph objects where the type parameters are instantiated with String. All code must compile and all tests must pass when you submit your homework. In particular, your test drivers for both Homework 5 and 6 must work correctly so we can test your code. Depending on your changes, some of your implementation tests may no longer be valid. Try to adapt your implementation tests to your new implementation, or discard them and write new ones: they should help you build confidence in your implementation. But, don't overdo it: as with any testing, stop when you feel that the additional effort is not being repaid in terms of increased confidence in your implementation. Learning when to stop working on a given task is an important skill.

Build tools and generic code

Double-check that you have configured Eclipse to issue errors for improper use of generic types.

Eclipse's built-in compiler sometimes handles generics differently from javac, the standard command-line compiler. This means code that compiles in Eclipse may not compile when we run our grading scripts, leaving us unable to test your code and significantly impacting your grade. You should periodically make sure your code compiles (builds) with javac by running ant build from the hw7 directory (which will also build hw5 and hw6 automatically). You can do this in one of two ways:

If Ant reports that the build succeeded, all is well: your code compiles with javac.

Hint: after encountering build errors in Ant, you may find that classes which previously compiled are now reporting "[some class] cannot be resolved" errors in Eclipse. You can fix these errors by doing a clean build: go to Project >> Properties >> Clean..., select your cse331 project, and hit OK. If you are encountering these errors on the command line run ant clean prior to running ant build.

Problem 2: Weighted Graphs and Least-Cost Paths [30 points]

In a weighted graph, the label on each edge is a weight (also known as a cost) representing the cost of traversing that edge. Depending on the application, the cost may be measured in time, money, physical distance (length), etc. The total cost of a path is the sum of the costs of all edges in that path, and the minimum-cost path between two nodes is the path with the lowest total cost between those nodes.

In Homework 8, you will build a edge-weighted graph where nodes represent locations on campus and edges represent straight-line walking segments connecting the two locations. The cost of an edge is the physical length of that straight-line segment. Finding the shortest walking route between two locations is a matter of finding the minimum-cost path between them.

Dijkstra's algorithm

You will implement Dijkstra's algorithm, which finds a minimum-cost path between two given nodes in a graph with all nonnegative edge weights. Below is a pseudocode algorithm that you may use in your implementation. You are free to modify it as long as you are essentially still implementing Dijkstra's algorithm. Your implementation of the algorithm may assume a graph with Double edge weights.

The algorithm uses a data structure known as a priority queue. A priority queue stores elements that can be compared to one another, such as numbers. A priority queue has two main operations:

For example, if you inserted the integers 1, 8, 5, 0 into a priority queue, they would be removed in the order 0, 1, 5, 8. It is permitted to interleave adding and removing. The standard Java libraries include an implementation of a PriorityQueue.

    Dijkstra's algorithm assumes a graph with all nonnegative edge weights.

    start = starting node
    dest = destination node
    active = priority queue.  Each element is a path from start to a given node.
             A path's "priority" in the queue is the total cost of that path.
             Nodes for which no path is known yet are not in the queue.
    finished = set of nodes for which we know the minimum-cost path from start.

    // Initially we only know of the path from start to itself, which has a cost
    // of zero because it contains no edges.
    Add a path from start to itself to active

    while active is non-empty:
        // minPath is the lowest-cost path in active and is the minimum-cost
        // path for some node
        minPath = active.removeMin()
        minDest = destination node in minPath
        
        if minDest is dest:
            return minPath

        if minDest is in finished:
            continue

        for each edge e = ⟨minDest, child⟩:
            // If we don't know the minimum-cost path from start to child,
            // examine the path we've just found
            if child is not in finished:
                newPath = minPath + e
                add newPath to active

        add minDest to finished

    If the loop terminates, then no path exists from start to dest.
    The implementation should indicate this to the client.

Dijkstra's Algorithm in Marvel Paths

You will write a modified version of your Marvel Paths application in which your application finds its paths using Dijkstra's algorithm instead of BFS. Dijkstra's algorithm requires weighted edges. To simulate edge weights over the Marvel dataset, the weight of the edge between two characters will be based on how well-connected those two characters are. Specifically, the weight is the inverse of how many comic books two characters are in together. For example, if Amazing Amoeba and Zany Zebra appeared in 5 comic books together, the weight of the edge between them would be 1/5. Thus, the more well-connected two characters are, the lower the weight and the more likely that a path is taken through them. In summary, the idea with the marvel data is to treat the number of edges from one node to another as a “distance” — if there are several edges from one node to another then that is a “shorter” distance than another pair of nodes that are only connected by a single edge.

Things to note:

Place your new Marvel application in hw7/MarvelPaths2.java. In choosing how to organize your code, remember to avoid duplicating code as much as possible. In particular, reuse existing code where possible, and keep in mind that you will need to use the same implementation of Dijkstra's algorithm in a completely different application in Homework 8.

For this assignment, your program must be able to construct the graph and find a path in less than 30 seconds on attu using the full Marvel dataset. ScriptFileTests is set to put a 30000 ms (30 second) timeout for each test, run without assertions enabled. As suggested in hw6, running ant test is a convenient way to time your program.

As before, you are welcome to write a main method for your application, but you are not required to do so.

This assignment does not reuse your breadth-first search algorithm. A breadth-first search between two nodes finds the path with the fewest number of edges. In a weighted graph, it does not always find the minimum-cost path. In the example below, a breadth-first search from A to B would find the path {⟨A,B⟩} with total cost 10. But the alternative path {⟨A,C⟩,⟨C,D⟩,⟨D,B⟩} has a total cost of 3, making it a lower-cost path even though it has more edges.

A graph with a minimum-cost path of 3
A graph whose minimum-cost path is not found by BFS.

Breadth-first search gives the same results as Dijkstra's algorithm when all edge weights are equal.

Problem 3: Testing Your Solution [13 points]

The format for writing tests follows the usual specification/implementation structure. You should write the majority of your tests as specification tests according to the test script file format defined below, specifying the test commands, expected output, and graph data in *.test, *.expected, and *.tsv files, respectively. The *.tsv files should be structured in the same format as marvel.tsv. As usual, you will also write a class HW7TestDriver to run your specification tests. We provide a starter file for the test driver which you are free to modify or replace.

If your solution has additional implementation-specific behavior to test, write these tests in a regular JUnit test class or classes and add the class name(s) to ImplementationTests.java.

The specification tests do not directly test the property that your graph is generic. However, the Homework 5 and Homework 6 test scripts use String edge labels, while Homework 7 uses numeric values. Supporting all three test drivers implicitly tests the generic behavior of your graph.

Test script file format

The test script file format for Homework 7 uses the same commands and format as Homework 6, but with a few differences in arguments and output:

Sample testing files

Several sample test files demonstrating the changes in format are provided in hw7/test.

Hints

Documentation

When you add generic type parameters to a class, make sure to describe these type parameters in the class's Javadoc comments so the client understands their purpose.

As usual, include an abstraction function, representation invariant, and checkRep in all classes 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.) Please come to office hours if you feel unsure about what counts as an ADT and what doesn't.

Code Organization

In deciding how to organize your code, remember that you will need to reuse Dijkstra's algorithm in Homework 8. That assignment has nothing to do with Marvel and, depending on your implementation, might use a different generic type for nodes. How can you structure your code so that your implementation of Dijkstra's algorithm is convenient to use for both assignments?

What to Turn In

You should add and commit the following files to SVN:

Additionally, be sure to commit all updates you make to the following files:

Run ant validate to verify that you have submitted all files and that your code builds and runs correctly on attu.