saigIsoFast.c File Reference

#include "saig.h"

Go to the source code of this file.

Data Structures
struct	Iso_Dat_t_
struct	Iso_Dat2_t_
struct	Iso_Sto_t_

Macros
#define	AIG_ISO_NUM   16
	DECLARATIONS ///. More...

Typedefs
typedef struct Iso_Dat_t_	Iso_Dat_t
typedef struct Iso_Dat2_t_	Iso_Dat2_t
typedef struct Iso_Sto_t_	Iso_Sto_t

Functions
Iso_Sto_t *	Iso_StoStart (Aig_Man_t *pAig)
	FUNCTION DEFINITIONS ///. More...
void	Iso_StoStop (Iso_Sto_t *p)
void	Iso_StoCollectInfo_rec (Aig_Man_t *p, Aig_Obj_t *pObj, int fCompl, Vec_Int_t *vVisited, Iso_Dat_t *pData, Vec_Ptr_t *vRoots)
Vec_Int_t *	Iso_StoCollectInfo (Iso_Sto_t *p, Aig_Obj_t *pPo)
int	Iso_StoCompareVecInt (Vec_Int_t **p1, Vec_Int_t **p2)
Vec_Vec_t *	Saig_IsoDetectFast (Aig_Man_t *pAig)

Macro Definition Documentation

#define AIG_ISO_NUM   16

DECLARATIONS ///.

CFile****************************************************************

FileName [aigIsoFast.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Graph isomorphism package.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id:

aigIsoFast.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

]

Definition at line 30 of file saigIsoFast.c.

Typedef Documentation

typedef struct Iso_Dat2_t_ Iso_Dat2_t

Definition at line 44 of file saigIsoFast.c.

typedef struct Iso_Dat_t_ Iso_Dat_t

Definition at line 32 of file saigIsoFast.c.

typedef struct Iso_Sto_t_ Iso_Sto_t

Definition at line 50 of file saigIsoFast.c.

Function Documentation

Vec_Int_t* Iso_StoCollectInfo	(	Iso_Sto_t *	p,
		Aig_Obj_t *	pPo
	)

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

Synopsis [Collect statistics about one output.]

Description []

SideEffects []

SeeAlso []

Definition at line 176 of file saigIsoFast.c.

{
    int fVerboseShow = 0;
    Vec_Int_t * vInfo;
    Iso_Dat2_t * pData2 = (Iso_Dat2_t *)p->pData;
    Aig_Man_t * pAig = p->pAig;
    Aig_Obj_t * pObj;
    int i, Value, Entry, * pPerm;
//    abctime clk = Abc_Clock();

    assert( Aig_ObjIsCo(pPo) );

    // collect initial POs
    Vec_IntClear( p->vVisited );
    Vec_PtrClear( p->vRoots );
    Vec_PtrPush( p->vRoots, pPo );

    // mark internal nodes
    Vec_PtrForEachEntry( Aig_Obj_t *, p->vRoots, pObj, i )
        if ( !Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) )
            Iso_StoCollectInfo_rec( pAig, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), p->vVisited, p->pData, p->vRoots );
//    time_Trav += Abc_Clock() - clk;

    // count how many times each data entry appears
    Vec_IntClear( p->vPlaces );
    Vec_IntForEachEntry( p->vVisited, Entry, i )
    {
        Value = pData2[Entry].Data;
//        assert( Value > 0 );
        if ( p->pCounters[Value]++ == 0 )
            Vec_IntPush( p->vPlaces, Value );
//        pData2[Entry].Data = 0;
        *((int *)(p->pData + Entry)) = 0;
    }

    // collect non-trivial counters
    Vec_IntClear( p->vVisited );
    Vec_IntForEachEntry( p->vPlaces, Entry, i )
    {
        assert( p->pCounters[Entry] );
        Vec_IntPush( p->vVisited, p->pCounters[Entry] );
        p->pCounters[Entry] = 0;
    }
