Java代写: 软件设计与实现

修改之前的漫威宇宙simulator, 加入dijkstra算法来寻找最短路。

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

Please follow the required changes to be made regarding the Checker Framework. There are additional extra credit instructions, but please make sure to at least follow the required ones. If you do not, then your code will not build. Make sure to run ‘ant validate’ for hw5, hw6, and hw7 to help you make sure things are working as they should.

Modify Your Graph and Marvel Paths

Checker Framework Required Changes

The staff has pushed changes to your repos that will now use the checker framework to check for nullness annotations. So, now if you try to ‘ant validate’ your hw5 and hw6 submissions, you will find that they will fail because you have not added the annotations.
Please install the Checker Framework Eclipse Plug-in by following the installation steps mentioned here.
IMPORTANT: You must add @SuppressWarnings(“nullness”) directly on top of all your java classes for hw5, hw6, and for hw7. This would go directly above the ‘public class …’ declaration. It is best to do this for all *.java files, including the files that were given to you like the HW Test Drivers. Please do this regardless of if you do the Checker Framework Extra Credit.
You should definitely run ant validate in attu for your project after your final commit and push which will fail due to checker framework errors if you have forgotten the suppress warnings line somewhere. But you can also run the checker in Eclipse by right-clicking a homework directory and going to Checker Framework -> Run Built-in Checker -> Nulness Checker. Note, this may take a few seconds to run. Once it is complete, click on the Problems tab instead of the Console and if you did everything correctly you should not see any Warnings related to the checker framework missing annotations.

Problem 1: Make the 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 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.

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

  • Through Eclipse: Right-click build.xml under hw7 and click Run As >> Ant Build... (note the ellipsis). In the window that appears, select build [from import ../common.xml] and hit Run.
  • At the command line: Run ant build from the hw7 directory.

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.

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 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 this 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:

  • add: Insert an element.
  • remove: Remove the least element. (This is sometimes called removeMin, for emphasis.)

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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 to 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 for Marvel Paths

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

Things to note:

  • A path from a character to itself is defined to have cost 0.0.
  • Edge weights should be calculated when the Marvel data is read and the graph created. This assignment is different from the last one in that now, after the graph is initialized from the input data, there should be at most one directed edge from any particular node to any other node. The edge between any two character nodes should have a label containing the multiplicative inverse of how many books they share. Since the “connected” relationship is symmetric, if there is an edge from one node to another, there will be another edge between the same two nodes in the opposite direction with the same label.
  • When the Marvel data has been read and the graph has been initialized, there will be at most one directed edge from one Marvel character to another, but clients of the graph can later add additional edges. The new edges may or may not have a matching, symmetric edge in the other direction. If client code wants to have a matching edge in the other direction, it would be added in a separate operation. These new edges could lead to a graph containing multiple weighted edges between two nodes. You must be sure that the pathfinding algorithm uses the least cost edge between two nodes if there are multiple edges. In other words, if a new edge is added to your graph after it is initialized by processing the Marvel data, then the pathfinding algorithm should be able to use this new edge in its calculations, and you should not re-calculate the weights of other, existing edges or delete or overwrite any existing edges.

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 program 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 with assertions enabled. You will almost certainly want to have a compile-time variable that controls how extensive your checkRep tests are. If you do exhaustive tests after ever graph operation with the full dataset, you could easily exceed the timeout, but these tests are also very useful while debugging and testing. Leave all the checks on during development and testing, then change the variable value and recompile to disable the expensive tests in the version you validate and submit for grading. 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.

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 [15 points]

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. Do not modify ScriptFileTests.java.

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.

Checker Framework EXTRA CREDIT

For up to 5 extra credit points remove as many of the @SuppressWarnings(“nullness”) as you can and try to add the nullness annotations in your code. Not that you can also add the @SuppressWarnings(“nullness”) directly above individual methods instead of above the whole class.
No matter how much work you do for the extra-credit, please really make sure you run ant validate on your final submission to verify your work builds and your tests pass. Because if ant validate fails because of the nullness checker than the build will fail when our grading scripts run, and you will not pass any of the tests. It is important that the rest of your work for this homework assignment is counted correctly.
Please use the provided resources to help you with this. You can review the checker framework lecture. You can also see the checker framework manual.
Because this is extra-credit, the TAs will not provide help in regards to checker framework annotations in Piazza or through Office Hours. You can definitely use Piazza to discuss ideas regarding annotations amongst each other, but please refrain from posting large, revealing sections of your code that display work done for other parts of this assignment.

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:

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

  • FindPath searches with Dijkstra’s algorithm instead of BFS and prints its output in the form:

    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.

  • For readability, the output of ListChildren, AddEdge, and FindPath should print numeric values with exactly 3 digits after the decimal point, rounding to the nearest value if they have more digits. The easiest way to specify the desired format of a value is using format strings. For example, you could create the String “Weight of 1.760” by writing:

    String.format("Weight of %.3f", 1.759555555555);
    

    In FindPath, 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.

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

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, commit, and push the following files to your GitLab repository:

  • hw7/MarvelPaths2.java
  • hw7/*.java [Other classes you create, if any]
  • hw7/test/*.test
  • hw7/test/*.expected
  • hw7/data/*.tsv
  • hw7/test/*Test.java [Other JUnit test classes you create, if any]

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

  • hw5/* [Your graph ADT and test classes]
  • hw6/* [Your Marvel Paths application]
  • hw7/HW7TestDriver.java
  • hw7/test/ImplementationTests.java

When you have committed and pushed all of your changes and are done with the assignment, you should create a git tag in your repository named hw7-final and push that tag to your repository. Once you have committed and pushed that tag, your assignment has been submitted and the staff will grade the files in your repository that are labeled with that tag.

Run ant validate on a newly checked-out copy of your project to verify that you have submitted all files and that your code builds and runs correctly on attu.

For problems or questions regarding this page, contact: cse331-staff@cs.washington.edu.

kamisama wechat
KamiSama