retFlow.c

Go to the documentation of this file.

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

  FileName    [retFlow.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

  Synopsis    [Implementation of maximum flow (min-area retiming).]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - Oct 31, 2006.]

  Revision    [$Id: retFlow.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $]

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

#include "retInt.h"

ABC_NAMESPACE_IMPL_START


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

static inline int         Abc_ObjSetPath( Abc_Obj_t * pObj, Abc_Obj_t * pNext ) { pObj->pCopy = pNext; return 1;   }
static inline Abc_Obj_t * Abc_ObjGetPath( Abc_Obj_t * pObj )                    { return pObj->pCopy;              }
static inline Abc_Obj_t * Abc_ObjGetFanoutPath( Abc_Obj_t * pObj ) 
{ 
    Abc_Obj_t * pFanout;
    int i;
    assert( Abc_ObjGetPath(pObj) ); 
    Abc_ObjForEachFanout( pObj, pFanout, i )
        if ( Abc_ObjGetPath(pFanout) == pObj )
            return pFanout;
    return NULL;
}
static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * pObj ) 
{ 
    Abc_Obj_t * pFanin;
    int i;
    assert( Abc_ObjGetPath(pObj) ); 
    Abc_ObjForEachFanin( pObj, pFanin, i )
        if ( Abc_ObjGetPath(pFanin) == pObj )
            return pFanin;
    return NULL;
}
static inline Abc_Obj_t * Abc_ObjGetPredecessorBwd( Abc_Obj_t * pObj ) 
{ 
    Abc_Obj_t * pNext;
    int i;
    Abc_ObjForEachFanout( pObj, pNext, i )
        if ( Abc_ObjGetPath(pNext) == pObj )
            return pNext;
    Abc_ObjForEachFanin( pObj, pNext, i )
        if ( Abc_ObjGetPath(pNext) == pObj )
            return pNext;
    return NULL;
}
static inline Abc_Obj_t * Abc_ObjGetPredecessorFwd( Abc_Obj_t * pObj ) 
{ 
    Abc_Obj_t * pNext;
    int i;
    Abc_ObjForEachFanin( pObj, pNext, i )
        if ( Abc_ObjGetPath(pNext) == pObj )
            return pNext;
    Abc_ObjForEachFanout( pObj, pNext, i )
        if ( Abc_ObjGetPath(pNext) == pObj )
            return pNext;
    return NULL;
}

static int         Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
static int         Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
static int         Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
static int         Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
//static int         Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj );
static int         Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin );
static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward );
static void        Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
static int         Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
static void        Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
static void        Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward );

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

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

  Synopsis    [Test-bench for the max-flow computation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
{
    Vec_Ptr_t * vMinCut;
    Abc_Obj_t * pObj;
    int i;

    // forward flow
    Abc_NtkForEachPo( pNtk, pObj, i )
        pObj->fMarkA = 1;
    Abc_NtkForEachLatch( pNtk, pObj, i )
        pObj->fMarkA = Abc_ObjFanin0(pObj)->fMarkA = 1;
//        Abc_ObjFanin0(pObj)->fMarkA = 1;
    vMinCut = Abc_NtkMaxFlow( pNtk, 1, 1 );
    Vec_PtrFree( vMinCut );
    Abc_NtkCleanMarkA( pNtk );

    // backward flow
    Abc_NtkForEachPi( pNtk, pObj, i )
        pObj->fMarkA = 1;
    Abc_NtkForEachLatch( pNtk, pObj, i )
        pObj->fMarkA = Abc_ObjFanout0(pObj)->fMarkA = 1;
//        Abc_ObjFanout0(pObj)->fMarkA = 1;
    vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 );
    Vec_PtrFree( vMinCut );
    Abc_NtkCleanMarkA( pNtk );

}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
{
    Vec_Ptr_t * vMinCut;
    Abc_Obj_t * pLatch;
    int Flow, FlowCur, RetValue, i;
    abctime clk = Abc_Clock();
    int fUseDirectedFlow = 1;

    // find the max-flow
    Abc_NtkCleanCopy( pNtk );
    Flow = 0;
    Abc_NtkIncrementTravId(pNtk);
    Abc_NtkForEachLatch( pNtk, pLatch, i )
    {
        if ( fForward )
        {
//            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
            FlowCur  = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
//            FlowCur  = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
            Flow    += FlowCur;
        }
        else
        {
            assert( !Abc_ObjFanin0(pLatch)->fMarkA );
            FlowCur  = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
            Flow    += FlowCur;
        }
        if ( FlowCur )
            Abc_NtkIncrementTravId(pNtk);
    }

    if ( !fUseDirectedFlow )
    {
        Abc_NtkIncrementTravId(pNtk);
        Abc_NtkForEachLatch( pNtk, pLatch, i )
        {
            if ( fForward )
            {
    //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
                FlowCur  = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
                Flow    += FlowCur;
            }
            else
            {
                assert( !Abc_ObjFanin0(pLatch)->fMarkA );
                FlowCur  = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
                Flow    += FlowCur;
            }
            if ( FlowCur )
                Abc_NtkIncrementTravId(pNtk);
        }
    }
//    Abc_NtkMaxFlowPrintFlow( pNtk, fForward );

    // mark the nodes reachable from the latches
    Abc_NtkIncrementTravId(pNtk);
    Abc_NtkForEachLatch( pNtk, pLatch, i )
    {
        if ( fForward )
        {
//            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
            if ( fUseDirectedFlow )
                RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
//                RetValue = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
            else
                RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
        }
        else
        {
            assert( !Abc_ObjFanin0(pLatch)->fMarkA );
            if ( fUseDirectedFlow )
                RetValue = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
            else
                RetValue = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
        }
        assert( RetValue == 0 );
    }

    // find the min-cut with the smallest volume
    vMinCut = Abc_NtkMaxFlowMinCut( pNtk, fForward );
    // verify the cut
    if ( !Abc_NtkMaxFlowVerifyCut(pNtk, vMinCut, fForward) )
        printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" );
    // make the cut retimable
    Abc_NtkMaxFlowMinCutUpdate( pNtk, vMinCut, fForward );

    // report the results
    if ( fVerbose )
    {
    printf( "L = %6d. %s max-flow = %6d.  Min-cut = %6d.  ", 
        Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) );
ABC_PRT( "Time", Abc_Clock() - clk );
    }

