Loyola College in Maryland
CS 462 - Algorithm Analysis
Spring 2004
Loyola College >
Department of Computer Science >
Dr. James Glenn >
CS 462 >
Programming Projects >
Project 4 - Graph Algorithms
Due
Tuesday, April 27th 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
- to implement graph algorithms
Assignment
There are three parts to this assignment.
- Build a graph as in Project 3 with the following modification:
the user should be able to select whether edges in opposite directions
cancel each other out. In other words, if X beat Y twice and
Y beat X once, the user should be able to select whether there should
be an edge (X, Y) with weight 2 and an edge (Y, X) or only an
single edge (X, Y). In general, when using the new option,
if team X beat team Y a times and lost b times then if a > b there
is an edge (X, Y) of weight (a - b); if a < b there is an edge
(Y, X) of weight (b - a); and if a = b there is no edge between
X and Y.
- Display the strongly connected components of the graph built in
the first step.
- For an pairs of teams given as input, display a path from the
first team to the second team.
Much of what you need is already present in your Graph class.
You may, of course, add new methods as you require them.
Input and Output
Input will come in three sections:
- one line with "cancel" to indicate that edges in opposote directions
should cancel each other out or "no cancel" otherwise;
- input for results of games (winner followed by loser on separate lines
just like in project 3) followed by a blank line
- a list of pairs of teams to connect, listed as source and destination
on separate lines.
So if the input is
no cancel
Virginia
Maryland
Virginia
Duke
Maryland
Duke
Virginia
Duke
Maryland
Wake Forest
Wake Forest
Maryland
Maryland
North Carolina
Virginia
North Carolina
Duke
Virginia
then the output should be
--- COMPONENT 1 ---
Virginia
--- COMPONENT 2 ---
Maryland
Wake Forest
--- COMPONENT 3 ---
North Carolina
--- COMPONENT 4 ---
Duke
Virginia
Maryland
North Carolina
Duke over Virginia is impossible
Files
2003-4 NCAA Division I Men's Basketball
Grading
For full credit, your code must:
- have reasonable asymptotic running times; and
- not create memory leaks.
Submissions
Submit all source code files necessary to build your code in a tar file
(preferably compressed).