CMSC 341 Fall 2006

Project 2

Assigned  27 Sept 2006
Due 10 Oct 2006, 11:42pm
Updates 05 Oct To avoid complex code when reading the data files for the matrices, we now promise that the data files WILL NOT contain comments. This allows you to use operator>> for data file input

02 Oct In the descriptions of SMRowBegin, SMRowEnd, SMColumnBegin, and SMColumnEnd, the use of "row" and "column" was incorrect. These descriptions have been updated.


Background

A matrix is a set of values arranged in rows and columns.&nsp; Matrices are used in many fields of mathematics including linear algebra. In that application, the values represent the coefficients of the terms of many simultaneous equations. In some applications, most of the values in the matrix are zero. Such a matrix is known as a "sparse" matrix since it has few non-zero values. Because there are few non-zero values, programs which implement sparse matrices do not use the usual 2-dimensional array -- to do so would be a large waste of memory. Instead, sparse matrices are implemented with other data structures whose structure is hidden by the implementation of the matrix operations.

Description

In this project, you will implement a sparse matrix class (SMatrix) using the author's List code as a starting point. You will also create an SMatrixData class as well as iterators for the SMatrix.
You must implement the SMatrix ADT as a sorted linked list Code for the textbook's linked list and linked list iterator classes is provided. You are free to use this code if you wish. You must create your own Makefile for this project as well.

The ADTs described here are expanded on in the "ADT" section, below. Use these expanded versions to design your classes. Please remember that you must provide good documentation as described in the "Project Organization" handout.

Here are your tasks:

  1. Read and understand the List and related iterator code described in the text and discussed in class. Code for the textbook's double linked list and linke list iterator classes is available in the public directory.

  2. /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2
  3. Implement the SMatrixData ADT described below. This class stores the 0-base row number, 0-based column number, and the value for each non-zero element of the matrix.
  4. Implement the SMatrix ADT described below. This ADT must throw exceptions when operations are attempted on incompatible SMatrix objects.
  5. Define and implement the necessary exception classes in P2Exceptions.h which is #included in Proj2.cpp.
  6. Implement the functions required by main( ) in Proj2_aux.cpp. Put their prototypes in Proj2_aux.h which is #included in Proj2.cpp. As in project 1, we are providing main( ) in Proj2.cpp which is found in the directory
    /afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2

    In this program, main( ) takes three parameters -- the names of files which contain the data from which to construct three sparse matrices. The format of these files is specified below.

  7. Copy the file
    /afs/umbc.edu/users/d/e/dennispub/CMSC341/Proj2/341-Fall06-proj2_questions.txt

    to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it is 10% of this project's grade.

  8. Write a makefile for project 2.

ADT Definitions

The following ADTs must be implemented for this project. In some instances, the implementation of the ADT is partially specified.
You may add whatever private data and methods you deem appropriate for any class. You may assume that the SMatrix (and therefore the SMatrixData class) will only be used for integers. Therefore, you need not implement these classes as templates.

The SMatrix ADT

A sparse matrix is a set of values arranged in rows and columns, but in which the vast majority are zero. The sparse matrix supports all the usual matrix operations. To easily implement these functions, the data in the SMatrix should be sorted by row, then column within row (or vice-versa, your choice).

Your SMatrix class MUST be implemented using a single, sorted LIST of SMatrixData objects (described below) and use SMatrix row and column iterators to traverse the matrix to perform the matrix operations defined above.

Feel free to delete any unused code in List.h and to improve the author's code by adding appropriate error checking.

The public operations allowed on the SMatrix ADT are:

Warning/Hint/Alert:
Think very carefully about
  1. How these iterators are related to the underlying List iterators
  2. Possible/Necessary use of friendship. In the author's linked list, the List is a friend of the itertors. Depending on your implementation, more friendship may be necessary.
  3. What "beginning of row", "end of row", "beginning of column", and "end of column" mean, especially considering that some rows and/or columns may contain all zeros.
  4. How can an iterator call methods of the matrix that created it?

The SMatrixData ADT

Because the data for the sparse matrix is not stored in a 2-dimensional array, the row and column information for each non-zero value must be specified and stored in matrix. SMatrixData contains the row, column and non-zero value for a single entry in the matrix.

Since only the SMatrix class should be creating SMatrixData objects, the SMatrixData definition must be nested within the SMatrix. As with the nested Node in the linked list, SMatrixData may be implemented as a struct rather than a class. You may implement any methods of SMatrixData you feel are necessary.

The output format for an SMatrixData object is [row, column, value ] as shown in the sample output.

The SMatrix Iterator ADTs

Iterators are used with any data structure if it is necessary to access the individual elements of that data structure.
In the case of the SMatrix class, it is necessary to access the individual elements two ways. One way is starting at (row 0, column 0), and moving along the row (across the columns) to (row 0, column 1), (row 0, column 2), .... to (row 0, column N-1). It is also necessary to have an iterator that starts at (row 0, column 0) and moves down the column (across the rows) to (row 1, column 0), (row 2, column 0), ... to (row M-1, column 0). This column iterator might be used in operator * (matrix multiplication).
These iterators are referred to as SMColumnIter and SMRowIter, respectively.

