Tuesday, June 1, 2010

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:

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.

No comments: