Project Description
This project has three objectives: 1) for you to implement Dijkstra’s shortest path (least cost) algorithm, 2) to give you an experience similar to that of performing real-world maintenance work on existing applications, and 3) to show you some production-like use of the object-oriented ideas we have been discussing.
Typically developers spend 60 percent of their time performing maintenance work on existing applications. Unlike typical classroom assignments, maintenance work seldom involves elegant, idealized structures, is never code you wrote, typically sits in the middle of applications so large that you can never afford to read every line of the app before you start work, often involves code which is shared between multiple applications, might come (in the best shops) with lots of developer and test support infrastructure, and is seldom supported with precise and clear instructions. In fact, you might have drawn this code because the last person to have worked it left the company before taking time to writing the related documentation.
For this project you play the role of a (new to the project) employee who will complete a partially finished new “shortest path” feature in two different graph-based applications: Maze and Explore. Maze is a very small application that builds graphs. Explore builds terrain maps on an extended version of the same graph used by Maze. Explore is a much larger application (though still small compared to most commercial applications) , and is currently broken because another feature change (revising the way that Explore parses input files) is not quite finished.
Specifically, you must supply code at the “//TODO:” markers in
- Maze’s PathFinder.findPath() method an
- Explore’s TerrainLoader() class, and
- uncomment a line in Explore’s TerrainBoard.paint() method.
This work will require that you:
1) write your own implementation of Dijkstra’s shortest algorithm using Maze’s existing Graph, Heap, and Stack code. (We will variously call this “the solver” or Pathfinder class.)
2) Insert your solver code into a presently stubbed method in the already working and otherwise complete Maze application (PathFinder.findpath()).
3) Complete three or four parsing methods in one class in Explore, using some classes especially designed for the task (a special Scanner, for example). With the specialized classes, each of these methods should be just a few lines long.
4) Uncomment a line in Explore to activate its new shortest path feature (which uses a sub classed version of the same graph class as Maze, thus your solver should be just what is needed in both applications.)
Like many real employers, we assume you are a quick study, and rather than ask a senior developer to sit with you and guide you through the task, we have collected, for you, all the existing documentation associated with these two applications. We assume that somewhere in that documentation or in the source code, you will find what you need. (Just don’t spend too much time trying to understand all the code in Explore, or you’ll miss the ship date.) Unlike most employers, we will at least point you to the existing developer infrastructure and give some advice about when and how to use them.
We will supply two documentation packages via BlackBoard, one for Maze and one for Explore.
You will find related requirements mostly in the Javadoc within the source code or in the developer notes in the respective documentation packages. If you have questions, pose them first on Blackboard.
The documentation packages are divided into three sections: end user documentation, developer documentation, and supporting background material . These documents are similar to, but more in some ways more generous, and generally more targeted than the information that might be available to you as a new employee in a typical software company. Your goal in reading this material should be to better understand the application and how your work fits into it. Remember, some of the specific instructions in the User Documentation are meant to apply to end users only; you are a developer.
It is unreasonable to expect every line of these packages to relate only to some specific, separately graded task required of you. It is equally unreasonable to think you can do a good job without reading anything but this project description document and the code.
You should follow this work plan:
- Get Maze running without a solver.
- Build a solver using Maze and supplied drivers, demo data, tests etc. as your development harness.
- Complete the TerrainLoader for Explore. Use the supplied Junit driver initially, because it does not require a full working app. Add code for and test each new feature description section separately.
- Add your solver and the TerrainViewer, to the test driver. Uncomment the wiring that uses the solver.
The Templates
The “templates” will be supplied in two different zips, one for Maze and one for Explore. You should work on Maze now. When the Explore templates are available, you should copy the source into a new project and then copy the “shared” package from your working Maze project into the appropriate place in the new Explore code. Do not attempt to import either project into the other. We will not make any allowances for “accidents.” If you destroy your work at some point in this project, we will make no accommodation in your grade. You are responsible if your work is lost because you haven’t observed necessary backup protocols.
Submission
You will submit a single project containing both applications. You are required to include, in your submission, the source code for each of the classes: You need to write proper documentation with Javadoc for any additional helper methods you might define. You must not make any change to Graph. Your solver should operate on the graph only through the Bare interfaces.
Write your class so that its package name is hw5. Your source files (.java files) will be placed in the directory, as defined in the Maze and Expire template files. Be sure to insert your name after the @author tag in the PathFinder class and the TerrainLoader class. Your zip file should be named Firstname Lastname HW5.zip. You may submit a draft version of your code early to see if you have any submission problem with Blackboard Learn. We will grade only your latest submission.