You are not required to completely implement both "const" and "non-const" versions of these iterators. Implement only as much as needed for your project.

As iterators, these ADTs support the generic iterator methods described in class:

Exceptions in Project 2

Since some SMatrix operations are invalid unless the matrices are compatible, these methods must detect this incompatibility and throw an exception when it occurs. These exceptions are then caught in main( ) and the appropriate action is taken.

In this project, will implement MatrixAddException and MatrixMultiplyException which are caught in main( ). Both exceptions must support the public what( ) which prints an appropriate method. (Note that what( ) is a standard method for all STL exceptions). These exceptions should be implemented in a file named P2Exceptions.h which is #included in Proj2.cpp.

If you wish to add more exceptions in this project, you may do so.


Proj2_aux.cpp

As in project 1, we are providing main( ) in Proj2.cpp in Mr. Frey's public driectory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/Proj2

As in project 1, this file should not be copied to your directory and should not be modified. Your makefile should reference this file. Do not submit Proj2.cpp.

Note that main( ) calls functions which are not found in Proj2.cpp. You must provide these functions in Proj2_aux.cpp and provide their prototypes in Proj2_aux.h which is #included in Proj2.cpp.



Sparse Matrix Data Files

Project 2 will be executed with three (3) command line arguments which are the names of files that contain the sparse matrix data. If the files can be opened, you may assume the data follows the format specified below. The row/column/value triples will be randomly generated. NO ORDERING of the data should be assumed, but you may assume the zero-based row and column numbers are valid. As in project 1, the data files may contain blank lines and/or comments (whose first character is '#'). These lines should be ignored.

Matrix Operations

For those who have not taken MATH 221 yet, or have simply forgotten, this section gives a brief explanation of matrix addition and multiplication.

Matrix Addition

Two matricies may be added if and only if they have the same dimensions (number of rows and columns). To add the matrices, simply add the corresponding elements of each matrix. The resulting matrix will be the same size as the matrices added together. The example belows shows the addition of two 2 X 3 matrices.
             Matrix A    Matrix B       Sum
            ---------   ---------    ---------
             4  6  8     3  0  0      7  6  8
            12  0 -3     2  0  7     14  0  4

Matrix Multiplication

Two matrices can be multiplied if and only if the number of columns of the left hand matrix is the same as the number of rows of the right hand matrix. For example, you can multiply a 3 x 4 matrix with a 4 X 2 matrix (the result is a 3 X 2 matrix), but you can't multiply a 3 X 4 matrix with a 2 X 4 matrix.
Consider the following example which multiplies the 2 X 3 matrix on the left with the 3 X 2 matrix on the right, resulting in the 2 X 2 matrix below Each element is labelled with its row and column number.
             Matrix A      Matrix B
            -----------   ---------
            a11 a12 a13   b11   b12
            a21 a22 a23   b21   b22
                          b31   b32


                             Matrix A * Matrix B (2 x 2)
            ----------------------------------------------------------
            a11*b11 + a12*b21 + a13*b31     a11*b12 + a12*b22+ a13*b32
            a21*b11 + a22*b21 + a13*b31     a21*b12 + a22*b22+ a23*b32

To form the product, we multiply the elements of each of matrix A's rows with the corresponding elements of each of matrix B's columns and sum the product of each element-wise multiplication.


Sample Output

A Matrix should be output by rows. Each non-zero value of the row is output in the form [row, column, value].
For example, this 3 x 3 matrix
         3 x 3 Matrix
         ------------
         12    0    7
          0    4    0
          0    0    3
would be output as
     [0, 0, 12]
     [0, 2, 7]
     [1, 1, 4]
     [2, 2, 3]
Putting multiple non-zero values for the same row on the same line will help keep your output shorter, but is not required. DO NOT mix data from different rows on the same line.


What to Submit

For this project, you must submit the following files:
  1. Your makefile -- it must be named "makefile" or "Makefile". The graders will simply type "make" and your file must compile and link all source files as appropriate
  2. Proj2_aux.cpp which contains the functions called from main( )
  3. SMatrix.h (and SMatrix.cpp if used) -- the definition and implementation file for the SMatrix class. Because they are tightly related, SMatrixRowIter, SMatrixColumnItr, and SMatrixData may also be defined and implemented in this file (as in the text and discussed in class).
  4. P2Exceptions.h which contains the exceptions caught in main( ) and any other exceptions you deem necessary.
  5. Your answers to the project questions.


Grading and Academic Integrity


Project grading is described in the Project Policy handout.

Your answers to 341-Fall06-proj2_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after the due date will not be accepted. Do not submit any files
after that time.