EG 724 - Algorithm Design - Spring 2003
Project 3 - Graph Algorithms

Loyola College > Department of Computer Science > EG 724 > Projects > Project 3

Due

Wednesday, April 30th at 11:59pm. Late projects will be assessed a 20% penalty for each day past the due date. Projects will not be accepted more than four days past the due date.

Objectives

Assignment

Choose one of the following assignments.

Dijkstra's Algorithm

Add a method List findPath(Object src, Object dest) to your Graph class that returns a path from the given source vertex to the given destination. The path should be ordered to start at the source vertex and end at the destination vertex. If no path exists, findPath should return an empty path.

Add another method Graph dijkstraShortestPaths(Object s) that returns the shortest paths tree as computed by Dijkstra's algorithm. The original graph should not be modified; a new graph should be returned The new Graph should have the same vertex set as the one the method is called on (some of those vertices may be unreachable in the new graph). Calling findPath on the new graph should return the shortest path in the original graph. You may make minor modifications to your PriorityQueue class to make it more useful for Dijkstra's algorithm.

Strongly Connected Components

Add a List getStronglyConnectedComponents() method to your Graph class that returns a list of lists corresponding to the strongly connected components of the graph the method is invoked on.

Add another method Graph getComponentGraph() that returns a new graph that is the component graph of the one the method is invoked on. The original graph should not be modified. The vertex labels for the new graph may be chosen arbitrarily. The new graph may not have multiple edges between the vertices that represent components in the original graph.

Grading

For full credit, your code must have reasonable worst case running times.

Submissions

Submit all source code files necessary to build your code, any test drivers you have created, and an explanation of how to modify your code to work with different classes.