Description
This assignment is about implementing and testing classes for sparse matrix operations. Sparse Matrix/Vector • A sparse matrix/vector holds only the non-zero data but acts as a regular matrix/vector. Basic Elements SparseVector Class • Represents a single dimensional sparse data. • Requirements: – SparseArray : Constructors ∗ Write the required constructors. For example, you need a constructor which takes a string filename data, opens the file, reads the contents, creates and populates an object. – operator+ : Adds two SparseVectors ∗ Usage: sparse_vec_1 + sparse_vec_2. ∗ Creates another SparseVector object. – operator- : Subtracts one SparseVector from another ∗ Similar to operator+ – operator- : Negates elements of a SparseVector ∗ Creates another SparseVector object which is element-by-element negative of the operant. – operator= : Assigns one SparseVector to another ∗ Usage: sparse_vec_1 = sparse_vec_2 – operator<< : Sends contents of a SparseVector to a std::ostream object. ∗ Creates the text representation of a SparseVector and sends it to a std::ostream object. (See Text Representations section for more details) – function dot : Calculates the dot product(inner product) of two SparseVectors ∗ Returns a real number (See Dot Product Section for more details) SparseMatrix Class • Represents a two dimensional sparse data. • Requirements: – SparseMatrix : Constructors. ∗ Similar to SparsVector class description. – operator+ : Adds two matrices ∗ Similar to SparsVector class description. – operator- : Subtracts one matrix from another 1 ∗ Similar to SparsVector class description. – operator- : Negates elements of a matrix ∗ Similar to SparsVector class description. – operator= : Assigns one matrix to another ∗ Similar to SparsVector class description. – operator<< : Sends contents of a SparseMatrix to a std::ostream object. ∗ Similar to SparsVector class description. – operator* : Multiplies two matrices (Regular matrix multiplication) ∗ Similar to SparsVector class description. – function transpose : Returns the transpose of a matrix ∗ Creates another SparseMatrix which is the transpose of the original object. Driver Program • This part describes how you test various operations for the classes you created. • Your classes will be tested by a driver program. The driver program perform various SparseVector and SparseMatrix operations and incrementally fill a file with the changing contents of the objects created • Below is an example driver program.(Not all operations are shown) #include #include #include #include “SparseVector.h” #include “SparseMatrix.h” using namespace std; int main() { ofstream outfile; outfile.open(“output.txt”, ios::out | ios::trunc ); //Creating a SparseVector from file SparseVector a1(“a1.txt”); outfile<<“a1″<<endl<<a1<<endl; //Binary operations and assignment a1 = a1 + a1; outfile<<“a1″<<endl<<a1<<endl; //Creating SparseMatrix from file SparseMatrix m1(“m1.txt”); SparseMatrix m2(“m2.txt”); outfile<<“m2″<<endl<<m2<<endl; //Transpose outfile<<m2.transpose()<<endl; //Dot product outfile<<dot(a1,a1)<<endl; return 0; } 2 Text Representations Text Representation of SparseVector • format: : : :… • index is in ascending order (natural number) • example: 4:23.8 7:10.7 10:34 12:20 1012:5 • For the above example non-zero indices are 4,7,10,12,1012 Text Representation of SparseMatrix • format: : : :… : : :… : : :… . . . • index and row_index are in ascending order (natural numbers) • example: 3 3:24.6 4:5.5 4 1:1.15 8 5:6.4 8:34.1 9:13.1 Dot Product • Dot product of two vectors is a scalar operation • Dot product of vector_1 and vector_2: dot_product = vector_1[0]*vector_2[0] + vector_1[1]*vector_2[1] + vector_1[2]*vector_2[2] + … Transpose • Matrix: : : :… : : :… : : :… . . . • Transpose of the Matrix : : :… : : :… : : :… . . . 3 File I/O File I/O objects are defined in header. In order to write to a file, first wee need to create the file stream object. A file stream object is similar to std::cout. For output, It is type is std::ofstream. This type is derived from std::ostream. //create the file stream object ofstream couttofile; //open the file and associate it with the object couttofile.open(“output.txt”, ios::out | ios::trunc ); //write to stream object couttofile<<“Test”<<endl; couttofile<<“Test2″<<endl; . . . In order to write to a file, first wee need to create the file stream object. A file stream object is similar to std::cin. For input, It is type is std::ifstream. This type is derived from std::istream. //create the file stream object ifstream cinfromfile; //open the file and associate it with the object cinfromfile.open(“input.txt”); //read “12:23.5” from stream object int a; double b; char c; cinfromfile>>a>>c>>b; //in order to read the a line from a file, you can use getline() // function from library. string s; std::getline(cinfromfile, s); //reading lines in a loop //a helper function in order to secure file read operations int check_errors(ifstream* f) { int stop = 0; if (f->eof()) { // EOF after std::getline() is not the criterion to stop processing // data: In case there is data between the last delimiter and EOF, // getline() extracts it and sets the eofbit. stop = 0; } if (f->fail()) { stop = 1; } if (f->bad()) { stop = 1; } return stop; } 4 //Create a string string line; //Create an ifstream object by providing a filename // This opens the file as well ifstream f (“file.txt”); //check if it is open if (f.is_open()) { while(1) { getline(f, line); if (check_errors(&f)) { //skip the data processing and break break; } // This is the actual operation on the data obtained and we want to // protect it from errors during the last IO operation on the stream cout << “data line ” << “: ” << line << endl; } } Remarks • Write comments in your code. • If your code does not compile you will get 0 • Do not share your code with your classmates. Turn in: • “SparseVector.h” • “SparseMatrix.h” • .cpp implementations of classes and everything else you created. • Your code will be compiled according to the following GNU make script • You can also provide your own makefile script • Do not send any IDE specific files. SRC_DIR := . OBJ_DIR := . SRC_FILES := $(wildcard $(SRC_DIR)/*.cpp) OBJ_FILES := $(patsubst $(SRC_DIR)/%.cpp,$(OBJ_DIR)/%.o,$(SRC_FILES)) LDFLAGS := … CPPFLAGS := … CXXFLAGS := … main.out: $(OBJ_FILES) g++ $(LDFLAGS) -o $@ $^ $(OBJ_DIR)/%.o: $(SRC_DIR)/%.cpp g++ $(CPPFLAGS) $(CXXFLAGS) -c -o $@ $< CPPFLAGS += -std=c++11 CXXFLAGS += -MMD -include $(OBJ_FILES:.o=.d) 5 Late Submission • (0,24] hours: -20% • (24,48] hours: -40% • (48,72] hours: -60% • (72,-) hours: -100% 6