//    printf( "%d ", Vec_IntSize(p->vVisited) );

    // sort the costs in the increasing order
    pPerm = Abc_MergeSortCost( Vec_IntArray(p->vVisited), Vec_IntSize(p->vVisited) );
    assert( Vec_IntEntry(p->vVisited, pPerm[0]) <= Vec_IntEntry(p->vVisited, pPerm[Vec_IntSize(p->vVisited)-1]) );

    // create information
    vInfo = Vec_IntAlloc( Vec_IntSize(p->vVisited) );
    for ( i = Vec_IntSize(p->vVisited)-1; i >= 0; i-- )
    {
        Entry = Vec_IntEntry( p->vVisited, pPerm[i] );
        Entry = (Entry << AIG_ISO_NUM) | Vec_IntEntry( p->vPlaces, pPerm[i] );
        Vec_IntPush( vInfo, Entry );
    }
    ABC_FREE( pPerm );

    // show the final result
    if ( fVerboseShow )
    Vec_IntForEachEntry( vInfo, Entry, i )
    {
        Iso_Dat2_t Data = { Entry & 0xFFFF };
        Iso_Dat_t * pData = (Iso_Dat_t *)&Data;

        printf( "%6d : ", i );
        printf( "Freq =%6d ", Entry >> 16 );

        printf( "FiNeg =%3d ", pData->nFiNeg );
        printf( "FoNeg =%3d ", pData->nFoNeg );
        printf( "FoPos =%3d ", pData->nFoPos );
        printf( "Fi0L  =%3d ", pData->Fi0Lev );
        printf( "Fi1L  =%3d ", pData->Fi1Lev );
        printf( "Lev   =%3d ", pData->Level  );
        printf( "\n" );
    }
    return vInfo;
}

void Iso_StoCollectInfo_rec	(	Aig_Man_t *	p,
		Aig_Obj_t *	pObj,
		int	fCompl,
		Vec_Int_t *	vVisited,
		Iso_Dat_t *	pData,
		Vec_Ptr_t *	vRoots
	)

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

Synopsis [Collect statistics about one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file saigIsoFast.c.

{
    Iso_Dat_t * pThis = pData + Aig_ObjId(pObj);
    assert( Aig_ObjIsCi(pObj) || Aig_ObjIsNode(pObj) );
    if ( pThis->fVisit )
    {
        if ( fCompl )
            pThis->nFoNeg++;
        else
            pThis->nFoPos++;
        return;
    }
    assert( *((int *)pThis) == 0 );
    pThis->fVisit = 1;
    if ( fCompl )
        pThis->nFoNeg++;
    else
        pThis->nFoPos++;
    pThis->Level = pObj->Level;
    pThis->nFiNeg = Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
    if ( Aig_ObjIsNode(pObj) )
    {
        if ( Aig_ObjFaninC0(pObj) < Aig_ObjFaninC1(pObj) || (Aig_ObjFaninC0(pObj) == Aig_ObjFaninC1(pObj) && Aig_ObjFanin0(pObj)->Level < Aig_ObjFanin1(pObj)->Level) )
        {
            pThis->Fi0Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
            pThis->Fi1Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
        }
        else
        {
            pThis->Fi0Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
            pThis->Fi1Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
        }
        Iso_StoCollectInfo_rec( p, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), vVisited, pData, vRoots );
        Iso_StoCollectInfo_rec( p, Aig_ObjFanin1(pObj), Aig_ObjFaninC1(pObj), vVisited, pData, vRoots );
    }
    else if ( Saig_ObjIsLo(p, pObj) )
    {
        pThis->Fi0Lev = 1;
        pThis->Fi1Lev = 0;
        Vec_PtrPush( vRoots, Saig_ObjLoToLi(p, pObj) );
    }
    else if ( Saig_ObjIsPi(p, pObj) )
    {
        pThis->Fi0Lev = 0;
        pThis->Fi1Lev = 0;
    }
    else
        assert( 0 );
    assert( pThis->nFoNeg + pThis->nFoPos );
    Vec_IntPush( vVisited, Aig_ObjId(pObj) );
}

int Iso_StoCompareVecInt	(	Vec_Int_t **	p1,
		Vec_Int_t **	p2
	)

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

Synopsis [Takes multi-output sequential AIG.]

Description [Returns candidate equivalence classes of POs.]

SideEffects []

SeeAlso []

Definition at line 267 of file saigIsoFast.c.

{
    return Vec_IntCompareVec( *p1, *p2 );
}

