Question

How to compact a sparse matrix in PHP

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.

// Convert a sparse matrix into compact (triplet) form
function compactMatrix($matrix) {
    $rows = count($matrix);
    $cols = count($matrix[0]);

    // Count non-zero elements
    $count = 0;
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($matrix[$i][$j] != 0) {
                $count++;
            }
        }
    }

    // Compact matrix has 3 rows: row index, col index, value
    $compact = [
        array_fill(0, $count, 0),
        array_fill(0, $count, 0),
        array_fill(0, $count, 0)
    ];

    $k = 0;

    // Fill compact matrix
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($matrix[$i][$j] != 0) {
                $compact[0][$k] = $i;            // row
                $compact[1][$k] = $j;            // column
                $compact[2][$k] = $matrix[$i][$j]; // value
                $k++;
            }
        }
    }

    return $compact;
}

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

$compact = compactMatrix($matrix);

echo "Compact matrix:\n";
for ($i = 0; $i < 3; $i++) {
    for ($j = 0; $j < count($compact[0]); $j++) {
        echo $compact[$i][$j] . " ";
    }
    echo "\n";
}

/*
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