
NeoBio API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +neobio.alignment.Smawk
This class implement the SMAWK algorithm to compute column maxima on a totally monotone matrix as described.
This implementation derives from the paper of A.Aggarwal, M.Klawe, S.Moran, P.Shor, and R.Wilber, Geometric Applications of a Matrix Searching Algorithm, Algorithmica, 2, 195208 (1987).
The matrix must be an object that implements the Matrix interface. It is also expected to be totally monotone, and the number of rows should be greater than or equals to the number of columns. If these conditions are not met, the the result is unpredictable and can lead to an ArrayIndexOutOfBoundsException.
computeColumnMaxima
is the main public method of this
class. It computes the column maxima of a given matrix, i.e. the rows that contain the
maximum value of each column in O(n) (linear) time, where n is the number of rows. This
method does not return the maximum values itself, but just the indexes of their
rows.
Note that it is necessary to create an instance of this class to execute the
computeColumnMaxima
because it stores temporary data is that instance. To
prevent problems with concurrent access, the computeColumnMaxima
method is
declared synchronized
.
// create an instance of Smawk Smawk smawk = new Smawk(); // create an array to store the result int col_maxima = new int [some_matrix.numColumns()]; // now compute column maxima smawk.computeColumnMaxima (some_matrix, col_maxima)
Note that the array of column maxima indexes (the computation result) must be created beforehand and its size must be equal to the number of columns of the matrix.
This implementation creates arrays of row and column indexes from the original array and simulates all operations (reducing, deletion of odd columns, etc.) by manipulating these arrays. The benefit is twofold. First the matrix is not required to implement any of these this operations but only a simple method to retrieve a value at a given position. Moreover, it tends to be faster since it uses a manipulation of these small vectors and no row or column is actually deleted. The downside is, of course, the use of extra memory (in practice, however, this is negligible).
Note that this class does not contain a computeRowMaxima
method,
however, the computeColumnMaxima
can easily be used to compute row maxima
by using a transposed matrix interface, i.e. one that inverts the indexes of the
valueAt
method (returning [col,row] when [row,col] is requested) and swaps
the number of rows by the number of columns, and viceversa.
Another simpler method, naiveComputeColumnMaxima
,
does the same job without using the SMAWK algorithm. It takes advantage of the monotone
property of the matrix only (SMAWK explores the stronger constraint of total
monotonicity), and therefore has a worst case time complexity of O(n * m), where n is
the number of rows and m is the number of columns. However, this method tends to be
faster for small matrices because it avoids recursions and row and column
manipulations. There is also a
naiveComputeRowMaxima method to compute row maxima
with the naive approach.
Matrix
Field Summary  
protected int[] 
col
An array of column indexes reflecting the current state of the matrix. 
protected Matrix 
matrix
A pointer to the matrix that is being manipulated. 
protected int 
numcols
The matrix's current number of columns. 
protected int 
numrows
The matrix's current number of rows. 
protected int[] 
row
An array of row indexes reflecting the current state of the matrix. 
protected int[] 
row_position
This array is used to store for each row of the original matrix, its index in the current state of the matrix, i.e. its index in the row array. 
Constructor Summary  
Smawk()

Method Summary  
protected void 
computeColumnMaxima(int[] col_maxima)
This method implements the SMAWK algorithm to compute the column maxima of a given matrix. 
void 
computeColumnMaxima(Matrix matrix,
int[] col_maxima)
Computes the column maxima of a given matrix. 
protected void 
deleteOddColumns()
This method simulates a deletion of odd rows by manipulating the col
array of indexes. 
protected void 
deleteRow(int reduced_rows,
int k)
This method simulates a deletion of a row in the matrix during the reduce operation. 
static void 
naiveComputeColumnMaxima(Matrix matrix,
int[] col_maxima)
This is a simpler method for calculating column maxima. 
static void 
naiveComputeRowMaxima(Matrix matrix,
int[] row_maxima)
This is a simpler method for calculating row maxima. 
protected void 
printMatrix()
Prints the current state of the matrix (reflecting deleted rows and columns) in the standard output. 
static void 
printMatrix(Matrix matrix)
Prints the contents of an object implementing the matrix interface in the standard output. 
protected void 
reduce()
This method is the key component of the SMAWK algorithm. 
protected void 
restoreOddColumns(int original_numcols)
Restores the col array of indexes to the state it was before the
deleteOddColumns method was called. 
protected void 
restoreRows(int original_numrows)
Restores the row array of indexes to the state it was before the
reduce method was called. 
protected int 
valueAt(int r,
int c)
This is a helper method to simplify the call to the valueAt method
of the matrix. 
Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 
protected Matrix matrix
protected int numrows
protected int[] row
protected int[] row_position
row
array.
protected int numcols
protected int[] col
Constructor Detail 
public Smawk()
Method Detail 
public void computeColumnMaxima(Matrix matrix, int[] col_maxima)
computeColumnMaxima
method.
The matrix is required to be an object that implements the Matrix
interface. It is also expected to be totally monotone, and the number of rows
should be greater than or equals to the number of columns. If it is not, the the
result is unpredictable and can lead to an ArrayIndexOutOfBoundsException.
This method does not return the maximum values itself, but just the indexes of their rows. Note that the array of column maxima (the computation result) must be created beforehand and its size must be equal to the number of columns of the matrix.
To prevent problems with concurrent access, this method is declared
synchronized
.
matrix
 the matrix that will have its column maxima computedcol_maxima
 the array of column maxima (indexes of the rows containing
maximum values of each column); this is the computation resultcomputeColumnMaxima(int[])
protected void computeColumnMaxima(int[] col_maxima)
The first step is to reduce the matrix to a quadratic size (if necessary). It
then delete all odd columns and recursively computes column maxima for this matrix.
Finally, using the information computed for the odd columns, it searches for
column maxima of the even columns. The column maxima are progressively stored in
the col_maxima
array (each recursive call will compute a set of
column maxima).
col_maxima
 the array of column maxima (the computation result)protected final int valueAt(int r, int c)