Iso_Sto_t* Iso_StoStart

(

Aig_Man_t *

pAig

)

FUNCTION DEFINITIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 77 of file saigIsoFast.c.

{
    Iso_Sto_t * p;
    p = ABC_CALLOC( Iso_Sto_t, 1 );
    p->pAig      = pAig;
    p->nObjs     = Aig_ManObjNumMax( pAig );
    p->pData     = ABC_CALLOC( Iso_Dat_t, p->nObjs );
    p->vVisited  = Vec_IntStart( 1000 );
    p->vPlaces   = Vec_IntStart( 1000 );
    p->vRoots    = Vec_PtrStart( 1000 );
    p->pCounters = ABC_CALLOC( int, (1 << AIG_ISO_NUM) );
    return p;
}

void Iso_StoStop

(

Iso_Sto_t *

p

)

Definition at line 90 of file saigIsoFast.c.

{
    Vec_IntFree( p->vPlaces );
    Vec_IntFree( p->vVisited );
    Vec_PtrFree( p->vRoots );
    ABC_FREE( p->pCounters );
    ABC_FREE( p->pData );
    ABC_FREE( p );
}

Vec_Vec_t* Saig_IsoDetectFast

(

Aig_Man_t *

pAig

)

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

Synopsis [Takes multi-output sequential AIG.]

Description [Returns candidate equivalence classes of POs.]

SideEffects []

SeeAlso []

Definition at line 283 of file saigIsoFast.c.

{
    Iso_Sto_t * pMan;
    Aig_Obj_t * pObj;
    Vec_Ptr_t * vClasses, * vInfos;
    Vec_Int_t * vInfo, * vPrev, * vLevel;
    int i, Number, nUnique = 0;
    abctime clk = Abc_Clock();

    // collect infos and remember their number
    pMan = Iso_StoStart( pAig );
    vInfos = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
    Saig_ManForEachPo( pAig, pObj, i )
    {
        vInfo = Iso_StoCollectInfo(pMan, pObj);
        Vec_IntPush( vInfo, i );
        Vec_PtrPush( vInfos, vInfo );
    }
    Iso_StoStop( pMan );
    Abc_PrintTime( 1, "Info computation time", Abc_Clock() - clk );

    // sort the infos
    clk = Abc_Clock();
    Vec_PtrSort( vInfos, (int (*)(void))Iso_StoCompareVecInt );

    // create classes
    clk = Abc_Clock();
    vClasses = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
    // start the first class
    Vec_PtrPush( vClasses, (vLevel = Vec_IntAlloc(4)) );
    vPrev = (Vec_Int_t *)Vec_PtrEntry( vInfos, 0 );
    Vec_IntPush( vLevel, Vec_IntPop(vPrev) );
    // consider other classes
    Vec_PtrForEachEntryStart( Vec_Int_t *, vInfos, vInfo, i, 1 )
    {
        Number = Vec_IntPop( vInfo );
        if ( Vec_IntCompareVec(vPrev, vInfo) )
            Vec_PtrPush( vClasses, Vec_IntAlloc(4) );
        vLevel = (Vec_Int_t *)Vec_PtrEntryLast( vClasses );
        Vec_IntPush( vLevel, Number );
        vPrev = vInfo;
    }
    Vec_VecFree( (Vec_Vec_t *)vInfos );
    Abc_PrintTime( 1, "Sorting time", Abc_Clock() - clk );
//    Abc_PrintTime( 1, "Traversal time", time_Trav );

    // report the results
//    Vec_VecPrintInt( (Vec_Vec_t *)vClasses );
    printf( "Devided %d outputs into %d cand equiv classes.\n", Saig_ManPoNum(pAig), Vec_PtrSize(vClasses) );

    Vec_PtrForEachEntry( Vec_Int_t *, vClasses, vLevel, i )
        if ( Vec_IntSize(vLevel) > 1 )
            printf( "%d ", Vec_IntSize(vLevel) );
        else
            nUnique++;
    printf( " Unique = %d\n", nUnique );

//    return (Vec_Vec_t *)vClasses;
    Vec_VecFree( (Vec_Vec_t *)vClasses );
    return NULL;
}