abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
llb2Flow.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [llb2Flow.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [BDD based reachability.]
8 
9  Synopsis [Flow computation.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: llb2Flow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "llbInt.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static inline int Llb_ObjSetPath( Aig_Obj_t * pObj, Aig_Obj_t * pNext ) { pObj->pData = (void *)pNext; return 1; }
31 static inline Aig_Obj_t * Llb_ObjGetPath( Aig_Obj_t * pObj ) { return (Aig_Obj_t *)pObj->pData; }
32 static inline Aig_Obj_t * Llb_ObjGetFanoutPath( Aig_Man_t * p, Aig_Obj_t * pObj )
33 {
34  Aig_Obj_t * pFanout;
35  int i, iFanout = -1;
36  assert( Llb_ObjGetPath(pObj) );
37  Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
38  if ( Llb_ObjGetPath(pFanout) == pObj )
39  return pFanout;
40  return NULL;
41 }
42 
43 extern Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper );
44 
45 ////////////////////////////////////////////////////////////////////////
46 /// FUNCTION DEFINITIONS ///
47 ////////////////////////////////////////////////////////////////////////
48 
49 
50 /**Function*************************************************************
51 
52  Synopsis [For each cut, returns PIs that can be quantified.]
53 
54  Description []
55 
56  SideEffects []
57 
58  SeeAlso []
59 
60 ***********************************************************************/
61 Vec_Ptr_t * Llb_ManCutSupps( Aig_Man_t * p, Vec_Ptr_t * vResult )
62 {
63  Vec_Ptr_t * vSupps, * vOne, * vLower, * vUpper;
64  int i;
65  vSupps = Vec_PtrAlloc( 100 );
66  Vec_PtrPush( vSupps, Vec_PtrAlloc(0) );
67  vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 );
68  Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 )
69  {
70  vOne = Llb_ManCutSupp( p, vLower, vUpper );
71  Vec_PtrPush( vSupps, vOne );
72  vLower = vUpper;
73  }
74  assert( Vec_PtrSize(vSupps) == Vec_PtrSize(vResult) );
75  return vSupps;
76 }
77 
78 /**Function*************************************************************
79 
80  Synopsis [For each cut, returns PIs that can be quantified.]
81 
82  Description []
83 
84  SideEffects []
85 
86  SeeAlso []
87 
88 ***********************************************************************/
89 Vec_Ptr_t * Llb_ManCutMap( Aig_Man_t * p, Vec_Ptr_t * vResult, Vec_Ptr_t * vSupps )
90 {
91  int fShowMatrix = 1;
92  Vec_Ptr_t * vMaps, * vOne;
93  Vec_Int_t * vMap, * vPrev, * vNext;
94  Aig_Obj_t * pObj;
95  int * piFirst, * piLast;
96  int i, k, CounterPlus, CounterMinus, Counter;
97 
98  vMaps = Vec_PtrAlloc( 100 );
99  Vec_PtrForEachEntry( Vec_Ptr_t *, vResult, vOne, i )
100  {
101  vMap = Vec_IntStart( Aig_ManObjNumMax(p) );
102  Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k )
103  {
104  if ( !Saig_ObjIsPi(p, pObj) )
105  Vec_IntWriteEntry( vMap, pObj->Id, 1 );
106 // else
107 //printf( "*" );
108 //printf( "%d ", pObj->Id );
109  }
110  Vec_PtrPush( vMaps, vMap );
111 //printf( "\n" );
112  }
113  Vec_PtrPush( vMaps, Vec_IntStart( Aig_ManObjNumMax(p) ) );
114  assert( Vec_PtrSize(vMaps) == Vec_PtrSize(vResult)+1 );
115 
116  // collect the first and last PIs
117  piFirst = ABC_ALLOC( int, Saig_ManPiNum(p) );
118  piLast = ABC_ALLOC( int, Saig_ManPiNum(p) );
119  Saig_ManForEachPi( p, pObj, i )
120  piFirst[i] = piLast[i] = -1;
121  Vec_PtrForEachEntry( Vec_Ptr_t *, vSupps, vOne, i )
122  {
123  Vec_PtrForEachEntry( Aig_Obj_t *, vOne, pObj, k )
124  {
125  if ( !Saig_ObjIsPi(p, pObj) )
126  continue;
127  if ( piFirst[Aig_ObjCioId(pObj)] == -1 )
128  piFirst[Aig_ObjCioId(pObj)] = i;
129  piLast[Aig_ObjCioId(pObj)] = i;
130  }
131  }
132  // PIs feeding into the flops should be extended to the last frame
133  Saig_ManForEachLi( p, pObj, i )
134  {
135  if ( !Saig_ObjIsPi(p, Aig_ObjFanin0(pObj)) )
136  continue;
137  piLast[Aig_ObjCioId(Aig_ObjFanin0(pObj))] = Vec_PtrSize(vMaps)-1;
138  }
139 
140  // set the PI map
141  Saig_ManForEachPi( p, pObj, i )
142  {
143  if ( piFirst[i] == -1 )
144  continue;
145  if ( piFirst[i] == piLast[i] )
146  {
147  vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, piFirst[i] );
148  Vec_IntWriteEntry( vMap, pObj->Id, 2 );
149  continue;
150  }
151 
152  // set support for all in between
153  for ( k = piFirst[i]; k <= piLast[i]; k++ )
154  {
155  vMap = (Vec_Int_t *)Vec_PtrEntry( vMaps, k );
156  Vec_IntWriteEntry( vMap, pObj->Id, 1 );
157  }
158  }
159  ABC_FREE( piFirst );
160  ABC_FREE( piLast );
161 
162 
163  // find all that will appear here
164  Counter = Aig_ManRegNum(p);
165  printf( "%d ", Counter );
166  Vec_PtrForEachEntryStart( Vec_Int_t *, vMaps, vMap, i, 1 )
167  {
168  vPrev = (Vec_Int_t *)Vec_PtrEntry( vMaps, i-1 );
169  vNext = (i == Vec_PtrSize(vMaps)-1)? NULL: (Vec_Int_t *)Vec_PtrEntry( vMaps, i+1 );
170 
171  CounterPlus = CounterMinus = 0;
172  Aig_ManForEachObj( p, pObj, k )
173  {
174  if ( Saig_ObjIsPi(p, pObj) )
175  {
176  if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 )
177  CounterPlus++;
178  if ( Vec_IntEntry(vMap, k) == 1 && (vNext == NULL || Vec_IntEntry(vNext, k) == 0) )
179  CounterMinus++;
180  }
181  else
182  {
183  if ( Vec_IntEntry(vPrev, k) == 0 && Vec_IntEntry(vMap, k) == 1 )
184  CounterPlus++;
185  if ( Vec_IntEntry(vPrev, k) == 1 && Vec_IntEntry(vMap, k) == 0 )
186  CounterMinus++;
187  }
188  }
189  Counter = Counter + CounterPlus - CounterMinus;
190  printf( "%d=%d ", i, Counter );
191  }
192  printf( "\n" );
193 
194  if ( !fShowMatrix )
195  return vMaps;
196  Aig_ManForEachObj( p, pObj, i )
197  {
198  if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) )
199  continue;
200  Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k )
201  if ( Vec_IntEntry(vMap, i) )
202  break;
203  if ( k == Vec_PtrSize(vMaps) )
204  continue;
205  printf( "Obj = %4d : ", i );
206  if ( Saig_ObjIsPi(p,pObj) )
207  printf( "pi " );
208  else if ( Saig_ObjIsLo(p,pObj) )
209  printf( "lo " );
210  else if ( Aig_ObjIsNode(pObj) )
211  printf( "and " );
212 
213  Vec_PtrForEachEntry( Vec_Int_t *, vMaps, vMap, k )
214  printf( "%d", Vec_IntEntry(vMap, i) );
215  printf( "\n" );
216  }
217  return vMaps;
218 }
219 
220 /**Function*************************************************************
221 
222  Synopsis [Counts the number of PIs in the cut]
223 
224  Description []
225 
226  SideEffects []
227 
228  SeeAlso []
229 
230 ***********************************************************************/
231 int Llb_ManCutPiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
232 {
233  Aig_Obj_t * pObj;
234  int i, Counter = 0;
235  Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
236  if ( Saig_ObjIsPi(p,pObj) )
237  Counter++;
238  return Counter;
239 }
240 
241 /**Function*************************************************************
242 
243  Synopsis [Counts the number of LOs in the cut]
244 
245  Description []
246 
247  SideEffects []
248 
249  SeeAlso []
250 
251 ***********************************************************************/
252 int Llb_ManCutLoNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
253 {
254  Aig_Obj_t * pObj;
255  int i, Counter = 0;
256  Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
257  if ( Saig_ObjIsLo(p,pObj) )
258  Counter++;
259  return Counter;
260 }
261 
262 /**Function*************************************************************
263 
264  Synopsis [Counts the number of LIs in the cut]
265 
266  Description []
267 
268  SideEffects []
269 
270  SeeAlso []
271 
272 ***********************************************************************/
273 int Llb_ManCutLiNum( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
274 {
275  Aig_Obj_t * pFanout;
276  Aig_Obj_t * pObj;
277  int i, k, iFanout = -1, Counter = 0;
278  Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
279  {
280  if ( Aig_ObjIsCi(pObj) )
281  continue;
282  Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, k )
283  {
284  if ( Saig_ObjIsLi(p, pFanout) )
285  {
286  Counter++;
287  break;
288  }
289  }
290  }
291  return Counter;
292 }
293 
294 /**Function*************************************************************
295 
296  Synopsis [Computes volume of the cut.]
297 
298  Description []
299 
300  SideEffects []
301 
302  SeeAlso []
303 
304 ***********************************************************************/
305 int Llb_ManCutVolume_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
306 {
307  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
308  return 0;
309  Aig_ObjSetTravIdCurrent(p, pObj);
310  assert( Aig_ObjIsNode(pObj) );
311  return 1 + Llb_ManCutVolume_rec(p, Aig_ObjFanin0(pObj)) +
312  Llb_ManCutVolume_rec(p, Aig_ObjFanin1(pObj));
313 }
314 
315 /**Function*************************************************************
316 
317  Synopsis [Computes volume of the cut.]
318 
319  Description []
320 
321  SideEffects []
322 
323  SeeAlso []
324 
325 ***********************************************************************/
326 int Llb_ManCutVolume( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
327 {
328  Aig_Obj_t * pObj;
329  int i, Counter = 0;
330  // mark the lower cut with the traversal ID
331  Aig_ManIncrementTravId(p);
332  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
333  Aig_ObjSetTravIdCurrent( p, pObj );
334  // count the upper cut
335  Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
336  Counter += Llb_ManCutVolume_rec( p, pObj );
337  return Counter;
338 }
339 
340 
341 /**Function*************************************************************
342 
343  Synopsis [Computes volume of the cut.]
344 
345  Description []
346 
347  SideEffects []
348 
349  SeeAlso []
350 
351 ***********************************************************************/
352 void Llb_ManCutNodes_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vNodes )
353 {
354  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
355  return;
356  Aig_ObjSetTravIdCurrent(p, pObj);
357  assert( Aig_ObjIsNode(pObj) );
358  Llb_ManCutNodes_rec(p, Aig_ObjFanin0(pObj), vNodes);
359  Llb_ManCutNodes_rec(p, Aig_ObjFanin1(pObj), vNodes);
360  Vec_PtrPush( vNodes, pObj );
361 }
362 
363 /**Function*************************************************************
364 
365  Synopsis [Computes volume of the cut.]
366 
367  Description []
368 
369  SideEffects []
370 
371  SeeAlso []
372 
373 ***********************************************************************/
374 Vec_Ptr_t * Llb_ManCutNodes( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
375 {
376  Vec_Ptr_t * vNodes;
377  Aig_Obj_t * pObj;
378  int i;
379  // mark the lower cut with the traversal ID
380  Aig_ManIncrementTravId(p);
381  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
382  Aig_ObjSetTravIdCurrent( p, pObj );
383  // count the upper cut
384  vNodes = Vec_PtrAlloc( 100 );
385  Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
386  Llb_ManCutNodes_rec( p, pObj, vNodes );
387  return vNodes;
388 }
389 
390 /**Function*************************************************************
391 
392  Synopsis [Computes volume of the cut.]
393 
394  Description []
395 
396  SideEffects []
397 
398  SeeAlso []
399 
400 ***********************************************************************/
401 Vec_Ptr_t * Llb_ManCutSupp( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
402 {
403  Vec_Ptr_t * vNodes, * vSupp;
404  Aig_Obj_t * pObj;
405  int i;
406  vNodes = Llb_ManCutNodes( p, vLower, vUpper );
407  // mark support of the nodes
408  Aig_ManIncrementTravId(p);
409  Vec_PtrForEachEntry( Aig_Obj_t *, vNodes, pObj, i )
410  {
411  assert( Aig_ObjIsNode(pObj) );
412  Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin0(pObj) );
413  Aig_ObjSetTravIdCurrent( p, Aig_ObjFanin1(pObj) );
414  }
415  Vec_PtrFree( vNodes );
416  // collect the support nodes
417  vSupp = Vec_PtrAlloc( 100 );
418  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
419  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
420  Vec_PtrPush( vSupp, pObj );
421  return vSupp;
422 
423 }
424 
425 /**Function*************************************************************
426 
427  Synopsis [Computes volume of the cut.]
428 
429  Description []
430 
431  SideEffects []
432 
433  SeeAlso []
434 
435 ***********************************************************************/
436 Vec_Ptr_t * Llb_ManCutRange( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
437 {
438  Vec_Ptr_t * vRange;
439  Aig_Obj_t * pObj;
440  int i;
441  // mark the lower cut with the traversal ID
442  Aig_ManIncrementTravId(p);
443  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
444  Aig_ObjSetTravIdCurrent( p, pObj );
445  // collect the upper ones that are not marked
446  vRange = Vec_PtrAlloc( 100 );
447  Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
448  if ( !Aig_ObjIsTravIdCurrent(p, pObj) )
449  Vec_PtrPush( vRange, pObj );
450  return vRange;
451 }
452 
453 
454 
455 
456 /**Function*************************************************************
457 
458  Synopsis [Prints the given cluster.]
459 
460  Description []
461 
462  SideEffects []
463 
464  SeeAlso []
465 
466 ***********************************************************************/
467 void Llb_ManCutPrint( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
468 {
469  Vec_Ptr_t * vSupp, * vRange;
470  int Pis, Ffs, And;
471 
472  Pis = Llb_ManCutPiNum(p, vLower);
473  Ffs = Llb_ManCutLoNum(p, vLower);
474  And = Vec_PtrSize(vLower) - Pis - Ffs;
475  printf( "Leaf: %3d=%3d+%3d+%3d ", Vec_PtrSize(vLower), Pis, Ffs, And );
476 
477  Pis = Llb_ManCutPiNum(p, vUpper);
478  Ffs = Llb_ManCutLiNum(p, vUpper);
479  And = Vec_PtrSize(vUpper) - Pis - Ffs;
480  printf( "Root: %3d=%3d+%3d+%3d ", Vec_PtrSize(vUpper), Pis, Ffs, And );
481 
482  vSupp = Llb_ManCutSupp( p, vLower, vUpper );
483  Pis = Llb_ManCutPiNum(p, vSupp);
484  Ffs = Llb_ManCutLoNum(p, vSupp);
485  And = Vec_PtrSize(vSupp) - Pis - Ffs;
486  printf( "Supp: %3d=%3d+%3d+%3d ", Vec_PtrSize(vSupp), Pis, Ffs, And );
487 
488  vRange = Llb_ManCutRange( p, vLower, vUpper );
489  Pis = Llb_ManCutPiNum(p, vRange);
490  Ffs = Llb_ManCutLiNum(p, vRange);
491  And = Vec_PtrSize(vRange) - Pis - Ffs;
492  printf( "Range: %3d=%3d+%3d+%3d ", Vec_PtrSize(vRange), Pis, Ffs, And );
493 
494  printf( "S =%3d. V =%3d.\n",
495  Vec_PtrSize(vSupp)+Vec_PtrSize(vRange), Llb_ManCutVolume(p, vLower, vUpper) );
496  Vec_PtrFree( vSupp );
497  Vec_PtrFree( vRange );
498 /*
499  {
500  Aig_Obj_t * pObj;
501  int i;
502  printf( "Lower: " );
503  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
504  printf( " %d", pObj->Id );
505  printf( " " );
506  printf( "Upper: " );
507  Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
508  printf( " %d", pObj->Id );
509  printf( "\n" );
510  }
511 */
512 }
513 
514 /**Function*************************************************************
515 
516  Synopsis [Prints the given cluster.]
517 
518  Description []
519 
520  SideEffects []
521 
522  SeeAlso []
523 
524 ***********************************************************************/
525 void Llb_ManResultPrint( Aig_Man_t * p, Vec_Ptr_t * vResult )
526 {
527  Vec_Ptr_t * vLower, * vUpper = NULL;
528  int i;
529  Vec_PtrForEachEntryReverse( Vec_Ptr_t *, vResult, vLower, i )
530  {
531  if ( i < Vec_PtrSize(vResult) - 1 )
532  Llb_ManCutPrint( p, vLower, vUpper );
533  vUpper = vLower;
534  }
535 }
536 
537 /**Function*************************************************************
538 
539  Synopsis [Tries to find an augmenting path originating in this node.]
540 
541  Description [This procedure works for directed graphs only!]
542 
543  SideEffects []
544 
545  SeeAlso []
546 
547 ***********************************************************************/
548 int Llb_ManFlowBwdPath2_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
549 {
550  Aig_Obj_t * pFanout;
551  assert( Aig_ObjIsNode(pObj) || Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) );
552  // skip visited nodes
553  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
554  return 0;
555  Aig_ObjSetTravIdCurrent(p, pObj);
556  // process node without flow
557  if ( !Llb_ObjGetPath(pObj) )
558  {
559  // start the path if we reached a terminal node
560  if ( pObj->fMarkA )
561  return Llb_ObjSetPath( pObj, (Aig_Obj_t *)1 );
562  // explore the fanins
563 // Abc_ObjForEachFanin( pObj, pFanin, i )
564 // if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
565 // return Abc_ObjSetPath( pObj, pFanin );
566  if ( Aig_ObjIsNode(pObj) )
567  {
568  if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) ) )
569  return Llb_ObjSetPath( pObj, Aig_ObjFanin0(pObj) );
570  if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) ) )
571  return Llb_ObjSetPath( pObj, Aig_ObjFanin1(pObj) );
572  }
573  return 0;
574  }
575  // pObj has flow - find the fanout with flow
576  pFanout = Llb_ObjGetFanoutPath( p, pObj );
577  if ( pFanout == NULL )
578  return 0;
579  // go through the fanins of the fanout with flow
580 // Abc_ObjForEachFanin( pFanout, pFanin, i )
581 // if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) )
582 // return Abc_ObjSetPath( pFanout, pFanin );
583  assert( Aig_ObjIsNode(pFanout) );
584  if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pFanout) ) )
585  return Llb_ObjSetPath( pFanout, Aig_ObjFanin0(pFanout) );
586  if ( Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pFanout) ) )
587  return Llb_ObjSetPath( pFanout, Aig_ObjFanin1(pFanout) );
588  // try the fanout
589  if ( Llb_ManFlowBwdPath2_rec( p, pFanout ) )
590  return Llb_ObjSetPath( pFanout, NULL );
591  return 0;
592 }
593 
594 
595 /**Function*************************************************************
596 
597  Synopsis [Cleans markB.]
598 
599  Description []
600 
601  SideEffects []
602 
603  SeeAlso []
604 
605 ***********************************************************************/
606 void Llb_ManFlowLabelTfi_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
607 {
608  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
609  return;
610  Aig_ObjSetTravIdCurrent(p, pObj);
611  if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
612  return;
613  assert( Aig_ObjIsNode(pObj) );
614  Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin0(pObj) );
615  Llb_ManFlowLabelTfi_rec( p, Aig_ObjFanin1(pObj) );
616 }
617 
618 /**Function*************************************************************
619 
620  Synopsis []
621 
622  Description []
623 
624  SideEffects []
625 
626  SeeAlso []
627 
628 ***********************************************************************/
629 void Llb_ManFlowUpdateCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
630 {
631  Aig_Obj_t * pObj;
632  int i;
633  // label the TFI of the cut nodes
634  Aig_ManIncrementTravId(p);
635  Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
636  Llb_ManFlowLabelTfi_rec( p, pObj );
637  // collect labeled fanins of non-labeled nodes
638  Vec_PtrClear( vMinCut );
639  Aig_ManIncrementTravId(p);
640  Aig_ManForEachObj( p, pObj, i )
641  {
642  if ( !Aig_ObjIsCo(pObj) && !Aig_ObjIsNode(pObj) )
643  continue;
644  if ( Aig_ObjIsTravIdCurrent(p, pObj) || Aig_ObjIsTravIdPrevious(p, pObj) )
645  continue;
646  if ( Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin0(pObj)) )
647  {
648  Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin0(pObj));
649  Vec_PtrPush( vMinCut, Aig_ObjFanin0(pObj) );
650  }
651  if ( Aig_ObjIsNode(pObj) && Aig_ObjIsTravIdPrevious(p, Aig_ObjFanin1(pObj)) )
652  {
653  Aig_ObjSetTravIdCurrent(p, Aig_ObjFanin1(pObj));
654  Vec_PtrPush( vMinCut, Aig_ObjFanin1(pObj) );
655  }
656  }
657 }
658 
659 /**Function*************************************************************
660 
661  Synopsis [Find minimum-volume minumum cut.]
662 
663  Description []
664 
665  SideEffects []
666 
667  SeeAlso []
668 
669 ***********************************************************************/
670 Vec_Ptr_t * Llb_ManFlowMinCut( Aig_Man_t * p )
671 {
672  Vec_Ptr_t * vMinCut;
673  Aig_Obj_t * pObj;
674  int i;
675  // collect the cut nodes
676  vMinCut = Vec_PtrAlloc( Aig_ManRegNum(p) );
677  Aig_ManForEachObj( p, pObj, i )
678  {
679  // node without flow is not a cut node
680  if ( !Llb_ObjGetPath(pObj) )
681  continue;
682  // unvisited node is below the cut
683  if ( !Aig_ObjIsTravIdCurrent(p, pObj) )
684  continue;
685  // add terminal with flow or node whose path is not visited
686  if ( pObj->fMarkA || !Aig_ObjIsTravIdCurrent( p, Llb_ObjGetPath(pObj) ) )
687  Vec_PtrPush( vMinCut, pObj );
688  }
689  return vMinCut;
690 }
691 
692 /**Function*************************************************************
693 
694  Synopsis [Verifies the min-cut is indeed a cut.]
695 
696  Description []
697 
698  SideEffects []
699 
700  SeeAlso []
701 
702 ***********************************************************************/
703 int Llb_ManFlowVerifyCut_rec( Aig_Man_t * p, Aig_Obj_t * pObj )
704 {
705  // skip visited nodes
706  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
707  return 1;
708  Aig_ObjSetTravIdCurrent(p, pObj);
709  // visit the node
710  if ( Aig_ObjIsConst1(pObj) )
711  return 1;
712  if ( Aig_ObjIsCi(pObj) )
713  return 0;
714  // explore the fanins
715  assert( Aig_ObjIsNode(pObj) );
716  if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin0(pObj)) )
717  return 0;
718  if ( !Llb_ManFlowVerifyCut_rec(p, Aig_ObjFanin1(pObj)) )
719  return 0;
720  return 1;
721 }
722 
723 /**Function*************************************************************
724 
725  Synopsis [Verifies the min-cut is indeed a cut.]
726 
727  Description []
728 
729  SideEffects []
730 
731  SeeAlso []
732 
733 ***********************************************************************/
734 int Llb_ManFlowVerifyCut( Aig_Man_t * p, Vec_Ptr_t * vMinCut )
735 {
736  Aig_Obj_t * pObj;
737  int i;
738  // mark the cut with the current traversal ID
739  Aig_ManIncrementTravId(p);
740  Vec_PtrForEachEntry( Aig_Obj_t *, vMinCut, pObj, i )
741  Aig_ObjSetTravIdCurrent( p, pObj );
742  // search from the latches for a path to the COs/CIs
743  Saig_ManForEachLi( p, pObj, i )
744  {
745  if ( !Llb_ManFlowVerifyCut_rec( p, Aig_ObjFanin0(pObj) ) )
746  return 0;
747  }
748  return 1;
749 }
750 
751 /**Function*************************************************************
752 
753  Synopsis [Implementation of max-flow/min-cut computation.]
754 
755  Description []
756 
757  SideEffects []
758 
759  SeeAlso []
760 
761 ***********************************************************************/
762 Vec_Ptr_t * Llb_ManFlow( Aig_Man_t * p, Vec_Ptr_t * vSources, int * pnFlow )
763 {
764  Vec_Ptr_t * vMinCut;
765  Aig_Obj_t * pObj;
766  int Flow, FlowCur, RetValue, i;
767  // find the max-flow
768  Flow = 0;
769  Aig_ManCleanData( p );
770  Aig_ManIncrementTravId(p);
771  Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i )
772  {
773  assert( !pObj->fMarkA && pObj->fMarkB );
774  if ( !Aig_ObjFanin0(pObj)->fMarkB )
775  {
776  FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
777  Flow += FlowCur;
778  if ( FlowCur )
779  Aig_ManIncrementTravId(p);
780  }
781  if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
782  {
783  FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
784  Flow += FlowCur;
785  if ( FlowCur )
786  Aig_ManIncrementTravId(p);
787  }
788  }
789  if ( pnFlow )
790  *pnFlow = Flow;
791 
792  // mark the nodes reachable from the latches
793  Aig_ManIncrementTravId(p);
794  Vec_PtrForEachEntry( Aig_Obj_t *, vSources, pObj, i )
795  {
796  assert( !pObj->fMarkA && pObj->fMarkB );
797  if ( !Aig_ObjFanin0(pObj)->fMarkB )
798  {
799  RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
800  assert( RetValue == 0 );
801  }
802  if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
803  {
804  RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
805  assert( RetValue == 0 );
806  }
807  }
808 
809  // find the min-cut with the smallest volume
810  vMinCut = Llb_ManFlowMinCut( p );
811  assert( Vec_PtrSize(vMinCut) == Flow );
812  // verify the cut
813  if ( !Llb_ManFlowVerifyCut(p, vMinCut) )
814  printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" );
815 // Llb_ManFlowPrintCut( p, vMinCut );
816  return vMinCut;
817 }
818 
819 /**Function*************************************************************
820 
821  Synopsis [Implementation of max-flow/min-cut computation.]
822 
823  Description []
824 
825  SideEffects []
826 
827  SeeAlso []
828 
829 ***********************************************************************/
830 Vec_Ptr_t * Llb_ManFlowCompute( Aig_Man_t * p )
831 {
832  Vec_Ptr_t * vMinCut;
833  Aig_Obj_t * pObj;
834  int Flow, FlowCur, RetValue, i;
835  // find the max-flow
836  Flow = 0;
837  Aig_ManCleanData( p );
838  Aig_ManIncrementTravId(p);
839  Aig_ManForEachObj( p, pObj, i )
840  {
841  if ( !pObj->fMarkB )
842  continue;
843  assert( !pObj->fMarkA );
844  if ( !Aig_ObjFanin0(pObj)->fMarkB )
845  {
846 //printf( "%d ", Aig_ObjFanin0(pObj)->Id );
847  FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
848  Flow += FlowCur;
849  if ( FlowCur )
850  Aig_ManIncrementTravId(p);
851  }
852  if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
853  {
854 //printf( "%d ", Aig_ObjFanin1(pObj)->Id );
855  FlowCur = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
856  Flow += FlowCur;
857  if ( FlowCur )
858  Aig_ManIncrementTravId(p);
859  }
860  }
861 //printf( "\n" );
862 
863  // mark the nodes reachable from the latches
864  Aig_ManIncrementTravId(p);
865  Aig_ManForEachObj( p, pObj, i )
866  {
867  if ( !pObj->fMarkB )
868  continue;
869  assert( !pObj->fMarkA );
870  if ( !Aig_ObjFanin0(pObj)->fMarkB )
871  {
872  RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin0(pObj) );
873  assert( RetValue == 0 );
874  }
875  if ( Aig_ObjIsNode(pObj) && !Aig_ObjFanin1(pObj)->fMarkB )
876  {
877  RetValue = Llb_ManFlowBwdPath2_rec( p, Aig_ObjFanin1(pObj) );
878  assert( RetValue == 0 );
879  }
880  }
881  // find the min-cut with the smallest volume
882  vMinCut = Llb_ManFlowMinCut( p );
883  assert( Vec_PtrSize(vMinCut) == Flow );
884 //printf( "%d ", Vec_PtrSize(vMinCut) );
885  Llb_ManFlowUpdateCut( p, vMinCut );
886 //printf( "%d ", Vec_PtrSize(vMinCut) );
887  // verify the cut
888  if ( !Llb_ManFlowVerifyCut(p, vMinCut) )
889  printf( "Llb_ManFlow() error! The computed min-cut is not a cut!\n" );
890 // Llb_ManFlowPrintCut( p, vMinCut );
891  return vMinCut;
892 }
893 
894 
895 
896 
897 /**Function*************************************************************
898 
899  Synopsis [Cleans markB.]
900 
901  Description []
902 
903  SideEffects []
904 
905  SeeAlso []
906 
907 ***********************************************************************/
908 void Llb_ManFlowCleanMarkB_rec( Aig_Obj_t * pObj )
909 {
910  if ( pObj->fMarkB == 0 )
911  return;
912  pObj->fMarkB = 0;
913  assert( Aig_ObjIsNode(pObj) );
914  Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin0(pObj) );
915  Llb_ManFlowCleanMarkB_rec( Aig_ObjFanin1(pObj) );
916 }
917 
918 /**Function*************************************************************
919 
920  Synopsis [Cleans markB.]
921 
922  Description []
923 
924  SideEffects []
925 
926  SeeAlso []
927 
928 ***********************************************************************/
929 void Llb_ManFlowSetMarkA_rec( Aig_Obj_t * pObj )
930 {
931  if ( pObj->fMarkA )
932  return;
933  pObj->fMarkA = 1;
934  if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
935  return;
936  assert( Aig_ObjIsNode(pObj) );
937  Llb_ManFlowSetMarkA_rec( Aig_ObjFanin0(pObj) );
938  Llb_ManFlowSetMarkA_rec( Aig_ObjFanin1(pObj) );
939 }
940 
941 /**Function*************************************************************
942 
943  Synopsis [Prepares flow computation.]
944 
945  Description []
946 
947  SideEffects []
948 
949  SeeAlso []
950 
951 ***********************************************************************/
952 void Llb_ManFlowPrepareCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper )
953 {
954  Aig_Obj_t * pObj;
955  int i;
956  // reset marks
957  Aig_ManForEachObj( p, pObj, i )
958  {
959  pObj->fMarkA = 0;
960  pObj->fMarkB = 1;
961  }
962  // clean PIs and const
963  Aig_ManConst1(p)->fMarkB = 0;
964  Aig_ManForEachCi( p, pObj, i )
965  pObj->fMarkB = 0;
966  // clean upper cut
967 //printf( "Upper: ");
968  Vec_PtrForEachEntry( Aig_Obj_t *, vUpper, pObj, i )
969  {
970  Llb_ManFlowCleanMarkB_rec( pObj );
971 //printf( "%d ", pObj->Id );
972  }
973 //printf( "\n" );
974  // set lower cut
975 //printf( "Lower: ");
976  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
977  {
978 //printf( "%d ", pObj->Id );
979  assert( pObj->fMarkB == 0 );
980  Llb_ManFlowSetMarkA_rec( pObj );
981  }
982 //printf( "\n" );
983 }
984 
985 /**Function*************************************************************
986 
987  Synopsis [Prepares flow computation.]
988 
989  Description []
990 
991  SideEffects []
992 
993  SeeAlso []
994 
995 ***********************************************************************/
996 void Llb_ManFlowUnmarkCone( Aig_Man_t * p, Vec_Ptr_t * vCone )
997 {
998  Aig_Obj_t * pObj;
999  int i;
1000  Vec_PtrForEachEntry( Aig_Obj_t *, vCone, pObj, i )
1001  {
1002  assert( Aig_ObjIsNode(pObj) );
1003  assert( pObj->fMarkB == 1 );
1004  pObj->fMarkB = 0;
1005  }
1006 }
1007 
1008 /**Function*************************************************************
1009 
1010  Synopsis []
1011 
1012  Description []
1013 
1014  SideEffects []
1015 
1016  SeeAlso []
1017 
1018 ***********************************************************************/
1019 void Llb_ManFlowCollectAndMarkCone_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Ptr_t * vCone )
1020 {
1021  Aig_Obj_t * pFanout;
1022  int i, iFanout = -1;
1023  if ( Saig_ObjIsLi(p, pObj) )
1024  return;
1025  if ( pObj->fMarkB )
1026  return;
1027  if ( pObj->fMarkA == 0 )
1028  {
1029  assert( Aig_ObjIsNode(pObj) );
1030  pObj->fMarkB = 1;
1031  if ( Aig_ObjIsNode(pObj) )
1032  Vec_PtrPush( vCone, pObj );
1033  }
1034  Aig_ObjForEachFanout( p, pObj, pFanout, iFanout, i )
1035  Llb_ManFlowCollectAndMarkCone_rec( p, pFanout, vCone );
1036 }
1037 
1038 /**Function*************************************************************
1039 
1040  Synopsis [Collects the cone.]
1041 
1042  Description []
1043 
1044  SideEffects []
1045 
1046  SeeAlso []
1047 
1048 ***********************************************************************/
1049 void Llb_ManFlowCollectAndMarkCone( Aig_Man_t * p, Vec_Ptr_t * vStarts, Vec_Ptr_t * vCone )
1050 {
1051  Aig_Obj_t * pObj;
1052  int i;
1053  Vec_PtrClear( vCone );
1054  Vec_PtrForEachEntry( Aig_Obj_t *, vStarts, pObj, i )
1055  {
1056  assert( pObj->fMarkA && !pObj->fMarkB );
1057  Llb_ManFlowCollectAndMarkCone_rec( p, pObj, vCone );
1058  }
1059 }
1060 
1061 
1062 
1063 
1064 /**Function*************************************************************
1065 
1066  Synopsis [Finds balanced cut.]
1067 
1068  Description []
1069 
1070  SideEffects []
1071 
1072  SeeAlso []
1073 
1074 ***********************************************************************/
1075 Vec_Ptr_t * Llb_ManComputeCutLo( Aig_Man_t * p )
1076 {
1077  Vec_Ptr_t * vMinCut;
1078  Aig_Obj_t * pObj;
1079  int i;
1080  vMinCut = Vec_PtrAlloc( 100 );
1081  Aig_ManForEachCi( p, pObj, i )
1082  Vec_PtrPush( vMinCut, pObj );
1083  return vMinCut;
1084 }
1085 
1086 /**Function*************************************************************
1087 
1088  Synopsis [Finds balanced cut.]
1089 
1090  Description []
1091 
1092  SideEffects []
1093 
1094  SeeAlso []
1095 
1096 ***********************************************************************/
1097 Vec_Ptr_t * Llb_ManComputeCutLi( Aig_Man_t * p )
1098 {
1099  Vec_Ptr_t * vMinCut;
1100  Aig_Obj_t * pObj;
1101  int i;
1102  assert( Saig_ManPoNum(p) == 0 );
1103  vMinCut = Vec_PtrAlloc( 100 );
1104  Aig_ManIncrementTravId(p);
1105  Saig_ManForEachLi( p, pObj, i )
1106  {
1107  pObj = Aig_ObjFanin0(pObj);
1108  if ( Aig_ObjIsConst1(pObj) )
1109  continue;
1110  if ( Aig_ObjIsTravIdCurrent(p, pObj) )
1111  continue;
1112  Aig_ObjSetTravIdCurrent(p, pObj);
1113  Vec_PtrPush( vMinCut, pObj );
1114  }
1115  return vMinCut;
1116 }
1117 
1118 
1119 
1120 /**Function*************************************************************
1121 
1122  Synopsis [Finds balanced cut.]
1123 
1124  Description []
1125 
1126  SideEffects []
1127 
1128  SeeAlso []
1129 
1130 ***********************************************************************/
1131 void Llb_ManFlowGetObjSet( Aig_Man_t * p, Vec_Ptr_t * vLower, int iStart, int nSize, Vec_Ptr_t * vSet )
1132 {
1133  Aig_Obj_t * pObj;
1134  int i;
1135  Vec_PtrClear( vSet );
1136  for ( i = 0; i < nSize; i++ )
1137  {
1138  pObj = (Aig_Obj_t *)Vec_PtrEntry( vLower, (iStart + i) % Vec_PtrSize(vLower) );
1139  Vec_PtrPush( vSet, pObj );
1140  }
1141 }
1142 
1143 /**Function*************************************************************
1144 
1145  Synopsis [Finds balanced cut.]
1146 
1147  Description []
1148 
1149  SideEffects []
1150 
1151  SeeAlso []
1152 
1153 ***********************************************************************/
1154 Vec_Ptr_t * Llb_ManFlowFindBestCut( Aig_Man_t * p, Vec_Ptr_t * vLower, Vec_Ptr_t * vUpper, int Num )
1155 {
1156  int nVolMin = Aig_ManNodeNum(p) / Num / 2;
1157  Vec_Ptr_t * vMinCut;
1158  Vec_Ptr_t * vCone, * vSet;
1159  Aig_Obj_t * pObj;
1160  int i, s, Vol, VolLower, VolUpper, VolCmp;
1161  int iBest = -1, iMinCut = ABC_INFINITY, iVolBest = 0;
1162 
1163  Vol = Llb_ManCutVolume( p, vLower, vUpper );
1164  assert( Vol > nVolMin );
1165  VolCmp = Abc_MinInt( nVolMin, Vol - nVolMin );
1166  vCone = Vec_PtrAlloc( 100 );
1167  vSet = Vec_PtrAlloc( 100 );
1168  Llb_ManFlowPrepareCut( p, vLower, vUpper );
1169  for ( s = 1; s < Aig_ManRegNum(p); s += 5 )
1170  {
1171  Vec_PtrForEachEntry( Aig_Obj_t *, vLower, pObj, i )
1172  {
1173  Llb_ManFlowGetObjSet( p, vLower, i, s, vSet );
1174  Llb_ManFlowCollectAndMarkCone( p, vSet, vCone );
1175  if ( Vec_PtrSize(vCone) == 0 )
1176  continue;
1177  vMinCut = Llb_ManFlowCompute( p );
1178  Llb_ManFlowUnmarkCone( p, vCone );
1179 
1180  VolLower = Llb_ManCutVolume( p, vLower, vMinCut );
1181  VolUpper = Llb_ManCutVolume( p, vMinCut, vUpper );
1182  Vol = Abc_MinInt( VolLower, VolUpper );
1183  if ( Vol >= VolCmp && (iMinCut == -1 ||
1184  iMinCut > Vec_PtrSize(vMinCut) ||
1185  (iMinCut == Vec_PtrSize(vMinCut) && iVolBest < Vol)) )
1186  {
1187  iBest = i;
1188  iMinCut = Vec_PtrSize(vMinCut);
1189  iVolBest = Vol;
1190  }
1191  Vec_PtrFree( vMinCut );
1192  }
1193  if ( iBest >= 0 )
1194  break;
1195  }
1196  if ( iBest == -1 )
1197  {
1198  // cleanup
1199  Vec_PtrFree( vCone );
1200  Vec_PtrFree( vSet );
1201  return NULL;
1202  }
1203  // get the best cut
1204  assert( iBest >= 0 );
1205  Llb_ManFlowGetObjSet( p, vLower, iBest, s, vSet );
1206  Llb_ManFlowCollectAndMarkCone( p, vSet, vCone );
1207  vMinCut = Llb_ManFlowCompute( p );
1208  Llb_ManFlowUnmarkCone( p, vCone );
1209  // cleanup
1210  Vec_PtrFree( vCone );
1211  Vec_PtrFree( vSet );
1212  return vMinCut;
1213 }
1214 
1215 /**Function*************************************************************
1216 
1217  Synopsis [Finds balanced cut.]
1218 
1219  Description []
1220 
1221  SideEffects []
1222 
1223  SeeAlso []
1224 
1225 ***********************************************************************/
1226 Vec_Ptr_t * Llb_ManComputeCuts( Aig_Man_t * p, int Num, int fVerbose, int fVeryVerbose )
1227 {
1228  int nVolMax = Aig_ManNodeNum(p) / Num;
1229  Vec_Ptr_t * vResult, * vMinCut = NULL, * vLower, * vUpper;
1230  int i, k, nVol;
1231  abctime clk = Abc_Clock();
1232  vResult = Vec_PtrAlloc( 100 );
1233  Vec_PtrPush( vResult, Llb_ManComputeCutLo(p) );
1234  Vec_PtrPush( vResult, Llb_ManComputeCutLi(p) );
1235  while ( 1 )
1236  {
1237  // find a place to insert new cut
1238  vLower = (Vec_Ptr_t *)Vec_PtrEntry( vResult, 0 );
1239  Vec_PtrForEachEntryStart( Vec_Ptr_t *, vResult, vUpper, i, 1 )
1240  {
1241  nVol = Llb_ManCutVolume( p, vLower, vUpper );
1242  if ( nVol <= nVolMax )
1243  {
1244  vLower = vUpper;
1245  continue;
1246  }
1247 
1248  if ( fVeryVerbose )
1249  Llb_ManCutPrint( p, vLower, vUpper );
1250  vMinCut = Llb_ManFlowFindBestCut( p, vLower, vUpper, Num );
1251  if ( vMinCut == NULL )
1252  {
1253  if ( fVeryVerbose )
1254  printf( "Could not break the cut.\n" );
1255  if ( fVeryVerbose )
1256  printf( "\n" );
1257  vLower = vUpper;
1258  continue;
1259  }
1260 
1261  if ( fVeryVerbose )
1262  Llb_ManCutPrint( p, vMinCut, vUpper );
1263  if ( fVeryVerbose )
1264  Llb_ManCutPrint( p, vLower, vMinCut );
1265  if ( fVeryVerbose )
1266  printf( "\n" );
1267 
1268  break;
1269  }
1270  if ( i == Vec_PtrSize(vResult) )
1271  break;
1272  // insert vMinCut before vUpper
1273  Vec_PtrPush( vResult, NULL );
1274  for ( k = Vec_PtrSize(vResult) - 1; k > i; k-- )
1275  Vec_PtrWriteEntry( vResult, k, Vec_PtrEntry(vResult, k-1) );
1276  Vec_PtrWriteEntry( vResult, i, vMinCut );
1277  }
1278  if ( fVerbose )
1279  {
1280  printf( "Finished computing %d partitions. ", Vec_PtrSize(vResult) - 1 );
1281  Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
1282  Llb_ManResultPrint( p, vResult );
1283  }
1284  return vResult;
1285 }
1286 
1287 /**Function*************************************************************
1288 
1289  Synopsis []
1290 
1291  Description []
1292 
1293  SideEffects []
1294 
1295  SeeAlso []
1296 
1297 ***********************************************************************/
1298 void Llb_BddSetDefaultParams( Gia_ParLlb_t * p )
1299 {
1300  memset( p, 0, sizeof(Gia_ParLlb_t) );
1301  p->nBddMax = 1000000;
1302  p->nIterMax = 10000000;
1303  p->nClusterMax = 20;
1304  p->nHintDepth = 0;
1305  p->HintFirst = 0;
1306  p->fUseFlow = 0; // use flow
1307  p->nVolumeMax = 100; // max volume
1308  p->nVolumeMin = 30; // min volume
1309  p->fReorder = 1;
1310  p->fIndConstr = 0;
1311  p->fUsePivots = 0;
1312  p->fCluster = 0;
1313  p->fSchedule = 0;
1314  p->fVerbose = 0;
1315  p->fVeryVerbose = 0;
1316  p->fSilent = 0;
1317  p->TimeLimit = 0;
1318 // p->TimeLimit = 0;
1319  p->TimeLimitGlo = 0;
1320  p->TimeTarget = 0;
1321  p->iFrame = -1;
1322 }
1323 
1324 /**Function*************************************************************
1325 
1326  Synopsis [Finds balanced cut.]
1327 
1328  Description []
1329 
1330  SideEffects []
1331 
1332  SeeAlso []
1333 
1334 ***********************************************************************/
1335 void Llb_ManMinCutTest( Aig_Man_t * pAig, int Num )
1336 {
1337  extern void Llb_BddConstructTest( Aig_Man_t * p, Vec_Ptr_t * vResult );
1338  extern void Llb_BddExperiment( Aig_Man_t * pInit, Aig_Man_t * pAig, Gia_ParLlb_t * pPars, Vec_Ptr_t * vResult, Vec_Ptr_t * vMaps );
1339 
1340 
1341 // int fVerbose = 1;
1342  Gia_ParLlb_t Pars, * pPars = &Pars;
1343  Vec_Ptr_t * vResult;//, * vSupps, * vMaps;
1344  Aig_Man_t * p;
1345 
1346  Llb_BddSetDefaultParams( pPars );
1347 
1348  p = Aig_ManDupFlopsOnly( pAig );
1349 //Aig_ManShow( p, 0, NULL );
1350  Aig_ManPrintStats( pAig );
1351  Aig_ManPrintStats( p );
1352  Aig_ManFanoutStart( p );
1353 
1354  vResult = Llb_ManComputeCuts( p, Num, 1, 0 );
1355 // vSupps = Llb_ManCutSupps( p, vResult );
1356 // vMaps = Llb_ManCutMap( p, vResult, vSupps );
1357 
1358 // Llb_BddExperiment( pAig, p, pPars, vResult, vMaps );
1359  Llb_CoreExperiment( pAig, p, pPars, vResult, 0 );
1360 
1361 // Vec_VecFree( (Vec_Vec_t *)vMaps );
1362 // Vec_VecFree( (Vec_Vec_t *)vSupps );
1363  Vec_VecFree( (Vec_Vec_t *)vResult );
1364 
1365  Aig_ManFanoutStop( p );
1366  Aig_ManCleanMarkAB( p );
1367  Aig_ManStop( p );
1368 }
1369 
1370 ////////////////////////////////////////////////////////////////////////
1371 /// END OF FILE ///
1372 ////////////////////////////////////////////////////////////////////////
1373 
1374 
1375 ABC_NAMESPACE_IMPL_END
1376 
memset
char * memset()
Aig_ObjIsTravIdPrevious
static int Aig_ObjIsTravIdPrevious(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aig.h:296
Aig_ObjForEachFanout
#define Aig_ObjForEachFanout(p, pObj, pFanout, iFan, i)
Definition: aig.h:427
Llb_ObjGetFanoutPath
static Aig_Obj_t * Llb_ObjGetFanoutPath(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: llb2Flow.c:32
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Llb_ManFlowVerifyCut_rec
int Llb_ManFlowVerifyCut_rec(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: llb2Flow.c:703
Vec_PtrForEachEntryStart
#define Vec_PtrForEachEntryStart(Type, vVec, pEntry, i, Start)
Definition: vecPtr.h:57
Llb_ManFlowCompute
Vec_Ptr_t * Llb_ManFlowCompute(Aig_Man_t *p)
Definition: llb2Flow.c:830
Vec_Vec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Vec_t_ Vec_Vec_t
INCLUDES ///.
Definition: vecVec.h:42
Saig_ManPoNum
static int Saig_ManPoNum(Aig_Man_t *p)
Definition: saig.h:74
Saig_ObjIsLo
static int Saig_ObjIsLo(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: saig.h:84
Aig_Man_t
typedefABC_NAMESPACE_HEADER_START struct Aig_Man_t_ Aig_Man_t
INCLUDES ///.
Definition: aig.h:50
Llb_ManCutVolume_rec
int Llb_ManCutVolume_rec(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: llb2Flow.c:305
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Llb_ManFlowPrepareCut
void Llb_ManFlowPrepareCut(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
Definition: llb2Flow.c:952
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Aig_ManStop
void Aig_ManStop(Aig_Man_t *p)
Definition: aigMan.c:187
Vec_PtrForEachEntryReverse
#define Vec_PtrForEachEntryReverse(Type, vVec, pEntry, i)
Definition: vecPtr.h:63
Aig_ObjIsTravIdCurrent
static int Aig_ObjIsTravIdCurrent(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aig.h:295
Llb_ManCutNodes_rec
void Llb_ManCutNodes_rec(Aig_Man_t *p, Aig_Obj_t *pObj, Vec_Ptr_t *vNodes)
Definition: llb2Flow.c:352
Aig_Obj_t_::fMarkB
unsigned int fMarkB
Definition: aig.h:80
Aig_Obj_t_::pData
void * pData
Definition: aig.h:87
Aig_ObjFanin0
static Aig_Obj_t * Aig_ObjFanin0(Aig_Obj_t *pObj)
Definition: aig.h:308
Llb_ManCutLoNum
int Llb_ManCutLoNum(Aig_Man_t *p, Vec_Ptr_t *vMinCut)
Definition: llb2Flow.c:252
Aig_ManPrintStats
void Aig_ManPrintStats(Aig_Man_t *p)
Definition: aigMan.c:379
Llb_BddSetDefaultParams
void Llb_BddSetDefaultParams(Gia_ParLlb_t *p)
Definition: llb2Flow.c:1298
Llb_ManFlowMinCut
Vec_Ptr_t * Llb_ManFlowMinCut(Aig_Man_t *p)
Definition: llb2Flow.c:670
Aig_ManForEachCi
#define Aig_ManForEachCi(p, pObj, i)
ITERATORS ///.
Definition: aig.h:393
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Aig_Obj_t_::fMarkA
unsigned int fMarkA
Definition: aig.h:79
Gia_ParLlb_t
typedefABC_NAMESPACE_HEADER_START struct Gia_ParLlb_t_ Gia_ParLlb_t
INCLUDES ///.
Definition: llb.h:41
Llb_ManFlow
Vec_Ptr_t * Llb_ManFlow(Aig_Man_t *p, Vec_Ptr_t *vSources, int *pnFlow)
Definition: llb2Flow.c:762
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Llb_ManComputeCuts
Vec_Ptr_t * Llb_ManComputeCuts(Aig_Man_t *p, int Num, int fVerbose, int fVeryVerbose)
Definition: llb2Flow.c:1226
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Aig_ObjFanin1
static Aig_Obj_t * Aig_ObjFanin1(Aig_Obj_t *pObj)
Definition: aig.h:309
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Llb_ManFlowVerifyCut
int Llb_ManFlowVerifyCut(Aig_Man_t *p, Vec_Ptr_t *vMinCut)
Definition: llb2Flow.c:734
Vec_VecFree
static void Vec_VecFree(Vec_Vec_t *p)
Definition: vecVec.h:347
Aig_ObjSetTravIdCurrent
static void Aig_ObjSetTravIdCurrent(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: aig.h:293
Aig_ManNodeNum
static int Aig_ManNodeNum(Aig_Man_t *p)
Definition: aig.h:256
Saig_ObjIsLi
static int Saig_ObjIsLi(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: saig.h:85
Llb_ManResultPrint
void Llb_ManResultPrint(Aig_Man_t *p, Vec_Ptr_t *vResult)
Definition: llb2Flow.c:525
Aig_ManFanoutStart
void Aig_ManFanoutStart(Aig_Man_t *p)
FUNCTION DEFINITIONS ///.
Definition: aigFanout.c:56
Llb_ManCutNodes
Vec_Ptr_t * Llb_ManCutNodes(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
DECLARATIONS ///.
Definition: llb2Flow.c:374
Aig_ManFanoutStop
void Aig_ManFanoutStop(Aig_Man_t *p)
Definition: aigFanout.c:89
Llb_ObjSetPath
static ABC_NAMESPACE_IMPL_START int Llb_ObjSetPath(Aig_Obj_t *pObj, Aig_Obj_t *pNext)
DECLARATIONS ///.
Definition: llb2Flow.c:30
Llb_ManCutSupps
Vec_Ptr_t * Llb_ManCutSupps(Aig_Man_t *p, Vec_Ptr_t *vResult)
FUNCTION DEFINITIONS ///.
Definition: llb2Flow.c:61
Aig_ManIncrementTravId
void Aig_ManIncrementTravId(Aig_Man_t *p)
DECLARATIONS ///.
Definition: aigUtil.c:44
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Aig_ObjIsNode
static int Aig_ObjIsNode(Aig_Obj_t *pObj)
Definition: aig.h:280
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Llb_ManCutPiNum
int Llb_ManCutPiNum(Aig_Man_t *p, Vec_Ptr_t *vMinCut)
Definition: llb2Flow.c:231
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
Vec_IntStart
static Vec_Int_t * Vec_IntStart(int nSize)
Definition: bblif.c:172
Llb_ObjGetPath
static Aig_Obj_t * Llb_ObjGetPath(Aig_Obj_t *pObj)
Definition: llb2Flow.c:31
Llb_ManCutPrint
void Llb_ManCutPrint(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
Definition: llb2Flow.c:467
Saig_ManForEachLi
#define Saig_ManForEachLi(p, pObj, i)
Definition: saig.h:98
Llb_ManFlowCollectAndMarkCone_rec
void Llb_ManFlowCollectAndMarkCone_rec(Aig_Man_t *p, Aig_Obj_t *pObj, Vec_Ptr_t *vCone)
Definition: llb2Flow.c:1019
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Aig_ManDupFlopsOnly
Aig_Man_t * Aig_ManDupFlopsOnly(Aig_Man_t *p)
Definition: aigDup.c:871
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Llb_ManFlowCollectAndMarkCone
void Llb_ManFlowCollectAndMarkCone(Aig_Man_t *p, Vec_Ptr_t *vStarts, Vec_Ptr_t *vCone)
Definition: llb2Flow.c:1049
Aig_ObjIsConst1
static int Aig_ObjIsConst1(Aig_Obj_t *pObj)
Definition: aig.h:274
Aig_Obj_t_
Definition: aig.h:69
Llb_ManCutVolume
int Llb_ManCutVolume(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
Definition: llb2Flow.c:326
Counter
static int Counter
Definition: extraBddMisc.c:1877
Llb_ManCutRange
Vec_Ptr_t * Llb_ManCutRange(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
Definition: llb2Flow.c:436
Llb_ManFlowUpdateCut
void Llb_ManFlowUpdateCut(Aig_Man_t *p, Vec_Ptr_t *vMinCut)
Definition: llb2Flow.c:629
Llb_ManCutMap
Vec_Ptr_t * Llb_ManCutMap(Aig_Man_t *p, Vec_Ptr_t *vResult, Vec_Ptr_t *vSupps)
Definition: llb2Flow.c:89
Llb_ManFlowLabelTfi_rec
void Llb_ManFlowLabelTfi_rec(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: llb2Flow.c:606
Llb_ManMinCutTest
void Llb_ManMinCutTest(Aig_Man_t *pAig, int Num)
Definition: llb2Flow.c:1335
Vec_PtrWriteEntry
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
Aig_ManObjNumMax
static int Aig_ManObjNumMax(Aig_Man_t *p)
Definition: aig.h:259
Llb_ManFlowCleanMarkB_rec
void Llb_ManFlowCleanMarkB_rec(Aig_Obj_t *pObj)
Definition: llb2Flow.c:908
Aig_ManConst1
static Aig_Obj_t * Aig_ManConst1(Aig_Man_t *p)
Definition: aig.h:264
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Llb_ManFlowBwdPath2_rec
int Llb_ManFlowBwdPath2_rec(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: llb2Flow.c:548
Aig_ManRegNum
static int Aig_ManRegNum(Aig_Man_t *p)
Definition: aig.h:260
Llb_ManFlowFindBestCut
Vec_Ptr_t * Llb_ManFlowFindBestCut(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper, int Num)
Definition: llb2Flow.c:1154
Llb_ManComputeCutLo
Vec_Ptr_t * Llb_ManComputeCutLo(Aig_Man_t *p)
Definition: llb2Flow.c:1075
Aig_ManForEachObj
#define Aig_ManForEachObj(p, pObj, i)
Definition: aig.h:403
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Llb_CoreExperiment
int Llb_CoreExperiment(Aig_Man_t *pInit, Aig_Man_t *pAig, Gia_ParLlb_t *pPars, Vec_Ptr_t *vResult, abctime TimeTarget)
Definition: llb2Core.c:694
Saig_ManPiNum
static int Saig_ManPiNum(Aig_Man_t *p)
MACRO DEFINITIONS ///.
Definition: saig.h:73
Llb_ManCutLiNum
int Llb_ManCutLiNum(Aig_Man_t *p, Vec_Ptr_t *vMinCut)
Definition: llb2Flow.c:273
Aig_ManCleanMarkAB
void Aig_ManCleanMarkAB(Aig_Man_t *p)
Definition: aigUtil.c:186
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Llb_ManFlowUnmarkCone
void Llb_ManFlowUnmarkCone(Aig_Man_t *p, Vec_Ptr_t *vCone)
Definition: llb2Flow.c:996
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
Llb_ManFlowGetObjSet
void Llb_ManFlowGetObjSet(Aig_Man_t *p, Vec_Ptr_t *vLower, int iStart, int nSize, Vec_Ptr_t *vSet)
Definition: llb2Flow.c:1131
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Llb_ManFlowSetMarkA_rec
void Llb_ManFlowSetMarkA_rec(Aig_Obj_t *pObj)
Definition: llb2Flow.c:929
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Aig_ObjIsCi
static int Aig_ObjIsCi(Aig_Obj_t *pObj)
Definition: aig.h:275
Llb_ManCutSupp
Vec_Ptr_t * Llb_ManCutSupp(Aig_Man_t *p, Vec_Ptr_t *vLower, Vec_Ptr_t *vUpper)
Definition: llb2Flow.c:401
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Llb_ManComputeCutLi
Vec_Ptr_t * Llb_ManComputeCutLi(Aig_Man_t *p)
Definition: llb2Flow.c:1097
Aig_ManCleanData
void Aig_ManCleanData(Aig_Man_t *p)
Definition: aigUtil.c:205
Aig_Obj_t_::Id
int Id
Definition: aig.h:85
Saig_ObjIsPi
static int Saig_ObjIsPi(Aig_Man_t *p, Aig_Obj_t *pObj)
Definition: saig.h:82
Aig_ObjIsCo
static int Aig_ObjIsCo(Aig_Obj_t *pObj)
Definition: aig.h:276
Aig_ObjCioId
static int Aig_ObjCioId(Aig_Obj_t *pObj)
Definition: aig.h:285
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
Saig_ManForEachPi
#define Saig_ManForEachPi(p, pObj, i)
Definition: saig.h:91