## 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 Team_{i}
and
the "loser" is Team_{j}, you should print a list of games
in which Team_{i} beats Team_{1}, Team_{1} beats
Team_{2},...,
Team_{n-1} beats Team_{n}, and Team_{n} beats
Team_{j}. In
the shortest case n=0, that is, Team_{i} beats Team_{j}
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.