//    Abc_NtkMaxFlowPrintCut( pNtk, vMinCut );
    return vMinCut;
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pNext, * pPred;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 0;
    Abc_NodeSetTravIdCurrent(pObj);
    // get the predecessor
    pPred = Abc_ObjGetPredecessorBwd( pObj );
    // process node without flow
    if ( !Abc_ObjGetPath(pObj) )
    {
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
        // explore the fanins
        Abc_ObjForEachFanin( pObj, pNext, i )
            if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
                return Abc_ObjSetPath( pObj, pNext );
        Abc_ObjForEachFanout( pObj, pNext, i )
            if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
                return Abc_ObjSetPath( pObj, pNext );
        return 0;
    }
    // pObj has flow - find the fanout with flow
    if ( pPred == NULL )
        return 0;
    // go through the successors of the predecessor
    Abc_ObjForEachFanin( pPred, pNext, i )
        if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
            return Abc_ObjSetPath( pPred, pNext );
    Abc_ObjForEachFanout( pPred, pNext, i )
        if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
            return Abc_ObjSetPath( pPred, pNext );
    // try the fanout
    if ( Abc_NtkMaxFlowBwdPath_rec( pPred ) )
        return Abc_ObjSetPath( pPred, NULL );
    return 0;
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pNext, * pPred;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 0;
    Abc_NodeSetTravIdCurrent(pObj);
    // get the predecessor
    pPred = Abc_ObjGetPredecessorFwd( pObj );
    // process node without flow
    if ( !Abc_ObjGetPath(pObj) )
    {
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
        // explore the fanins
        Abc_ObjForEachFanout( pObj, pNext, i )
            if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
                return Abc_ObjSetPath( pObj, pNext );
        Abc_ObjForEachFanin( pObj, pNext, i )
            if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
                return Abc_ObjSetPath( pObj, pNext );
        return 0;
    }
    // pObj has flow - find the fanout with flow
    if ( pPred == NULL )
        return 0;
    // go through the successors of the predecessor
    Abc_ObjForEachFanout( pPred, pNext, i )
        if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
            return Abc_ObjSetPath( pPred, pNext );
    Abc_ObjForEachFanin( pPred, pNext, i )
        if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
            return Abc_ObjSetPath( pPred, pNext );
    // try the fanout
    if ( Abc_NtkMaxFlowFwdPath_rec( pPred ) )
        return Abc_ObjSetPath( pPred, NULL );
    return 0;
}


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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin )
{
    Abc_Obj_t * pFanin, * pFanout;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 0;
    Abc_NodeSetTravIdCurrent(pObj);
    // skip the fanin which already has flow
    if ( fFanin && Abc_ObjGetPath(pPrev) )
        return 0;
    // if the node has no flow, try to push through the fanouts
    if ( !Abc_ObjGetPath(pObj) )
    {
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
        // try to push flow through the fanouts
        Abc_ObjForEachFanout( pObj, pFanout, i )
            if ( Abc_NtkMaxFlowFwdPath3_rec(pFanout, pObj, 1) )
                return fFanin? Abc_ObjSetPath(pPrev, pObj) : 1;
    }
    // try to push through the fanins
    Abc_ObjForEachFanin( pObj, pFanin, i )
        if ( !Abc_ObjIsLatch(pFanin) && Abc_NtkMaxFlowFwdPath3_rec(pFanin, pObj, 0) )
            return Abc_ObjSetPath( pFanin, NULL );
    return 0;
}

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

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

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

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pFanout, * pFanin;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 0;
    Abc_NodeSetTravIdCurrent(pObj);
    // process node without flow
    if ( !Abc_ObjGetPath(pObj) )
    {
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
        // explore the fanins
        Abc_ObjForEachFanin( pObj, pFanin, i )
            if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
                return Abc_ObjSetPath( pObj, pFanin );
        return 0;
    }
    // pObj has flow - find the fanout with flow
    pFanout = Abc_ObjGetFanoutPath( 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 );
    // try the fanout
    if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) )
        return Abc_ObjSetPath( pFanout, NULL );
    return 0;
}

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

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

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

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pFanout, * pFanin;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 0;
    Abc_NodeSetTravIdCurrent(pObj);
    // process node without flow
    if ( !Abc_ObjGetPath(pObj) )
    { 
        // start the path if we reached a terminal node
        if ( pObj->fMarkA )
            return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
        // explore the fanins
        Abc_ObjForEachFanout( pObj, pFanout, i )
            if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) )
                return Abc_ObjSetPath( pObj, pFanout );
        return 0;
    }
    // pObj has flow - find the fanout with flow
    pFanin = Abc_ObjGetFaninPath( pObj );
    if ( pFanin == NULL )
        return 0;
    // go through the fanins of the fanout with flow
    Abc_ObjForEachFanout( pFanin, pFanout, i )
        if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) )
            return Abc_ObjSetPath( pFanin, pFanout );
    // try the fanout
    if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) )
        return Abc_ObjSetPath( pFanin, NULL );
    return 0;
}

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

  Synopsis    [Find minimum-volume minumum cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward )
{
    Vec_Ptr_t * vMinCut;
    Abc_Obj_t * pObj;
    int i;
    // collect the cut nodes
    vMinCut = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
    Abc_NtkForEachObj( pNtk, pObj, i )
    {
        // node without flow is not a cut node
        if ( !Abc_ObjGetPath(pObj) )
            continue;
        // unvisited node is below the cut
        if ( !Abc_NodeIsTravIdCurrent(pObj) )
            continue;
        // add terminal with flow or node whose path is not visited
        if ( pObj->fMarkA || !Abc_NodeIsTravIdCurrent( Abc_ObjGetPath(pObj) ) )
            Vec_PtrPush( vMinCut, pObj );
    }
    return vMinCut;
}

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

  Synopsis    [Marks the TFI cone with MarkA.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowMarkCut_rec( Abc_Obj_t * pObj )
{
    Abc_Obj_t * pNext;
    int i;
    if ( pObj->fMarkA )
        return;
    pObj->fMarkA = 1;
    Abc_ObjForEachFanin( pObj, pNext, i )
        Abc_NtkMaxFlowMarkCut_rec( pNext );
}

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

  Synopsis    [Visits the TFI up to marked nodes and collects marked nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowCollectCut_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
    Abc_Obj_t * pNext;
    int i;
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return;
    Abc_NodeSetTravIdCurrent(pObj);
    if ( pObj->fMarkA )
    {
        Vec_PtrPush( vNodes, pObj );
        return;
    }
    Abc_ObjForEachFanin( pObj, pNext, i )
        Abc_NtkMaxFlowCollectCut_rec( pNext, vNodes );
}

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

  Synopsis    [Updates the minimum cut to be retimable.]

  Description [This procedure also labels the nodes reachable from
  the latches to the cut with fMarkA.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
{
    Abc_Obj_t * pObj, * pNext;
    int i, k;
    // clean marks
    Abc_NtkForEachObj( pNtk, pObj, i )
        pObj->fMarkA = 0;
    // set latch outputs
    Abc_NtkForEachLatch( pNtk, pObj, i )
        Abc_ObjFanout0(pObj)->fMarkA = 1;
    // traverse from cut nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
        Abc_NtkMaxFlowMarkCut_rec( pObj );
    if ( fForward )
    {
        // change mincut to be nodes with unmarked fanouts
        Vec_PtrClear( vMinCut );
        Abc_NtkForEachObj( pNtk, pObj, i )
        {
            if ( !pObj->fMarkA )
                continue;
            Abc_ObjForEachFanout( pObj, pNext, k )
            {
                if ( pNext->fMarkA )
                    continue;
                Vec_PtrPush( vMinCut, pObj );
                break;
            }
        }
    }
    else
    {
        // change mincut to be marked fanins of the unmarked nodes
        Vec_PtrClear( vMinCut );
        Abc_NtkIncrementTravId(pNtk);
        Abc_NtkForEachLatch( pNtk, pObj, i )
            Abc_NtkMaxFlowCollectCut_rec( Abc_ObjFanin0(pObj), vMinCut );
        // transfer the attribute
        Abc_NtkForEachObj( pNtk, pObj, i )
            pObj->fMarkA = Abc_NodeIsTravIdCurrent(pObj);
        // unmark the cut nodes
        Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
            pObj->fMarkA = 0;
    }
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowVerifyCut_rec( Abc_Obj_t * pObj, int fForward )
{
    Abc_Obj_t * pNext;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pObj) )
        return 1;
    Abc_NodeSetTravIdCurrent(pObj);
    // visit the node
    if ( fForward )
    {
        if ( Abc_ObjIsCo(pObj) )
            return 0;
        // explore the fanouts
        Abc_ObjForEachFanout( pObj, pNext, i )
            if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
                return 0;
    }
    else
    {
        if ( Abc_ObjIsCi(pObj) )
            return 0;
        // explore the fanins
        Abc_ObjForEachFanin( pObj, pNext, i )
            if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
                return 0;
    }
    return 1;
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
{
    Abc_Obj_t * pObj;
    int i;
    // mark the cut with the current traversal ID
    Abc_NtkIncrementTravId(pNtk);
    Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
        Abc_NodeSetTravIdCurrent( pObj );
    // search from the latches for a path to the COs/CIs
    Abc_NtkForEachLatch( pNtk, pObj, i )
    {
        if ( fForward )
        {
            if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) )
                return 0;
        }
        else
        {
            if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) )
                return 0;
        }
    }
