Update to Assignment 1

I kept thinking about the assignment and found the negative weight search problem so interesting that I went back and spent another hour or so on it. I now have a full solution to the standard and both bonus assignments that includes solutions for graphs with negative weights.

Main fixes

1. Fixed an error in my implementation of the Bellman-Ford algorithm. I misread the bounds of the inner loop: I thought it looped through all the edges in the current node, but rather, it loops through all the edges of the entire graph. I was able to simplify the code considerably once I realized my error.
2. I also realized that for the bonus questions, any negative weight node can be used in a cycle, and this will break the Bellman-Ford algorithm. For example:
1. Input is: 
2. "B1"
3. "3 3 1,1 2,3"
4. "1 -10 2"
5. "5 2 -1"
6. "2 1 3"
7. There is a cycle between nodes (1,2), and (2, 3). The Bellman-Ford algorithm cannot handle this case.
3. To solve this challenge, I implemented a brute force exhaustive search that tries searching all nodes to all nodes recursively. This is not elegant but solves the problem quickly enough for small data sets. My solution is more of a proof of concept than anything and could use some heavy optimization. The best way to do this would be to profile the code, and see where the hotspots are.
4. Fixed a potential array index out of bounds error when inputting start and end nodes.

The code is available here.

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!