A printable PDF is available.

# Assignment 5 -- Graph Adjacency Matrix

*Due:
Monday, December 7*

**Objective:** The objective of this assignment is for students
to gain experience working with graphs by implementing the graph class
using an adjacency matrix (rather than the adjacency list used in the
book's implementation).
*This
program is longer and more involved than others assignments in this class, so
this assignment will be graded out of 150 points -- in other words,
it will count one and a half times as much as your previous full
assignments.*

**What To Do:**
This programming assignment comes straight out of the book: Do
Programming Project (exercise) 42, on page 1019. You will be
modifying the book's graph class, and code for that implementation can
be found
here.

Unfortunately, the graphs given in the book do not match the problem
description. The problem asks for the graph to be output twice, and
the graphs that your program should have at that time are drawn in
Figure 16-29 (page 1020). However, it's not clear what the original
input graph is -- it's clearly *not* Figure 16-28(a) as stated
in the problem. Please use the graph below for your original input:

You'll need to encode this in the graph file format used by the book's graph input function.

Note that I'll also test your implementation with different graphs, so please test your implementation thoroughly so that you are confident that your code works correctly in general. My test graphs will have no more than 25 vertices, so it is safe for you to use MAXGRAPHSIZE of 25.

**To Turn In:** Use the `330submit`

program (see
Handout 3)
in order to turn in your code, using assignment name `assign5`

.
On the due date, you should turn in a
printout of your code.

**Sample Input/Output:**

SAMPLE INPUT

*You should create a file containing the input graph shown on the
previous page.*

SAMPLE OUTPUT

Result of breadth-first search from A: A B C D E Graph after first two operations: A: in-degree 1 out-degree 2 Edges: B (4) D (6) B: in-degree 1 out-degree 1 Edges: A (2) D: in-degree 1 out-degree 1 Edges: E (4) E: in-degree 1 out-degree 0 Edges: Final graph: A: in-degree 2 out-degree 2 Edges: B (4) D (6) B: in-degree 1 out-degree 2 Edges: A (2) F (5) F: in-degree 2 out-degree 1 Edges: A (3) D: in-degree 1 out-degree 1 Edges: E (4) E: in-degree 1 out-degree 1 Edges: F (2)