The first part of the assignment works as specified, including negative weights.
For the bonus, I ran into a bug where in some cases the shortest path is not found when using negative weights. A valid path is found, but it is not always the shortest. Given more time, I could definitely figure this out, but I have reached the deadline. Please see my Bonus1GraphTest.
TestNegativeSearch() for a failing test.
1. Download the zip file from here: http://ninjagreg.slashdothost.com/assignment1/CylindricalMatrix.zip
2. Extract the zip file
3. The app and unit test source code is in the CylindricalMatrix and CMTests folders, respectively.
4. The code is in C#.
I originally intended to write this assignment using Dijkstra's algorithm to compute the shortest path in the matrix, until I realized negative weights were valid; I therefore switched to the Bellman-Ford algorithm because it can work with negative weights. To model the graph search problem, I created a graph, node and edge classes.
The general workflow is:
The InputParser parses the input, and returns a matrix, and start and end nodes. A graph is then created from the matrix, and the shortest path is computed. The results are output to the user.
- The InputParser class reads input from any TextReader stream. The TextReader stream can be stdin, for user input, or a mocked stdin to aid in testing and debuggin.
- The Matrix class I modeled after the Data Transfer Object (DTO) pattern. Future programmers may want to search for the shortest path using a non-graph algorithm, therefore I thought it best to keep the Matrix class "dumb" and only use it to be passed to other modules.
- The graph classes do the meat of the assignment including the transform of matrix to graph, and searching.
- There is a BaseGraph class that has default graph building and searching functionality.
- The StandardGraph class is derived off BaseGraph and implements features specific to the Standard portion of the assignment, such as there being no start or end row defined.
- Bonus1Graph is derived off BaseGraph and extends the graph building functionality to search in all cardinal directions.
- Bonus2Graph is derived off Bonus1Graph to implement "torus" wrapping.