aigWin.c

Go to the documentation of this file.

 
#include "aig.h"
 
ABC_NAMESPACE_IMPL_START
 



static inline int Aig_NodeGetLeafCostOne( Aig_Obj_t * pNode, int nFanoutLimit )
{
    int Cost;
    // make sure the node is in the construction zone
    assert( pNode->fMarkA );  
    // cannot expand over the PI node
    if ( Aig_ObjIsCi(pNode) )
        return 999;
    // get the cost of the cone
    Cost = (!Aig_ObjFanin0(pNode)->fMarkA) + (!Aig_ObjFanin1(pNode)->fMarkA);
    // always accept if the number of leaves does not increase
    if ( Cost < 2 )
        return Cost;
    // skip nodes with many fanouts
    if ( (int)pNode->nRefs > nFanoutLimit )
        return 999;
    // return the number of nodes that will be on the leaves if this node is removed
    return Cost;
}

int Aig_ManFindCut_int( Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited, int nSizeLimit, int nFanoutLimit )
{
    Aig_Obj_t * pNode, * pFaninBest, * pNext;
    int CostBest, CostCur, i;
    // find the best fanin
    CostBest   = 100;
    pFaninBest = NULL;
//printf( "Evaluating fanins of the cut:\n" );
    Vec_PtrForEachEntry( Aig_Obj_t *, vFront, pNode, i )
    {
        CostCur = Aig_NodeGetLeafCostOne( pNode, nFanoutLimit );
//printf( "    Fanin %s has cost %d.\n", Aig_ObjName(pNode), CostCur );
        if ( CostBest > CostCur ||
            (CostBest == CostCur && pNode->Level > pFaninBest->Level) )
        {
            CostBest   = CostCur;
            pFaninBest = pNode;
        }
        if ( CostBest == 0 )
            break;
    }
    if ( pFaninBest == NULL )
        return 0;
    assert( CostBest < 3 );
    if ( Vec_PtrSize(vFront) - 1 + CostBest > nSizeLimit )
        return 0;
    assert( Aig_ObjIsNode(pFaninBest) );
    // remove the node from the array
    Vec_PtrRemove( vFront, pFaninBest );
//printf( "Removing fanin %s.\n", Aig_ObjName(pFaninBest) );
 
    // add the left child to the fanins
    pNext = Aig_ObjFanin0(pFaninBest);
    if ( !pNext->fMarkA )
    {
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
        pNext->fMarkA = 1;
        Vec_PtrPush( vFront, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    // add the right child to the fanins
    pNext = Aig_ObjFanin1(pFaninBest);
    if ( !pNext->fMarkA )
    {
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
        pNext->fMarkA = 1;
        Vec_PtrPush( vFront, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    assert( Vec_PtrSize(vFront) <= nSizeLimit );
    // keep doing this
    return 1;
}

void Aig_ManFindCut( Aig_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited, int nSizeLimit, int nFanoutLimit )
{
    Aig_Obj_t * pNode;
    int i;
 
    assert( !Aig_IsComplement(pRoot) );
    assert( Aig_ObjIsNode(pRoot) );
    assert( Aig_ObjChild0(pRoot) );
    assert( Aig_ObjChild1(pRoot) );
 
    // start the cut 
    Vec_PtrClear( vFront );
    Vec_PtrPush( vFront, Aig_ObjFanin0(pRoot) );
    Vec_PtrPush( vFront, Aig_ObjFanin1(pRoot) );
 
    // start the visited nodes
    Vec_PtrClear( vVisited );
    Vec_PtrPush( vVisited, pRoot );
    Vec_PtrPush( vVisited, Aig_ObjFanin0(pRoot) );
    Vec_PtrPush( vVisited, Aig_ObjFanin1(pRoot) );
 
    // mark these nodes
    assert( !pRoot->fMarkA );
    assert( !Aig_ObjFanin0(pRoot)->fMarkA );
    assert( !Aig_ObjFanin1(pRoot)->fMarkA );
    pRoot->fMarkA = 1;
    Aig_ObjFanin0(pRoot)->fMarkA = 1;
    Aig_ObjFanin1(pRoot)->fMarkA = 1;
 
    // compute the cut
    while ( Aig_ManFindCut_int( vFront, vVisited, nSizeLimit, nFanoutLimit ) );
    assert( Vec_PtrSize(vFront) <= nSizeLimit );
 
    // clean the visit markings
    Vec_PtrForEachEntry( Aig_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 0;
}

 
 
ABC_NAMESPACE_IMPL_END