CPSC 220 Fall 2005
Program 4: Winning Paths

Overview

In the last program you developed a rating system for a set of lacrosse teams. In this program you will look for paths by which one team indirectly "beats" another.

Assignment

Write a program that prompts the user for the codes for two teams -- a "winner" and a "loser" -- and prints a list of games that provide the shortest "winning path" between them. That is, if the "winner" is Teami and the "loser" is Teamj, you should print a list of games in which Teami beats Team1, Team1 beats Team2,..., Teamn-1 beats Teamn, and Teamn beats Teamj. In the shortest case n=0, that is, Teami beats Teamj directly. Provide team codes, team names, date and score for each game. If no such path exists, print an appropriate message.

Program Structure

You should construct a directed, unweighted graph representing the games played, where an edge from team A to team B indicates that A beat B in a game. You may choose the graph representation you want to use, but you must justify your choice. You can do this in the documentation in the graph class (and be sure that your graph code is neatly encapsulated in its own class). Note that team A could beat team B more than once in a single season (and this does occur in our data); in this case you can use any of the relevant games to represent the A->B edge in the graph.

Use the BFS algorithm discussed in class to find the shortest path from one vertex to another. Note that you don't need to use Dijkstra's algorithm for this, as the edges are unweighted. Your code should be clean and reasonably efficient.

What to Turn In

Turn in hardcopy of your program and e-mail me a tar file of the program.