ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
retFlow.c
Go to the documentation of this file.
1
20
21#include "retInt.h"
22
23ABC_NAMESPACE_IMPL_START
24
25
29
30static inline int Abc_ObjSetPath( Abc_Obj_t * pObj, Abc_Obj_t * pNext ) { pObj->pCopy = pNext; return 1; }
31static inline Abc_Obj_t * Abc_ObjGetPath( Abc_Obj_t * pObj ) { return pObj->pCopy; }
32static inline Abc_Obj_t * Abc_ObjGetFanoutPath( Abc_Obj_t * pObj )
33{
34 Abc_Obj_t * pFanout;
35 int i;
36 assert( Abc_ObjGetPath(pObj) );
37 Abc_ObjForEachFanout( pObj, pFanout, i )
38 if ( Abc_ObjGetPath(pFanout) == pObj )
39 return pFanout;
40 return NULL;
41}
42static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * pObj )
43{
44 Abc_Obj_t * pFanin;
45 int i;
46 assert( Abc_ObjGetPath(pObj) );
47 Abc_ObjForEachFanin( pObj, pFanin, i )
48 if ( Abc_ObjGetPath(pFanin) == pObj )
49 return pFanin;
50 return NULL;
51}
52static inline Abc_Obj_t * Abc_ObjGetPredecessorBwd( Abc_Obj_t * pObj )
53{
54 Abc_Obj_t * pNext;
55 int i;
56 Abc_ObjForEachFanout( pObj, pNext, i )
57 if ( Abc_ObjGetPath(pNext) == pObj )
58 return pNext;
59 Abc_ObjForEachFanin( pObj, pNext, i )
60 if ( Abc_ObjGetPath(pNext) == pObj )
61 return pNext;
62 return NULL;
63}
64static inline Abc_Obj_t * Abc_ObjGetPredecessorFwd( Abc_Obj_t * pObj )
65{
66 Abc_Obj_t * pNext;
67 int i;
68 Abc_ObjForEachFanin( pObj, pNext, i )
69 if ( Abc_ObjGetPath(pNext) == pObj )
70 return pNext;
71 Abc_ObjForEachFanout( pObj, pNext, i )
72 if ( Abc_ObjGetPath(pNext) == pObj )
73 return pNext;
74 return NULL;
75}
76
77static int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
78static int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
79static int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
80static int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
81//static int Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj );
82static int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin );
83static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward );
84static void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
85static int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
86static void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
87static void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward );
88
92
104void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
105{
106 Vec_Ptr_t * vMinCut;
107 Abc_Obj_t * pObj;
108 int i;
109
110 // forward flow
111 Abc_NtkForEachPo( pNtk, pObj, i )
112 pObj->fMarkA = 1;
113 Abc_NtkForEachLatch( pNtk, pObj, i )
114 pObj->fMarkA = Abc_ObjFanin0(pObj)->fMarkA = 1;
115// Abc_ObjFanin0(pObj)->fMarkA = 1;
116 vMinCut = Abc_NtkMaxFlow( pNtk, 1, 1 );
117 Vec_PtrFree( vMinCut );
118 Abc_NtkCleanMarkA( pNtk );
119
120 // backward flow
121 Abc_NtkForEachPi( pNtk, pObj, i )
122 pObj->fMarkA = 1;
123 Abc_NtkForEachLatch( pNtk, pObj, i )
124 pObj->fMarkA = Abc_ObjFanout0(pObj)->fMarkA = 1;
125// Abc_ObjFanout0(pObj)->fMarkA = 1;
126 vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 );
127 Vec_PtrFree( vMinCut );
128 Abc_NtkCleanMarkA( pNtk );
129
130}
131
143Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
144{
145 Vec_Ptr_t * vMinCut;
146 Abc_Obj_t * pLatch;
147 int Flow, FlowCur, RetValue, i;
148 abctime clk = Abc_Clock();
149 int fUseDirectedFlow = 1;
150
151 // find the max-flow
152 Abc_NtkCleanCopy( pNtk );
153 Flow = 0;
154 Abc_NtkIncrementTravId(pNtk);
155 Abc_NtkForEachLatch( pNtk, pLatch, i )
156 {
157 if ( fForward )
158 {
159// assert( !Abc_ObjFanout0(pLatch)->fMarkA );
160 FlowCur = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
161// FlowCur = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
162 Flow += FlowCur;
163 }
164 else
165 {
166 assert( !Abc_ObjFanin0(pLatch)->fMarkA );
167 FlowCur = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
168 Flow += FlowCur;
169 }
170 if ( FlowCur )
171 Abc_NtkIncrementTravId(pNtk);
172 }
173
174 if ( !fUseDirectedFlow )
175 {
176 Abc_NtkIncrementTravId(pNtk);
177 Abc_NtkForEachLatch( pNtk, pLatch, i )
178 {
179 if ( fForward )
180 {
181 // assert( !Abc_ObjFanout0(pLatch)->fMarkA );
182 FlowCur = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
183 Flow += FlowCur;
184 }
185 else
186 {
187 assert( !Abc_ObjFanin0(pLatch)->fMarkA );
188 FlowCur = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
189 Flow += FlowCur;
190 }
191 if ( FlowCur )
192 Abc_NtkIncrementTravId(pNtk);
193 }
194 }
195// Abc_NtkMaxFlowPrintFlow( pNtk, fForward );
196
197 // mark the nodes reachable from the latches
198 Abc_NtkIncrementTravId(pNtk);
199 Abc_NtkForEachLatch( pNtk, pLatch, i )
200 {
201 if ( fForward )
202 {
203// assert( !Abc_ObjFanout0(pLatch)->fMarkA );
204 if ( fUseDirectedFlow )
205 RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
206// RetValue = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
207 else
208 RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
209 }
210 else
211 {
212 assert( !Abc_ObjFanin0(pLatch)->fMarkA );
213 if ( fUseDirectedFlow )
214 RetValue = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) );
215 else
216 RetValue = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) );
217 }
218 assert( RetValue == 0 );
219 }
220
221 // find the min-cut with the smallest volume
222 vMinCut = Abc_NtkMaxFlowMinCut( pNtk, fForward );
223 // verify the cut
224 if ( !Abc_NtkMaxFlowVerifyCut(pNtk, vMinCut, fForward) )
225 printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" );
226 // make the cut retimable
227 Abc_NtkMaxFlowMinCutUpdate( pNtk, vMinCut, fForward );
228
229 // report the results
230 if ( fVerbose )
231 {
232 printf( "L = %6d. %s max-flow = %6d. Min-cut = %6d. ",
233 Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) );
234ABC_PRT( "Time", Abc_Clock() - clk );
235 }
236
237// Abc_NtkMaxFlowPrintCut( pNtk, vMinCut );
238 return vMinCut;
239}
240
252int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj )
253{
254 Abc_Obj_t * pNext, * pPred;
255 int i;
256 // skip visited nodes
257 if ( Abc_NodeIsTravIdCurrent(pObj) )
258 return 0;
259 Abc_NodeSetTravIdCurrent(pObj);
260 // get the predecessor
261 pPred = Abc_ObjGetPredecessorBwd( pObj );
262 // process node without flow
263 if ( !Abc_ObjGetPath(pObj) )
264 {
265 // start the path if we reached a terminal node
266 if ( pObj->fMarkA )
267 return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
268 // explore the fanins
269 Abc_ObjForEachFanin( pObj, pNext, i )
270 if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
271 return Abc_ObjSetPath( pObj, pNext );
272 Abc_ObjForEachFanout( pObj, pNext, i )
273 if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) )
274 return Abc_ObjSetPath( pObj, pNext );
275 return 0;
276 }
277 // pObj has flow - find the fanout with flow
278 if ( pPred == NULL )
279 return 0;
280 // go through the successors of the predecessor
281 Abc_ObjForEachFanin( pPred, pNext, i )
282 if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
283 return Abc_ObjSetPath( pPred, pNext );
284 Abc_ObjForEachFanout( pPred, pNext, i )
285 if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) )
286 return Abc_ObjSetPath( pPred, pNext );
287 // try the fanout
288 if ( Abc_NtkMaxFlowBwdPath_rec( pPred ) )
289 return Abc_ObjSetPath( pPred, NULL );
290 return 0;
291}
292
304int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
305{
306 Abc_Obj_t * pNext, * pPred;
307 int i;
308 // skip visited nodes
309 if ( Abc_NodeIsTravIdCurrent(pObj) )
310 return 0;
311 Abc_NodeSetTravIdCurrent(pObj);
312 // get the predecessor
313 pPred = Abc_ObjGetPredecessorFwd( pObj );
314 // process node without flow
315 if ( !Abc_ObjGetPath(pObj) )
316 {
317 // start the path if we reached a terminal node
318 if ( pObj->fMarkA )
319 return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
320 // explore the fanins
321 Abc_ObjForEachFanout( pObj, pNext, i )
322 if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
323 return Abc_ObjSetPath( pObj, pNext );
324 Abc_ObjForEachFanin( pObj, pNext, i )
325 if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) )
326 return Abc_ObjSetPath( pObj, pNext );
327 return 0;
328 }
329 // pObj has flow - find the fanout with flow
330 if ( pPred == NULL )
331 return 0;
332 // go through the successors of the predecessor
333 Abc_ObjForEachFanout( pPred, pNext, i )
334 if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
335 return Abc_ObjSetPath( pPred, pNext );
336 Abc_ObjForEachFanin( pPred, pNext, i )
337 if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) )
338 return Abc_ObjSetPath( pPred, pNext );
339 // try the fanout
340 if ( Abc_NtkMaxFlowFwdPath_rec( pPred ) )
341 return Abc_ObjSetPath( pPred, NULL );
342 return 0;
343}
344
345
357int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin )
358{
359 Abc_Obj_t * pFanin, * pFanout;
360 int i;
361 // skip visited nodes
362 if ( Abc_NodeIsTravIdCurrent(pObj) )
363 return 0;
364 Abc_NodeSetTravIdCurrent(pObj);
365 // skip the fanin which already has flow
366 if ( fFanin && Abc_ObjGetPath(pPrev) )
367 return 0;
368 // if the node has no flow, try to push through the fanouts
369 if ( !Abc_ObjGetPath(pObj) )
370 {
371 // start the path if we reached a terminal node
372 if ( pObj->fMarkA )
373 return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
374 // try to push flow through the fanouts
375 Abc_ObjForEachFanout( pObj, pFanout, i )
376 if ( Abc_NtkMaxFlowFwdPath3_rec(pFanout, pObj, 1) )
377 return fFanin? Abc_ObjSetPath(pPrev, pObj) : 1;
378 }
379 // try to push through the fanins
380 Abc_ObjForEachFanin( pObj, pFanin, i )
381 if ( !Abc_ObjIsLatch(pFanin) && Abc_NtkMaxFlowFwdPath3_rec(pFanin, pObj, 0) )
382 return Abc_ObjSetPath( pFanin, NULL );
383 return 0;
384}
385
397int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj )
398{
399 Abc_Obj_t * pFanout, * pFanin;
400 int i;
401 // skip visited nodes
402 if ( Abc_NodeIsTravIdCurrent(pObj) )
403 return 0;
404 Abc_NodeSetTravIdCurrent(pObj);
405 // process node without flow
406 if ( !Abc_ObjGetPath(pObj) )
407 {
408 // start the path if we reached a terminal node
409 if ( pObj->fMarkA )
410 return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
411 // explore the fanins
412 Abc_ObjForEachFanin( pObj, pFanin, i )
413 if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) )
414 return Abc_ObjSetPath( pObj, pFanin );
415 return 0;
416 }
417 // pObj has flow - find the fanout with flow
418 pFanout = Abc_ObjGetFanoutPath( pObj );
419 if ( pFanout == NULL )
420 return 0;
421 // go through the fanins of the fanout with flow
422 Abc_ObjForEachFanin( pFanout, pFanin, i )
423 if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) )
424 return Abc_ObjSetPath( pFanout, pFanin );
425 // try the fanout
426 if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) )
427 return Abc_ObjSetPath( pFanout, NULL );
428 return 0;
429}
430
442int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj )
443{
444 Abc_Obj_t * pFanout, * pFanin;
445 int i;
446 // skip visited nodes
447 if ( Abc_NodeIsTravIdCurrent(pObj) )
448 return 0;
449 Abc_NodeSetTravIdCurrent(pObj);
450 // process node without flow
451 if ( !Abc_ObjGetPath(pObj) )
452 {
453 // start the path if we reached a terminal node
454 if ( pObj->fMarkA )
455 return Abc_ObjSetPath( pObj, (Abc_Obj_t *)1 );
456 // explore the fanins
457 Abc_ObjForEachFanout( pObj, pFanout, i )
458 if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) )
459 return Abc_ObjSetPath( pObj, pFanout );
460 return 0;
461 }
462 // pObj has flow - find the fanout with flow
463 pFanin = Abc_ObjGetFaninPath( pObj );
464 if ( pFanin == NULL )
465 return 0;
466 // go through the fanins of the fanout with flow
467 Abc_ObjForEachFanout( pFanin, pFanout, i )
468 if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) )
469 return Abc_ObjSetPath( pFanin, pFanout );
470 // try the fanout
471 if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) )
472 return Abc_ObjSetPath( pFanin, NULL );
473 return 0;
474}
475
487Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward )
488{
489 Vec_Ptr_t * vMinCut;
490 Abc_Obj_t * pObj;
491 int i;
492 // collect the cut nodes
493 vMinCut = Vec_PtrAlloc( Abc_NtkLatchNum(pNtk) );
494 Abc_NtkForEachObj( pNtk, pObj, i )
495 {
496 // node without flow is not a cut node
497 if ( !Abc_ObjGetPath(pObj) )
498 continue;
499 // unvisited node is below the cut
500 if ( !Abc_NodeIsTravIdCurrent(pObj) )
501 continue;
502 // add terminal with flow or node whose path is not visited
503 if ( pObj->fMarkA || !Abc_NodeIsTravIdCurrent( Abc_ObjGetPath(pObj) ) )
504 Vec_PtrPush( vMinCut, pObj );
505 }
506 return vMinCut;
507}
508
520void Abc_NtkMaxFlowMarkCut_rec( Abc_Obj_t * pObj )
521{
522 Abc_Obj_t * pNext;
523 int i;
524 if ( pObj->fMarkA )
525 return;
526 pObj->fMarkA = 1;
527 Abc_ObjForEachFanin( pObj, pNext, i )
528 Abc_NtkMaxFlowMarkCut_rec( pNext );
529}
530
542void Abc_NtkMaxFlowCollectCut_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes )
543{
544 Abc_Obj_t * pNext;
545 int i;
546 if ( Abc_NodeIsTravIdCurrent(pObj) )
547 return;
548 Abc_NodeSetTravIdCurrent(pObj);
549 if ( pObj->fMarkA )
550 {
551 Vec_PtrPush( vNodes, pObj );
552 return;
553 }
554 Abc_ObjForEachFanin( pObj, pNext, i )
555 Abc_NtkMaxFlowCollectCut_rec( pNext, vNodes );
556}
557
570void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
571{
572 Abc_Obj_t * pObj, * pNext;
573 int i, k;
574 // clean marks
575 Abc_NtkForEachObj( pNtk, pObj, i )
576 pObj->fMarkA = 0;
577 // set latch outputs
578 Abc_NtkForEachLatch( pNtk, pObj, i )
579 Abc_ObjFanout0(pObj)->fMarkA = 1;
580 // traverse from cut nodes
581 Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
582 Abc_NtkMaxFlowMarkCut_rec( pObj );
583 if ( fForward )
584 {
585 // change mincut to be nodes with unmarked fanouts
586 Vec_PtrClear( vMinCut );
587 Abc_NtkForEachObj( pNtk, pObj, i )
588 {
589 if ( !pObj->fMarkA )
590 continue;
591 Abc_ObjForEachFanout( pObj, pNext, k )
592 {
593 if ( pNext->fMarkA )
594 continue;
595 Vec_PtrPush( vMinCut, pObj );
596 break;
597 }
598 }
599 }
600 else
601 {
602 // change mincut to be marked fanins of the unmarked nodes
603 Vec_PtrClear( vMinCut );
604 Abc_NtkIncrementTravId(pNtk);
605 Abc_NtkForEachLatch( pNtk, pObj, i )
606 Abc_NtkMaxFlowCollectCut_rec( Abc_ObjFanin0(pObj), vMinCut );
607 // transfer the attribute
608 Abc_NtkForEachObj( pNtk, pObj, i )
609 pObj->fMarkA = Abc_NodeIsTravIdCurrent(pObj);
610 // unmark the cut nodes
611 Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
612 pObj->fMarkA = 0;
613 }
614}
615
627int Abc_NtkMaxFlowVerifyCut_rec( Abc_Obj_t * pObj, int fForward )
628{
629 Abc_Obj_t * pNext;
630 int i;
631 // skip visited nodes
632 if ( Abc_NodeIsTravIdCurrent(pObj) )
633 return 1;
634 Abc_NodeSetTravIdCurrent(pObj);
635 // visit the node
636 if ( fForward )
637 {
638 if ( Abc_ObjIsCo(pObj) )
639 return 0;
640 // explore the fanouts
641 Abc_ObjForEachFanout( pObj, pNext, i )
642 if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
643 return 0;
644 }
645 else
646 {
647 if ( Abc_ObjIsCi(pObj) )
648 return 0;
649 // explore the fanins
650 Abc_ObjForEachFanin( pObj, pNext, i )
651 if ( !Abc_NtkMaxFlowVerifyCut_rec(pNext, fForward) )
652 return 0;
653 }
654 return 1;
655}
656
668int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward )
669{
670 Abc_Obj_t * pObj;
671 int i;
672 // mark the cut with the current traversal ID
673 Abc_NtkIncrementTravId(pNtk);
674 Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
675 Abc_NodeSetTravIdCurrent( pObj );
676 // search from the latches for a path to the COs/CIs
677 Abc_NtkForEachLatch( pNtk, pObj, i )
678 {
679 if ( fForward )
680 {
681 if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) )
682 return 0;
683 }
684 else
685 {
686 if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) )
687 return 0;
688 }
689 }
690/*
691 {
692 // count the volume of the cut
693 int Counter = 0;
694 Abc_NtkForEachObj( pNtk, pObj, i )
695 Counter += Abc_NodeIsTravIdCurrent( pObj );
696 printf( "Volume = %d.\n", Counter );
697 }
698*/
699 return 1;
700}
701
713void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward )
714{
715 Abc_Obj_t * pLatch, * pNext;
716 Abc_Obj_t * pPrev = NULL; // Suppress "might be used uninitialized"
717 int i;
718 if ( fForward )
719 {
720 Vec_PtrForEachEntry( Abc_Obj_t *, pNtk->vBoxes, pLatch, i )
721 {
722 assert( !Abc_ObjFanout0(pLatch)->fMarkA );
723 if ( Abc_ObjGetPath(Abc_ObjFanout0(pLatch)) == NULL ) // no flow through this latch
724 continue;
725 printf( "Path = " );
726 for ( pNext = Abc_ObjFanout0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
727 {
728 printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
729 pPrev = pNext;
730 }
731 if ( !Abc_ObjIsPo(pPrev) )
732 printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanout0(pPrev)), Abc_ObjFanout0(pPrev)->Id );
733 printf( "\n" );
734 }
735 }
736 else
737 {
738 Vec_PtrForEachEntry( Abc_Obj_t *, pNtk->vBoxes, pLatch, i )
739 {
740 assert( !Abc_ObjFanin0(pLatch)->fMarkA );
741 if ( Abc_ObjGetPath(Abc_ObjFanin0(pLatch)) == NULL ) // no flow through this latch
742 continue;
743 printf( "Path = " );
744 for ( pNext = Abc_ObjFanin0(pLatch); pNext != (void *)1; pNext = Abc_ObjGetPath(pNext) )
745 {
746 printf( "%s(%d) ", Abc_ObjName(pNext), pNext->Id );
747 pPrev = pNext;
748 }
749 if ( !Abc_ObjIsPi(pPrev) )
750 printf( "%s(%d) ", Abc_ObjName(Abc_ObjFanin0(pPrev)), Abc_ObjFanin0(pPrev)->Id );
751 printf( "\n" );
752 }
753 }
754}
755
767void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut )
768{
769 Abc_Obj_t * pObj;
770 int i;
771 printf( "Min-cut: " );
772 Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
773 printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
774 printf( "\n" );
775 printf( "Marked nodes: " );
776 Abc_NtkForEachObj( pNtk, pObj, i )
777 if ( pObj->fMarkA )
778 printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id );
779 printf( "\n" );
780}
781
782
786
787
788ABC_NAMESPACE_IMPL_END
789
Abc_Obj_t
struct Abc_Obj_t_ Abc_Obj_t
Definition abc.h:116
Abc_NtkCleanMarkA
ABC_DLL void Abc_NtkCleanMarkA(Abc_Ntk_t *pNtk)
Definition abcUtil.c:696
Abc_NtkForEachPo
#define Abc_NtkForEachPo(pNtk, pPo, i)
Definition abc.h:520
Abc_NtkForEachLatch
#define Abc_NtkForEachLatch(pNtk, pObj, i)
Definition abc.h:500
Abc_NtkForEachObj
#define Abc_NtkForEachObj(pNtk, pObj, i)
ITERATORS ///.
Definition abc.h:449
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition abc.h:527
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition abc.h:529
Abc_ObjName
ABC_DLL char * Abc_ObjName(Abc_Obj_t *pNode)
DECLARATIONS ///.
Definition abcNames.c:49
Abc_Ntk_t
struct Abc_Ntk_t_ Abc_Ntk_t
Definition abc.h:115
Abc_NtkForEachPi
#define Abc_NtkForEachPi(pNtk, pPi, i)
Definition abc.h:516
Abc_NtkCleanCopy
ABC_DLL void Abc_NtkCleanCopy(Abc_Ntk_t *pNtk)
Definition abcUtil.c:540
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_PRT
#define ABC_PRT(a, t)
Definition abc_global.h:255
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Abc_NtkMaxFlowCollectCut_rec
void Abc_NtkMaxFlowCollectCut_rec(Abc_Obj_t *pObj, Vec_Ptr_t *vNodes)
Definition retFlow.c:542
Abc_NtkMaxFlowTest
void Abc_NtkMaxFlowTest(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition retFlow.c:104
Abc_NtkMaxFlowMarkCut_rec
void Abc_NtkMaxFlowMarkCut_rec(Abc_Obj_t *pObj)
Definition retFlow.c:520
Abc_NtkMaxFlow
Vec_Ptr_t * Abc_NtkMaxFlow(Abc_Ntk_t *pNtk, int fForward, int fVerbose)
Definition retFlow.c:143
Abc_NtkMaxFlowVerifyCut_rec
int Abc_NtkMaxFlowVerifyCut_rec(Abc_Obj_t *pObj, int fForward)
Definition retFlow.c:627
Abc_Ntk_t_::vBoxes
Vec_Ptr_t * vBoxes
Definition abc.h:168
Abc_Obj_t_::Id
int Id
Definition abc.h:132
Abc_Obj_t_::pCopy
Abc_Obj_t * pCopy
Definition abc.h:148
Abc_Obj_t_::fMarkA
unsigned fMarkA
Definition abc.h:134
assert
#define assert(ex)
Definition util_old.h:213
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition vecPtr.h:42
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition vecPtr.h:55