Project 4

CS1118-99 Discrete Structure of Computer Science, Fall 2010

Due 11:55pm Sunday Dec. 12th. (15 points)

Purpose:

 The purpose of this project is to help understanding how adjacency matrix is used to represent a graph.

Problem:

 Given an adjacency matrix of an undirected graph, list the edges of this graph and give the number of times each edge appears.  Please keep in mind that the matrix for an undirected graph is symmetric with respect to the diagonal line.
Problem Details:

  1. Design an algorithm to solve the problem.

  2. Translate the algorithm into a program. 

  3. Test the program with the following adjacency matrix.  Please note you can write a subroutine to read the matrix from the keyboard or hard code it.  If you choose to hard code it, you must make sure your program works for general cases.  Otherwise, the program will not receive credits.  For testing purpose, it might be a good idea toe hard code the matrix while testing your program unless you are familiar with file processing in the language you are using.

    Adjacency Matrix 1

    0 1 1 1
    1 0 1 0
    1 1 0 0
    1 0 0 0
    Output:

    u1-u2, 1
    u1-u3, 1
    u1-u4, 1
    u2-u3, 1

    Adjacency Matrix 2

    0 3 0 2
    3 0 1 1
    0 1 1 2
    2 1 2 0
    Output:

    u1-u2, 3
    u1-u4, 2
    u2-u3, 1
    u2-u4, 1
    u3-u3, 1
    u3-u4, 2

  4. Make sure to include basic documentation in your program: your name, date, class, project title, and the purpose of the program.
What to submit: Your source code.