retFlow.c File Reference

#include "retInt.h"

Include dependency graph for retFlow.c:

Go to the source code of this file.

Functions
void	Abc_NtkMaxFlowTest (Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///.
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

Abc_NtkMaxFlow()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkMaxFlowCollectCut_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkMaxFlowMarkCut_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkMaxFlowTest()

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

Here is the call graph for this function:

Abc_NtkMaxFlowVerifyCut_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function: