| /**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 |
| |
