NOTE: Our project uses the sqrt() function from the math library, and, 
as such, should be compiled with the -lm switch.

Project file list:
map.h
routing.h
path_main.c
map.c
routing.c
report.txt

/**********************************************************************
 * Project Report Template
 * Project 3, ECE368, Fall 2006
 **********************************************************************/

Names of team members:
      Scott Pillow
      William Ehlhardt

Logins of team members:
       spillow
       wehlhard

/**********************************************************************
 *  Explain your overall approach to the problem and a short
 *  general summary of your solution and code.
 **********************************************************************/

The general approach of the problem very closely followed the pseudocode
for Dijkstra's Algorithm presented in class. The only difference was that
this project called for the solution of undirected graphs.  Accomodating this 
was fairly simple; the Relax(Edge) function simply checked "both 
directions" instead of only one way.

The pseudocode for our algorithm looks something like this:

Nodes = array of the nodes in the graph
Edges = array of the edges in the graph

for each node N in Nodes:
	N.Cost = INFINITY
Nodes[Start].Cost = 0

for each node in Nodes:
	for each edge E in Edges:
		Relax(E) // "bidirectional" relax - pretty intuitive

(Relax(E), if it changes anything, also sets a "Previous" field on the 
higher-cost node in the edge pair to point to the lower-cost node.)

Finally, starting at the end node, trace back along the path of Previous 
fields to build the list of nodes in the path, and print it.

The algorithm also called for setting all of the vertices besides the 
source vertex to infinity to reflect that they haven't been found yet.  
This was done by setting the "Cost" field of each vertex to the maximum 
value that can be held by an unsigned long int. This also necessitated 
some changes in the Relax() code - see "Limitations" below.

/**********************************************************************
 *  Known bugs / limitations of your program / assumptions made.
 **********************************************************************/

Since the Cost and node coordinate variables are of type long int (for 
speed purposes), exceptionally long distances will cause an integer 
overflow.

Also, since the Cost for each node is set to the maximum value it can 
hold (in lieu of "infinity"), adding the edge distance to the node cost 
will cause an overflow and errors. Thus, we used algebra to use 
subtraction instead of addition and avoid overflows.

As always, the input is assumed to be correct (i.e., the graph should be 
connected, input files are properly formatted) so mistakes in that will 
very likely crash the program.

/**********************************************************************
 *  List whatever help (if any) that you received.
 **********************************************************************/

We verified a few of our results against ones posted on the class discussion
board.

/**********************************************************************
 *  Describe any serious problems you encountered.                    
 **********************************************************************/

Scott:
The biggest problem was probably in deciding how to layout the structure
of the program.  We ended up taking a rather Object Oriented approach 
that I think really organized the data and made the writing and reading
of the code an easier process.

William:
As Scott said, the design of the program required some hard thinking.

Probably the worst bug encounted was one where we mistakenly used malloc 
to allocate space for N objects of one type when the array was supposed 
to be another type; worse, this didn't show up unless the number of 
queries was fairly large, and the compiler gave no hints. However, we 
did fix it.

/**********************************************************************
 *  Describe how the team members shared the work (i.e., what 
 *  were the contributions of each team member?).                    
 **********************************************************************/

Scott:
- wrote initial slow pathfinding algorithm
- wrote main() outline
- wrote query loading
- wrote some report
- did some testing

William:
- sped up the pathfinding algorithm by rewriting it in a simpler manner
- wrote automated tests
- bug fixing
- edited the report to incorporate changes to the algorithm
- managed the source control repository

/**********************************************************************
 *  List any other comments/feedback here (e.g., whether you
 *  enjoyed doing the exercise, it was too easy/tough, etc.).
 **********************************************************************/

Scott:
This was a solid exercise that was probably on par in difficulty with 
Project 2.  The algorithm is pretty straightforward so the hardest part
is turning it into working C code.

William:
I thought this project would be more difficult than it was. We 
implemented the dead-simple approach given in class, thinking that it 
would be far too slow; however, it turned out to run pretty well, 
processing 100 queries against the "usa" map in about 6 minutes on my 
machine.

As such, the algorithm was not a particularly difficult part of 
the project; I think that fact that it was in C (a picky language) made 
things more difficult than the algorithm itself did.

The work we did on this project is retained in a Subversion source code 
repository, which is available upon request.