giaEdge.c

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

  FileName    [giaEdge.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Edge-related procedures.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"
#include "misc/tim/tim.h"

ABC_NAMESPACE_IMPL_START

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

static inline int Gia_ObjEdgeCount( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
    return (Vec_IntEntry(vEdge1, iObj) > 0) + (Vec_IntEntry(vEdge2, iObj) > 0);
}
static inline int Gia_ObjEdgeAdd( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
    int RetValue = 0;
    if ( Vec_IntEntry(vEdge1, iObj) == 0 )
        Vec_IntWriteEntry(vEdge1, iObj, iNext);
    else if ( Vec_IntEntry(vEdge2, iObj) == 0 )
        Vec_IntWriteEntry(vEdge2, iObj, iNext);
    else RetValue = 1;
    return RetValue;
}
static inline void Gia_ObjEdgeRemove( int iObj, int iNext, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
    assert( Vec_IntEntry(vEdge1, iObj) == iNext || Vec_IntEntry(vEdge2, iObj) == iNext );
    if ( Vec_IntEntry(vEdge1, iObj) == iNext )
        Vec_IntWriteEntry( vEdge1, iObj, Vec_IntEntry(vEdge2, iObj) );
    Vec_IntWriteEntry( vEdge2, iObj, 0 );
}
static inline void Gia_ObjEdgeClean( int iObj, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2 )
{
    Vec_IntWriteEntry( vEdge1, iObj, 0 );
    Vec_IntWriteEntry( vEdge2, iObj, 0 );
}

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

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

  Synopsis    [Transforms edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManEdgeFromArray( Gia_Man_t * p, Vec_Int_t * vArray )
{
    int i, iObj1, iObj2, Count = 0;
    Vec_IntFreeP( &p->vEdge1 );
    Vec_IntFreeP( &p->vEdge2 );
    p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
    Vec_IntForEachEntryDouble( vArray, iObj1, iObj2, i )
    {
        assert( iObj1 < iObj2 );
        Count += Gia_ObjEdgeAdd( iObj1, iObj2, p->vEdge1, p->vEdge2 );
        Count += Gia_ObjEdgeAdd( iObj2, iObj1, p->vEdge1, p->vEdge2 );
    }
    if ( Count ) 
        printf( "Found %d violations during edge conversion.\n", Count );
}
Vec_Int_t * Gia_ManEdgeToArray( Gia_Man_t * p )
{
    int iObj, iFanin;
    Vec_Int_t * vArray = Vec_IntAlloc( 1000 );
    assert( p->vEdge1 && p->vEdge2 );
    assert( Vec_IntSize(p->vEdge1) == Gia_ManObjNum(p) );
    assert( Vec_IntSize(p->vEdge2) == Gia_ManObjNum(p) );
    for ( iObj = 0; iObj < Gia_ManObjNum(p); iObj++ )
    {
        iFanin = Vec_IntEntry( p->vEdge1, iObj );
        if ( iFanin && iFanin < iObj )
            Vec_IntPushTwo( vArray, iFanin, iObj );
        iFanin = Vec_IntEntry( p->vEdge2, iObj );
        if ( iFanin && iFanin < iObj )
            Vec_IntPushTwo( vArray, iFanin, iObj );
    }
    return vArray;
}

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

  Synopsis    [Prints mapping statistics.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManConvertPackingToEdges( Gia_Man_t * p )
{
    int i, k, Entry, nEntries, nEntries2, nNodes[4], Count = 0;
    if ( p->vPacking == NULL )
        return;
    Vec_IntFreeP( &p->vEdge1 );
    Vec_IntFreeP( &p->vEdge2 );
    p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
    // iterate through structures
    nEntries = Vec_IntEntry( p->vPacking, 0 );
    nEntries2 = 0;
    Vec_IntForEachEntryStart( p->vPacking, Entry, i, 1 )
    {
        assert( Entry > 0 && Entry < 4 );
        i++;
        for ( k = 0; k < Entry; k++, i++ )
            nNodes[k] = Vec_IntEntry(p->vPacking, i);
        i--;
        nEntries2++;
        // create edges
        if ( Entry == 2 )
        {
            Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[1], p->vEdge1, p->vEdge2 );
            Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[0], p->vEdge1, p->vEdge2 );
        }
        else if ( Entry == 3 )
        {
            Count += Gia_ObjEdgeAdd( nNodes[0], nNodes[2], p->vEdge1, p->vEdge2 );
            Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[0], p->vEdge1, p->vEdge2 );
            Count += Gia_ObjEdgeAdd( nNodes[1], nNodes[2], p->vEdge1, p->vEdge2 );
            Count += Gia_ObjEdgeAdd( nNodes[2], nNodes[1], p->vEdge1, p->vEdge2 );
        }
    }
    assert( nEntries == nEntries2 );
    if ( Count )
        printf( "Skipped %d illegal edges.\n", Count );
}

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

  Synopsis    [Evaluates given edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Gia_ObjHaveEdge( Gia_Man_t * p, int iObj, int iNext )
{
    return Vec_IntEntry(p->vEdge1, iObj) == iNext || Vec_IntEntry(p->vEdge2, iObj) == iNext;
}
int Gia_ObjCheckEdge( Gia_Man_t * p, int iObj, int iNext )
{
    return Gia_ObjHaveEdge( p, iObj, iNext );
}
static inline int Gia_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
    int nEdgeDelay = 2;
    int i, iFan, Delay, DelayMax = 0;
    if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
    {
        assert( Gia_ObjLutSize(p, iObj) <= 4 );
        Gia_LutForEachFanin( p, iObj, iFan, i )
        {
            Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
            DelayMax = Abc_MaxInt( DelayMax, Delay );
        }
    }
    else if ( Gia_ObjIsLut2(p, iObj) )
    {
        assert( Gia_ObjLutSize2(p, iObj) <= 4 );
        Gia_LutForEachFanin2( p, iObj, iFan, i )
        {
            Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? nEdgeDelay : 10);
            DelayMax = Abc_MaxInt( DelayMax, Delay );
        }
    }
    else assert( 0 );
    return DelayMax;
}
int Gia_ManEvalEdgeDelay( Gia_Man_t * p )
{
    int k, iLut, DelayMax = 0;
    assert( p->vEdge1 && p->vEdge2 );
    Vec_IntFreeP( &p->vEdgeDelay );
    p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
    if ( Gia_ManHasMapping(p) )
    {
        if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
        {
            Gia_Obj_t * pObj; 
            Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
            Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
            Gia_ManForEachObjVec( vNodes, p, pObj, k )
            {
                iLut = Gia_ObjId( p, pObj );
                if ( Gia_ObjIsAnd(pObj) )
                {
                    if ( Gia_ObjIsLut(p, iLut) )
                        Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
                }
                else if ( Gia_ObjIsCi(pObj) )
                {
                    int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
                    Vec_IntWriteEntry( p->vEdgeDelay,  iLut, arrTime );
                }
                else if ( Gia_ObjIsCo(pObj) )
                {
                    int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
                    Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
                }
                else if ( !Gia_ObjIsConst0(pObj) ) 
                    assert( 0 );
            }
            Vec_IntFree( vNodes );
        }
        else
        {
            Gia_ManForEachLut( p, iLut )
                Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
        }
    }
    else if ( Gia_ManHasMapping2(p) )
    {
        if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
        {
            Gia_Obj_t * pObj; 
            Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
            Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
            Gia_ManForEachObjVec( vNodes, p, pObj, k )
            {
                iLut = Gia_ObjId( p, pObj );
                if ( Gia_ObjIsAnd(pObj) )
                {
                    if ( Gia_ObjIsLut2(p, iLut) )
                        Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
                }
                else if ( Gia_ObjIsCi(pObj) )
                {
                    int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
                    Vec_IntWriteEntry( p->vEdgeDelay,  iLut, arrTime );
                }
                else if ( Gia_ObjIsCo(pObj) )
                {
                    int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
                    Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
                }
                else if ( !Gia_ObjIsConst0(pObj) ) 
                    assert( 0 );
            }
            Vec_IntFree( vNodes );
        }
        else
        {
            Gia_ManForEachLut2( p, iLut )
                Vec_IntWriteEntry( p->vEdgeDelay, iLut, Gia_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay) );
        }
    }
    else assert( 0 );
    Gia_ManForEachCoDriverId( p, iLut, k )
        DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
    return DelayMax;
}
int Gia_ManEvalEdgeCount( Gia_Man_t * p )
{
    return (Vec_IntCountPositive(p->vEdge1) + Vec_IntCountPositive(p->vEdge2))/2;
}


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

  Synopsis    [Finds edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ObjComputeEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, int fUseTwo )
{
    int i, iFan, Delay, Status1, Status2;
    int DelayMax = 0, DelayMax2 = 0, nCountMax = 0;
    int iFanMax1 = -1, iFanMax2 = -1;
    Vec_IntWriteEntry(vEdge1, iObj, 0);
    Vec_IntWriteEntry(vEdge2, iObj, 0);
    if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
    {
        assert( Gia_ObjLutSize(p, iObj) <= 4 );
        Gia_LutForEachFanin( p, iObj, iFan, i )
        {
            Delay = Vec_IntEntry( vDelay, iFan ) + 10;
            if ( DelayMax < Delay )
            {
                DelayMax2 = DelayMax;
                DelayMax  = Delay;
                iFanMax1  = iFan;
                nCountMax = 1;
            }
            else if ( DelayMax == Delay )
            {
                iFanMax2  = iFan;
                nCountMax++;
                if ( !fUseTwo )
                    DelayMax2 = DelayMax;
            }
            else
                DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
        }
    }
    else if ( Gia_ObjIsLut2(p, iObj) )
    {
        assert( Gia_ObjLutSize2(p, iObj) <= 4 );
        Gia_LutForEachFanin2( p, iObj, iFan, i )
        {
            Delay = Vec_IntEntry( vDelay, iFan ) + 10;
            if ( DelayMax < Delay )
            {
                DelayMax2 = DelayMax;
                DelayMax  = Delay;
                iFanMax1  = iFan;
                nCountMax = 1;
            }
            else if ( DelayMax == Delay )
            {
                iFanMax2  = iFan;
                nCountMax++;
                if ( !fUseTwo )
                    DelayMax2 = DelayMax;
            }
            else
                DelayMax2 = Abc_MaxInt( DelayMax2, Delay );
        }
    }
    else assert( 0 );
    assert( nCountMax > 0 );
    if ( DelayMax <= 10 )
    {} // skip first level
    else if ( nCountMax == 1 )
    {
        Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
        if ( Status1 <= 1 )
        {
            Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
            DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
            Vec_IntWriteEntry( vDelay, iObj, DelayMax );
            return DelayMax;
        }
    }
    else if ( fUseTwo && nCountMax == 2 )
    {
        Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
        Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
        if ( Status1 <= 1 && Status2 <= 1 )
        {
            Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
            DelayMax = Abc_MaxInt( DelayMax2, DelayMax - 8 );
            Vec_IntWriteEntry( vDelay, iObj, DelayMax );
            return DelayMax;
        }
    }
    Vec_IntWriteEntry( vDelay, iObj, DelayMax );
    return DelayMax;
}
int Gia_ManComputeEdgeDelay( Gia_Man_t * p, int fUseTwo )
{
    int k, iLut, DelayMax = 0;
    Vec_IntFreeP( &p->vEdgeDelay );
    Vec_IntFreeP( &p->vEdge1 );
    Vec_IntFreeP( &p->vEdge2 );
    p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
    if ( Gia_ManHasMapping(p) )
    {
        if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
        {
            Gia_Obj_t * pObj; 
            Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
            Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
            Gia_ManForEachObjVec( vNodes, p, pObj, k )
            {
                iLut = Gia_ObjId( p, pObj );
                if ( Gia_ObjIsAnd(pObj) )
                {
                    if ( Gia_ObjIsLut(p, iLut) )
                        Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
                }
                else if ( Gia_ObjIsCi(pObj) )
                {
                    int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
                    Vec_IntWriteEntry( p->vEdgeDelay,  iLut, arrTime );
                }
                else if ( Gia_ObjIsCo(pObj) )
                {
                    int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
                    Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
                }
                else if ( !Gia_ObjIsConst0(pObj) ) 
                    assert( 0 );
            }
            Vec_IntFree( vNodes );
        }
        else
        {
            Gia_ManForEachLut( p, iLut )
                Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
        }
    }
    else if ( Gia_ManHasMapping2(p) )
    {
        if ( p->pManTime != NULL && Tim_ManBoxNum((Tim_Man_t*)p->pManTime) )
        {
            Gia_Obj_t * pObj; 
            Vec_Int_t * vNodes = Gia_ManOrderWithBoxes( p );
            Tim_ManIncrementTravId( (Tim_Man_t*)p->pManTime );
            Gia_ManForEachObjVec( vNodes, p, pObj, k )
            {
                iLut = Gia_ObjId( p, pObj );
                if ( Gia_ObjIsAnd(pObj) )
                {
                    if ( Gia_ObjIsLut2(p, iLut) )
                        Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
                }
                else if ( Gia_ObjIsCi(pObj) )
                {
                    int arrTime = Tim_ManGetCiArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj) );
                    Vec_IntWriteEntry( p->vEdgeDelay,  iLut, arrTime );
                }
                else if ( Gia_ObjIsCo(pObj) )
                {
                    int arrTime = Vec_IntEntry( p->vEdgeDelay, Gia_ObjFaninId0(pObj, iLut) );
                    Tim_ManSetCoArrival( (Tim_Man_t*)p->pManTime, Gia_ObjCioId(pObj), arrTime );
                }
                else if ( !Gia_ObjIsConst0(pObj) ) 
                    assert( 0 );
            }
            Vec_IntFree( vNodes );
        }
        else
        {
            Gia_ManForEachLut2( p, iLut )
                Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
        }
    }
    else assert( 0 );
    Gia_ManForEachCoDriverId( p, iLut, k )
        DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
    //printf( "The number of edges = %d.  Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
    return DelayMax;
}

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

  Synopsis    [Finds edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ObjComputeEdgeDelay2( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay, Vec_Int_t * vEdge1, Vec_Int_t * vEdge2, Vec_Int_t * vFanMax1, Vec_Int_t * vFanMax2, Vec_Int_t * vCountMax )
{
    int i, iFan, DelayFanin, Status1, Status2;
    int DelayMax = 0, nCountMax = 0;
    int iFanMax1 = -1, iFanMax2 = -1;
    Vec_IntWriteEntry(vEdge1, iObj, 0);
    Vec_IntWriteEntry(vEdge2, iObj, 0);
    // analyze this node
    DelayMax = Vec_IntEntry( vDelay, iObj );
    nCountMax = Vec_IntEntry( vCountMax, iObj );
    if ( DelayMax == 0 )
    {}
    else if ( nCountMax == 1 )
    {
        iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
        Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
        if ( Status1 <= 1 )
        {
            Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
            DelayMax--;
        }
    }
    else if ( nCountMax == 2 )
    {
        iFanMax1 = Vec_IntEntry( vFanMax1, iObj );
        iFanMax2 = Vec_IntEntry( vFanMax2, iObj );
        Status1 = Gia_ObjEdgeCount( iFanMax1, vEdge1, vEdge2 );
        Status2 = Gia_ObjEdgeCount( iFanMax2, vEdge1, vEdge2 );
        if ( Status1 <= 1 && Status2 <= 1 )
        {
            Gia_ObjEdgeAdd( iFanMax1, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iFanMax2, iObj, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax1, vEdge1, vEdge2 );
            Gia_ObjEdgeAdd( iObj, iFanMax2, vEdge1, vEdge2 );
            DelayMax--;
        }
    }
    Vec_IntWriteEntry( vDelay, iObj, DelayMax );
    // computed DelayMax at this point
    if ( Gia_ManHasMapping(p) && Gia_ObjIsLut(p, iObj) )
    {
        Gia_LutForEachFanin( p, iObj, iFan, i )
        {
            DelayFanin = Vec_IntEntry( vDelay, iFan );
            if ( DelayFanin < DelayMax + 1 )
            {
                Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
                Vec_IntWriteEntry( vFanMax1, iFan, iObj );
                Vec_IntWriteEntry( vCountMax, iFan, 1 );
            }
            else if ( DelayFanin == DelayMax + 1 )
            {
                Vec_IntWriteEntry( vFanMax2, iFan, iObj );
                Vec_IntAddToEntry( vCountMax, iFan, 1 );
            }
        }
    }
    else if ( Gia_ObjIsLut2(p, iObj) )
    {
        Gia_LutForEachFanin2( p, iObj, iFan, i )
        {
            DelayFanin = Vec_IntEntry( vDelay, iFan );
            if ( DelayFanin < DelayMax + 1 )
            {
                Vec_IntWriteEntry( vDelay, iFan, DelayMax + 1 );
                Vec_IntWriteEntry( vFanMax1, iFan, iObj );
                Vec_IntWriteEntry( vCountMax, iFan, 1 );
            }
            else if ( DelayFanin == DelayMax + 1 )
            {
                Vec_IntWriteEntry( vFanMax2, iFan, iObj );
                Vec_IntAddToEntry( vCountMax, iFan, 1 );
            }
        }
    }
    else assert( 0 );
    return DelayMax;
}
int Gia_ManComputeEdgeDelay2( Gia_Man_t * p )
{
    int k, iLut, DelayMax = 0;
    Vec_Int_t * vFanMax1 = Vec_IntStart( Gia_ManObjNum(p) );
    Vec_Int_t * vFanMax2 = Vec_IntStart( Gia_ManObjNum(p) );
    Vec_Int_t * vCountMax = Vec_IntStart( Gia_ManObjNum(p) );
    assert( p->pManTime == NULL );
    Vec_IntFreeP( &p->vEdgeDelay );
    Vec_IntFreeP( &p->vEdge1 );
    Vec_IntFreeP( &p->vEdge2 );
    p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
//    Gia_ManForEachCoDriverId( p, iLut, k )
//        Vec_IntWriteEntry( p->vEdgeDelay, iLut, 1 );
    if ( Gia_ManHasMapping(p) )
        Gia_ManForEachLutReverse( p, iLut )
            Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
    else if ( Gia_ManHasMapping2(p) )
        Gia_ManForEachLut2Reverse( p, iLut )
            Gia_ObjComputeEdgeDelay2( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, vFanMax1, vFanMax2, vCountMax );
    else assert( 0 );
    Gia_ManForEachCiId( p, iLut, k )
        DelayMax = Abc_MaxInt( DelayMax, Vec_IntEntry(p->vEdgeDelay, iLut) );
    Vec_IntFree( vFanMax1 );
    Vec_IntFree( vFanMax2 );
    Vec_IntFree( vCountMax );
    //printf( "The number of edges = %d.  Delay = %d.\n", Gia_ManEvalEdgeCount(p), DelayMax );
    return DelayMax;
}

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

  Synopsis    [Finds edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManUpdateMapping( Gia_Man_t * p, Vec_Int_t * vNodes, Vec_Wec_t * vWin )
{
    int i, iNode;
    Vec_IntForEachEntry( vNodes, iNode, i )
        ABC_SWAP( Vec_Int_t, *Vec_WecEntry(p->vMapping2, iNode), *Vec_WecEntry(vWin, i) );
}
int Gia_ManEvalWindowInc( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
{
    int i, iLut, Delay, DelayMax = 0;
    assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
    Gia_ManUpdateMapping( p, vNodes, vWin );
    Gia_ManCollectTfo( p, vLeaves, vTemp );
    Vec_IntReverseOrder( vTemp );
    Vec_IntForEachEntry( vTemp, iLut, i )
    {
        if ( !Gia_ObjIsLut(p, iLut) )
            continue;
        Delay = Gia_ObjComputeEdgeDelay( p, iLut, p->vEdgeDelay, p->vEdge1, p->vEdge2, fUseTwo );
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    Gia_ManUpdateMapping( p, vNodes, vWin );
    return DelayMax;
}
int Gia_ManEvalWindow( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, Vec_Wec_t * vWin, Vec_Int_t * vTemp, int fUseTwo )
{
    int DelayMax;
    assert( Vec_IntSize(vNodes) == Vec_WecSize(vWin) );
    Gia_ManUpdateMapping( p, vNodes, vWin );
    DelayMax = Gia_ManComputeEdgeDelay( p, fUseTwo );
    Gia_ManUpdateMapping( p, vNodes, vWin );
    return DelayMax;
}




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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Edg_ManToMapping( Gia_Man_t * p )
{
    int iObj, iFanin, k;
    assert( Gia_ManHasMapping(p) );
    Vec_WecFreeP( &p->vMapping2 );
    Vec_WecFreeP( &p->vFanouts2 );
    p->vMapping2 = Vec_WecStart( Gia_ManObjNum(p) );
    p->vFanouts2 = Vec_WecStart( Gia_ManObjNum(p) );
    Gia_ManForEachLut( p, iObj )
    {
        assert( Gia_ObjLutSize(p, iObj) <= 4 );
        Gia_LutForEachFanin( p, iObj, iFanin, k )
        {
            Vec_WecPush( p->vMapping2, iObj, iFanin );
            Vec_WecPush( p->vFanouts2, iFanin, iObj );
        }
    }
}

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

  Synopsis    [Computes delay for the given edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Edg_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
    int DelayEdge = 0; // 2;
    int DelayNoEdge = 1;
    int i, iFan, Delay, DelayMax = 0;
    assert( Gia_ObjIsLut2(p, iObj) );
    Gia_LutForEachFanin2( p, iObj, iFan, i )
    {
        Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    //printf( "Obj %d - Level %d\n", iObj, DelayMax );
    return DelayMax;
}
int Edg_ManEvalEdgeDelay( Gia_Man_t * p )
{
    int iLut, Delay, DelayMax = 0;
    assert( p->vEdge1 && p->vEdge2 );
    if ( p->vEdgeDelay == NULL )
        p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) );
    else
        Vec_IntFill( p->vEdgeDelay, Gia_ManObjNum(p), 0 );
    Gia_ManForEachLut2( p, iLut )
    {
        Delay = Edg_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay);
        Vec_IntWriteEntry( p->vEdgeDelay, iLut, Delay );
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    return DelayMax;
}

static inline int Edg_ObjEvalEdgeDelayR( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay )
{
    int DelayEdge = 0; // 2;
    int DelayNoEdge = 1;
    int i, iFan, Delay, DelayMax = 0;
    assert( Gia_ObjIsLut2(p, iObj) );
    Gia_LutForEachFanout2( p, iObj, iFan, i )
    {
        Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge);
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    //printf( "Obj %d - LevelR %d\n", iObj, DelayMax );
    return DelayMax;
}
int Edg_ManEvalEdgeDelayR( Gia_Man_t * p )
{
//    int k, DelayNoEdge = 1;
    int iLut, Delay, DelayMax = 0;
    assert( p->vEdge1 && p->vEdge2 );
    if ( p->vEdgeDelayR == NULL )
        p->vEdgeDelayR = Vec_IntStart( Gia_ManObjNum(p) );
    else
        Vec_IntFill( p->vEdgeDelayR, Gia_ManObjNum(p), 0 );
//    Gia_ManForEachCoDriverId( p, iLut, k )
//        Vec_IntWriteEntry( p->vEdgeDelayR, iLut, DelayNoEdge );
    Gia_ManForEachLut2Reverse( p, iLut )
    {
        Delay = Edg_ObjEvalEdgeDelayR(p, iLut, p->vEdgeDelayR);
        Vec_IntWriteEntry( p->vEdgeDelayR, iLut, Delay );
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    return DelayMax;
}

void Edg_ManCollectCritEdges( Gia_Man_t * p, Vec_Wec_t * vEdges, int DelayMax )
{
    Vec_Int_t * vLevel;
    int k, iLut, Delay1, Delay2;
    assert( p->vEdge1 && p->vEdge2 );
    Vec_WecClear( vEdges );
    Vec_WecInit( vEdges, DelayMax + 1 );
    Gia_ManForEachLut2( p, iLut )
    {
        Delay1 = Vec_IntEntry( p->vEdgeDelay, iLut );
        Delay2 = Vec_IntEntry( p->vEdgeDelayR, iLut );
        assert( Delay1 + Delay2 <= DelayMax );
        if ( Delay1 + Delay2 == DelayMax )
            Vec_WecPush( vEdges, Delay1, iLut );
    }
    // every level should have critical nodes, except the first one
    //Vec_WecPrint( vEdges, 0 );
    Vec_WecForEachLevelStart( vEdges, vLevel, k, 1 )
        assert( Vec_IntSize(vLevel) > 0 );
}


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

  Synopsis    [Update one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Edg_ObjImprove( Gia_Man_t * p, int iObj, int nEdgeLimit, int DelayMax, int fVerbose )
{
    int nFaninsC = 0,   nFanoutsC = 0;    // critical
    int nFaninsEC = 0,  nFanoutsEC = 0;   // edge-critical
    int nFaninsENC = 0, nFanoutsENC = 0;  // edge-non-critial
    int pFanins[4], pFanouts[4];
    int nEdgeDiff, nEdges = 0, Count = 0;
    int i, iNext, Delay1, Delay2;
    // count how many fanins have critical edge
    Delay1 = Vec_IntEntry( p->vEdgeDelayR, iObj );
    //if ( Delay1 > 1 )
    Gia_LutForEachFanin2( p, iObj, iNext, i )
    {
        if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
            continue;
        Delay2 = Vec_IntEntry( p->vEdgeDelay, iNext );
        if ( Gia_ObjHaveEdge(p, iObj, iNext) )
        {
            nEdges++;
            assert( Delay1 + Delay2 <= DelayMax );
            if ( Delay1 + Delay2 == DelayMax )
                nFaninsEC++;
            else
                nFaninsENC++;
        }
        else
        {
            assert( Delay1 + Delay2 + 1 <= DelayMax );
            if ( Delay1 + Delay2 + 1 == DelayMax )
                pFanins[nFaninsC++] = iNext;
        }
    }
    // count how many fanouts have critical edge
    Delay1 = Vec_IntEntry( p->vEdgeDelay, iObj );
    //if ( Delay2 < DelayMax - 1 )
    Gia_LutForEachFanout2( p, iObj, iNext, i )
    {
        //if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) )
        //    continue;
        assert( Gia_ObjIsAnd(Gia_ManObj(p, iNext)) );
        Delay2 = Vec_IntEntry( p->vEdgeDelayR, iNext );
        if ( Gia_ObjHaveEdge(p, iObj, iNext) )
        {
            nEdges++;
            assert( Delay1 + Delay2 <= DelayMax );
            if ( Delay1 + Delay2 == DelayMax )
                nFanoutsEC++;
            else
                nFanoutsENC++;
        }
        else
        {
            assert( Delay1 + Delay2 + 1 <= DelayMax );
            if ( Delay1 + Delay2 + 1 == DelayMax )
            {
                if ( nFanoutsC < nEdgeLimit )
                    pFanouts[nFanoutsC] = iNext;
                nFanoutsC++;
            }
        }
    }
    if ( fVerbose )
    {
        printf( "%8d : ", iObj );
        printf( "Edges = %d  ", nEdges );
        printf( "Fanins (all %d  EC %d  ENC %d  C %d)  ", 
            Gia_ObjLutSize2(p, iObj), nFaninsEC, nFaninsENC, nFaninsC );
        printf( "Fanouts (all %d  EC %d  ENC %d  C %d)  ", 
            Gia_ObjLutFanoutNum2(p, iObj), nFanoutsEC, nFanoutsENC, nFanoutsC );
    }
    // consider simple cases
    assert( nEdges <= nEdgeLimit );
    if ( nEdges == nEdgeLimit )
    {
        if ( fVerbose )
            printf( "Full\n" );
        return 0;
    }
    nEdgeDiff = nEdgeLimit - nEdges;
    // check if fanins or fanouts could be improved
    if ( nFaninsEC == 0 && nFaninsC && nFaninsC <= nEdgeDiff )
    {
        for ( i = 0; i < nFaninsC; i++ )
            if ( Gia_ObjEdgeCount(pFanins[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
                break;
        if ( i == nFaninsC )
        {
            for ( i = 0; i < nFaninsC; i++ )
            {
                Count += Gia_ObjEdgeAdd( iObj, pFanins[i], p->vEdge1, p->vEdge2 );
                Count += Gia_ObjEdgeAdd( pFanins[i], iObj, p->vEdge1, p->vEdge2 );
            }
            if ( Count )
                printf( "Wrong number of edges.\n" );
            if ( fVerbose )
                printf( "Fixed %d critical fanins\n", nFaninsC );
            return 1;
        }
    }
    if ( nFanoutsEC == 0 && nFanoutsC && nFanoutsC <= nEdgeDiff )
    {
        for ( i = 0; i < nFanoutsC; i++ )
            if ( Gia_ObjEdgeCount(pFanouts[i], p->vEdge1, p->vEdge2) == nEdgeLimit )
                break;
        if ( i == nFanoutsC )
        {
            for ( i = 0; i < nFanoutsC; i++ )
            {
                Count += Gia_ObjEdgeAdd( iObj, pFanouts[i], p->vEdge1, p->vEdge2 );
                Count += Gia_ObjEdgeAdd( pFanouts[i], iObj, p->vEdge1, p->vEdge2 );
            }
            if ( Count )
                printf( "Wrong number of edges.\n" );
            if ( fVerbose )
                printf( "Fixed %d critical fanouts\n", nFanoutsC );
            return 1;
        }
    }
    if ( fVerbose )
        printf( "Cannot fix\n" );
    return 0;
}

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

  Synopsis    [Finds edge assignment.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Edg_ManAssignEdgeNew( Gia_Man_t * p, int nEdges, int fVerbose )
{
    int DelayNoEdge = 1;
    int fLevelVerbose = 0;
    Vec_Int_t * vLevel;
    Vec_Wec_t * vEdges = Vec_WecStart(0);
    Vec_Int_t * vEdge1 = NULL, * vEdge2 = NULL;
    int DelayD = 0, DelayR = 0, DelayPrev = ABC_INFINITY;
    int k, j, i, iLast = -1, iObj;
    if ( fVerbose )
        printf( "Running edge assignment with E = %d.\n", nEdges );
    // create fanouts
    Edg_ManToMapping( p );
    // create empty assignment
    Vec_IntFreeP( &p->vEdge1 );
    Vec_IntFreeP( &p->vEdge2 );
    p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) );
    p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) );
    // perform optimization
    for ( i = 0; i < 10000; i++ )
    {
        // if there is no improvement after 10 iterations, quit
        if ( i > iLast + 50 )
            break;
        // create delay information
        DelayD = Edg_ManEvalEdgeDelay( p );
        DelayR = Edg_ManEvalEdgeDelayR( p );
        assert( DelayD == DelayR + DelayNoEdge );
        if ( DelayPrev > DelayD )
        {
            //printf( "Saving backup point at %d levels.\n", DelayD );
            Vec_IntFreeP( &vEdge1 );  vEdge1 = Vec_IntDup( p->vEdge1 );
            Vec_IntFreeP( &vEdge2 );  vEdge2 = Vec_IntDup( p->vEdge2 );
            DelayPrev = DelayD;
            iLast = i;
        }
        if ( fVerbose )
            printf( "\nIter %4d : Delay = %4d\n", i, DelayD );
        // collect critical nodes (nodes with critical edges)
        Edg_ManCollectCritEdges( p, vEdges, DelayD );
        // sort levels according to the number of critical edges
        if ( fLevelVerbose )
        {
            Vec_WecForEachLevel( vEdges, vLevel, k )
                Vec_IntPush( vLevel, k );
        }
        Vec_WecSort( vEdges, 0 );
        if ( fLevelVerbose )
        {
            Vec_WecForEachLevel( vEdges, vLevel, k )
            {
                int Level = Vec_IntPop( vLevel );
                printf( "%d: Level %2d : ", k, Level );
                Vec_IntPrint( vLevel );
            }
        }
        Vec_WecForEachLevel( vEdges, vLevel, k )
        {
            Vec_IntForEachEntry( vLevel, iObj, j )
                if ( Edg_ObjImprove(p, iObj, nEdges, DelayD, fVerbose) ) // improved
                    break;
            if ( j < Vec_IntSize(vLevel) )
                break;
        }
        if ( k == Vec_WecSize(vEdges) ) // if we could not improve anything, quit
            break;
    }
    Vec_WecFree( vEdges );
    // update to the saved version
    Vec_IntFreeP( &p->vEdge1 );  p->vEdge1 = vEdge1;
    Vec_IntFreeP( &p->vEdge2 );  p->vEdge2 = vEdge2;
    return DelayD;
}


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


ABC_NAMESPACE_IMPL_END