llb1Matrix.c File Reference

#include "llbInt.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START void	Llb_MtrVerifyRowsAll (Llb_Mtr_t *p)
	DECLARATIONS ///. More...
void	Llb_MtrVerifyColumnsAll (Llb_Mtr_t *p)
void	Llb_MtrVerifyMatrix (Llb_Mtr_t *p)
int *	Llb_MtrFindVarOrder (Llb_Mtr_t *p)
char *	Llb_MtrVarName (Llb_Mtr_t *p, int iVar)
void	Llb_MtrPrint (Llb_Mtr_t *p, int fOrder)
void	Llb_MtrPrintMatrixStats (Llb_Mtr_t *p)
Llb_Mtr_t *	Llb_MtrAlloc (int nPis, int nFfs, int nCols, int nRows)
void	Llb_MtrFree (Llb_Mtr_t *p)
void	Llb_MtrAddColumn (Llb_Mtr_t *p, Llb_Grp_t *pGrp)
void	Llb_MtrRemoveSingletonRows (Llb_Mtr_t *p)
Llb_Mtr_t *	Llb_MtrCreate (Llb_Man_t *p)

Function Documentation

void Llb_MtrAddColumn	(	Llb_Mtr_t *	p,
		Llb_Grp_t *	pGrp
	)

Function*************************************************************

Synopsis [Creates one column with vars in the array.]

Description []

SideEffects []

SeeAlso []

Definition at line 346 of file llb1Matrix.c.

{
    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]++;
    }
}

Llb_Mtr_t* Llb_MtrAlloc	(	int	nPis,
		int	nFfs,
		int	nCols,
		int	nRows
	)

Function*************************************************************

Synopsis [Starts the matrix representation.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file llb1Matrix.c.

{
    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;
}

Llb_Mtr_t* Llb_MtrCreate

(

Llb_Man_t *

p

)

Function*************************************************************

Synopsis [Matrix reduce.]

Description []

SideEffects []

SeeAlso []

Definition at line 410 of file llb1Matrix.c.

{
    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;
}

int* Llb_MtrFindVarOrder

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Sort variables in the order of removal.]

Description []

SideEffects []

SeeAlso []

Definition at line 132 of file llb1Matrix.c.

{
    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;
}

void Llb_MtrFree

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Stops the matrix representation.]

Description []

SideEffects []

SeeAlso []

Definition at line 321 of file llb1Matrix.c.

{
    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 );
}

void Llb_MtrPrint	(	Llb_Mtr_t *	p,
		int	fOrder
	)

Function*************************************************************

Synopsis [Creates one column with vars in the array.]

Description []

SideEffects []

SeeAlso []

Definition at line 206 of file llb1Matrix.c.

{
    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 );
}

void Llb_MtrPrintMatrixStats

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Verify columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 236 of file llb1Matrix.c.

{
    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 );
}

void Llb_MtrRemoveSingletonRows

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Matrix reduce.]

Description []

SideEffects []

SeeAlso []

Definition at line 381 of file llb1Matrix.c.

{
    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]--;
                }
            }
        }
}

char* Llb_MtrVarName	(	Llb_Mtr_t *	p,
		int	iVar
	)

Function*************************************************************

Synopsis [Returns type of a variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 181 of file llb1Matrix.c.

{
    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;
}

void Llb_MtrVerifyColumnsAll

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Verify columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file llb1Matrix.c.

{
    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] );
    }
}

void Llb_MtrVerifyMatrix

(

Llb_Mtr_t *

p

)

Function*************************************************************

Synopsis [Verify columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 115 of file llb1Matrix.c.

{
    Llb_MtrVerifyRowsAll( p );
    Llb_MtrVerifyColumnsAll( p );
}

ABC_NAMESPACE_IMPL_START void Llb_MtrVerifyRowsAll

(

Llb_Mtr_t *

p

)

DECLARATIONS ///.

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

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Verify columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 67 of file llb1Matrix.c.

{
    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] );
    }
}