| /**CFile**************************************************************** |
| |
| FileName [llb2Flow.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [BDD based reachability.] |
| |
| Synopsis [Flow computation.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: llb2Flow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "llbInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| static inline int Llb_ObjSetPath( Aig_Obj_t * pObj, Aig_Obj_t * pNext ) { pObj->pData = (void *)pNext; return 1; } |
| static inline Aig_Obj_t * Llb_ObjGetPath( Aig_Obj_t * pObj ) { return (Aig_Obj_t *)pObj->pData; } |
| static inline Aig_Obj_t * Llb_ObjGetFanoutPath( Aig_Man_t * p, Aig_Obj_t * pObj ) |
| { |
| Aig_Obj_t * pFanout; |
| int i, iFanout = -1; |
| assert( Llb_ObjGetPath(pObj) ); |
| Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i ) |
| if ( Llb_ObjGetPath(pFanout) == pObj ) |
| return pFanout; |
| return NULL; |
| } |
| |
| extern Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ); |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [For each cut, returns PIs that can be quantified.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManCutSupps( Aig_Man_t * p, Vec_Ptr_t * vResult ) |
| { |
| Vec_Ptr_t * vSupps, * vOne, * vLower, * vUpper; |
| int i; |
| vSupps = Vec_PtrAlloc( 100 ); |
| Vec_PtrPush( vSupps, Vec_PtrAlloc(0) ); |
| vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 ); |
| Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 ) |
| { |
| vOne = Llb_ManCutSupp( p, vLower, vUpper ); |
| Vec_PtrPush( vSupps, vOne ); |
| vLower = vUpper; |
| } |
| assert( Vec_PtrSize(vSupps) == Vec_PtrSize(vResult) ); |
| return vSupps; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [For each cut, returns PIs that can be quantified.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManCutMap( Aig_Man_t * p, Vec_Ptr_t * vResult, Vec_Ptr_t * vSupps ) |
| { |
| int fShowMatrix = 1; |
| Vec_Ptr_t * vMaps, * vOne; |
| Vec_Int_t * vMap, * vPrev, * vNext; |
| Aig_Obj_t * pObj; |
| int * piFirst, * piLast; |
| int i, k, CounterPlus, CounterMinus, Counter; |
| |
| vMaps = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Vec_Ptr_t *, vResult, vOne, i ) |
| { |
| vMap = Vec_IntStart( Aig_ManObjNumMax(p) ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k ) |
| { |
| if ( !Saig_ObjIsPi(p, pObj) ) |
| Vec_IntWriteEntry( vMap, pObj->Id, 1 ); |
| // else |
| //printf( "*" ); |
| //printf( "%d ", pObj->Id ); |
| } |
| Vec_PtrPush( vMaps, vMap ); |
| //printf( "\n" ); |
| } |
| Vec_PtrPush( vMaps, Vec_IntStart( Aig_ManObjNumMax(p) ) ); |
| assert( Vec_PtrSize(vMaps) == Vec_PtrSize(vResult)+1 ); |
| |
| // collect the first and last PIs |
| piFirst = ABC_ALLOC( int, Saig_ManPiNum(p) ); |
| piLast = ABC_ALLOC( int, Saig_ManPiNum(p) ); |
| Saig_ManForEachPi( p, pObj, i ) |
| piFirst[i] = piLast[i] = -1; |
| Vec_PtrForEachEntry( Vec_Ptr_t *, vSupps, vOne, i ) |
| { |
| Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k ) |
| { |
| if ( !Saig_ObjIsPi(p, pObj) ) |
| continue; |
| if ( piFirst[Aig_ObjCioId(pObj)] == -1 ) |
| piFirst[Aig_ObjCioId(pObj)] = i; |
| piLast[Aig_ObjCioId(pObj)] = i; |
| } |
| } |
| // PIs feeding into the flops should be extended to the last frame |
| Saig_ManForEachLi( p, pObj, i ) |
| { |
| if ( !Saig_ObjIsPi(p, Aig_ObjFanin0(pObj)) ) |
| continue; |
| piLast[Aig_ObjCioId(Aig_ObjFanin0(pObj))] = Vec_PtrSize(vMaps)-1; |
| } |
| |
| // set the PI map |
| Saig_ManForEachPi( p, pObj, i ) |
| { |
| if ( piFirst[i] == -1 ) |
| continue; |
| if ( piFirst[i] == piLast[i] ) |
| { |
| vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, piFirst[i] ); |
| Vec_IntWriteEntry( vMap, pObj->Id, 2 ); |
| continue; |
| } |
| |
| // set support for all in between |
| for ( k = piFirst[i]; k <= piLast[i]; k++ ) |
| { |
| vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, k ); |
| Vec_IntWriteEntry( vMap, pObj->Id, 1 ); |
| } |
| } |
| ABC_FREE( piFirst ); |
| ABC_FREE( piLast ); |
| |
| |
| // find all that will appear here |
| Counter = Aig_ManRegNum(p); |
| printf( "%d ", Counter ); |
| Vec_PtrForEachEntryStart( Vec_Int_t *, vMaps, vMap, i, 1 ) |
| { |
| vPrev = (Vec_Int_t *)Vec_PtrEntry( vMaps, i-1 ); |
| vNext = (i == Vec_PtrSize(vMaps)-1)? NULL: (Vec_Int_t *)Vec_PtrEntry( vMaps, i+1 ); |
| |
| CounterPlus = CounterMinus = 0; |
| Aig_ManForEachObj( p, pObj, k ) |
| { |
| if ( Saig_ObjIsPi(p, pObj) ) |
| { |
| if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 ) |
| CounterPlus++; |
| if ( Vec_IntEntry(vMap, k) == 1 && (vNext == NULL || Vec_IntEntry(vNext, k) == 0) ) |
| CounterMinus++; |
| } |
| else |
| { |
| if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 ) |
| CounterPlus++; |
| if ( Vec_IntEntry(vPrev, k) == 1 && Vec_IntEntry(vMap, k) == 0 ) |
| CounterMinus++; |
| } |
| } |
| Counter = Counter + CounterPlus - CounterMinus; |
| printf( "%d=%d ", i, Counter ); |
| } |
| printf( "\n" ); |
| |
| if ( !fShowMatrix ) |
| return vMaps; |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) ) |
| continue; |
| Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k ) |
| if ( Vec_IntEntry(vMap, i) ) |
| break; |
| if ( k == Vec_PtrSize(vMaps) ) |
| continue; |
| printf( "Obj = %4d : ", i ); |
| if ( Saig_ObjIsPi(p,pObj) ) |
| printf( "pi " ); |
| else if ( Saig_ObjIsLo(p,pObj) ) |
| printf( "lo " ); |
| else if ( Aig_ObjIsNode(pObj) ) |
| printf( "and " ); |
| |
| Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k ) |
| printf( "%d", Vec_IntEntry(vMap, i) ); |
| printf( "\n" ); |
| } |
| return vMaps; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts the number of PIs in the cut] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManCutPiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut ) |
| { |
| Aig_Obj_t * pObj; |
| int i, Counter = 0; |
| Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i ) |
| if ( Saig_ObjIsPi(p,pObj) ) |
| Counter++; |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts the number of LOs in the cut] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManCutLoNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut ) |
| { |
| Aig_Obj_t * pObj; |
| int i, Counter = 0; |
| Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i ) |
| if ( Saig_ObjIsLo(p,pObj) ) |
| Counter++; |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts the number of LIs in the cut] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManCutLiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut ) |
| { |
| Aig_Obj_t * pFanout; |
| Aig_Obj_t * pObj; |
| int i, k, iFanout = -1, Counter = 0; |
| Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i ) |
| { |
| if ( Aig_ObjIsCi(pObj) ) |
| continue; |
| Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, k ) |
| { |
| if ( Saig_ObjIsLi(p, pFanout) ) |
| { |
| Counter++; |
| break; |
| } |
| } |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManCutVolume_rec( Aig_Man_t * p, Aig_Obj_t * pObj ) |
| { |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| return 0; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| assert( Aig_ObjIsNode(pObj) ); |
| return 1 + Llb_ManCutVolume_rec(p, Aig_ObjFanin0(pObj)) + |
| Llb_ManCutVolume_rec(p, Aig_ObjFanin1(pObj)); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManCutVolume( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Aig_Obj_t * pObj; |
| int i, Counter = 0; |
| // mark the lower cut with the traversal ID |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| Aig_ObjSetTravIdCurrent( p, pObj ); |
| // count the upper cut |
| Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i ) |
| Counter += Llb_ManCutVolume_rec( p, pObj ); |
| return Counter; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManCutNodes_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vNodes ) |
| { |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| return; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| assert( Aig_ObjIsNode(pObj) ); |
| Llb_ManCutNodes_rec(p, Aig_ObjFanin0(pObj), vNodes); |
| Llb_ManCutNodes_rec(p, Aig_ObjFanin1(pObj), vNodes); |
| Vec_PtrPush( vNodes, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManCutNodes( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Vec_Ptr_t * vNodes; |
| Aig_Obj_t * pObj; |
| int i; |
| // mark the lower cut with the traversal ID |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| Aig_ObjSetTravIdCurrent( p, pObj ); |
| // count the upper cut |
| vNodes = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i ) |
| Llb_ManCutNodes_rec( p, pObj, vNodes ); |
| return vNodes; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Vec_Ptr_t * vNodes, * vSupp; |
| Aig_Obj_t * pObj; |
| int i; |
| vNodes = Llb_ManCutNodes( p, vLower, vUpper ); |
| // mark support of the nodes |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i ) |
| { |
| assert( Aig_ObjIsNode(pObj) ); |
| Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin0(pObj) ); |
| Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin1(pObj) ); |
| } |
| Vec_PtrFree( vNodes ); |
| // collect the support nodes |
| vSupp = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| Vec_PtrPush( vSupp, pObj ); |
| return vSupp; |
| |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes volume of the cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManCutRange( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Vec_Ptr_t * vRange; |
| Aig_Obj_t * pObj; |
| int i; |
| // mark the lower cut with the traversal ID |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| Aig_ObjSetTravIdCurrent( p, pObj ); |
| // collect the upper ones that are not marked |
| vRange = Vec_PtrAlloc( 100 ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i ) |
| if ( !Aig_ObjIsTravIdCurrent(p, pObj) ) |
| Vec_PtrPush( vRange, pObj ); |
| return vRange; |
| } |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints the given cluster.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManCutPrint( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Vec_Ptr_t * vSupp, * vRange; |
| int Pis, Ffs, And; |
| |
| Pis = Llb_ManCutPiNum(p, vLower); |
| Ffs = Llb_ManCutLoNum(p, vLower); |
| And = Vec_PtrSize(vLower) - Pis - Ffs; |
| printf( "Leaf: %3d=%3d+%3d+%3d ", Vec_PtrSize(vLower), Pis, Ffs, And ); |
| |
| Pis = Llb_ManCutPiNum(p, vUpper); |
| Ffs = Llb_ManCutLiNum(p, vUpper); |
| And = Vec_PtrSize(vUpper) - Pis - Ffs; |
| printf( "Root: %3d=%3d+%3d+%3d ", Vec_PtrSize(vUpper), Pis, Ffs, And ); |
| |
| vSupp = Llb_ManCutSupp( p, vLower, vUpper ); |
| Pis = Llb_ManCutPiNum(p, vSupp); |
| Ffs = Llb_ManCutLoNum(p, vSupp); |
| And = Vec_PtrSize(vSupp) - Pis - Ffs; |
| printf( "Supp: %3d=%3d+%3d+%3d ", Vec_PtrSize(vSupp), Pis, Ffs, And ); |
| |
| vRange = Llb_ManCutRange( p, vLower, vUpper ); |
| Pis = Llb_ManCutPiNum(p, vRange); |
| Ffs = Llb_ManCutLiNum(p, vRange); |
| And = Vec_PtrSize(vRange) - Pis - Ffs; |
| printf( "Range: %3d=%3d+%3d+%3d ", Vec_PtrSize(vRange), Pis, Ffs, And ); |
| |
| printf( "S =%3d. V =%3d.\n", |
| Vec_PtrSize(vSupp)+Vec_PtrSize(vRange), Llb_ManCutVolume(p, vLower, vUpper) ); |
| Vec_PtrFree( vSupp ); |
| Vec_PtrFree( vRange ); |
| /* |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| printf( "Lower: " ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| printf( " %d", pObj->Id ); |
| printf( " " ); |
| printf( "Upper: " ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i ) |
| printf( " %d", pObj->Id ); |
| printf( "\n" ); |
| } |
| */ |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints the given cluster.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManResultPrint( Aig_Man_t * p, Vec_Ptr_t * vResult ) |
| { |
| Vec_Ptr_t * vLower, * vUpper = NULL; |
| int i; |
| Vec_PtrForEachEntryReverse( Vec_Ptr_t *, vResult, vLower, i ) |
| { |
| if ( i < Vec_PtrSize(vResult) - 1 ) |
| Llb_ManCutPrint( p, vLower, vUpper ); |
| vUpper = vLower; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Tries to find an augmenting path originating in this node.] |
| |
| Description [This procedure works for directed graphs only!] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManFlowBwdPath2_rec( Aig_Man_t * p, Aig_Obj_t * pObj ) |
| { |
| Aig_Obj_t * pFanout; |
| assert( Aig_ObjIsNode(pObj) || Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) ); |
| // skip visited nodes |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| return 0; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| // process node without flow |
| if ( !Llb_ObjGetPath(pObj) ) |
| { |
| // start the path if we reached a terminal node |
| if ( pObj->fMarkA ) |
| return Llb_ObjSetPath( pObj, (Aig_Obj_t *)1 ); |
| // explore the fanins |
| // Abc_ObjForEachFanin( pObj, pFanin, i ) |
| // if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) ) |
| // return Abc_ObjSetPath( pObj, pFanin ); |
| if ( Aig_ObjIsNode(pObj) ) |
| { |
| if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ) ) |
| return Llb_ObjSetPath( pObj, Aig_ObjFanin0(pObj) ); |
| if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ) ) |
| return Llb_ObjSetPath( pObj, Aig_ObjFanin1(pObj) ); |
| } |
| return 0; |
| } |
| // pObj has flow - find the fanout with flow |
| pFanout = Llb_ObjGetFanoutPath( p, 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 ); |
| assert( Aig_ObjIsNode(pFanout) ); |
| if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pFanout) ) ) |
| return Llb_ObjSetPath( pFanout, Aig_ObjFanin0(pFanout) ); |
| if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pFanout) ) ) |
| return Llb_ObjSetPath( pFanout, Aig_ObjFanin1(pFanout) ); |
| // try the fanout |
| if ( Llb_ManFlowBwdPath2_rec( p, pFanout ) ) |
| return Llb_ObjSetPath( pFanout, NULL ); |
| return 0; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Cleans markB.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowLabelTfi_rec( Aig_Man_t * p, Aig_Obj_t * pObj ) |
| { |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| return; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) ) |
| return; |
| assert( Aig_ObjIsNode(pObj) ); |
| Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin0(pObj) ); |
| Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin1(pObj) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowUpdateCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| // label the TFI of the cut nodes |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i ) |
| Llb_ManFlowLabelTfi_rec( p, pObj ); |
| // collect labeled fanins of non-labeled nodes |
| Vec_PtrClear( vMinCut ); |
| Aig_ManIncrementTravId(p); |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| if ( !Aig_ObjIsCo(pObj) && !Aig_ObjIsNode(pObj) ) |
| continue; |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) || Aig_ObjIsTravIdPrevious(p, pObj) ) |
| continue; |
| if ( Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin0(pObj)) ) |
| { |
| Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin0(pObj)); |
| Vec_PtrPush( vMinCut, Aig_ObjFanin0(pObj) ); |
| } |
| if ( Aig_ObjIsNode(pObj) && Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin1(pObj)) ) |
| { |
| Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin1(pObj)); |
| Vec_PtrPush( vMinCut, Aig_ObjFanin1(pObj) ); |
| } |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Find minimum-volume minumum cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManFlowMinCut( Aig_Man_t * p ) |
| { |
| Vec_Ptr_t * vMinCut; |
| Aig_Obj_t * pObj; |
| int i; |
| // collect the cut nodes |
| vMinCut = Vec_PtrAlloc( Aig_ManRegNum(p) ); |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| // node without flow is not a cut node |
| if ( !Llb_ObjGetPath(pObj) ) |
| continue; |
| // unvisited node is below the cut |
| if ( !Aig_ObjIsTravIdCurrent(p, pObj) ) |
| continue; |
| // add terminal with flow or node whose path is not visited |
| if ( pObj->fMarkA || !Aig_ObjIsTravIdCurrent( p, Llb_ObjGetPath(pObj) ) ) |
| Vec_PtrPush( vMinCut, pObj ); |
| } |
| return vMinCut; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verifies the min-cut is indeed a cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManFlowVerifyCut_rec( Aig_Man_t * p, Aig_Obj_t * pObj ) |
| { |
| // skip visited nodes |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| return 1; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| // visit the node |
| if ( Aig_ObjIsConst1(pObj) ) |
| return 1; |
| if ( Aig_ObjIsCi(pObj) ) |
| return 0; |
| // explore the fanins |
| assert( Aig_ObjIsNode(pObj) ); |
| if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin0(pObj)) ) |
| return 0; |
| if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin1(pObj)) ) |
| return 0; |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verifies the min-cut is indeed a cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Llb_ManFlowVerifyCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| // mark the cut with the current traversal ID |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i ) |
| Aig_ObjSetTravIdCurrent( p, pObj ); |
| // search from the latches for a path to the COs/CIs |
| Saig_ManForEachLi( p, pObj, i ) |
| { |
| if ( !Llb_ManFlowVerifyCut_rec( p, Aig_ObjFanin0(pObj) ) ) |
| return 0; |
| } |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Implementation of max-flow/min-cut computation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManFlow( Aig_Man_t * p, Vec_Ptr_t * vSources, int * pnFlow ) |
| { |
| Vec_Ptr_t * vMinCut; |
| Aig_Obj_t * pObj; |
| int Flow, FlowCur, RetValue, i; |
| // find the max-flow |
| Flow = 0; |
| Aig_ManCleanData( p ); |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i ) |
| { |
| assert( !pObj->fMarkA && pObj->fMarkB ); |
| if ( !Aig_ObjFanin0(pObj)->fMarkB ) |
| { |
| FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ); |
| Flow += FlowCur; |
| if ( FlowCur ) |
| Aig_ManIncrementTravId(p); |
| } |
| if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB ) |
| { |
| FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ); |
| Flow += FlowCur; |
| if ( FlowCur ) |
| Aig_ManIncrementTravId(p); |
| } |
| } |
| if ( pnFlow ) |
| *pnFlow = Flow; |
| |
| // mark the nodes reachable from the latches |
| Aig_ManIncrementTravId(p); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i ) |
| { |
| assert( !pObj->fMarkA && pObj->fMarkB ); |
| if ( !Aig_ObjFanin0(pObj)->fMarkB ) |
| { |
| RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ); |
| assert( RetValue == 0 ); |
| } |
| if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB ) |
| { |
| RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ); |
| assert( RetValue == 0 ); |
| } |
| } |
| |
| // find the min-cut with the smallest volume |
| vMinCut = Llb_ManFlowMinCut( p ); |
| assert( Vec_PtrSize(vMinCut) == Flow ); |
| // verify the cut |
| if ( !Llb_ManFlowVerifyCut(p, vMinCut) ) |
| printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" ); |
| // Llb_ManFlowPrintCut( p, vMinCut ); |
| return vMinCut; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Implementation of max-flow/min-cut computation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManFlowCompute( Aig_Man_t * p ) |
| { |
| Vec_Ptr_t * vMinCut; |
| Aig_Obj_t * pObj; |
| int Flow, FlowCur, RetValue, i; |
| // find the max-flow |
| Flow = 0; |
| Aig_ManCleanData( p ); |
| Aig_ManIncrementTravId(p); |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| if ( !pObj->fMarkB ) |
| continue; |
| assert( !pObj->fMarkA ); |
| if ( !Aig_ObjFanin0(pObj)->fMarkB ) |
| { |
| //printf( "%d ", Aig_ObjFanin0(pObj)->Id ); |
| FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ); |
| Flow += FlowCur; |
| if ( FlowCur ) |
| Aig_ManIncrementTravId(p); |
| } |
| if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB ) |
| { |
| //printf( "%d ", Aig_ObjFanin1(pObj)->Id ); |
| FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ); |
| Flow += FlowCur; |
| if ( FlowCur ) |
| Aig_ManIncrementTravId(p); |
| } |
| } |
| //printf( "\n" ); |
| |
| // mark the nodes reachable from the latches |
| Aig_ManIncrementTravId(p); |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| if ( !pObj->fMarkB ) |
| continue; |
| assert( !pObj->fMarkA ); |
| if ( !Aig_ObjFanin0(pObj)->fMarkB ) |
| { |
| RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ); |
| assert( RetValue == 0 ); |
| } |
| if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB ) |
| { |
| RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ); |
| assert( RetValue == 0 ); |
| } |
| } |
| // find the min-cut with the smallest volume |
| vMinCut = Llb_ManFlowMinCut( p ); |
| assert( Vec_PtrSize(vMinCut) == Flow ); |
| //printf( "%d ", Vec_PtrSize(vMinCut) ); |
| Llb_ManFlowUpdateCut( p, vMinCut ); |
| //printf( "%d ", Vec_PtrSize(vMinCut) ); |
| // verify the cut |
| if ( !Llb_ManFlowVerifyCut(p, vMinCut) ) |
| printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" ); |
| // Llb_ManFlowPrintCut( p, vMinCut ); |
| return vMinCut; |
| } |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Cleans markB.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowCleanMarkB_rec( Aig_Obj_t * pObj ) |
| { |
| if ( pObj->fMarkB == 0 ) |
| return; |
| pObj->fMarkB = 0; |
| assert( Aig_ObjIsNode(pObj) ); |
| Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin0(pObj) ); |
| Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin1(pObj) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Cleans markB.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowSetMarkA_rec( Aig_Obj_t * pObj ) |
| { |
| if ( pObj->fMarkA ) |
| return; |
| pObj->fMarkA = 1; |
| if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) ) |
| return; |
| assert( Aig_ObjIsNode(pObj) ); |
| Llb_ManFlowSetMarkA_rec( Aig_ObjFanin0(pObj) ); |
| Llb_ManFlowSetMarkA_rec( Aig_ObjFanin1(pObj) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prepares flow computation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowPrepareCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| // reset marks |
| Aig_ManForEachObj( p, pObj, i ) |
| { |
| pObj->fMarkA = 0; |
| pObj->fMarkB = 1; |
| } |
| // clean PIs and const |
| Aig_ManConst1(p)->fMarkB = 0; |
| Aig_ManForEachCi( p, pObj, i ) |
| pObj->fMarkB = 0; |
| // clean upper cut |
| //printf( "Upper: "); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i ) |
| { |
| Llb_ManFlowCleanMarkB_rec( pObj ); |
| //printf( "%d ", pObj->Id ); |
| } |
| //printf( "\n" ); |
| // set lower cut |
| //printf( "Lower: "); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| { |
| //printf( "%d ", pObj->Id ); |
| assert( pObj->fMarkB == 0 ); |
| Llb_ManFlowSetMarkA_rec( pObj ); |
| } |
| //printf( "\n" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prepares flow computation.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowUnmarkCone( Aig_Man_t * p, Vec_Ptr_t * vCone ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| Vec_PtrForEachEntry( Aig_Obj_t *, vCone, pObj, i ) |
| { |
| assert( Aig_ObjIsNode(pObj) ); |
| assert( pObj->fMarkB == 1 ); |
| pObj->fMarkB = 0; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowCollectAndMarkCone_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vCone ) |
| { |
| Aig_Obj_t * pFanout; |
| int i, iFanout = -1; |
| if ( Saig_ObjIsLi(p, pObj) ) |
| return; |
| if ( pObj->fMarkB ) |
| return; |
| if ( pObj->fMarkA == 0 ) |
| { |
| assert( Aig_ObjIsNode(pObj) ); |
| pObj->fMarkB = 1; |
| if ( Aig_ObjIsNode(pObj) ) |
| Vec_PtrPush( vCone, pObj ); |
| } |
| Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i ) |
| Llb_ManFlowCollectAndMarkCone_rec( p, pFanout, vCone ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects the cone.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowCollectAndMarkCone( Aig_Man_t * p, Vec_Ptr_t * vStarts, Vec_Ptr_t * vCone ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| Vec_PtrClear( vCone ); |
| Vec_PtrForEachEntry( Aig_Obj_t *, vStarts, pObj, i ) |
| { |
| assert( pObj->fMarkA && !pObj->fMarkB ); |
| Llb_ManFlowCollectAndMarkCone_rec( p, pObj, vCone ); |
| } |
| } |
| |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManComputeCutLo( Aig_Man_t * p ) |
| { |
| Vec_Ptr_t * vMinCut; |
| Aig_Obj_t * pObj; |
| int i; |
| vMinCut = Vec_PtrAlloc( 100 ); |
| Aig_ManForEachCi( p, pObj, i ) |
| Vec_PtrPush( vMinCut, pObj ); |
| return vMinCut; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManComputeCutLi( Aig_Man_t * p ) |
| { |
| Vec_Ptr_t * vMinCut; |
| Aig_Obj_t * pObj; |
| int i; |
| assert( Saig_ManPoNum(p) == 0 ); |
| vMinCut = Vec_PtrAlloc( 100 ); |
| Aig_ManIncrementTravId(p); |
| Saig_ManForEachLi( p, pObj, i ) |
| { |
| pObj = Aig_ObjFanin0(pObj); |
| if ( Aig_ObjIsConst1(pObj) ) |
| continue; |
| if ( Aig_ObjIsTravIdCurrent(p, pObj) ) |
| continue; |
| Aig_ObjSetTravIdCurrent(p, pObj); |
| Vec_PtrPush( vMinCut, pObj ); |
| } |
| return vMinCut; |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManFlowGetObjSet( Aig_Man_t * p, Vec_Ptr_t * vLower, int iStart, int nSize, Vec_Ptr_t * vSet ) |
| { |
| Aig_Obj_t * pObj; |
| int i; |
| Vec_PtrClear( vSet ); |
| for ( i = 0; i < nSize; i++ ) |
| { |
| pObj = (Aig_Obj_t *)Vec_PtrEntry( vLower, (iStart + i) % Vec_PtrSize(vLower) ); |
| Vec_PtrPush( vSet, pObj ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManFlowFindBestCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper, int Num ) |
| { |
| int nVolMin = Aig_ManNodeNum(p) / Num / 2; |
| Vec_Ptr_t * vMinCut; |
| Vec_Ptr_t * vCone, * vSet; |
| Aig_Obj_t * pObj; |
| int i, s, Vol, VolLower, VolUpper, VolCmp; |
| int iBest = -1, iMinCut = ABC_INFINITY, iVolBest = 0; |
| |
| Vol = Llb_ManCutVolume( p, vLower, vUpper ); |
| assert( Vol > nVolMin ); |
| VolCmp = Abc_MinInt( nVolMin, Vol - nVolMin ); |
| vCone = Vec_PtrAlloc( 100 ); |
| vSet = Vec_PtrAlloc( 100 ); |
| Llb_ManFlowPrepareCut( p, vLower, vUpper ); |
| for ( s = 1; s < Aig_ManRegNum(p); s += 5 ) |
| { |
| Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i ) |
| { |
| Llb_ManFlowGetObjSet( p, vLower, i, s, vSet ); |
| Llb_ManFlowCollectAndMarkCone( p, vSet, vCone ); |
| if ( Vec_PtrSize(vCone) == 0 ) |
| continue; |
| vMinCut = Llb_ManFlowCompute( p ); |
| Llb_ManFlowUnmarkCone( p, vCone ); |
| |
| VolLower = Llb_ManCutVolume( p, vLower, vMinCut ); |
| VolUpper = Llb_ManCutVolume( p, vMinCut, vUpper ); |
| Vol = Abc_MinInt( VolLower, VolUpper ); |
| if ( Vol >= VolCmp && (iMinCut == -1 || |
| iMinCut > Vec_PtrSize(vMinCut) || |
| (iMinCut == Vec_PtrSize(vMinCut) && iVolBest < Vol)) ) |
| { |
| iBest = i; |
| iMinCut = Vec_PtrSize(vMinCut); |
| iVolBest = Vol; |
| } |
| Vec_PtrFree( vMinCut ); |
| } |
| if ( iBest >= 0 ) |
| break; |
| } |
| if ( iBest == -1 ) |
| { |
| // cleanup |
| Vec_PtrFree( vCone ); |
| Vec_PtrFree( vSet ); |
| return NULL; |
| } |
| // get the best cut |
| assert( iBest >= 0 ); |
| Llb_ManFlowGetObjSet( p, vLower, iBest, s, vSet ); |
| Llb_ManFlowCollectAndMarkCone( p, vSet, vCone ); |
| vMinCut = Llb_ManFlowCompute( p ); |
| Llb_ManFlowUnmarkCone( p, vCone ); |
| // cleanup |
| Vec_PtrFree( vCone ); |
| Vec_PtrFree( vSet ); |
| return vMinCut; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Llb_ManComputeCuts( Aig_Man_t * p, int Num, int fVerbose, int fVeryVerbose ) |
| { |
| int nVolMax = Aig_ManNodeNum(p) / Num; |
| Vec_Ptr_t * vResult, * vMinCut = NULL, * vLower, * vUpper; |
| int i, k, nVol; |
| abctime clk = Abc_Clock(); |
| vResult = Vec_PtrAlloc( 100 ); |
| Vec_PtrPush( vResult, Llb_ManComputeCutLo(p) ); |
| Vec_PtrPush( vResult, Llb_ManComputeCutLi(p) ); |
| while ( 1 ) |
| { |
| // find a place to insert new cut |
| vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 ); |
| Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 ) |
| { |
| nVol = Llb_ManCutVolume( p, vLower, vUpper ); |
| if ( nVol <= nVolMax ) |
| { |
| vLower = vUpper; |
| continue; |
| } |
| |
| if ( fVeryVerbose ) |
| Llb_ManCutPrint( p, vLower, vUpper ); |
| vMinCut = Llb_ManFlowFindBestCut( p, vLower, vUpper, Num ); |
| if ( vMinCut == NULL ) |
| { |
| if ( fVeryVerbose ) |
| printf( "Could not break the cut.\n" ); |
| if ( fVeryVerbose ) |
| printf( "\n" ); |
| vLower = vUpper; |
| continue; |
| } |
| |
| if ( fVeryVerbose ) |
| Llb_ManCutPrint( p, vMinCut, vUpper ); |
| if ( fVeryVerbose ) |
| Llb_ManCutPrint( p, vLower, vMinCut ); |
| if ( fVeryVerbose ) |
| printf( "\n" ); |
| |
| break; |
| } |
| if ( i == Vec_PtrSize(vResult) ) |
| break; |
| // insert vMinCut before vUpper |
| Vec_PtrPush( vResult, NULL ); |
| for ( k = Vec_PtrSize(vResult) - 1; k > i; k-- ) |
| Vec_PtrWriteEntry( vResult, k, Vec_PtrEntry(vResult, k-1) ); |
| Vec_PtrWriteEntry( vResult, i, vMinCut ); |
| } |
| if ( fVerbose ) |
| { |
| printf( "Finished computing %d partitions. ", Vec_PtrSize(vResult) - 1 ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); |
| Llb_ManResultPrint( p, vResult ); |
| } |
| return vResult; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_BddSetDefaultParams( Gia_ParLlb_t * p ) |
| { |
| memset( p, 0, sizeof(Gia_ParLlb_t) ); |
| p->nBddMax = 1000000; |
| p->nIterMax = 10000000; |
| p->nClusterMax = 20; |
| p->nHintDepth = 0; |
| p->HintFirst = 0; |
| p->fUseFlow = 0; // use flow |
| p->nVolumeMax = 100; // max volume |
| p->nVolumeMin = 30; // min volume |
| p->fReorder = 1; |
| p->fIndConstr = 0; |
| p->fUsePivots = 0; |
| p->fCluster = 0; |
| p->fSchedule = 0; |
| p->fVerbose = 0; |
| p->fVeryVerbose = 0; |
| p->fSilent = 0; |
| p->TimeLimit = 0; |
| // p->TimeLimit = 0; |
| p->TimeLimitGlo = 0; |
| p->TimeTarget = 0; |
| p->iFrame = -1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Finds balanced cut.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Llb_ManMinCutTest( Aig_Man_t * pAig, int Num ) |
| { |
| extern void Llb_BddConstructTest( Aig_Man_t * p, Vec_Ptr_t * vResult ); |
| extern void Llb_BddExperiment( Aig_Man_t * pInit, Aig_Man_t * pAig, Gia_ParLlb_t * pPars, Vec_Ptr_t * vResult, Vec_Ptr_t * vMaps ); |
| |
| |
| // int fVerbose = 1; |
| Gia_ParLlb_t Pars, * pPars = &Pars; |
| Vec_Ptr_t * vResult;//, * vSupps, * vMaps; |
| Aig_Man_t * p; |
| |
| Llb_BddSetDefaultParams( pPars ); |
| |
| p = Aig_ManDupFlopsOnly( pAig ); |
| //Aig_ManShow( p, 0, NULL ); |
| Aig_ManPrintStats( pAig ); |
| Aig_ManPrintStats( p ); |
| Aig_ManFanoutStart( p ); |
| |
| vResult = Llb_ManComputeCuts( p, Num, 1, 0 ); |
| // vSupps = Llb_ManCutSupps( p, vResult ); |
| // vMaps = Llb_ManCutMap( p, vResult, vSupps ); |
| |
| // Llb_BddExperiment( pAig, p, pPars, vResult, vMaps ); |
| Llb_CoreExperiment( pAig, p, pPars, vResult, 0 ); |
| |
| // Vec_VecFree( (Vec_Vec_t *)vMaps ); |
| // Vec_VecFree( (Vec_Vec_t *)vSupps ); |
| Vec_VecFree( (Vec_Vec_t *)vResult ); |
| |
| Aig_ManFanoutStop( p ); |
| Aig_ManCleanMarkAB( p ); |
| Aig_ManStop( p ); |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
