llb2Flow.c

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

  FileName    [llb2Flow.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [BDD based reachability.]

  Synopsis    [Flow computation.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "llbInt.h"

ABC_NAMESPACE_IMPL_START


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

static inline int         Llb_ObjSetPath( Aig_Obj_t * pObj, Aig_Obj_t * pNext ) { pObj->pData = (void *)pNext; return 1;  }
static inline Aig_Obj_t * Llb_ObjGetPath( Aig_Obj_t * pObj )                    { return (Aig_Obj_t *)pObj->pData;        }
static inline Aig_Obj_t * Llb_ObjGetFanoutPath( Aig_Man_t * p, Aig_Obj_t * pObj ) 
{ 
    Aig_Obj_t * pFanout;
    int i, iFanout;
    assert( Llb_ObjGetPath(pObj) ); 
    Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
        if ( Llb_ObjGetPath(pFanout) == pObj )
            return pFanout;
    return NULL;
}

extern Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper );

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


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

  Synopsis    [For each cut, returns PIs that can be quantified.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManCutSupps( Aig_Man_t * p, Vec_Ptr_t * vResult )
{
    Vec_Ptr_t * vSupps, * vOne, * vLower, * vUpper;
    int i;
    vSupps = Vec_PtrAlloc( 100 );
    Vec_PtrPush( vSupps, Vec_PtrAlloc(0) );
    vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 );
    Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 )
    {
        vOne  = Llb_ManCutSupp( p, vLower, vUpper );
        Vec_PtrPush( vSupps, vOne );
        vLower = vUpper;
    }
    assert( Vec_PtrSize(vSupps) == Vec_PtrSize(vResult) );
    return vSupps;
}

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

  Synopsis    [For each cut, returns PIs that can be quantified.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManCutMap( Aig_Man_t * p, Vec_Ptr_t * vResult, Vec_Ptr_t * vSupps )
{
    int fShowMatrix = 1;
    Vec_Ptr_t * vMaps, * vOne;
    Vec_Int_t * vMap, * vPrev, * vNext;
    Aig_Obj_t * pObj;
    int * piFirst, * piLast;
    int i, k, CounterPlus, CounterMinus, Counter;

    vMaps = Vec_PtrAlloc( 100 );
    Vec_PtrForEachEntry( Vec_Ptr_t *, vResult, vOne, i )
    {
        vMap = Vec_IntStart( Aig_ManObjNumMax(p) );
        Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k )
        {
            if ( !Saig_ObjIsPi(p, pObj) )
                Vec_IntWriteEntry( vMap, pObj->Id, 1 );
//            else
//printf( "*" );
//printf( "%d ", pObj->Id );
        }
        Vec_PtrPush( vMaps, vMap );
//printf( "\n" );
    }
    Vec_PtrPush( vMaps, Vec_IntStart( Aig_ManObjNumMax(p) ) );
    assert( Vec_PtrSize(vMaps) == Vec_PtrSize(vResult)+1 );

    // collect the first and last PIs
    piFirst = ABC_ALLOC( int, Saig_ManPiNum(p) );
    piLast  = ABC_ALLOC( int, Saig_ManPiNum(p) );
    Saig_ManForEachPi( p, pObj, i )
        piFirst[i] = piLast[i] = -1;
    Vec_PtrForEachEntry( Vec_Ptr_t *, vSupps, vOne, i )
    {
        Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k )
        {
            if ( !Saig_ObjIsPi(p, pObj) )
                continue;
            if ( piFirst[Aig_ObjCioId(pObj)] == -1 )
                 piFirst[Aig_ObjCioId(pObj)] = i;
            piLast[Aig_ObjCioId(pObj)] = i;
        }
    }
    // PIs feeding into the flops should be extended to the last frame
    Saig_ManForEachLi( p, pObj, i )
    {
        if ( !Saig_ObjIsPi(p, Aig_ObjFanin0(pObj)) )
            continue;
        piLast[Aig_ObjCioId(Aig_ObjFanin0(pObj))] = Vec_PtrSize(vMaps)-1;
    }

    // set the PI map
    Saig_ManForEachPi( p, pObj, i )
    {
        if ( piFirst[i] == -1 )
            continue;
        if ( piFirst[i] == piLast[i] )
        {
            vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, piFirst[i] );
            Vec_IntWriteEntry( vMap, pObj->Id, 2 );
            continue;
        }

        // set support for all in between        
        for ( k = piFirst[i]; k <= piLast[i]; k++ )
        {
            vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, k );
            Vec_IntWriteEntry( vMap, pObj->Id, 1 );
        }
    }
    ABC_FREE( piFirst );
    ABC_FREE( piLast );


    // find all that will appear here
    Counter = Aig_ManRegNum(p);
    printf( "%d ", Counter );
    Vec_PtrForEachEntryStart( Vec_Int_t *, vMaps, vMap, i, 1 )
    {
        vPrev = (Vec_Int_t *)Vec_PtrEntry( vMaps, i-1 );
        vNext = (i == Vec_PtrSize(vMaps)-1)? NULL: (Vec_Int_t *)Vec_PtrEntry( vMaps, i+1 );

        CounterPlus = CounterMinus = 0;
        Aig_ManForEachObj( p, pObj, k )
        {
            if ( Saig_ObjIsPi(p, pObj) )
            {
                if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 )
                    CounterPlus++;
                if ( Vec_IntEntry(vMap, k) == 1 && (vNext == NULL || Vec_IntEntry(vNext, k) == 0) )
                    CounterMinus++;
            }
            else
            {
                if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 )
                    CounterPlus++;
                if ( Vec_IntEntry(vPrev, k) == 1 && Vec_IntEntry(vMap, k) == 0 )
                    CounterMinus++;
            }
        }
        Counter = Counter + CounterPlus - CounterMinus;
        printf( "%d=%d ", i, Counter );
    }
    printf( "\n" );

    if ( fShowMatrix )
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) )
            continue;
        Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k )
            if ( Vec_IntEntry(vMap, i) )
                break;
        if ( k == Vec_PtrSize(vMaps) )
            continue;
        printf( "Obj = %4d : ", i );
        if ( Saig_ObjIsPi(p,pObj) )
            printf( "pi  " );
        else if ( Saig_ObjIsLo(p,pObj) )
            printf( "lo  " );
        else if ( Aig_ObjIsNode(pObj) )
            printf( "and " );

        Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k )
            printf( "%d", Vec_IntEntry(vMap, i) );
        printf( "\n" );
    }
    return vMaps;
}

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

  Synopsis    [Counts the number of PIs in the cut]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManCutPiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
{
    Aig_Obj_t * pObj;
    int i, Counter = 0;
    Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
        if ( Saig_ObjIsPi(p,pObj) )
            Counter++;
    return Counter;
}

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

  Synopsis    [Counts the number of LOs in the cut]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManCutLoNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
{
    Aig_Obj_t * pObj;
    int i, Counter = 0;
    Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
        if ( Saig_ObjIsLo(p,pObj) )
            Counter++;
    return Counter;
}

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

  Synopsis    [Counts the number of LIs in the cut]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManCutLiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
{
    Aig_Obj_t * pFanout;
    Aig_Obj_t * pObj;
    int i, k, iFanout = -1, Counter = 0;
    Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
    {
        if ( Aig_ObjIsCi(pObj) )
            continue;
        Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, k )
        {
            if ( Saig_ObjIsLi(p, pFanout) )
            {
                Counter++;
                break;
            }
        }
    }
    return Counter;
}

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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManCutVolume_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
{
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Aig_ObjSetTravIdCurrent(p, pObj);
    assert( Aig_ObjIsNode(pObj) );
    return 1 + Llb_ManCutVolume_rec(p, Aig_ObjFanin0(pObj)) + 
        Llb_ManCutVolume_rec(p, Aig_ObjFanin1(pObj));
}

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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManCutVolume( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Aig_Obj_t * pObj;
    int i, Counter = 0;
    // mark the lower cut with the traversal ID
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
        Aig_ObjSetTravIdCurrent( p, pObj );
    // count the upper cut
    Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
        Counter += Llb_ManCutVolume_rec( p, pObj );
    return Counter;
}


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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManCutNodes_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(p, pObj);
    assert( Aig_ObjIsNode(pObj) );
    Llb_ManCutNodes_rec(p, Aig_ObjFanin0(pObj), vNodes);
    Llb_ManCutNodes_rec(p, Aig_ObjFanin1(pObj), vNodes);
    Vec_PtrPush( vNodes, pObj );
}

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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManCutNodes( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Vec_Ptr_t * vNodes;
    Aig_Obj_t * pObj;
    int i;
    // mark the lower cut with the traversal ID
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
        Aig_ObjSetTravIdCurrent( p, pObj );
    // count the upper cut
    vNodes = Vec_PtrAlloc( 100 );
    Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
        Llb_ManCutNodes_rec( p, pObj, vNodes );
    return vNodes;
}

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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Vec_Ptr_t * vNodes, * vSupp;
    Aig_Obj_t * pObj;
    int i;
    vNodes = Llb_ManCutNodes( p, vLower, vUpper );
    // mark support of the nodes
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
    {
        assert( Aig_ObjIsNode(pObj) );
        Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin0(pObj) );
        Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin1(pObj) );
    }
    Vec_PtrFree( vNodes );
    // collect the support nodes
    vSupp = Vec_PtrAlloc( 100 );
    Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
        if ( Aig_ObjIsTravIdCurrent(p, pObj) )
            Vec_PtrPush( vSupp, pObj );
    return vSupp;

}

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

  Synopsis    [Computes volume of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManCutRange( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Vec_Ptr_t * vRange;
    Aig_Obj_t * pObj;
    int i;
    // mark the lower cut with the traversal ID
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
        Aig_ObjSetTravIdCurrent( p, pObj );
    // collect the upper ones that are not marked
    vRange = Vec_PtrAlloc( 100 );
    Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
        if ( !Aig_ObjIsTravIdCurrent(p, pObj) )
            Vec_PtrPush( vRange, pObj );
    return vRange;
}




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

  Synopsis    [Prints the given cluster.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManCutPrint( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Vec_Ptr_t * vSupp, * vRange;
    int Pis, Ffs, And;

    Pis = Llb_ManCutPiNum(p, vLower);
    Ffs = Llb_ManCutLoNum(p, vLower);
    And = Vec_PtrSize(vLower) - Pis - Ffs;
    printf( "Leaf: %3d=%3d+%3d+%3d  ",  Vec_PtrSize(vLower), Pis, Ffs, And );

    Pis = Llb_ManCutPiNum(p, vUpper);
    Ffs = Llb_ManCutLiNum(p, vUpper);
    And = Vec_PtrSize(vUpper) - Pis - Ffs;
    printf( "Root: %3d=%3d+%3d+%3d  ", Vec_PtrSize(vUpper), Pis, Ffs, And );

    vSupp = Llb_ManCutSupp( p, vLower, vUpper );
    Pis = Llb_ManCutPiNum(p, vSupp);
    Ffs = Llb_ManCutLoNum(p, vSupp);
    And = Vec_PtrSize(vSupp) - Pis - Ffs;
    printf( "Supp: %3d=%3d+%3d+%3d  ", Vec_PtrSize(vSupp), Pis, Ffs, And );

    vRange = Llb_ManCutRange( p, vLower, vUpper );
    Pis = Llb_ManCutPiNum(p, vRange);
    Ffs = Llb_ManCutLiNum(p, vRange);
    And = Vec_PtrSize(vRange) - Pis - Ffs;
    printf( "Range: %3d=%3d+%3d+%3d  ", Vec_PtrSize(vRange), Pis, Ffs, And );

    printf( "S =%3d. V =%3d.\n", 
        Vec_PtrSize(vSupp)+Vec_PtrSize(vRange), Llb_ManCutVolume(p, vLower, vUpper) );
    Vec_PtrFree( vSupp );
    Vec_PtrFree( vRange );
/*   
    {
        Aig_Obj_t * pObj;
        int i;
        printf( "Lower: " );
        Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
            printf( " %d", pObj->Id );
        printf( "     " );
        printf( "Upper: " );
        Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
            printf( " %d", pObj->Id );
        printf( "\n" );
    }
*/
}

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

  Synopsis    [Prints the given cluster.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManResultPrint( Aig_Man_t * p, Vec_Ptr_t * vResult )
{
    Vec_Ptr_t * vLower, * vUpper;
    int i;
    Vec_PtrForEachEntryReverse( Vec_Ptr_t *, vResult, vLower, i )
    {
        if ( i < Vec_PtrSize(vResult) - 1 )
            Llb_ManCutPrint( p, vLower, vUpper );
        vUpper = vLower;
    }
}

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

  Synopsis    [Tries to find an augmenting path originating in this node.]

  Description [This procedure works for directed graphs only!]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManFlowBwdPath2_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
{
    Aig_Obj_t * pFanout;
    assert( Aig_ObjIsNode(pObj) || Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) );
    // skip visited nodes
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Aig_ObjSetTravIdCurrent(p, pObj);
    // process node without flow
    if ( !Llb_ObjGetPath(pObj) )
    {
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Llb_ObjSetPath( pObj, (Aig_Obj_t *)1 );
        // explore the fanins
//        Abc_ObjForEachFanin( pObj, pFanin, i )
//            if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
//                return Abc_ObjSetPath( pObj, pFanin );
        if ( Aig_ObjIsNode(pObj) )
        {
            if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ) )
                return Llb_ObjSetPath( pObj, Aig_ObjFanin0(pObj) );
            if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ) )
                return Llb_ObjSetPath( pObj, Aig_ObjFanin1(pObj) );
        }
        return 0;
    }
    // pObj has flow - find the fanout with flow
    pFanout = Llb_ObjGetFanoutPath( p, pObj );
    if ( pFanout == NULL )
        return 0;
    // go through the fanins of the fanout with flow
