src/opt/ret/retFlow.c File Reference
#include "retInt.h"
Include dependency graph for retFlow.c:
Go to the source code of this file.
Function Documentation
Function*************************************************************
Synopsis [Implementation of max-flow/min-cut computation.]
Description []
SideEffects []
SeeAlso []
Definition at line 140 of file retFlow.c.
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 }
| 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 394 of file retFlow.c.
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 }
| 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 249 of file retFlow.c.
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 }
Function*************************************************************
Synopsis [Visits the TFI up to marked nodes and collects marked nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 539 of file retFlow.c.
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 }
| 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 439 of file retFlow.c.
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 }
Function*************************************************************
Synopsis [Tries to find an augmenting path originating in this edge.]
Description []
SideEffects []
SeeAlso []
Definition at line 354 of file retFlow.c.
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 }
| 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 301 of file retFlow.c.
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 }
| void Abc_NtkMaxFlowMarkCut_rec | ( | Abc_Obj_t * | pObj | ) |
Function*************************************************************
Synopsis [Marks the TFI cone with MarkA.]
Description []
SideEffects []
SeeAlso []
Definition at line 517 of file retFlow.c.
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 }
Function*************************************************************
Synopsis [Find minimum-volume minumum cut.]
Description []
SideEffects []
SeeAlso []
Definition at line 484 of file retFlow.c.
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 }
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 567 of file retFlow.c.
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 }
Function*************************************************************
Synopsis [Prints the min-cut.]
Description []
SideEffects []
SeeAlso []
Definition at line 763 of file retFlow.c.
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 }
| void Abc_NtkMaxFlowPrintFlow | ( | Abc_Ntk_t * | pNtk, | |
| int | fForward | |||
| ) | [static] |
Function*************************************************************
Synopsis [Prints the flows.]
Description []
SideEffects []
SeeAlso []
Definition at line 710 of file retFlow.c.
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 }
| void Abc_NtkMaxFlowTest | ( | Abc_Ntk_t * | pNtk | ) |
FUNCTION DEFINITIONS ///Function*************************************************************
Synopsis [Test-bench for the max-flow computation.]
Description []
SideEffects []
SeeAlso []
Definition at line 101 of file retFlow.c.
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 }
Function*************************************************************
Synopsis [Verifies the min-cut is indeed a cut.]
Description []
SideEffects []
SeeAlso []
Definition at line 665 of file retFlow.c.
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 }
| 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 624 of file retFlow.c.
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 }
Definition at line 39 of file retFlow.c.
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 }
Definition at line 29 of file retFlow.c.
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 }
Definition at line 49 of file retFlow.c.
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 }
Definition at line 61 of file retFlow.c.
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 }
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
] DECLARATIONS ///
Definition at line 27 of file retFlow.c.
00027 { pObj->pCopy = pNext; return 1; }
