Question

How to compact a sparse matrix in Pascal

Answer 1

// A sparse matrix is a matrix in which the majority of elements are zero.

// To compact a sparse matrix, use a method to store only the non‑zero
// entries using a triplet representation (row, column, value). 
// This reduces memory usage.

program CompactSparseMatrix;

type
  TIntMatrix = array of array of Integer;

// Convert a sparse matrix into compact (triplet) form
function CompactMatrix(var matrix: TIntMatrix): TIntMatrix;
var
  rows, cols, i, j, count, k: Integer;
  res: TIntMatrix;
begin
  rows := Length(matrix);
  cols := Length(matrix[0]);

  // Count non-zero elements
  count := 0;
  for i := 0 to rows - 1 do
    for j := 0 to cols - 1 do
      if matrix[i][j] <> 0 then
        Inc(count);

  // Compact matrix has 3 rows: row index, col index, value
  SetLength(res, 3);
  SetLength(res[0], count);
  SetLength(res[1], count);
  SetLength(res[2], count);

  k := 0;

  // Fill compact matrix
  for i := 0 to rows - 1 do
    for j := 0 to cols - 1 do
      if matrix[i][j] <> 0 then
      begin
        res[0][k] := i;            // row
        res[1][k] := j;            // column
        res[2][k] := matrix[i][j]; // value
        Inc(k);
      end;

  CompactMatrix := res;
end;

var
  matrix: TIntMatrix;
  compact: TIntMatrix;
  i, j: Integer;

begin
  SetLength(matrix, 5);

  matrix[0] := [0, 0, 3, 0, 8, 0, 0, 0, 0];
  matrix[1] := [0, 0, 5, 7, 0, 0, 1, 0, 0];
  matrix[2] := [0, 0, 0, 0, 0, 0, 0, 0, 0];
  matrix[3] := [0, 2, 6, 0, 0, 4, 0, 0, 0];
  matrix[4] := [0, 0, 0, 0, 9, 0, 0, 0, 0];

  compact := CompactMatrix(matrix);

  WriteLn('Compact matrix:');
  for i := 0 to 2 do
  begin
    for j := 0 to High(compact[0]) do
      Write(compact[i][j], ' ');
    WriteLn;
  end;
end.


(*
run:

Compact matrix:
0 0 1 1 1 3 3 3 4 
2 4 2 3 6 1 2 5 4 
3 8 5 7 1 2 6 4 9 

*)

 

70+ SQL courses for beginners and professionals