A graph whose minimum-cost path is not found by BFS.
Contents:
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.
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 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 the 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.
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 might not compile when we run our grading scripts, leaving us unable to test your code and significantly affecting 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 that previously compiled are now reporting "[some class] cannot be resolved" errors in Eclipse. You can fix these errors by doing a clean build to discard all of the existing compiler-generated files and then rebuild everything. 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.
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.
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 a PriorityQueue implementation.
Dijkstra's algorithm assumes a graph with 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.
Write a modified version of your Marvel Paths application in which your application finds 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 the number of comic books where two characters appear together. For example, if Amazing Amoeba and Zany Zebra appeared in 5 comic books together, the weight of the edge from one of them to the other would be 1/5. Thus, the more well-connected two characters are, the lower the weight and the more likely that the edge is used in a “shortest” path. So the idea is to treat the inverse of the number of books that two characters have in common as a “distance” — if two characters appear in several books together, then there is a shorter “distance” between the nodes for those two characters than between the nodes for two characters that only appear together in a single book.
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 has 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.
You are welcome to write a main method for your application as you did in the previous assignment, but this time 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.
Breadth-first search gives the same results as Dijkstra's algorithm when all edge weights are equal.
The format for writing tests follows the usual specification/implementation structure, but with some details changed to accomodate changes to the graph and the data stored in it. 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 before, you should 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.
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:
Edge labels are Doubles instead of Strings. If an edge label in a test script cannot be parsed as a number, the output is undefined. For ListChildren, the same rules as before apply for ordering output by nodes and edges, except that edges are now ordered numerically instead of alphabetically.
LoadGraph is still in use, similar to the previous homework. The only difference is after this method is called there should be at most one edge between any two nodes, with the edge's label containing the multiplicative inverse of how many books they share. Also, be sure your program now looks for data files in src/hw7/data.
path from CHAR 1 to CHAR N: CHAR 1 to CHAR 2 with weight w1 CHAR 2 to CHAR 3 with weight w2 ... CHAR N-1 to CHAR N with weight wN-1 total cost: W
where W is the sum of w1, w2, ..., wN-1.
In other words, the only changes in output are the way the edge labels are printed and the addition of a "total cost" line at the bottom. The output should remain the same as before when no path is found or the characters are not in the graph: in particular, do not print the "total cost" line in those cases. Also as before, underscores in node names are replaced by spaces for this command.
If there are two minimum-cost paths between CHAR 1 and CHAR N, it is undefined which one is printed.
String.format("Weight of %.3f", 1.759555555555);
In FindPaths, the total cost should be computed by summing the actual values of the individual weights, not the rounded values. Rounding should only be done when values are printed.
As in Homework 6, a path from a character to itself should be treated as a trivially empty path. Because this path contains no edges, it has a cost of zero. (Think of the path as a list of edges. The sum of an empty list is conventionally defined to be zero.) So your test driver should print the usual output for a path but without any edges, i.e.:
path from C to C: total cost: 0.000
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.
Several sample test files demonstrating the changes in format are provided in hw7/test.
When you add generic type parameters to a class, be 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 a data abstraction (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.
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?
You should add and commit the following files to SVN:
Additionally, be sure to commit all updates you make to the following files: