llb1Matrix.c

Go to the documentation of this file.

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