valueAt
method
of the matrix. It returns the value at row r
, column c
.
r
 the row number of the value being retrievedc
 the column number of the value being retrieved
r
, column c
Matrix.valueAt(int, int)
protected void deleteOddColumns()
col
array of indexes. In fact, nothing is deleted, but the indexes are moved to the end
of the array in a way that they can be easily restored by the
restoreOddColumns
method using a reverse approach.
restoreOddColumns(int)
protected void restoreOddColumns(int original_numcols)
col
array of indexes to the state it was before the
deleteOddColumns
method was called. It only needs to know how many
columns there was originally. The indexes that were moved to the end of the array
are restored to their original position.
original_numcols
 the number of columns before the odd ones were deleteddeleteOddColumns()
protected void reduce()
deleteRow
method.
It uses the total monotonicity property of the matrix to identify which rows can safely be deleted.
deleteRow(int, int)
protected void deleteRow(int reduced_rows, int k)
reduce
operation. It just moves the index to the end of the array in a
way that it can be restored afterwards by the restoreRows
method
(nothing is actually deleted). Deleted indexes are kept in ascending order.
reduced_rows
 the current number of rows in the reducing matrixk
 the index of the row to be deletedrestoreRows(int)
protected void restoreRows(int original_numrows)
row
array of indexes to the state it was before the
reduce
method was called. It only needs to know how many rows there
was originally. The indexes that were moved to the end of the array are restored to
their original position.
original_numrows
 the number of rows before the reduction was performeddeleteRow(int, int)
,
reduce()
public static void naiveComputeColumnMaxima(Matrix matrix, int[] col_maxima)
computeColumnMaxima
, but without complexity of the SMAWK algorithm.
The matrix is required to be an object that implements the Matrix
interface. It is also expected to be monotone. If it is not, the result is
unpredictable but, unlike computeColumnMaxima
, it cannot lead to an
ArrayIndexOutOfBoundsException.
This method does not return the maximum values itself, but just the indexes of their rows. Note that the array of column maxima (the computation result) must be created beforehand and its size must be equal to the number of columns of the matrix.
It takes advantage of the monotone property of the matrix only (SMAWK explores the stronger constraint of total monotonicity), and therefore has a worst case time complexity of O(n * m), where n is the number of rows and m is the number of columns. However, this method tends to be faster for small matrices because it avoids recursions and row and column manipulations.
matrix
 the matrix that will have its column maxima computedcol_maxima
 the array of column maxima (indexes of the rows containing
maximum values of each column); this is the computation resultnaiveComputeRowMaxima(neobio.alignment.Matrix, int[])
public static void naiveComputeRowMaxima(Matrix matrix, int[] row_maxima)
The matrix is required to be an object that implements the Matrix
interface. It is also expected to be monotone. If it is not, the result is
unpredictable but, unlike computeColumnMaxima
, it cannot lead to an
ArrayIndexOutOfBoundsException.
This method does not return the maximum values itself, but just the indexes of their columns. Note that the array of row maxima (the computation result) must be created beforehand and its size must be equal to the number of columns of the matrix.
It takes advantage of the monotone property of the matrix only (SMAWK explores the stronger constraint of total monotonicity), and therefore has a worst case time complexity of O(n * m), where n is the number of rows and m is the number of columns. However, this method tends to be faster for small matrices because it avoids recursions and row and column manipulations.
matrix
 the matrix that will have its row maxima computedrow_maxima
 the array of row maxima (indexes of the columns containing
maximum values of each row); this is the computation resultnaiveComputeColumnMaxima(neobio.alignment.Matrix, int[])
protected void printMatrix()
public static void printMatrix(Matrix matrix)
matrix
 a matrix


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 