abcReconv.c

/**CFile****************************************************************

  FileName    [abcReconv.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

  Synopsis    [Computation of reconvergence-driven cuts.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: abcReconv.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "base/abc/abc.h"

#ifdef ABC_USE_CUDD
#include "bdd/extrab/extraBdd.h"
#endif

ABC_NAMESPACE_IMPL_START


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

struct Abc_ManCut_t_
{
    // user specified parameters
    int              nNodeSizeMax;  // the limit on the size of the supernode
    int              nConeSizeMax;  // the limit on the size of the containing cone
    int              nNodeFanStop;  // the limit on the size of the supernode
    int              nConeFanStop;  // the limit on the size of the containing cone
    // internal parameters
    Vec_Ptr_t *      vNodeLeaves;   // fanins of the collapsed node (the cut)
    Vec_Ptr_t *      vConeLeaves;   // fanins of the containing cone
    Vec_Ptr_t *      vVisited;      // the visited nodes
    Vec_Vec_t *      vLevels;       // the data structure to compute TFO nodes
    Vec_Ptr_t *      vNodesTfo;     // the nodes in the TFO of the cut
};

static int   Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit );
static int   Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit );
static void  Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited );

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

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

  Synopsis    [Unmarks the TFI cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Abc_NodesMark( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 1;
}

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

  Synopsis    [Unmarks the TFI cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Abc_NodesUnmark( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkA = 0;
}

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

  Synopsis    [Unmarks the TFI cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Abc_NodesUnmarkB( Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    int i;
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        pNode->fMarkB = 0;
}

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

  Synopsis    [Evaluate the cost of removing the node from the set of leaves.]

  Description [Returns the number of new leaves that will be brought in.
  Returns large number if the node cannot be removed from the set of leaves.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Abc_NodeGetLeafCostOne( Abc_Obj_t * pNode, int nFaninLimit )
{
    int Cost;
    // make sure the node is in the construction zone
    assert( pNode->fMarkB == 1 );  
    // cannot expand over the PI node
    if ( Abc_ObjIsCi(pNode) )
        return 999;
    // get the cost of the cone
    Cost = (!Abc_ObjFanin0(pNode)->fMarkB) + (!Abc_ObjFanin1(pNode)->fMarkB);
    // always accept if the number of leaves does not increase
    if ( Cost < 2 )
        return Cost;
    // skip nodes with many fanouts
    if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
        return 999;
    // return the number of nodes that will be on the leaves if this node is removed
    return Cost;
}

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

  Synopsis    [Evaluate the cost of removing the node from the set of leaves.]

  Description [Returns the number of new leaves that will be brought in.
  Returns large number if the node cannot be removed from the set of leaves.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Abc_NodeGetLeafCostTwo( Abc_Obj_t * pNode, int nFaninLimit, 
    Abc_Obj_t ** ppLeafToAdd, Abc_Obj_t ** pNodeToMark1, Abc_Obj_t ** pNodeToMark2 )
{
    Abc_Obj_t * pFanin0, * pFanin1, * pTemp;
    Abc_Obj_t * pGrand, * pGrandToAdd;
    // make sure the node is in the construction zone
    assert( pNode->fMarkB == 1 );  
    // cannot expand over the PI node
    if ( Abc_ObjIsCi(pNode) )
        return 999;
    // skip nodes with many fanouts
//    if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
//        return 999;
    // get the children
    pFanin0 = Abc_ObjFanin0(pNode);
    pFanin1 = Abc_ObjFanin1(pNode);
    assert( !pFanin0->fMarkB && !pFanin1->fMarkB );
    // count the number of unique grandchildren that will be included
    // return infinite cost if this number if more than 1
    if ( Abc_ObjIsCi(pFanin0) && Abc_ObjIsCi(pFanin1) )
        return 999;
    // consider the special case when a non-CI fanin can be dropped
    if ( !Abc_ObjIsCi(pFanin0) && Abc_ObjFanin0(pFanin0)->fMarkB && Abc_ObjFanin1(pFanin0)->fMarkB )
    {
        *ppLeafToAdd  = pFanin1;
        *pNodeToMark1 = pFanin0;
        *pNodeToMark2 = NULL;
        return 1;
    }
    if ( !Abc_ObjIsCi(pFanin1) && Abc_ObjFanin0(pFanin1)->fMarkB && Abc_ObjFanin1(pFanin1)->fMarkB )
    {
        *ppLeafToAdd  = pFanin0;
        *pNodeToMark1 = pFanin1;
        *pNodeToMark2 = NULL;
        return 1;
    }

    // make the first node CI if any
    if ( Abc_ObjIsCi(pFanin1) )
        pTemp = pFanin0, pFanin0 = pFanin1, pFanin1 = pTemp;
    // consider the first node
    pGrandToAdd = NULL;
    if ( Abc_ObjIsCi(pFanin0) )
    {
        *pNodeToMark1 = NULL;
        pGrandToAdd = pFanin0;
    }
    else
    {
        *pNodeToMark1 = pFanin0;
        pGrand = Abc_ObjFanin0(pFanin0);
        if ( !pGrand->fMarkB )
        {
            if ( pGrandToAdd && pGrandToAdd != pGrand )
                return 999;
            pGrandToAdd = pGrand;
        }
        pGrand = Abc_ObjFanin1(pFanin0);
        if ( !pGrand->fMarkB )
        {
            if ( pGrandToAdd && pGrandToAdd != pGrand )
                return 999;
            pGrandToAdd = pGrand;
        }
    }
    // consider the second node
    *pNodeToMark2 = pFanin1;
    pGrand = Abc_ObjFanin0(pFanin1);
    if ( !pGrand->fMarkB )
    {
        if ( pGrandToAdd && pGrandToAdd != pGrand )
            return 999;
        pGrandToAdd = pGrand;
    }
    pGrand = Abc_ObjFanin1(pFanin1);
    if ( !pGrand->fMarkB )
    {
        if ( pGrandToAdd && pGrandToAdd != pGrand )
            return 999;
        pGrandToAdd = pGrand;
    }
    assert( pGrandToAdd != NULL );
    *ppLeafToAdd = pGrandToAdd;
    return 1;
}


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

  Synopsis    [Finds a fanin-limited, reconvergence-driven cut for the node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot, int fContain )
{
    Abc_Obj_t * pNode;
    int i;

    assert( !Abc_ObjIsComplement(pRoot) );
    assert( Abc_ObjIsNode(pRoot) );

    // start the visited nodes and mark them
    Vec_PtrClear( p->vVisited );
    Vec_PtrPush( p->vVisited, pRoot );
    Vec_PtrPush( p->vVisited, Abc_ObjFanin0(pRoot) );
    Vec_PtrPush( p->vVisited, Abc_ObjFanin1(pRoot) );
    pRoot->fMarkB = 1;
    Abc_ObjFanin0(pRoot)->fMarkB = 1;
    Abc_ObjFanin1(pRoot)->fMarkB = 1;

    // start the cut 
    Vec_PtrClear( p->vNodeLeaves );
    Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin0(pRoot) );
    Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin1(pRoot) );

    // compute the cut
    while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vNodeLeaves, p->nNodeSizeMax, p->nNodeFanStop ) );
    assert( Vec_PtrSize(p->vNodeLeaves) <= p->nNodeSizeMax );

    // return if containing cut is not requested
    if ( !fContain )
    {
        // unmark both fMarkA and fMarkB in tbe TFI
        Abc_NodesUnmarkB( p->vVisited );
        return p->vNodeLeaves;
    }

//printf( "\n\n\n" );
    // compute the containing cut
    assert( p->nNodeSizeMax < p->nConeSizeMax );
    // copy the current boundary
    Vec_PtrClear( p->vConeLeaves );
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodeLeaves, pNode, i )
        Vec_PtrPush( p->vConeLeaves, pNode );
    // compute the containing cut
    while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vConeLeaves, p->nConeSizeMax, p->nConeFanStop ) );
    assert( Vec_PtrSize(p->vConeLeaves) <= p->nConeSizeMax );
    // unmark TFI using fMarkA and fMarkB
    Abc_NodesUnmarkB( p->vVisited );
    return p->vNodeLeaves;
}

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

  Synopsis    [Builds reconvergence-driven cut by changing one leaf at a time.]

  Description [This procedure looks at the current leaves and tries to change 
  one leaf at a time in such a way that the cut grows as little as possible.
  In evaluating the fanins, this procedure looks only at their immediate 
  predecessors (this is why it is called a one-level construction procedure).]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit )
{
    Abc_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( Abc_Obj_t *, vLeaves, pNode, i )
    {
        CostCur = Abc_NodeGetLeafCostOne( pNode, nFaninLimit );
//printf( "    Fanin %s has cost %d.\n", Abc_ObjName(pNode), CostCur );
//        if ( CostBest > CostCur ) // performance improvement: expand the variable with the smallest level
        if ( CostBest > CostCur ||
             (CostBest == CostCur && pNode->Level > pFaninBest->Level) )
        {
            CostBest   = CostCur;
            pFaninBest = pNode;
        }
        if ( CostBest == 0 )
            break;
    }
    if ( pFaninBest == NULL )
        return 0;
//        return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );

    assert( CostBest < 3 );
    if ( vLeaves->nSize - 1 + CostBest > nSizeLimit )
        return 0;
//        return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );

    assert( Abc_ObjIsNode(pFaninBest) );
    // remove the node from the array
    Vec_PtrRemove( vLeaves, pFaninBest );
//printf( "Removing fanin %s.\n", Abc_ObjName(pFaninBest) );

    // add the left child to the fanins
    pNext = Abc_ObjFanin0(pFaninBest);
    if ( !pNext->fMarkB )
    {
//printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
        pNext->fMarkB = 1;
        Vec_PtrPush( vLeaves, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    // add the right child to the fanins
    pNext = Abc_ObjFanin1(pFaninBest);
    if ( !pNext->fMarkB )
    {
//printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
        pNext->fMarkB = 1;
        Vec_PtrPush( vLeaves, pNext );
        Vec_PtrPush( vVisited, pNext );
    }
    assert( vLeaves->nSize <= nSizeLimit );
    // keep doing this
    return 1;
}

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

  Synopsis    [Builds reconvergence-driven cut by changing one leaf at a time.]

  Description [This procedure looks at the current leaves and tries to change 
  one leaf at a time in such a way that the cut grows as little as possible.
  In evaluating the fanins, this procedure looks across two levels of fanins
  (this is why it is called a two-level construction procedure).]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit )
{
    Abc_Obj_t * pNode = NULL, * pLeafToAdd, * pNodeToMark1, * pNodeToMark2;
    int CostCur = 0, i;
    // find the best fanin
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
    {
        CostCur = Abc_NodeGetLeafCostTwo( pNode, nFaninLimit, &pLeafToAdd, &pNodeToMark1, &pNodeToMark2 );
        if ( CostCur < 2 )
            break;
    }
    if ( CostCur > 2 )
        return 0;
    // remove the node from the array
    Vec_PtrRemove( vLeaves, pNode );
    // add the node to the leaves
    if ( pLeafToAdd )
    {
        assert( !pLeafToAdd->fMarkB );
        pLeafToAdd->fMarkB = 1;
        Vec_PtrPush( vLeaves, pLeafToAdd );
        Vec_PtrPush( vVisited, pLeafToAdd );
    }
    // mark the other nodes
    if ( pNodeToMark1 )
    {
        assert( !pNodeToMark1->fMarkB );
        pNodeToMark1->fMarkB = 1;
        Vec_PtrPush( vVisited, pNodeToMark1 );
    }
    if ( pNodeToMark2 )
    {
        assert( !pNodeToMark2->fMarkB );
        pNodeToMark2->fMarkB = 1;
        Vec_PtrPush( vVisited, pNodeToMark2 );
    }
    // keep doing this
    return 1;
}


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

  Synopsis    [Get the nodes contained in the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NodeConeCollect( Abc_Obj_t ** ppRoots, int nRoots, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited, int fIncludeFanins )
{
    Abc_Obj_t * pTemp;
    int i;
    // mark the fanins of the cone
    Abc_NodesMark( vLeaves );
    // collect the nodes in the DFS order
    Vec_PtrClear( vVisited );
    // add the fanins
    if ( fIncludeFanins )
        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pTemp, i )
            Vec_PtrPush( vVisited, pTemp );
    // add other nodes
    for ( i = 0; i < nRoots; i++ )
        Abc_NodeConeMarkCollect_rec( ppRoots[i], vVisited );
    // unmark both sets
    Abc_NodesUnmark( vLeaves );
    Abc_NodesUnmark( vVisited );
}

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

  Synopsis    [Marks the TFI cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited )
{
    if ( pNode->fMarkA == 1 )
        return;
    // visit transitive fanin 
    if ( Abc_ObjIsNode(pNode) )
    {
        Abc_NodeConeMarkCollect_rec( Abc_ObjFanin0(pNode), vVisited );
        Abc_NodeConeMarkCollect_rec( Abc_ObjFanin1(pNode), vVisited );
    }
    assert( pNode->fMarkA == 0 );
    pNode->fMarkA = 1;
    Vec_PtrPush( vVisited, pNode );
}

#ifdef ABC_USE_CUDD

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

  Synopsis    [Returns BDD representing the logic function of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited )
{
    Abc_Obj_t * pNode;
    DdNode * bFunc0, * bFunc1, * bFunc = NULL;
    int i;
    // get the nodes in the cut without fanins in the DFS order
    Abc_NodeConeCollect( &pRoot, 1, vLeaves, vVisited, 0 );
    // set the elementary BDDs
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
        pNode->pCopy = (Abc_Obj_t *)pbVars[i];
    // compute the BDDs for the collected nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
    {
        assert( !Abc_ObjIsPi(pNode) );
        bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
        bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
        bFunc  = Cudd_bddAnd( dd, bFunc0, bFunc1 );    Cudd_Ref( bFunc );
        pNode->pCopy = (Abc_Obj_t *)bFunc;
    }
    assert(bFunc);
    Cudd_Ref( bFunc );
    // dereference the intermediate ones
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
    Cudd_Deref( bFunc );
    return bFunc;
}

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

  Synopsis    [Returns BDD representing the transition relation of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited )
{
    DdNode * bFunc0, * bFunc1, * bFunc, * bTrans, * bTemp, * bCube, * bResult;
    Abc_Obj_t * pNode;
    int i;
    // get the nodes in the cut without fanins in the DFS order
    Abc_NodeConeCollect( (Abc_Obj_t **)vRoots->pArray, vRoots->nSize, vLeaves, vVisited, 0 );
    // set the elementary BDDs
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
        pNode->pCopy = (Abc_Obj_t *)pbVarsX[i];
    // compute the BDDs for the collected nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
    {
        bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
        bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
        bFunc  = Cudd_bddAnd( dd, bFunc0, bFunc1 );    Cudd_Ref( bFunc );
        pNode->pCopy = (Abc_Obj_t *)bFunc;
    }
    // compute the transition relation of the cone
    bTrans = b1;    Cudd_Ref( bTrans );
    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, i )
    {
        bFunc = Cudd_bddXnor( dd, (DdNode *)pNode->pCopy, pbVarsY[i] );  Cudd_Ref( bFunc );
        bTrans = Cudd_bddAnd( dd, bTemp = bTrans, bFunc );               Cudd_Ref( bTrans );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bFunc );
    }
    // dereference the intermediate ones
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
        Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
    // compute don't-cares
    bCube = Extra_bddComputeRangeCube( dd, vRoots->nSize, vRoots->nSize + vLeaves->nSize );  Cudd_Ref( bCube );
    bResult = Cudd_bddExistAbstract( dd, bTrans, bCube );                Cudd_Ref( bResult );
    bResult = Cudd_Not( bResult );
    Cudd_RecursiveDeref( dd, bCube );
    Cudd_RecursiveDeref( dd, bTrans );
    Cudd_Deref( bResult );
    return bResult;
}
 
#endif

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

  Synopsis    [Starts the resynthesis manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax, int nNodeFanStop, int nConeFanStop )
{
    Abc_ManCut_t * p;
    p = ABC_ALLOC( Abc_ManCut_t, 1 );
    memset( p, 0, sizeof(Abc_ManCut_t) );
    p->vNodeLeaves  = Vec_PtrAlloc( 100 );
    p->vConeLeaves  = Vec_PtrAlloc( 100 );
    p->vVisited     = Vec_PtrAlloc( 100 );
    p->vLevels      = Vec_VecAlloc( 100 );
    p->vNodesTfo    = Vec_PtrAlloc( 100 );
    p->nNodeSizeMax = nNodeSizeMax;
    p->nConeSizeMax = nConeSizeMax;
    p->nNodeFanStop = nNodeFanStop;
    p->nConeFanStop = nConeFanStop;
    return p;
}

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

  Synopsis    [Stops the resynthesis manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkManCutStop( Abc_ManCut_t * p )
{
    Vec_PtrFree( p->vNodeLeaves );
    Vec_PtrFree( p->vConeLeaves );
    Vec_PtrFree( p->vVisited    );
    Vec_VecFree( p->vLevels );
    Vec_PtrFree( p->vNodesTfo );
    ABC_FREE( p );
}

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

  Synopsis    [Returns the leaves of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkManCutReadCutLarge( Abc_ManCut_t * p )
{
    return p->vConeLeaves;
}

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

  Synopsis    [Returns the leaves of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkManCutReadCutSmall( Abc_ManCut_t * p )
{
    return p->vNodeLeaves;
}

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

  Synopsis    [Returns the leaves of the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkManCutReadVisited( Abc_ManCut_t * p )
{
    return p->vVisited;
}



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

  Synopsis    [Collects the TFO of the cut in the topological order.]

  Description [TFO of the cut is defined as a set of nodes, for which the cut
  is a cut, that is, every path from the collected nodes to the CIs goes through 
  a node in the cut. The nodes are collected if their level does not exceed
  the given number (LevelMax). The nodes are returned in the topological order.
  If the root node is given, its MFFC is marked, so that the collected nodes
  do not contain any nodes in the MFFC.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NodeCollectTfoCands( Abc_ManCut_t * p, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, int LevelMax )
{
    Abc_Ntk_t * pNtk = pRoot->pNtk;
    Vec_Ptr_t * vVec;
    Abc_Obj_t * pNode, * pFanout;
    int i, k, v, LevelMin;
    assert( Abc_NtkIsStrash(pNtk) );

    // assuming that the structure is clean
    Vec_VecForEachLevel( p->vLevels, vVec, i )
        assert( vVec->nSize == 0 );

    // put fanins into the structure while labeling them
    Abc_NtkIncrementTravId( pNtk );
    LevelMin = -1;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
    {
        if ( pNode->Level > (unsigned)LevelMax )
            continue;
        Abc_NodeSetTravIdCurrent( pNode );
        Vec_VecPush( p->vLevels, pNode->Level, pNode );
        if ( LevelMin < (int)pNode->Level )
            LevelMin = pNode->Level;
    }
    assert( LevelMin >= 0 );

    // mark MFFC 
    if ( pRoot )
        Abc_NodeMffcLabelAig( pRoot );

    // go through the levels up
    Vec_PtrClear( p->vNodesTfo );
    Vec_VecForEachEntryStart( Abc_Obj_t *, p->vLevels, pNode, i, k, LevelMin )
    {
        if ( i > LevelMax )
            break;
        // if the node is not marked, it is not a fanin
        if ( !Abc_NodeIsTravIdCurrent(pNode) )
        {
            // check if it belongs to the TFO
            if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pNode)) || 
                 !Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pNode)) )
                 continue;
            // save the node in the TFO and label it
            Vec_PtrPush( p->vNodesTfo, pNode );
            Abc_NodeSetTravIdCurrent( pNode );
        }
        // go through the fanouts and add them to the structure if they meet the conditions
        Abc_ObjForEachFanout( pNode, pFanout, v )
        {
            // skip if fanout is a CO or its level exceeds
            if ( Abc_ObjIsCo(pFanout) || pFanout->Level > (unsigned)LevelMax )
                continue;
            // skip if it is already added or if it is in MFFC
            if ( Abc_NodeIsTravIdCurrent(pFanout) )
                continue;
            // add it to the structure but do not mark it (until tested later)
            Vec_VecPushUnique( p->vLevels, pFanout->Level, pFanout );
        }
    }

    // clear the levelized structure
    Vec_VecForEachLevelStart( p->vLevels, vVec, i, LevelMin )
    {
        if ( i > LevelMax )
            break;
        Vec_PtrClear( vVec );
    }
    return p->vNodesTfo;
}

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


ABC_NAMESPACE_IMPL_END