retFlow.c File Reference

#include "retInt.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START int	Abc_ObjSetPath (Abc_Obj_t *pObj, Abc_Obj_t *pNext)
	DECLARATIONS ///. More...
static Abc_Obj_t *	Abc_ObjGetPath (Abc_Obj_t *pObj)
static Abc_Obj_t *	Abc_ObjGetFanoutPath (Abc_Obj_t *pObj)
static Abc_Obj_t *	Abc_ObjGetFaninPath (Abc_Obj_t *pObj)
static Abc_Obj_t *	Abc_ObjGetPredecessorBwd (Abc_Obj_t *pObj)
static Abc_Obj_t *	Abc_ObjGetPredecessorFwd (Abc_Obj_t *pObj)
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_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)
void	Abc_NtkMaxFlowTest (Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///. More...
Vec_Ptr_t *	Abc_NtkMaxFlow (Abc_Ntk_t *pNtk, int fForward, int fVerbose)
void	Abc_NtkMaxFlowMarkCut_rec (Abc_Obj_t *pObj)
void	Abc_NtkMaxFlowCollectCut_rec (Abc_Obj_t *pObj, Vec_Ptr_t *vNodes)
int	Abc_NtkMaxFlowVerifyCut_rec (Abc_Obj_t *pObj, int fForward)

Function Documentation

Vec_Ptr_t* Abc_NtkMaxFlow	(	Abc_Ntk_t *	pNtk,
		int	fForward,
		int	fVerbose
	)

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 143 of file retFlow.c.

{
    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;
}

int Abc_NtkMaxFlowBwdPath2_rec ( Abc_Obj_t *  pObj )

static

Function*************************************************************

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

Description [This procedure works for directed graphs only!]

SideEffects []

SeeAlso []

Definition at line 397 of file retFlow.c.

{
    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;
}

int Abc_NtkMaxFlowBwdPath_rec ( Abc_Obj_t *  pObj )

static

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 252 of file retFlow.c.

{
    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;
}

void Abc_NtkMaxFlowCollectCut_rec	(	Abc_Obj_t *	pObj,
		Vec_Ptr_t *	vNodes
	)

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 542 of file retFlow.c.

{
    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 );
}

int Abc_NtkMaxFlowFwdPath2_rec ( Abc_Obj_t *  pObj )

static

Function*************************************************************

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

Description [This procedure works for directed graphs only!]

SideEffects []

SeeAlso []

Definition at line 442 of file retFlow.c.

{
    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;
}

int Abc_NtkMaxFlowFwdPath3_rec ( Abc_Obj_t *  pObj, Abc_Obj_t *  pPrev, int  fFanin  )

static

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 357 of file retFlow.c.

{
    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;
}

int Abc_NtkMaxFlowFwdPath_rec ( Abc_Obj_t *  pObj )

static

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file retFlow.c.

{
    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;
}

void Abc_NtkMaxFlowMarkCut_rec

(

Abc_Obj_t *

pObj

)

Function*************************************************************

Synopsis [Marks the TFI cone with MarkA.]

Description []

SideEffects []

SeeAlso []

Definition at line 520 of file retFlow.c.

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

Vec_Ptr_t * Abc_NtkMaxFlowMinCut ( Abc_Ntk_t *  pNtk, int  fForward  )

static

Function*************************************************************

Synopsis [Find minimum-volume minumum cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 487 of file retFlow.c.

{
    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;
}

void Abc_NtkMaxFlowMinCutUpdate ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vMinCut, int  fForward  )

static

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 []

Definition at line 570 of file retFlow.c.

{
    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;
    }
}

void Abc_NtkMaxFlowPrintCut ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vMinCut  )

static

Function*************************************************************

Synopsis [Prints the min-cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 767 of file retFlow.c.

{
    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" );
}

void Abc_NtkMaxFlowPrintFlow ( Abc_Ntk_t *  pNtk, int  fForward  )

static

Function*************************************************************

Synopsis [Prints the flows.]

Description []

SideEffects []

SeeAlso []

Definition at line 713 of file retFlow.c.

{
    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" );
        }
    }
}

void Abc_NtkMaxFlowTest

(

Abc_Ntk_t *

pNtk

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 104 of file retFlow.c.

{
    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 );

}

int Abc_NtkMaxFlowVerifyCut ( Abc_Ntk_t *  pNtk, Vec_Ptr_t *  vMinCut, int  fForward  )

static

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 668 of file retFlow.c.

{
    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;
}

int Abc_NtkMaxFlowVerifyCut_rec	(	Abc_Obj_t *	pObj,
		int	fForward
	)

Function*************************************************************

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

Description []

SideEffects []

SeeAlso []

Definition at line 627 of file retFlow.c.

{
    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;
}

static Abc_Obj_t* Abc_ObjGetFaninPath ( Abc_Obj_t *  pObj )

inlinestatic

Definition at line 42 of file retFlow.c.

{ 
    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 Abc_Obj_t* Abc_ObjGetFanoutPath ( Abc_Obj_t *  pObj )

inlinestatic

Definition at line 32 of file retFlow.c.

{ 
    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 Abc_Obj_t* Abc_ObjGetPath ( Abc_Obj_t *  pObj )

inlinestatic

Definition at line 31 of file retFlow.c.

{ return pObj->pCopy;              }

static Abc_Obj_t* Abc_ObjGetPredecessorBwd ( Abc_Obj_t *  pObj )

inlinestatic

Definition at line 52 of file retFlow.c.

{ 
    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 Abc_Obj_t* Abc_ObjGetPredecessorFwd ( Abc_Obj_t *  pObj )

inlinestatic

Definition at line 64 of file retFlow.c.

{ 
    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 ABC_NAMESPACE_IMPL_START int Abc_ObjSetPath ( Abc_Obj_t *  pObj, Abc_Obj_t *  pNext  )

inlinestatic

DECLARATIONS ///.

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

]

Definition at line 30 of file retFlow.c.

{ pObj->pCopy = pNext; return 1;   }