saigIsoFast.c

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

***********************************************************************/

#include "saig.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

#define AIG_ISO_NUM 16

typedef struct Iso_Dat_t_ Iso_Dat_t;
struct Iso_Dat_t_
{
    unsigned      nFiNeg    :  3;
    unsigned      nFoNeg    :  2;
    unsigned      nFoPos    :  2;
    unsigned      Fi0Lev    :  3;
    unsigned      Fi1Lev    :  3;
    unsigned      Level     :  3;
    unsigned      fVisit    : 16;
};

typedef struct Iso_Dat2_t_ Iso_Dat2_t;
struct Iso_Dat2_t_
{
    unsigned      Data      : 16;
};

typedef struct Iso_Sto_t_ Iso_Sto_t;
struct Iso_Sto_t_
{
    Aig_Man_t *   pAig;       // user's AIG manager
    int           nObjs;      // number of objects
    Iso_Dat_t *   pData;      // data for each object
    Vec_Int_t *   vVisited;   // visited nodes
    Vec_Ptr_t *   vRoots;     // root nodes
    Vec_Int_t *   vPlaces;    // places in the counter lists
    int *         pCounters;  // counters    
};

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Iso_Sto_t * Iso_StoStart( Aig_Man_t * pAig )
{
    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 )
{
    Vec_IntFree( p->vPlaces );
    Vec_IntFree( p->vVisited );
    Vec_PtrFree( p->vRoots );
    ABC_FREE( p->pCounters );
    ABC_FREE( p->pData );
    ABC_FREE( p );
}

/**Function*************************************************************

  Synopsis    [Collect statistics about one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

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

//static abctime time_Trav = 0;

/**Function*************************************************************

  Synopsis    [Collect statistics about one output.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Iso_StoCollectInfo( Iso_Sto_t * p, Aig_Obj_t * pPo )
{
    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;
}

/**Function*************************************************************

  Synopsis    [Takes multi-output sequential AIG.]

  Description [Returns candidate equivalence classes of POs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Iso_StoCompareVecInt( Vec_Int_t ** p1, Vec_Int_t ** p2 )
{
    return Vec_IntCompareVec( *p1, *p2 );
}

/**Function*************************************************************

  Synopsis    [Takes multi-output sequential AIG.]

  Description [Returns candidate equivalence classes of POs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Vec_t * Saig_IsoDetectFast( Aig_Man_t * pAig )
{
    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;
}



////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END