nwkDfs.c

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

  FileName    [nwkDfs.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Logic network representation.]

  Synopsis    [DFS traversals.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "nwk.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Verifies that the objects are in a topo order.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ManVerifyTopoOrder( Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj, * pNext;
    int i, k, iBox, iTerm1, nTerms;
    Nwk_ManIncrementTravId( pNtk );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
        {
            Nwk_ObjForEachFanin( pObj, pNext, k )
            {
                if ( !Nwk_ObjIsTravIdCurrent(pNext) )
                {
                    printf( "Node %d has fanin %d that is not in a topological order.\n", pObj->Id, pNext->Id );
                    return 0;
                }
            }
        }
        else if ( Nwk_ObjIsCi(pObj) )
        {
            if ( pNtk->pManTime )
            {
                iBox = Tim_ManBoxForCi( pNtk->pManTime, pObj->PioId );
                if ( iBox >= 0 ) // this is not a true PI
                {
                    iTerm1 = Tim_ManBoxInputFirst( pNtk->pManTime, iBox );
                    nTerms = Tim_ManBoxInputNum( pNtk->pManTime, iBox );
                    for ( k = 0; k < nTerms; k++ )
                    {
                        pNext = Nwk_ManCo( pNtk, iTerm1 + k );
                        if ( !Nwk_ObjIsTravIdCurrent(pNext) )
                        {
                            printf( "Box %d has input %d that is not in a topological order.\n", iBox, pNext->Id );
                            return 0;
                        }
                    }
                }
            }
        }
        else
            assert( 0 );
        Nwk_ObjSetTravIdCurrent( pObj );
    }
    return 1;
}

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

  Synopsis    [Computes the number of logic levels not counting PIs/POs.]

  Description [Assumes that white boxes have unit level.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ManLevelBackup( Nwk_Man_t * pNtk )
{
    Tim_Man_t * pManTimeUnit;
    Nwk_Obj_t * pObj, * pFanin;
    int i, k, LevelMax, Level;
    assert( Nwk_ManVerifyTopoOrder(pNtk) );
    // clean the levels
    Nwk_ManForEachObj( pNtk, pObj, i )
        Nwk_ObjSetLevel( pObj, 0 );
    // perform level computation
    LevelMax = 0;
    pManTimeUnit = pNtk->pManTime ? Tim_ManDup( pNtk->pManTime, 1 ) : NULL;
    if ( pManTimeUnit )
        Tim_ManIncrementTravId( pManTimeUnit );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsCi(pObj) )
        {
            Level = pManTimeUnit? (int)Tim_ManGetCiArrival( pManTimeUnit, pObj->PioId ) : 0;
            Nwk_ObjSetLevel( pObj, Level );
        }
        else if ( Nwk_ObjIsCo(pObj) )
        {
            Level = Nwk_ObjLevel( Nwk_ObjFanin0(pObj) );
            if ( pManTimeUnit )
                Tim_ManSetCoArrival( pManTimeUnit, pObj->PioId, (float)Level );
            Nwk_ObjSetLevel( pObj, Level );
            if ( LevelMax < Nwk_ObjLevel(pObj) )
                LevelMax = Nwk_ObjLevel(pObj);
        }
        else if ( Nwk_ObjIsNode(pObj) )
        {
            Level = 0;
            Nwk_ObjForEachFanin( pObj, pFanin, k )
                if ( Level < Nwk_ObjLevel(pFanin) )
                    Level = Nwk_ObjLevel(pFanin);
            Nwk_ObjSetLevel( pObj, Level + 1 );
        }
        else
            assert( 0 );
    }
    // set the old timing manager
    if ( pManTimeUnit )
        Tim_ManStop( pManTimeUnit );
    return LevelMax;
}

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

  Synopsis    [Computes the number of logic levels not counting PIs/POs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManLevel_rec( Nwk_Obj_t * pObj )
{
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
    Nwk_Obj_t * pNext;
    int i, iBox, iTerm1, nTerms, LevelMax = 0;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCi(pObj) )
    {
        if ( pManTime ) 
        {
            iBox = Tim_ManBoxForCi( pManTime, pObj->PioId );
            if ( iBox >= 0 ) // this is not a true PI
            {
                iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
                nTerms = Tim_ManBoxInputNum( pManTime, iBox );
                for ( i = 0; i < nTerms; i++ )
                {
                    pNext = Nwk_ManCo(pObj->pMan, iTerm1 + i);
                    Nwk_ManLevel_rec( pNext );
                    if ( LevelMax < Nwk_ObjLevel(pNext) )
                        LevelMax = Nwk_ObjLevel(pNext);
                }
                LevelMax++;
            }
        }
    }
    else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
    {
        Nwk_ObjForEachFanin( pObj, pNext, i )
        {
            Nwk_ManLevel_rec( pNext );
            if ( LevelMax < Nwk_ObjLevel(pNext) )
                LevelMax = Nwk_ObjLevel(pNext);
        }
        if ( Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0 )
            LevelMax++;
    }
    else
        assert( 0 );
    Nwk_ObjSetLevel( pObj, LevelMax );
}

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

  Synopsis    [Computes the number of logic levels not counting PIs/POs.]

  Description [Does not assume that the objects are in a topo order.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ManLevel( Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj;
    int i, LevelMax = 0;
    Nwk_ManForEachObj( pNtk, pObj, i )
        Nwk_ObjSetLevel( pObj, 0 );
    Nwk_ManIncrementTravId( pNtk );
    Nwk_ManForEachPo( pNtk, pObj, i )
    {
        Nwk_ManLevel_rec( pObj );
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    }
    Nwk_ManForEachCi( pNtk, pObj, i )
    {
        Nwk_ManLevel_rec( pObj );
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    }
    return LevelMax;
}

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

  Synopsis    [Computes the number of logic levels not counting PIs/POs.]

  Description [Does not assume that the objects are in a topo order.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ManLevelMax( Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj;
    int i, LevelMax = 0;
    Nwk_ManForEachPo( pNtk, pObj, i )
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    return LevelMax;
}

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

  Synopsis    [Returns the array of objects in the AIG manager ordered by level.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Vec_t * Nwk_ManLevelize( Nwk_Man_t * pNtk )
{
    Nwk_Obj_t * pObj;
    Vec_Vec_t * vLevels;
    int nLevels, i;
    assert( Nwk_ManVerifyLevel(pNtk) );
    nLevels = Nwk_ManLevelMax( pNtk );
    vLevels = Vec_VecStart( nLevels + 1 );
    Nwk_ManForEachNode( pNtk, pObj, i )
    {
        assert( Nwk_ObjLevel(pObj) <= nLevels );
        Vec_VecPush( vLevels, Nwk_ObjLevel(pObj), pObj );
    }
    return vLevels;
}



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

  Synopsis    [Performs DFS for one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManDfs_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    Nwk_Obj_t * pNext;
    int i;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    Nwk_ObjForEachFanin( pObj, pNext, i )
        Nwk_ManDfs_rec( pNext, vNodes );
    Vec_PtrPush( vNodes, pObj );
}
 
/**Function*************************************************************

  Synopsis    [Returns the DFS ordered array of all objects except latches.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Nwk_ManDfs( Nwk_Man_t * pNtk )
{
    Vec_Ptr_t * vNodes;
    Nwk_Obj_t * pObj;
    int i;
    Nwk_ManIncrementTravId( pNtk );
    vNodes = Vec_PtrAlloc( 100 );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsCi(pObj) )
        {
            Nwk_ObjSetTravIdCurrent( pObj );
            Vec_PtrPush( vNodes, pObj );
        }
        else if ( Nwk_ObjIsCo(pObj) )
            Nwk_ManDfs_rec( pObj, vNodes );
    }
    return vNodes;
}

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

  Synopsis    [Performs DFS for one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManDfsNodes_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    Nwk_Obj_t * pNext;
    int i;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCi(pObj) )
        return;
    assert( Nwk_ObjIsNode(pObj) );
    Nwk_ObjForEachFanin( pObj, pNext, i )
        Nwk_ManDfsNodes_rec( pNext, vNodes );
    Vec_PtrPush( vNodes, pObj );
}

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

  Synopsis    [Returns the set of internal nodes rooted in the given nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Nwk_ManDfsNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
{
    Vec_Ptr_t * vNodes;
    int i;
    // set the traversal ID
    Nwk_ManIncrementTravId( pNtk );
    // start the array of nodes
    vNodes = Vec_PtrAlloc( 100 );
    // go through the PO nodes and call for each of them
    for ( i = 0; i < nNodes; i++ )
        if ( Nwk_ObjIsCo(ppNodes[i]) )
            Nwk_ManDfsNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
        else
            Nwk_ManDfsNodes_rec( ppNodes[i], vNodes );
    return vNodes;
}

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

  Synopsis    [Performs DFS for one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManDfsReverse_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    Nwk_Obj_t * pNext;
    int i, iBox, iTerm1, nTerms;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCo(pObj) )
    {
        if ( pObj->pMan->pManTime )
        {
            iBox = Tim_ManBoxForCo( pObj->pMan->pManTime, pObj->PioId );
            if ( iBox >= 0 ) // this is not a true PO
            {
                iTerm1 = Tim_ManBoxOutputFirst( pObj->pMan->pManTime, iBox );
                nTerms = Tim_ManBoxOutputNum( pObj->pMan->pManTime, iBox );
                for ( i = 0; i < nTerms; i++ )
                {
                    pNext = Nwk_ManCi(pObj->pMan, iTerm1 + i);
                    Nwk_ManDfsReverse_rec( pNext, vNodes );
                }
            }
        }
    }
    else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) )
    {
        Nwk_ObjForEachFanout( pObj, pNext, i )
            Nwk_ManDfsReverse_rec( pNext, vNodes );
    }
    else
        assert( 0 );
    Vec_PtrPush( vNodes, pObj );
}

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

  Synopsis    [Returns the DFS ordered array of all objects except latches.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Nwk_ManDfsReverse( Nwk_Man_t * pNtk )
{
    Vec_Ptr_t * vNodes;
    Nwk_Obj_t * pObj;
    int i;
    Nwk_ManIncrementTravId( pNtk );
    vNodes = Vec_PtrAlloc( 100 );
    Nwk_ManForEachPi( pNtk, pObj, i )
        Nwk_ManDfsReverse_rec( pObj, vNodes );
    // add nodes without fanins
    Nwk_ManForEachNode( pNtk, pObj, i )
        if ( Nwk_ObjFaninNum(pObj) == 0 && !Nwk_ObjIsTravIdCurrent(pObj) )
            Vec_PtrPush( vNodes, pObj );
    return vNodes;
}

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

  Synopsis    [Performs DFS for one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManSupportNodes_rec( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes )
{
    Nwk_Obj_t * pFanin;
    int i;
    // if this node is already visited, skip
    if ( Nwk_ObjIsTravIdCurrent( pNode ) )
        return;
    // mark the node as visited
    Nwk_ObjSetTravIdCurrent( pNode );
    // collect the CI
    if ( Nwk_ObjIsCi(pNode) )
    {
        Vec_PtrPush( vNodes, pNode );
        return;
    }
    assert( Nwk_ObjIsNode( pNode ) );
    // visit the transitive fanin of the node
    Nwk_ObjForEachFanin( pNode, pFanin, i )
        Nwk_ManSupportNodes_rec( pFanin, vNodes );
}

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

  Synopsis    [Returns the set of CI nodes in the support of the given nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Nwk_ManSupportNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
{
    Vec_Ptr_t * vNodes;
    int i;
    // set the traversal ID
    Nwk_ManIncrementTravId( pNtk );
    // start the array of nodes
    vNodes = Vec_PtrAlloc( 100 );
    // go through the PO nodes and call for each of them
    for ( i = 0; i < nNodes; i++ )
        if ( Nwk_ObjIsCo(ppNodes[i]) )
            Nwk_ManSupportNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
        else
            Nwk_ManSupportNodes_rec( ppNodes[i], vNodes );
    return vNodes;
}

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

  Synopsis    [Computes the sum total of supports of all outputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ManSupportSum( Nwk_Man_t * pNtk )
{
    Vec_Ptr_t * vSupp;
    Nwk_Obj_t * pObj;
    int i, nTotalSupps = 0;
    Nwk_ManForEachCo( pNtk, pObj, i )
    {
        vSupp = Nwk_ManSupportNodes( pNtk, &pObj, 1 );
        nTotalSupps += Vec_PtrSize( vSupp );
        Vec_PtrFree( vSupp );
    }
    printf( "Total supports = %d.\n", nTotalSupps );
}


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

  Synopsis    [Dereferences the node's MFFC.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ObjDeref_rec( Nwk_Obj_t * pNode )
{
    Nwk_Obj_t * pFanin;
    int i, Counter = 1;
    if ( Nwk_ObjIsCi(pNode) )
        return 0;
    Nwk_ObjForEachFanin( pNode, pFanin, i )
    {
        assert( pFanin->nFanouts > 0 );
        if ( --pFanin->nFanouts == 0 )
            Counter += Nwk_ObjDeref_rec( pFanin );
    }
    return Counter;
}

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

  Synopsis    [References the node's MFFC.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Nwk_ObjRef_rec( Nwk_Obj_t * pNode )
{
    Nwk_Obj_t * pFanin;
    int i, Counter = 1;
    if ( Nwk_ObjIsCi(pNode) )
        return 0;
    Nwk_ObjForEachFanin( pNode, pFanin, i )
    {
        if ( pFanin->nFanouts++ == 0 )
            Counter += Nwk_ObjRef_rec( pFanin );
    }
    return Counter;
}

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

  Synopsis    [Collects the internal and boundary nodes in the derefed MFFC.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Nwk_ObjMffcLabel_rec( Nwk_Obj_t * pNode, int fTopmost )
{
    Nwk_Obj_t * pFanin;
    int i;
    // add to the new support nodes
    if ( !fTopmost && (Nwk_ObjIsCi(pNode) || pNode->nFanouts > 0) )
        return;
    // skip visited nodes
    if ( Nwk_ObjIsTravIdCurrent(pNode) )
        return;
    Nwk_ObjSetTravIdCurrent(pNode);
    // recur on the children
    Nwk_ObjForEachFanin( pNode, pFanin, i )
        Nwk_ObjMffcLabel_rec( pFanin, 0 );
    // collect the internal node
//    printf( "%d ", pNode->Id );
}

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

  Synopsis    [Collects the internal nodes of the MFFC limited by cut.]

  Description []
               
  SideEffects [Increments the trav ID and marks visited nodes.]

  SeeAlso     []

***********************************************************************/
int Nwk_ObjMffcLabel( Nwk_Obj_t * pNode )
{
    int Count1, Count2;
    // dereference the node
    Count1 = Nwk_ObjDeref_rec( pNode );
    // collect the nodes inside the MFFC
    Nwk_ManIncrementTravId( pNode->pMan );
    Nwk_ObjMffcLabel_rec( pNode, 1 );
    // reference it back
    Count2 = Nwk_ObjRef_rec( pNode );
    assert( Count1 == Count2 );
    return Count1;
}

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


ABC_NAMESPACE_IMPL_END