SE Computer Engineering Practical 17 solution

SE Computer Engineering Practical 17 solution

Question:

Write a python program for sparse matrix realization and operations on it- Transpose, Fast Transpose and addition of two matrices

Code:

class SparseMatrix:
   def __init__(self, matrix):
       self.matrix = matrix
       self.rows = len(matrix)
       self.cols = len(matrix[0])
       self.sparse = self.convert_to_sparse()

   def convert_to_sparse(self):
       sparse = []
       for i in range(self.rows):
           for j in range(self.cols):
               if self.matrix[i][j] != 0:
                   sparse.append([i, j, self.matrix[i][j]])
       return sparse

   def transpose(self):
       transposed_sparse = [[0, 0, 0] for _ in range(len(self.sparse))]
       for i in range(len(self.sparse)):
           transposed_sparse[i][0] = self.sparse[i][1]
           transposed_sparse[i][1] = self.sparse[i][0]
           transposed_sparse[i][2] = self.sparse[i][2]
       return transposed_sparse

   @staticmethod
   def display_sparse_matrix(sparse_matrix):
       for row in sparse_matrix:
           print(row)

   @staticmethod
   def fast_transpose(sparse_matrix):
       col_count = [0] * len(sparse_matrix[0])
       starting_pos = [0] * len(sparse_matrix[0])
       result = [[0, 0, 0] for _ in range(len(sparse_matrix))]
       for i in range(len(sparse_matrix)):
           col_count[sparse_matrix[i][1]] += 1

       starting_pos[0] = 0
       for i in range(1, len(sparse_matrix[0])):
           starting_pos[i] = starting_pos[i - 1] + col_count[i - 1]

       for i in range(len(sparse_matrix)):
           col = sparse_matrix[i][1]
           pos = starting_pos[col]
           result[pos][0] = sparse_matrix[i][1]
           result[pos][1] = sparse_matrix[i][0]
           result[pos][2] = sparse_matrix[i][2]
           starting_pos[col] += 1

       return result

   @staticmethod
   def add_matrices(matrix1, matrix2):
       result = []
       i, j = 0, 0
       while i < len(matrix1) and j < len(matrix2):
           if matrix1[i][0] == matrix2[j][0] and matrix1[i][1] == matrix2[j][1]:
               result.append([matrix1[i][0], matrix1[i][1], matrix1[i][2] + matrix2[j][2]])
               i += 1
               j += 1
           elif matrix1[i][0] < matrix2[j][0] or (matrix1[i][0] == matrix2[j][0] and matrix1[i][1] < matrix2[j][1]):
               result.append([matrix1[i][0], matrix1[i][1], matrix1[i][2]])
               i += 1
           else:
               result.append([matrix2[j][0], matrix2[j][1], matrix2[j][2]])
               j += 1

       while i < len(matrix1):
           result.append([matrix1[i][0], matrix1[i][1], matrix1[i][2]])
           i += 1

       while j < len(matrix2):
           result.append([matrix2[j][0], matrix2[j][1], matrix2[j][2]])
           j += 1

       return result


# Creating Sparse Matrix
matrix1 = [
   [1, 0, 0, 0],
   [0, 2, 0, 0],
   [0, 0, 0, 3]
]

matrix2 = [
   [0, 4, 0, 0],
   [0, 0, 5, 0],
   [6, 0, 0, 0]
]

# Initialize SparseMatrix objects
sparse_matrix1 = SparseMatrix(matrix1)
sparse_matrix2 = SparseMatrix(matrix2)

# Transpose of sparse_matrix1
print("Transpose of sparse_matrix1:")
transpose1 = sparse_matrix1.transpose()
SparseMatrix.display_sparse_matrix(transpose1)

# Fast Transpose of sparse_matrix2
print("\nFast Transpose of sparse_matrix2:")
fast_transpose2 = SparseMatrix.fast_transpose(sparse_matrix2.sparse)
SparseMatrix.display_sparse_matrix(fast_transpose2)

# Addition of sparse_matrix1 and sparse_matrix2
print("\nAddition of sparse_matrix1 and sparse_matrix2:")
addition = SparseMatrix.add_matrices(sparse_matrix1.sparse, sparse_matrix2.sparse)
SparseMatrix.display_sparse_matrix(addition)

Output:

Transpose of sparse_matrix1:
[0, 0, 1]
[1, 1, 2]
[3, 2, 3]

Fast Transpose of sparse_matrix2:
[0, 2, 6]
[1, 0, 4]
[2, 1, 5]

Addition of sparse_matrix1 and sparse_matrix2:
[0, 0, 1]
[0, 1, 4]
[1, 1, 2]
[1, 2, 5]
[2, 0, 6]
[2, 3, 3]

Process finished with exit code 0

Explanation:

In this program, we define a SparseMatrix class that represents a sparse matrix. The class takes a 2D matrix as input and converts it into a sparse matrix format using a list of lists. The matrix is represented as a list of tuples, where each tuple contains the row index, column index, and the non-zero value.

The SparseMatrix class provides methods for:

• convert_to_sparse: Converts a given matrix into a sparse matrix format.
• transpose: Transposes the sparse matrix.
• display_sparse_matrix: Displays a sparse matrix in a readable format.
• fast_transpose: Performs a fast transpose operation on a sparse matrix.
• add_matrices: Adds two sparse matrices.

The program creates two example matrices matrix1 and matrix2 and initializes SparseMatrix objects sparse_matrix1 and sparse_matrix2. It then demonstrates the transpose operation, fast transpose operation, and addition of the two sparse matrices. The results are displayed using the display_sparse_matrix method.