// import visualization libraries {
const { Array2DTracer, Layout, LogTracer, Tracer, VerticalLayout, HorizonLayout } = require( 'algorithm-visualizer' );
// }
// define tracer variables {
const matrixTracer = new Array2DTracer( 'A | b (reduce to an upper triangluar matrix, GEPP)' );
const logTracer = new LogTracer( 'Console' );
Layout.setRoot( new VerticalLayout( [ matrixTracer, logTracer ] ) );
// }
const random_range = 3;
const N = 8;
// initialization {
const matrix = [];
for ( let i = 0; i < N; ++i )
{
matrix.push( [] );
for ( let j = 0; j < N; ++j ) matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
matrix[ i ].push( '|' );
matrix[ i ].push( Math.random() * ( 2 * random_range ) - random_range );
matrix[ i ].push( '' );
matrix[ i ].push( '' );
matrix[ i ].push( '' );
}
// }
// visualization {
matrixTracer.set( matrix );
Tracer.delay();
// }
for ( let k = 0; k < N - 1; ++k )
{
// visualization {
logTracer.println( 'Make desired zeros in column ' + k );
// }
let pivot_index = k;
// visualization {
matrixTracer.select( pivot_index, k );
logTracer.println( 'Initial pivot index is ' + pivot_index );
// }
for ( let i = k + 1; i < N; ++i )
{
// visualization {
logTracer.println( 'Compare A[' + pivot_index + '][' + k + '] and A[' + i + '][' + k + ']' );
matrixTracer.select( i, k );
Tracer.delay();
// }
if ( Math.abs( matrix[ pivot_index ][ k ] ) < Math.abs( matrix[ i ][ k ] ) )
{
// visualization {
matrixTracer.deselect( pivot_index, k );
logTracer.println( 'Current pivot index is changed to ' + i );
// }
pivot_index = i;
}
else
{
// visualization {
matrixTracer.deselect( i, k );
logTracer.println( 'Pivot index remains the same' );
// }
}
// visualization {
Tracer.delay();
// }
}
// visualization {
matrixTracer.deselect( pivot_index, k );
// }
if ( pivot_index !== k )
{
// visualization {
logTracer.println( 'Swap row ' + k + ' and row ' + pivot_index );
// }
for ( let i = 0; i < N; ++i )
{
const temporary_swap_value = matrix[ k ][ i ];
matrix[ k ][ i ] = matrix[ pivot_index ][ i ];
matrix[ pivot_index ][ i ] = temporary_swap_value;
// visualization {
matrixTracer.patch( k, i, matrix[ k ][ i ] );
matrixTracer.patch( pivot_index, i, matrix[ pivot_index ][ i ] );
// }
}
const temporary_swap_value = matrix[ k ][ N + 1 ];
matrix[ k ][ N + 1 ] = matrix[ pivot_index ][ N + 1 ];
matrix[ pivot_index ][ N + 1 ] = temporary_swap_value;
// visualization {
matrixTracer.patch( k, N + 1, matrix[ k ][ N + 1 ] );
matrixTracer.patch( pivot_index, N + 1, matrix[ pivot_index ][ N + 1 ] );
Tracer.delay();
for ( let i = 0; i < N; ++i )
{
matrixTracer.depatch( k, i );
matrixTracer.depatch( pivot_index, i );
}
matrixTracer.depatch( k, N + 1 );
matrixTracer.depatch( pivot_index, N + 1 );
// }
}
else
{
// visualization {
logTracer.println( 'There is no need to swap rows' );
Tracer.delay();
// }
}
if ( Math.abs( matrix[ k ][ k ] ) < 1e-6 )
{
// visualization {
Tracer.delay();
logTracer.println( 'The algorithm stops because the pivot value is too small!' );
// }
break;
}
for ( let i = k + 1; i < N; ++i )
{
const multiplier = matrix[ i ][ k ] / matrix[ k ][ k ];
matrix[ i ][ k ] = 0;
// visualization {
matrixTracer.select( i, k );
matrixTracer.select( k, k );
matrixTracer.patch( i, N + 3, 'm =' );
matrixTracer.patch( i, N + 4, multiplier );
logTracer.println( 'm = A[' + i + '][' + k + '] / A[' + k + '][' + k + ']' );
logTracer.println( 'm = ' + multiplier );
Tracer.delay();
matrixTracer.deselect( i, k );
matrixTracer.deselect( k, k );
matrixTracer.depatch( i, N + 3 );
matrixTracer.depatch( i, N + 4 );
matrixTracer.patch( i, k, matrix[ i ][ k ] );
logTracer.println( 'A[' + i + '][' + k + '] = 0' );
Tracer.delay();
matrixTracer.depatch( i, k );
matrixTracer.select( i, N + 4 );
// }
for ( let j = k + 1; j < N; ++j )
{
matrix[ i ][ j ] -= multiplier * matrix[ k ][ j ];
// visualization {
matrixTracer.select( k, j );
matrixTracer.patch( i, j, matrix[ i ][ j ] );
logTracer.println( 'A[' + i + '][' + j + '] = A[' + i + '][' + j + '] - m A[' + k + '][' + j + ']' );
Tracer.delay();
matrixTracer.deselect( k, j );
matrixTracer.depatch( i, j );
// }
}
matrix[ i ][ N + 1 ] -= multiplier * matrix[ k ][ N + 1 ];
// visualization {
matrixTracer.select( k, N + 1 );
matrixTracer.patch( i, N + 1, matrix[ i ][ N + 1 ] );
logTracer.println( 'b[' + i + '] = b[' + i + '] - m b[' + k + ']' );
Tracer.delay();
matrixTracer.deselect( i, N + 4 );
matrixTracer.deselect( k, N + 1 );
matrixTracer.depatch( i, N + 1 );
matrixTracer.patch( i, N + 3, '' );
matrixTracer.patch( i, N + 4, '' );
matrixTracer.depatch( i, N + 3 );
matrixTracer.depatch( i, N + 4 );
// }
}
}