//    Abc_ObjForEachFanin( pFanout, pFanin, i )
//        if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) )
//            return Abc_ObjSetPath( pFanout, pFanin );
    assert( Aig_ObjIsNode(pFanout) );
    if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pFanout) ) )
        return Llb_ObjSetPath( pFanout, Aig_ObjFanin0(pFanout) );
    if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pFanout) ) )
        return Llb_ObjSetPath( pFanout, Aig_ObjFanin1(pFanout) );
    // try the fanout
    if ( Llb_ManFlowBwdPath2_rec( p, pFanout ) )
        return Llb_ObjSetPath( pFanout, NULL );
    return 0;
}


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

  Synopsis    [Cleans markB.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowLabelTfi_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
{
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(p, pObj);
    if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
        return;
    assert( Aig_ObjIsNode(pObj) );
    Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin0(pObj) );
    Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin1(pObj) );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowUpdateCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
{
    Aig_Obj_t * pObj;
    int i;
    // label the TFI of the cut nodes
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
        Llb_ManFlowLabelTfi_rec( p, pObj );
    // collect labeled fanins of non-labeled nodes
    Vec_PtrClear( vMinCut );
    Aig_ManIncrementTravId(p);
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( !Aig_ObjIsCo(pObj) && !Aig_ObjIsNode(pObj) )
            continue;
        if ( Aig_ObjIsTravIdCurrent(p, pObj) || Aig_ObjIsTravIdPrevious(p, pObj) )
            continue;
        if ( Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin0(pObj)) )
        {
            Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin0(pObj));
            Vec_PtrPush( vMinCut, Aig_ObjFanin0(pObj) );
        }
        if ( Aig_ObjIsNode(pObj) && Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin1(pObj)) )
        {
            Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin1(pObj));
            Vec_PtrPush( vMinCut, Aig_ObjFanin1(pObj) );
        }
    }
}

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

  Synopsis    [Find minimum-volume minumum cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManFlowMinCut( Aig_Man_t * p )
{
    Vec_Ptr_t * vMinCut;
    Aig_Obj_t * pObj;
    int i;
    // collect the cut nodes
    vMinCut = Vec_PtrAlloc( Aig_ManRegNum(p) );
    Aig_ManForEachObj( p, pObj, i )
    {
        // node without flow is not a cut node
        if ( !Llb_ObjGetPath(pObj) )
            continue;
        // unvisited node is below the cut
        if ( !Aig_ObjIsTravIdCurrent(p, pObj) )
            continue;
        // add terminal with flow or node whose path is not visited
        if ( pObj->fMarkA || !Aig_ObjIsTravIdCurrent( p, Llb_ObjGetPath(pObj) ) )
            Vec_PtrPush( vMinCut, pObj );
    }
    return vMinCut;
}

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

  Synopsis    [Verifies the min-cut is indeed a cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManFlowVerifyCut_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
{
    // skip visited nodes
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return 1;
    Aig_ObjSetTravIdCurrent(p, pObj);
    // visit the node
    if ( Aig_ObjIsConst1(pObj) )
        return 1;
    if ( Aig_ObjIsCi(pObj) )
        return 0;
    // explore the fanins
    assert( Aig_ObjIsNode(pObj) );
    if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin0(pObj)) )
        return 0;
    if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin1(pObj)) )
        return 0;
    return 1;
}

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

  Synopsis    [Verifies the min-cut is indeed a cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Llb_ManFlowVerifyCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
{
    Aig_Obj_t * pObj;
    int i;
    // mark the cut with the current traversal ID
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
        Aig_ObjSetTravIdCurrent( p, pObj );
    // search from the latches for a path to the COs/CIs
    Saig_ManForEachLi( p, pObj, i )
    {
        if ( !Llb_ManFlowVerifyCut_rec( p, Aig_ObjFanin0(pObj) ) )
            return 0;
    }
    return 1;
}

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

  Synopsis    [Implementation of max-flow/min-cut computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManFlow( Aig_Man_t * p, Vec_Ptr_t * vSources, int * pnFlow )
{
    Vec_Ptr_t * vMinCut;
    Aig_Obj_t * pObj;
    int Flow, FlowCur, RetValue, i;
    // find the max-flow
    Flow = 0;
    Aig_ManCleanData( p );
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i )
    {
        assert( !pObj->fMarkA && pObj->fMarkB );
        if ( !Aig_ObjFanin0(pObj)->fMarkB )
        {
            FlowCur  = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
            Flow    += FlowCur;
            if ( FlowCur )
                Aig_ManIncrementTravId(p);
        }
        if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
        {
            FlowCur  = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
            Flow    += FlowCur;
            if ( FlowCur )
                Aig_ManIncrementTravId(p);
        }
    }
    if ( pnFlow )
        *pnFlow = Flow;

    // mark the nodes reachable from the latches
    Aig_ManIncrementTravId(p);
    Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i )
    {
        assert( !pObj->fMarkA && pObj->fMarkB );
        if ( !Aig_ObjFanin0(pObj)->fMarkB )
        {
            RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
            assert( RetValue == 0 );
        }
        if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
        {
            RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
            assert( RetValue == 0 );
        }
    }

    // find the min-cut with the smallest volume
    vMinCut = Llb_ManFlowMinCut( p );
    assert( Vec_PtrSize(vMinCut) == Flow );
    // verify the cut
    if ( !Llb_ManFlowVerifyCut(p, vMinCut) )
        printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" );
//    Llb_ManFlowPrintCut( p, vMinCut );
    return vMinCut;
}

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

  Synopsis    [Implementation of max-flow/min-cut computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManFlowCompute( Aig_Man_t * p )
{
    Vec_Ptr_t * vMinCut;
    Aig_Obj_t * pObj;
    int Flow, FlowCur, RetValue, i;
    // find the max-flow
    Flow = 0;
    Aig_ManCleanData( p );
    Aig_ManIncrementTravId(p);
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( !pObj->fMarkB )
            continue;
        assert( !pObj->fMarkA );
        if ( !Aig_ObjFanin0(pObj)->fMarkB )
        {
//printf( "%d ", Aig_ObjFanin0(pObj)->Id );
            FlowCur  = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
            Flow    += FlowCur;
            if ( FlowCur )
                Aig_ManIncrementTravId(p);
        }
        if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
        {
//printf( "%d ", Aig_ObjFanin1(pObj)->Id );
            FlowCur  = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
            Flow    += FlowCur;
            if ( FlowCur )
                Aig_ManIncrementTravId(p);
        }
    }
//printf( "\n" );

    // mark the nodes reachable from the latches
    Aig_ManIncrementTravId(p);
    Aig_ManForEachObj( p, pObj, i )
    {
        if ( !pObj->fMarkB )
            continue;
        assert( !pObj->fMarkA );
        if ( !Aig_ObjFanin0(pObj)->fMarkB )
        {
            RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
            assert( RetValue == 0 );
        }
        if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
        {
            RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
            assert( RetValue == 0 );
        }
    }
    // find the min-cut with the smallest volume
    vMinCut = Llb_ManFlowMinCut( p );
    assert( Vec_PtrSize(vMinCut) == Flow );
//printf( "%d ", Vec_PtrSize(vMinCut) );
    Llb_ManFlowUpdateCut( p, vMinCut );
//printf( "%d   ", Vec_PtrSize(vMinCut) );
    // verify the cut
    if ( !Llb_ManFlowVerifyCut(p, vMinCut) )
        printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" );
//    Llb_ManFlowPrintCut( p, vMinCut );
    return vMinCut;
}




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

  Synopsis    [Cleans markB.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowCleanMarkB_rec( Aig_Obj_t * pObj )
{
    if ( pObj->fMarkB == 0 )
        return;
    pObj->fMarkB = 0;
    assert( Aig_ObjIsNode(pObj) );
    Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin0(pObj) );
    Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin1(pObj) );
}

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

  Synopsis    [Cleans markB.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowSetMarkA_rec( Aig_Obj_t * pObj )
{
    if ( pObj->fMarkA )
        return;
    pObj->fMarkA = 1;
    if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
        return;
    assert( Aig_ObjIsNode(pObj) );
    Llb_ManFlowSetMarkA_rec( Aig_ObjFanin0(pObj) );
    Llb_ManFlowSetMarkA_rec( Aig_ObjFanin1(pObj) );
}

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

  Synopsis    [Prepares flow computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowPrepareCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
{
    Aig_Obj_t * pObj;
    int i;
    // reset marks
    Aig_ManForEachObj( p, pObj, i )
    {
        pObj->fMarkA = 0;
        pObj->fMarkB = 1;
    }
    // clean PIs and const
    Aig_ManConst1(p)->fMarkB = 0;
    Aig_ManForEachCi( p, pObj, i )
        pObj->fMarkB = 0;
    // clean upper cut
//printf( "Upper: ");
    Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
    {
        Llb_ManFlowCleanMarkB_rec( pObj );
//printf( "%d ", pObj->Id );
    }
//printf( "\n" );
    // set lower cut
//printf( "Lower: ");
    Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
    {
//printf( "%d ", pObj->Id );
        assert( pObj->fMarkB == 0 );
        Llb_ManFlowSetMarkA_rec( pObj );
    }
//printf( "\n" );
}

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

  Synopsis    [Prepares flow computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowUnmarkCone( Aig_Man_t * p, Vec_Ptr_t * vCone )
{
    Aig_Obj_t * pObj;
    int i;
    Vec_PtrForEachEntry( Aig_Obj_t *, vCone, pObj, i )
    {
        assert( Aig_ObjIsNode(pObj) );
        assert( pObj->fMarkB == 1 );
        pObj->fMarkB = 0;
    }
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowCollectAndMarkCone_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vCone )
{
    Aig_Obj_t * pFanout;
    int i, iFanout = -1;
    if ( Saig_ObjIsLi(p, pObj) )
        return;
    if ( pObj->fMarkB )
        return;
    if ( pObj->fMarkA == 0 )
    {
        assert( Aig_ObjIsNode(pObj) );
        pObj->fMarkB = 1;
        if ( Aig_ObjIsNode(pObj) )
            Vec_PtrPush( vCone, pObj );
    }
    Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
        Llb_ManFlowCollectAndMarkCone_rec( p, pFanout, vCone );
}

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

  Synopsis    [Collects the cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowCollectAndMarkCone( Aig_Man_t * p, Vec_Ptr_t * vStarts, Vec_Ptr_t * vCone )
{
    Aig_Obj_t * pObj;
    int i;
    Vec_PtrClear( vCone );
    Vec_PtrForEachEntry( Aig_Obj_t *, vStarts, pObj, i )
    {
        assert( pObj->fMarkA && !pObj->fMarkB );
        Llb_ManFlowCollectAndMarkCone_rec( p, pObj, vCone );
    }
}




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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManComputeCutLo( Aig_Man_t * p )
{
    Vec_Ptr_t * vMinCut;
    Aig_Obj_t * pObj;
    int i;
    vMinCut = Vec_PtrAlloc( 100 );
    Aig_ManForEachCi( p, pObj, i )
        Vec_PtrPush( vMinCut, pObj );
    return vMinCut;
}

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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManComputeCutLi( Aig_Man_t * p )
{
    Vec_Ptr_t * vMinCut;
    Aig_Obj_t * pObj;
    int i;
    assert( Saig_ManPoNum(p) == 0 );
    vMinCut = Vec_PtrAlloc( 100 );
    Aig_ManIncrementTravId(p);
    Saig_ManForEachLi( p, pObj, i )
    {
        pObj = Aig_ObjFanin0(pObj);
        if ( Aig_ObjIsConst1(pObj) )
            continue;
        if ( Aig_ObjIsTravIdCurrent(p, pObj) )
            continue;
        Aig_ObjSetTravIdCurrent(p, pObj);
        Vec_PtrPush( vMinCut, pObj );
    }
    return vMinCut;
}



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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManFlowGetObjSet( Aig_Man_t * p, Vec_Ptr_t * vLower, int iStart, int nSize, Vec_Ptr_t * vSet )
{
    Aig_Obj_t * pObj;
    int i;
    Vec_PtrClear( vSet );
    for ( i = 0; i < nSize; i++ )
    {
        pObj = (Aig_Obj_t *)Vec_PtrEntry( vLower, (iStart + i) % Vec_PtrSize(vLower) );
        Vec_PtrPush( vSet, pObj );
    }
}

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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManFlowFindBestCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper, int Num )
{
    int nVolMin = Aig_ManNodeNum(p) / Num / 2;
    Vec_Ptr_t * vMinCut;
    Vec_Ptr_t * vCone, * vSet;
    Aig_Obj_t * pObj;
    int i, s, Vol, VolLower, VolUpper, VolCmp;
    int iBest = -1, iMinCut = ABC_INFINITY, iVolBest = 0;

    Vol = Llb_ManCutVolume( p, vLower, vUpper );
    assert( Vol > nVolMin );
    VolCmp = Abc_MinInt( nVolMin, Vol - nVolMin );
    vCone = Vec_PtrAlloc( 100 );
    vSet  = Vec_PtrAlloc( 100 );
    Llb_ManFlowPrepareCut( p, vLower, vUpper );
    for ( s = 1; s < Aig_ManRegNum(p); s += 5 )
    {
        Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
        {
            Llb_ManFlowGetObjSet( p, vLower, i, s, vSet );
            Llb_ManFlowCollectAndMarkCone( p, vSet, vCone );
            if ( Vec_PtrSize(vCone) == 0 )
                continue;
            vMinCut  = Llb_ManFlowCompute( p );
            Llb_ManFlowUnmarkCone( p, vCone );

            VolLower = Llb_ManCutVolume( p, vLower, vMinCut );
            VolUpper = Llb_ManCutVolume( p, vMinCut, vUpper );
            Vol = Abc_MinInt( VolLower, VolUpper );
            if ( Vol >= VolCmp &&  (iMinCut == -1 || 
                                    iMinCut >  Vec_PtrSize(vMinCut) || 
                                   (iMinCut == Vec_PtrSize(vMinCut) && iVolBest < Vol)) )
            {
                iBest = i;
                iMinCut = Vec_PtrSize(vMinCut);
                iVolBest = Vol;
            }
            Vec_PtrFree( vMinCut );
        }
        if ( iBest >= 0 )
            break;
    }
    if ( iBest == -1 )
    {
        // cleanup
        Vec_PtrFree( vCone );
        Vec_PtrFree( vSet );
        return NULL;
    }
    // get the best cut
    assert( iBest >= 0 );
    Llb_ManFlowGetObjSet( p, vLower, iBest, s, vSet );
    Llb_ManFlowCollectAndMarkCone( p, vSet, vCone );
    vMinCut = Llb_ManFlowCompute( p );
    Llb_ManFlowUnmarkCone( p, vCone );
    // cleanup
    Vec_PtrFree( vCone );
    Vec_PtrFree( vSet );
    return vMinCut;
}

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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Llb_ManComputeCuts( Aig_Man_t * p, int Num, int fVerbose, int fVeryVerbose )
{
    int nVolMax = Aig_ManNodeNum(p) / Num;
    Vec_Ptr_t * vResult, * vMinCut = NULL, * vLower, * vUpper;
    int i, k, nVol;
    clock_t clk = clock();
    vResult = Vec_PtrAlloc( 100 );
    Vec_PtrPush( vResult, Llb_ManComputeCutLo(p) );
    Vec_PtrPush( vResult, Llb_ManComputeCutLi(p) );
    while ( 1 ) 
    {
        // find a place to insert new cut
        vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 );
        Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 )
        {
            nVol = Llb_ManCutVolume( p, vLower, vUpper );
            if ( nVol <= nVolMax )
            {
                vLower = vUpper;
                continue;
            }

            if ( fVeryVerbose )
            Llb_ManCutPrint( p, vLower,  vUpper );
            vMinCut = Llb_ManFlowFindBestCut( p, vLower, vUpper, Num );
            if ( vMinCut == NULL )
            {
                if ( fVeryVerbose )
                printf( "Could not break the cut.\n" );
                if ( fVeryVerbose )
                printf( "\n" );
                vLower = vUpper;
                continue;
            }

            if ( fVeryVerbose )
            Llb_ManCutPrint( p, vMinCut, vUpper );
            if ( fVeryVerbose )
            Llb_ManCutPrint( p, vLower,  vMinCut );
            if ( fVeryVerbose )
            printf( "\n" );

            break;
        }
        if ( i == Vec_PtrSize(vResult) )
            break;
        // insert vMinCut before vUpper
        Vec_PtrPush( vResult, NULL );
        for ( k = Vec_PtrSize(vResult) - 1; k > i; k-- )
            Vec_PtrWriteEntry( vResult, k, Vec_PtrEntry(vResult, k-1) );
        Vec_PtrWriteEntry( vResult, i, vMinCut );
    }
    if ( fVerbose )
    {
        printf( "Finished computing %d partitions.  ", Vec_PtrSize(vResult) - 1 );
        Abc_PrintTime( 1, "Time", clock() - clk );
        Llb_ManResultPrint( p, vResult );
    }
    return vResult;
}
 
/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_BddSetDefaultParams( Gia_ParLlb_t * p )
{
    memset( p, 0, sizeof(Gia_ParLlb_t) );
    p->nBddMax       =  1000000;
    p->nIterMax      = 10000000;
    p->nClusterMax   =       20;
    p->nHintDepth    =        0;
    p->HintFirst     =        0;
    p->fUseFlow      =        0;  // use flow 
    p->nVolumeMax    =      100;  // max volume
    p->nVolumeMin    =       30;  // min volume
    p->fReorder      =        1;
    p->fIndConstr    =        0;
    p->fUsePivots    =        0;
    p->fCluster      =        0;
    p->fSchedule     =        0;
    p->fVerbose      =        0;
    p->fVeryVerbose  =        0;
    p->fSilent       =        0;
    p->TimeLimit     =        0;
//    p->TimeLimit     =        0;
    p->TimeLimitGlo  =        0;
    p->TimeTarget    =        0;
    p->iFrame        =       -1;
}

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

  Synopsis    [Finds balanced cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Llb_ManMinCutTest( Aig_Man_t * pAig, int Num )
{
    extern void Llb_BddConstructTest( Aig_Man_t * p, Vec_Ptr_t * vResult );
    extern void Llb_BddExperiment( Aig_Man_t * pInit, Aig_Man_t * pAig, Gia_ParLlb_t * pPars, Vec_Ptr_t * vResult, Vec_Ptr_t * vMaps );
 

//    int fVerbose = 1;
    Gia_ParLlb_t Pars, * pPars = &Pars;
    Vec_Ptr_t * vResult;//, * vSupps, * vMaps;
    Aig_Man_t * p;

    Llb_BddSetDefaultParams( pPars );

    p = Aig_ManDupFlopsOnly( pAig );
//Aig_ManShow( p, 0, NULL );
    Aig_ManPrintStats( pAig );
    Aig_ManPrintStats( p );
    Aig_ManFanoutStart( p );

    vResult = Llb_ManComputeCuts( p, Num, 1, 0 );
//    vSupps  = Llb_ManCutSupps( p, vResult );
//    vMaps   = Llb_ManCutMap( p, vResult, vSupps );

//    Llb_BddExperiment( pAig, p, pPars, vResult, vMaps );
    Llb_CoreExperiment( pAig, p, pPars, vResult, 0 );

//    Vec_VecFree( (Vec_Vec_t *)vMaps );
//    Vec_VecFree( (Vec_Vec_t *)vSupps );
    Vec_VecFree( (Vec_Vec_t *)vResult );

    Aig_ManFanoutStop( p );
    Aig_ManCleanMarkAB( p );
    Aig_ManStop( p );
}

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


ABC_NAMESPACE_IMPL_END