Shortest Path Assignment

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.

To use:

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

Design:

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.

Enjoy!