/**CFile****************************************************************
FileName [llb1Matrix.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [BDD based reachability.]
Synopsis [Partition clustering as a matrix problem.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: llb1Matrix.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "llbInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
// 0123 nCols
// +--------------------->
// pi 0 | 111 row0 pRowSums[0]
// pi 1 | 1 11 row1 pRowSums[1]
// pi 2 | 1 11 row2 pRowSums[2]
// CS |1 1
// CS |1 111
// CS |111 111
// int | 11111
// int | 111
// int | 111
// int | 111
// NS | 11 11
// NS | 11 1
// NS | 111
// nRows |
// v
// cccc pColSums[0]
// oooo pColSums[1]
// llll pColSums[2]
// 0123 pColSums[3]
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Verify columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrVerifyRowsAll( Llb_Mtr_t * p )
{
int iRow, iCol, Counter;
for ( iCol = 0; iCol < p->nCols; iCol++ )
{
Counter = 0;
for ( iRow = 0; iRow < p->nRows; iRow++ )
if ( p->pMatrix[iCol][iRow] == 1 )
Counter++;
assert( Counter == p->pColSums[iCol] );
}
}
/**Function*************************************************************
Synopsis [Verify columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrVerifyColumnsAll( Llb_Mtr_t * p )
{
int iRow, iCol, Counter;
for ( iRow = 0; iRow < p->nRows; iRow++ )
{
Counter = 0;
for ( iCol = 0; iCol < p->nCols; iCol++ )
if ( p->pMatrix[iCol][iRow] == 1 )
Counter++;
assert( Counter == p->pRowSums[iRow] );
}
}
/**Function*************************************************************
Synopsis [Verify columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrVerifyMatrix( Llb_Mtr_t * p )
{
Llb_MtrVerifyRowsAll( p );
Llb_MtrVerifyColumnsAll( p );
}
/**Function*************************************************************
Synopsis [Sort variables in the order of removal.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int * Llb_MtrFindVarOrder( Llb_Mtr_t * p )
{
int * pOrder, * pLast;
int i, k, fChanges, Temp;
pOrder = ABC_CALLOC( int, p->nRows );
pLast = ABC_CALLOC( int, p->nRows );
for ( i = 0; i < p->nRows; i++ )
{
pOrder[i] = i;
for ( k = p->nCols - 1; k >= 0; k-- )
if ( p->pMatrix[k][i] )
{
pLast[i] = k;
break;
}
}
do
{
fChanges = 0;
for ( i = 0; i < p->nRows - 1; i++ )
if ( pLast[i] > pLast[i+1] )
{
Temp = pOrder[i];
pOrder[i] = pOrder[i+1];
pOrder[i+1] = Temp;
Temp = pLast[i];
pLast[i] = pLast[i+1];
pLast[i+1] = Temp;
fChanges = 1;
}
}
while ( fChanges );
ABC_FREE( pLast );
return pOrder;
}
/**Function*************************************************************
Synopsis [Returns type of a variable.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
char * Llb_MtrVarName( Llb_Mtr_t * p, int iVar )
{
static char Buffer[10];
if ( iVar < p->nPis )
strcpy( Buffer, "pi" );
else if ( iVar < p->nPis + p->nFfs )
strcpy( Buffer, "CS" );
else if ( iVar >= p->nRows - p->nFfs )
strcpy( Buffer, "NS" );
else
strcpy( Buffer, "int" );
return Buffer;
}
/**Function*************************************************************
Synopsis [Creates one column with vars in the array.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrPrint( Llb_Mtr_t * p, int fOrder )
{
int * pOrder = NULL;
int i, iRow, iCol;
if ( fOrder )
pOrder = Llb_MtrFindVarOrder( p );
for ( i = 0; i < p->nRows; i++ )
{
iRow = pOrder ? pOrder[i] : i;
printf( "%3d : ", iRow );
printf( "%3d ", p->pRowSums[iRow] );
printf( "%3s ", Llb_MtrVarName(p, iRow) );
for ( iCol = 0; iCol < p->nCols; iCol++ )
printf( "%c", p->pMatrix[iCol][iRow] ? '*' : ' ' );
printf( "\n" );
}
ABC_FREE( pOrder );
}
/**Function*************************************************************
Synopsis [Verify columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrPrintMatrixStats( Llb_Mtr_t * p )
{
int iVar, iGrp, iGrp1, iGrp2, Span = 0, nCutSize = 0, nCutSizeMax = 0;
int * pGrp1 = ABC_CALLOC( int, p->nRows );
int * pGrp2 = ABC_CALLOC( int, p->nRows );
for ( iVar = 0; iVar < p->nRows; iVar++ )
{
if ( p->pRowSums[iVar] == 0 )
continue;
for ( iGrp1 = 0; iGrp1 < p->nCols; iGrp1++ )
if ( p->pMatrix[iGrp1][iVar] == 1 )
break;
for ( iGrp2 = p->nCols - 1; iGrp2 >= 0; iGrp2-- )
if ( p->pMatrix[iGrp2][iVar] == 1 )
break;
assert( iGrp1 <= iGrp2 );
pGrp1[iVar] = iGrp1;
pGrp2[iVar] = iGrp2;
Span += iGrp2 - iGrp1;
}
// compute span
for ( iGrp = 0; iGrp < p->nCols; iGrp++ )
{
for ( iVar = 0; iVar < p->nRows; iVar++ )
if ( pGrp1[iVar] == iGrp )
nCutSize++;
if ( nCutSizeMax < nCutSize )
nCutSizeMax = nCutSize;
for ( iVar = 0; iVar < p->nRows; iVar++ )
if ( pGrp2[iVar] == iGrp )
nCutSize--;
}
ABC_FREE( pGrp1 );
ABC_FREE( pGrp2 );
printf( "[%4d x %4d] Life-span =%6.2f Max-cut =%5d\n",
p->nCols, p->nRows, 1.0*Span/p->nRows, nCutSizeMax );
if ( nCutSize )
Abc_Print( -1, "Cut size is not zero (%d).\n", nCutSize );
}
/**Function*************************************************************
Synopsis [Starts the matrix representation.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Llb_Mtr_t * Llb_MtrAlloc( int nPis, int nFfs, int nCols, int nRows )
{
Llb_Mtr_t * p;
int i;
p = ABC_CALLOC( Llb_Mtr_t, 1 );
p->nPis = nPis;
p->nFfs = nFfs;
p->nRows = nRows;
p->nCols = nCols;
p->pRowSums = ABC_CALLOC( int, nRows );
p->pColSums = ABC_CALLOC( int, nCols );
p->pColGrps = ABC_CALLOC( Llb_Grp_t *, nCols );
p->pMatrix = ABC_CALLOC( char *, nCols );
for ( i = 0; i < nCols; i++ )
p->pMatrix[i] = ABC_CALLOC( char, nRows );
// partial product
p->pProdVars = ABC_CALLOC( char, nRows ); // variables in the partial product
p->pProdNums = ABC_CALLOC( int, nRows ); // var counts in the remaining partitions
return p;
}
/**Function*************************************************************
Synopsis [Stops the matrix representation.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrFree( Llb_Mtr_t * p )
{
int i;
ABC_FREE( p->pProdVars );
ABC_FREE( p->pProdNums );
for ( i = 0; i < p->nCols; i++ )
ABC_FREE( p->pMatrix[i] );
ABC_FREE( p->pRowSums );
ABC_FREE( p->pColSums );
ABC_FREE( p->pMatrix );
ABC_FREE( p->pColGrps );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Creates one column with vars in the array.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrAddColumn( Llb_Mtr_t * p, Llb_Grp_t * pGrp )
{
Aig_Obj_t * pVar;
int i, iRow, iCol = pGrp->Id;
assert( iCol >= 0 && iCol < p->nCols );
p->pColGrps[iCol] = pGrp;
Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vIns, pVar, i )
{
iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) );
assert( iRow >= 0 && iRow < p->nRows );
p->pMatrix[iCol][iRow] = 1;
p->pColSums[iCol]++;
p->pRowSums[iRow]++;
}
Vec_PtrForEachEntry( Aig_Obj_t *, pGrp->vOuts, pVar, i )
{
iRow = Vec_IntEntry( pGrp->pMan->vObj2Var, Aig_ObjId(pVar) );
assert( iRow >= 0 && iRow < p->nRows );
p->pMatrix[iCol][iRow] = 1;
p->pColSums[iCol]++;
p->pRowSums[iRow]++;
}
}
/**Function*************************************************************
Synopsis [Matrix reduce.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Llb_MtrRemoveSingletonRows( Llb_Mtr_t * p )
{
int i, k;
for ( i = 0; i < p->nRows; i++ )
if ( p->pRowSums[i] < 2 )
{
p->pRowSums[i] = 0;
for ( k = 0; k < p->nCols; k++ )
{
if ( p->pMatrix[k][i] == 1 )
{
p->pMatrix[k][i] = 0;
p->pColSums[k]--;
}
}
}
}
/**Function*************************************************************
Synopsis [Matrix reduce.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Llb_Mtr_t * Llb_MtrCreate( Llb_Man_t * p )
{
Llb_Mtr_t * pMatrix;
Llb_Grp_t * pGroup;
int i;
pMatrix = Llb_MtrAlloc( Saig_ManPiNum(p->pAig), Saig_ManRegNum(p->pAig),
Vec_PtrSize(p->vGroups), Vec_IntSize(p->vVar2Obj) );
Vec_PtrForEachEntry( Llb_Grp_t *, p->vGroups, pGroup, i )
Llb_MtrAddColumn( pMatrix, pGroup );
// Llb_MtrRemoveSingletonRows( pMatrix );
return pMatrix;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END