/*
    {
        // count the volume of the cut
        int Counter = 0;
        Abc_NtkForEachObj( pNtk, pObj, i )
            Counter += Abc_NodeIsTravIdCurrent( pObj );
        printf( "Volume = %d.\n", Counter );
    }
*/
    return 1;
}

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

  Synopsis    [Prints the flows.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward )
{
    Abc_Obj_t * pLatch, * pNext;
    Abc_Obj_t * pPrev = NULL; // Suppress "might be used uninitialized"
    int i;
    if ( fForward )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, pNtk->vBoxes, pLatch, i )
        {
            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
            if ( Abc_ObjGetPath(Abc_ObjFanout0(pLatch)) == NULL ) // no flow through this latch
                continue;
            printf( "Path = " );
            for ( pNext = Abc_ObjFanout0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
            {
                printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
                pPrev = pNext;
            }
            if ( !Abc_ObjIsPo(pPrev) )
            printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanout0(pPrev)), Abc_ObjFanout0(pPrev)->Id );
            printf( "\n" );
        }
    }
    else
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, pNtk->vBoxes, pLatch, i )
        {
            assert( !Abc_ObjFanin0(pLatch)->fMarkA );
            if ( Abc_ObjGetPath(Abc_ObjFanin0(pLatch)) == NULL ) // no flow through this latch
                continue;
            printf( "Path = " );
            for ( pNext = Abc_ObjFanin0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
            {
                printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
                pPrev = pNext;
            }
            if ( !Abc_ObjIsPi(pPrev) )
            printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanin0(pPrev)), Abc_ObjFanin0(pPrev)->Id );
            printf( "\n" );
        }
    }
}

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

  Synopsis    [Prints the min-cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
{
    Abc_Obj_t * pObj;
    int i;
    printf( "Min-cut: " );
    Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
        printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
    printf( "\n" );
    printf( "Marked nodes: " );
    Abc_NtkForEachObj( pNtk, pObj, i )
        if ( pObj->fMarkA )
            printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
    printf( "\n" );
}


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


ABC_NAMESPACE_IMPL_END