abc70930: src/opt/ret/retFlow.c Source File

00001 
00021 #include "retInt.h"
00022 
00026 
00027 static inline int         Abc_ObjSetPath( Abc_Obj_t * pObj, Abc_Obj_t * pNext ) { pObj->pCopy = pNext; return 1;   }
00028 static inline Abc_Obj_t * Abc_ObjGetPath( Abc_Obj_t * pObj )                    { return pObj->pCopy;              }
00029 static inline Abc_Obj_t * Abc_ObjGetFanoutPath( Abc_Obj_t * pObj ) 
00030 { 
00031     Abc_Obj_t * pFanout;
00032     int i;
00033     assert( Abc_ObjGetPath(pObj) ); 
00034     Abc_ObjForEachFanout( pObj, pFanout, i )
00035         if ( Abc_ObjGetPath(pFanout) == pObj )
00036             return pFanout;
00037     return NULL;
00038 }
00039 static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * pObj ) 
00040 { 
00041     Abc_Obj_t * pFanin;
00042     int i;
00043     assert( Abc_ObjGetPath(pObj) ); 
00044     Abc_ObjForEachFanin( pObj, pFanin, i )
00045         if ( Abc_ObjGetPath(pFanin) == pObj )
00046             return pFanin;
00047     return NULL;
00048 }
00049 static inline Abc_Obj_t * Abc_ObjGetPredecessorBwd( Abc_Obj_t * pObj ) 
00050 { 
00051     Abc_Obj_t * pNext;
00052     int i;
00053     Abc_ObjForEachFanout( pObj, pNext, i )
00054         if ( Abc_ObjGetPath(pNext) == pObj )
00055             return pNext;
00056     Abc_ObjForEachFanin( pObj, pNext, i )
00057         if ( Abc_ObjGetPath(pNext) == pObj )
00058             return pNext;
00059     return NULL;
00060 }
00061 static inline Abc_Obj_t * Abc_ObjGetPredecessorFwd( Abc_Obj_t * pObj ) 
00062 { 
00063     Abc_Obj_t * pNext;
00064     int i;
00065     Abc_ObjForEachFanin( pObj, pNext, i )
00066         if ( Abc_ObjGetPath(pNext) == pObj )
00067             return pNext;
00068     Abc_ObjForEachFanout( pObj, pNext, i )
00069         if ( Abc_ObjGetPath(pNext) == pObj )
00070             return pNext;
00071     return NULL;
00072 }
00073 
00074 static int         Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
00075 static int         Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
00076 static int         Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
00077 static int         Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
00078 //static int         Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj );
00079 static int         Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin );
00080 static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward );
00081 static void        Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
00082 static int         Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
00083 static void        Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
00084 static void        Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward );
00085 
00089 
00101 void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
00102 {
00103     Vec_Ptr_t * vMinCut;
00104     Abc_Obj_t * pObj;
00105     int i;
00106 
00107     // forward flow
00108     Abc_NtkForEachPo( pNtk, pObj, i )
00109         pObj->fMarkA = 1;
00110     Abc_NtkForEachLatch( pNtk, pObj, i )
00111         pObj->fMarkA = Abc_ObjFanin0(pObj)->fMarkA = 1;
00112 //        Abc_ObjFanin0(pObj)->fMarkA = 1;
00113     vMinCut = Abc_NtkMaxFlow( pNtk, 1, 1 );
00114     Vec_PtrFree( vMinCut );
00115     Abc_NtkCleanMarkA( pNtk );
00116 
00117     // backward flow
00118     Abc_NtkForEachPi( pNtk, pObj, i )
00119         pObj->fMarkA = 1;
00120     Abc_NtkForEachLatch( pNtk, pObj, i )
00121         pObj->fMarkA = Abc_ObjFanout0(pObj)->fMarkA = 1;
00122 //        Abc_ObjFanout0(pObj)->fMarkA = 1;
00123     vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 );
00124     Vec_PtrFree( vMinCut );
00125     Abc_NtkCleanMarkA( pNtk );
00126 
00127 }
00128 
00140 Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
00141 {
00142     Vec_Ptr_t * vMinCut;
00143     Abc_Obj_t * pLatch;
00144     int Flow, FlowCur, RetValue, i;
00145     int clk = clock();
00146     int fUseDirectedFlow = 1;
00147 
00148     // find the max-flow
00149     Abc_NtkCleanCopy( pNtk );
00150     Flow = 0;
00151     Abc_NtkIncrementTravId(pNtk);
00152     Abc_NtkForEachLatch( pNtk, pLatch, i )
00153     {
00154         if ( fForward )
00155         {
00156 //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
00157             FlowCur  = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
00158 //            FlowCur  = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
00159             Flow    += FlowCur;
00160         }
00161         else
00162         {
00163             assert( !Abc_ObjFanin0(pLatch)->fMarkA );
00164             FlowCur  = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
00165             Flow    += FlowCur;
00166         }
00167         if ( FlowCur )
00168             Abc_NtkIncrementTravId(pNtk);
00169     }
00170 
00171     if ( !fUseDirectedFlow )
00172     {
00173         Abc_NtkIncrementTravId(pNtk);
00174         Abc_NtkForEachLatch( pNtk, pLatch, i )
00175         {
00176             if ( fForward )
00177             {
00178     //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
00179                 FlowCur  = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
00180                 Flow    += FlowCur;
00181             }
00182             else
00183             {
00184                 assert( !Abc_ObjFanin0(pLatch)->fMarkA );
00185                 FlowCur  = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
00186                 Flow    += FlowCur;
00187             }
00188             if ( FlowCur )
00189                 Abc_NtkIncrementTravId(pNtk);
00190         }
00191     }
00192 //    Abc_NtkMaxFlowPrintFlow( pNtk, fForward );
00193 
00194     // mark the nodes reachable from the latches
00195     Abc_NtkIncrementTravId(pNtk);
00196     Abc_NtkForEachLatch( pNtk, pLatch, i )
00197     {
00198         if ( fForward )
00199         {
00200 //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
00201             if ( fUseDirectedFlow )
00202                 RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
00203 //                RetValue = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
00204             else
00205                 RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
00206         }
00207         else
00208         {
00209             assert( !Abc_ObjFanin0(pLatch)->fMarkA );
00210             if ( fUseDirectedFlow )
00211                 RetValue = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
00212             else
00213                 RetValue = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
00214         }
00215         assert( RetValue == 0 );
00216     }
00217 
00218     // find the min-cut with the smallest volume
00219     vMinCut = Abc_NtkMaxFlowMinCut( pNtk, fForward );
00220     // verify the cut
00221     if ( !Abc_NtkMaxFlowVerifyCut(pNtk, vMinCut, fForward) )
00222         printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" );
00223     // make the cut retimable
00224     Abc_NtkMaxFlowMinCutUpdate( pNtk, vMinCut, fForward );
00225 
00226     // report the results
00227     if ( fVerbose )
00228     {
00229     printf( "L = %6d. %s max-flow = %6d.  Min-cut = %6d.  ", 
00230         Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) );
00231 PRT( "Time", clock() - clk );
00232     }
00233 
00234 //    Abc_NtkMaxFlowPrintCut( pNtk, vMinCut );
00235     return vMinCut;
00236 }
00237 
00249 int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
00250 {
00251     Abc_Obj_t * pNext, * pPred;
00252     int i;
00253     // skip visited nodes
00254     if ( Abc_NodeIsTravIdCurrent(pObj) )
00255         return 0;
00256     Abc_NodeSetTravIdCurrent(pObj);
00257     // get the predecessor
00258     pPred = Abc_ObjGetPredecessorBwd( pObj );
00259     // process node without flow
00260     if ( !Abc_ObjGetPath(pObj) )
00261     {
00262         // start the path if we reached a terminal node
00263         if ( pObj->fMarkA )
00264             return Abc_ObjSetPath( pObj, (void *)1 );
00265         // explore the fanins
00266         Abc_ObjForEachFanin( pObj, pNext, i )
00267             if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
00268                 return Abc_ObjSetPath( pObj, pNext );
00269         Abc_ObjForEachFanout( pObj, pNext, i )
00270             if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
00271                 return Abc_ObjSetPath( pObj, pNext );
00272         return 0;
00273     }
00274     // pObj has flow - find the fanout with flow
00275     if ( pPred == NULL )
00276         return 0;
00277     // go through the successors of the predecessor
00278     Abc_ObjForEachFanin( pPred, pNext, i )
00279         if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
00280             return Abc_ObjSetPath( pPred, pNext );
00281     Abc_ObjForEachFanout( pPred, pNext, i )
00282         if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
00283             return Abc_ObjSetPath( pPred, pNext );
00284     // try the fanout
00285     if ( Abc_NtkMaxFlowBwdPath_rec( pPred ) )
00286         return Abc_ObjSetPath( pPred, NULL );
00287     return 0;
00288 }
00289 
00301 int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
00302 {
00303     Abc_Obj_t * pNext, * pPred;
00304     int i;
00305     // skip visited nodes
00306     if ( Abc_NodeIsTravIdCurrent(pObj) )
00307         return 0;
00308     Abc_NodeSetTravIdCurrent(pObj);
00309     // get the predecessor
00310     pPred = Abc_ObjGetPredecessorFwd( pObj );
00311     // process node without flow
00312     if ( !Abc_ObjGetPath(pObj) )
00313     {
00314         // start the path if we reached a terminal node
00315         if ( pObj->fMarkA )
00316             return Abc_ObjSetPath( pObj, (void *)1 );
00317         // explore the fanins
00318         Abc_ObjForEachFanout( pObj, pNext, i )
00319             if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
00320                 return Abc_ObjSetPath( pObj, pNext );
00321         Abc_ObjForEachFanin( pObj, pNext, i )
00322             if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
00323                 return Abc_ObjSetPath( pObj, pNext );
00324         return 0;
00325     }
00326     // pObj has flow - find the fanout with flow
00327     if ( pPred == NULL )
00328         return 0;
00329     // go through the successors of the predecessor
00330     Abc_ObjForEachFanout( pPred, pNext, i )
00331         if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
00332             return Abc_ObjSetPath( pPred, pNext );
00333     Abc_ObjForEachFanin( pPred, pNext, i )
00334         if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
00335             return Abc_ObjSetPath( pPred, pNext );
00336     // try the fanout
00337     if ( Abc_NtkMaxFlowFwdPath_rec( pPred ) )
00338         return Abc_ObjSetPath( pPred, NULL );
00339     return 0;
00340 }
00341 
00342 
00354 int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin )
00355 {
00356     Abc_Obj_t * pFanin, * pFanout;
00357     int i;
00358     // skip visited nodes
00359     if ( Abc_NodeIsTravIdCurrent(pObj) )
00360         return 0;
00361     Abc_NodeSetTravIdCurrent(pObj);
00362     // skip the fanin which already has flow
00363     if ( fFanin && Abc_ObjGetPath(pPrev) )
00364         return 0;
00365     // if the node has no flow, try to push through the fanouts
00366     if ( !Abc_ObjGetPath(pObj) )
00367     {
00368         // start the path if we reached a terminal node
00369         if ( pObj->fMarkA )
00370             return Abc_ObjSetPath( pObj, (void *)1 );
00371         // try to push flow through the fanouts
00372         Abc_ObjForEachFanout( pObj, pFanout, i )
00373             if ( Abc_NtkMaxFlowFwdPath3_rec(pFanout, pObj, 1) )
00374                 return fFanin? Abc_ObjSetPath(pPrev, pObj) : 1;
00375     }
00376     // try to push through the fanins
00377     Abc_ObjForEachFanin( pObj, pFanin, i )
00378         if ( !Abc_ObjIsLatch(pFanin) && Abc_NtkMaxFlowFwdPath3_rec(pFanin, pObj, 0) )
00379             return Abc_ObjSetPath( pFanin, NULL );
00380     return 0;
00381 }
00382 
00394 int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj )
00395 {
00396     Abc_Obj_t * pFanout, * pFanin;
00397     int i;
00398     // skip visited nodes
00399     if ( Abc_NodeIsTravIdCurrent(pObj) )
00400         return 0;
00401     Abc_NodeSetTravIdCurrent(pObj);
00402     // process node without flow
00403     if ( !Abc_ObjGetPath(pObj) )
00404     {
00405         // start the path if we reached a terminal node
00406         if ( pObj->fMarkA )
00407             return Abc_ObjSetPath( pObj, (void *)1 );
00408         // explore the fanins
00409         Abc_ObjForEachFanin( pObj, pFanin, i )
00410             if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
00411                 return Abc_ObjSetPath( pObj, pFanin );
00412         return 0;
00413     }
00414     // pObj has flow - find the fanout with flow
00415     pFanout = Abc_ObjGetFanoutPath( pObj );
00416     if ( pFanout == NULL )
00417         return 0;
00418     // go through the fanins of the fanout with flow
00419     Abc_ObjForEachFanin( pFanout, pFanin, i )
00420         if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) )
00421             return Abc_ObjSetPath( pFanout, pFanin );
00422     // try the fanout
00423     if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) )
00424         return Abc_ObjSetPath( pFanout, NULL );
00425     return 0;
00426 }
00427 
00439 int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj )
00440 {
00441     Abc_Obj_t * pFanout, * pFanin;
00442     int i;
00443     // skip visited nodes
00444     if ( Abc_NodeIsTravIdCurrent(pObj) )
00445         return 0;
00446     Abc_NodeSetTravIdCurrent(pObj);
00447     // process node without flow
00448     if ( !Abc_ObjGetPath(pObj) )
00449     { 
00450         // start the path if we reached a terminal node
00451         if ( pObj->fMarkA )
00452             return Abc_ObjSetPath( pObj, (void *)1 );
00453         // explore the fanins
00454         Abc_ObjForEachFanout( pObj, pFanout, i )
00455             if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) )
00456                 return Abc_ObjSetPath( pObj, pFanout );
00457         return 0;
00458     }
00459     // pObj has flow - find the fanout with flow
00460     pFanin = Abc_ObjGetFaninPath( pObj );
00461     if ( pFanin == NULL )
00462         return 0;
00463     // go through the fanins of the fanout with flow
00464     Abc_ObjForEachFanout( pFanin, pFanout, i )
00465         if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) )
00466             return Abc_ObjSetPath( pFanin, pFanout );
00467     // try the fanout
00468     if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) )
00469         return Abc_ObjSetPath( pFanin, NULL );
00470     return 0;
00471 }
00472 
00484 Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward )
00485 {
00486     Vec_Ptr_t * vMinCut;
00487     Abc_Obj_t * pObj;
00488     int i;
00489     // collect the cut nodes
00490     vMinCut = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
00491     Abc_NtkForEachObj( pNtk, pObj, i )
00492     {
00493         // node without flow is not a cut node
00494         if ( !Abc_ObjGetPath(pObj) )
00495             continue;
00496         // unvisited node is below the cut
00497         if ( !Abc_NodeIsTravIdCurrent(pObj) )
00498             continue;
00499         // add terminal with flow or node whose path is not visited
00500         if ( pObj->fMarkA || !Abc_NodeIsTravIdCurrent( Abc_ObjGetPath(pObj) ) )
00501             Vec_PtrPush( vMinCut, pObj );
00502     }
00503     return vMinCut;
00504 }
00505 
00517 void Abc_NtkMaxFlowMarkCut_rec( Abc_Obj_t * pObj )
00518 {
00519     Abc_Obj_t * pNext;
00520     int i;
00521     if ( pObj->fMarkA )
00522         return;
00523     pObj->fMarkA = 1;
00524     Abc_ObjForEachFanin( pObj, pNext, i )
00525         Abc_NtkMaxFlowMarkCut_rec( pNext );
00526 }
00527 
00539 void Abc_NtkMaxFlowCollectCut_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes )
00540 {
00541     Abc_Obj_t * pNext;
00542     int i;
00543     if ( Abc_NodeIsTravIdCurrent(pObj) )
00544         return;
00545     Abc_NodeSetTravIdCurrent(pObj);
00546     if ( pObj->fMarkA )
00547     {
00548         Vec_PtrPush( vNodes, pObj );
00549         return;
00550     }
00551     Abc_ObjForEachFanin( pObj, pNext, i )
00552         Abc_NtkMaxFlowCollectCut_rec( pNext, vNodes );
00553 }
00554 
00567 void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
00568 {
00569     Abc_Obj_t * pObj, * pNext;
00570     int i, k;
00571     // clean marks
00572     Abc_NtkForEachObj( pNtk, pObj, i )
00573         pObj->fMarkA = 0;
00574     // set latch outputs
00575     Abc_NtkForEachLatch( pNtk, pObj, i )
00576         Abc_ObjFanout0(pObj)->fMarkA = 1;
00577     // traverse from cut nodes
00578     Vec_PtrForEachEntry( vMinCut, pObj, i )
00579         Abc_NtkMaxFlowMarkCut_rec( pObj );
00580     if ( fForward )
00581     {
00582         // change mincut to be nodes with unmarked fanouts
00583         Vec_PtrClear( vMinCut );
00584         Abc_NtkForEachObj( pNtk, pObj, i )
00585         {
00586             if ( !pObj->fMarkA )
00587                 continue;
00588             Abc_ObjForEachFanout( pObj, pNext, k )
00589             {
00590                 if ( pNext->fMarkA )
00591                     continue;
00592                 Vec_PtrPush( vMinCut, pObj );
00593                 break;
00594             }
00595         }
00596     }
00597     else
00598     {
00599         // change mincut to be marked fanins of the unmarked nodes
00600         Vec_PtrClear( vMinCut );
00601         Abc_NtkIncrementTravId(pNtk);
00602         Abc_NtkForEachLatch( pNtk, pObj, i )
00603             Abc_NtkMaxFlowCollectCut_rec( Abc_ObjFanin0(pObj), vMinCut );
00604         // transfer the attribute
00605         Abc_NtkForEachObj( pNtk, pObj, i )
00606             pObj->fMarkA = Abc_NodeIsTravIdCurrent(pObj);
00607         // unmark the cut nodes
00608         Vec_PtrForEachEntry( vMinCut, pObj, i )
00609             pObj->fMarkA = 0;
00610     }
00611 }
00612 
00624 int Abc_NtkMaxFlowVerifyCut_rec( Abc_Obj_t * pObj, int fForward )
00625 {
00626     Abc_Obj_t * pNext;
00627     int i;
00628     // skip visited nodes
00629     if ( Abc_NodeIsTravIdCurrent(pObj) )
00630         return 1;
00631     Abc_NodeSetTravIdCurrent(pObj);
00632     // visit the node
00633     if ( fForward )
00634     {
00635         if ( Abc_ObjIsCo(pObj) )
00636             return 0;
00637         // explore the fanouts
00638         Abc_ObjForEachFanout( pObj, pNext, i )
00639             if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
00640                 return 0;
00641     }
00642     else
00643     {
00644         if ( Abc_ObjIsCi(pObj) )
00645             return 0;
00646         // explore the fanins
00647         Abc_ObjForEachFanin( pObj, pNext, i )
00648             if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
00649                 return 0;
00650     }
00651     return 1;
00652 }
00653 
00665 int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
00666 {
00667     Abc_Obj_t * pObj;
00668     int i;
00669     // mark the cut with the current traversal ID
00670     Abc_NtkIncrementTravId(pNtk);
00671     Vec_PtrForEachEntry( vMinCut, pObj, i )
00672         Abc_NodeSetTravIdCurrent( pObj );
00673     // search from the latches for a path to the COs/CIs
00674     Abc_NtkForEachLatch( pNtk, pObj, i )
00675     {
00676         if ( fForward )
00677         {
00678             if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) )
00679                 return 0;
00680         }
00681         else
00682         {
00683             if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) )
00684                 return 0;
00685         }
00686     }
00687 /*
00688     {
00689         // count the volume of the cut
00690         int Counter = 0;
00691         Abc_NtkForEachObj( pNtk, pObj, i )
00692             Counter += Abc_NodeIsTravIdCurrent( pObj );
00693         printf( "Volume = %d.\n", Counter );
00694     }
00695 */
00696     return 1;
00697 }
00698 
00710 void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward )
00711 {
00712     Abc_Obj_t * pLatch, * pNext, * pPrev;
00713     int i;
00714     if ( fForward )
00715     {
00716         Vec_PtrForEachEntry( pNtk->vBoxes, pLatch, i )
00717         {
00718             assert( !Abc_ObjFanout0(pLatch)->fMarkA );
00719             if ( Abc_ObjGetPath(Abc_ObjFanout0(pLatch)) == NULL ) // no flow through this latch
00720                 continue;
00721             printf( "Path = " );
00722             for ( pNext = Abc_ObjFanout0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
00723             {
00724                 printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
00725                 pPrev = pNext;
00726             }
00727             if ( !Abc_ObjIsPo(pPrev) )
00728             printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanout0(pPrev)), Abc_ObjFanout0(pPrev)->Id );
00729             printf( "\n" );
00730         }
00731     }
00732     else
00733     {
00734         Vec_PtrForEachEntry( pNtk->vBoxes, pLatch, i )
00735         {
00736             assert( !Abc_ObjFanin0(pLatch)->fMarkA );
00737             if ( Abc_ObjGetPath(Abc_ObjFanin0(pLatch)) == NULL ) // no flow through this latch
00738                 continue;
00739             printf( "Path = " );
00740             for ( pNext = Abc_ObjFanin0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
00741             {
00742                 printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
00743                 pPrev = pNext;
00744             }
00745             if ( !Abc_ObjIsPi(pPrev) )
00746             printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanin0(pPrev)), Abc_ObjFanin0(pPrev)->Id );
00747             printf( "\n" );
00748         }
00749     }
00750 }
00751 
00763 void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
00764 {
00765     Abc_Obj_t * pObj;
00766     int i;
00767     printf( "Min-cut: " );
00768     Vec_PtrForEachEntry( vMinCut, pObj, i )
00769         printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
00770     printf( "\n" );
00771     printf( "Marked nodes: " );
00772     Abc_NtkForEachObj( pNtk, pObj, i )
00773         if ( pObj->fMarkA )
00774             printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
00775     printf( "\n" );
00776 }
00777 
00778 
00782 
00783