1 /**CFile****************************************************************
2
3 FileName [retFlow.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Implementation of maximum flow (min-area retiming).]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - Oct 31, 2006.]
16
17 Revision [$Id: retFlow.c,v 1.00 2006/10/31 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "retInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
Abc_ObjSetPath(Abc_Obj_t * pObj,Abc_Obj_t * pNext)30 static inline int Abc_ObjSetPath( Abc_Obj_t * pObj, Abc_Obj_t * pNext ) { pObj->pCopy = pNext; return 1; }
Abc_ObjGetPath(Abc_Obj_t * pObj)31 static inline Abc_Obj_t * Abc_ObjGetPath( Abc_Obj_t * pObj ) { return pObj->pCopy; }
Abc_ObjGetFanoutPath(Abc_Obj_t * pObj)32 static 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 }
Abc_ObjGetFaninPath(Abc_Obj_t * pObj)42 static 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 }
Abc_ObjGetPredecessorBwd(Abc_Obj_t * pObj)52 static 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 }
Abc_ObjGetPredecessorFwd(Abc_Obj_t * pObj)64 static 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
77 static int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
78 static int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
79 static int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
80 static int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
81 //static int Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj );
82 static int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin );
83 static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward );
84 static void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
85 static int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
86 static void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut );
87 static void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward );
88
89 ////////////////////////////////////////////////////////////////////////
90 /// FUNCTION DEFINITIONS ///
91 ////////////////////////////////////////////////////////////////////////
92
93 /**Function*************************************************************
94
95 Synopsis [Test-bench for the max-flow computation.]
96
97 Description []
98
99 SideEffects []
100
101 SeeAlso []
102
103 ***********************************************************************/
Abc_NtkMaxFlowTest(Abc_Ntk_t * pNtk)104 void 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
132 /**Function*************************************************************
133
134 Synopsis [Implementation of max-flow/min-cut computation.]
135
136 Description []
137
138 SideEffects []
139
140 SeeAlso []
141
142 ***********************************************************************/
Abc_NtkMaxFlow(Abc_Ntk_t * pNtk,int fForward,int fVerbose)143 Vec_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) );
234 ABC_PRT( "Time", Abc_Clock() - clk );
235 }
236
237 // Abc_NtkMaxFlowPrintCut( pNtk, vMinCut );
238 return vMinCut;
239 }
240
241 /**Function*************************************************************
242
243 Synopsis [Tries to find an augmenting path originating in this node.]
244
245 Description []
246
247 SideEffects []
248
249 SeeAlso []
250
251 ***********************************************************************/
Abc_NtkMaxFlowBwdPath_rec(Abc_Obj_t * pObj)252 int 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
293 /**Function*************************************************************
294
295 Synopsis [Tries to find an augmenting path originating in this node.]
296
297 Description []
298
299 SideEffects []
300
301 SeeAlso []
302
303 ***********************************************************************/
Abc_NtkMaxFlowFwdPath_rec(Abc_Obj_t * pObj)304 int 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
346 /**Function*************************************************************
347
348 Synopsis [Tries to find an augmenting path originating in this edge.]
349
350 Description []
351
352 SideEffects []
353
354 SeeAlso []
355
356 ***********************************************************************/
Abc_NtkMaxFlowFwdPath3_rec(Abc_Obj_t * pObj,Abc_Obj_t * pPrev,int fFanin)357 int 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
386 /**Function*************************************************************
387
388 Synopsis [Tries to find an augmenting path originating in this node.]
389
390 Description [This procedure works for directed graphs only!]
391
392 SideEffects []
393
394 SeeAlso []
395
396 ***********************************************************************/
Abc_NtkMaxFlowBwdPath2_rec(Abc_Obj_t * pObj)397 int 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
431 /**Function*************************************************************
432
433 Synopsis [Tries to find an augmenting path originating in this node.]
434
435 Description [This procedure works for directed graphs only!]
436
437 SideEffects []
438
439 SeeAlso []
440
441 ***********************************************************************/
Abc_NtkMaxFlowFwdPath2_rec(Abc_Obj_t * pObj)442 int 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
476 /**Function*************************************************************
477
478 Synopsis [Find minimum-volume minumum cut.]
479
480 Description []
481
482 SideEffects []
483
484 SeeAlso []
485
486 ***********************************************************************/
Abc_NtkMaxFlowMinCut(Abc_Ntk_t * pNtk,int fForward)487 Vec_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
509 /**Function*************************************************************
510
511 Synopsis [Marks the TFI cone with MarkA.]
512
513 Description []
514
515 SideEffects []
516
517 SeeAlso []
518
519 ***********************************************************************/
Abc_NtkMaxFlowMarkCut_rec(Abc_Obj_t * pObj)520 void 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
531 /**Function*************************************************************
532
533 Synopsis [Visits the TFI up to marked nodes and collects marked nodes.]
534
535 Description []
536
537 SideEffects []
538
539 SeeAlso []
540
541 ***********************************************************************/
Abc_NtkMaxFlowCollectCut_rec(Abc_Obj_t * pObj,Vec_Ptr_t * vNodes)542 void 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
558 /**Function*************************************************************
559
560 Synopsis [Updates the minimum cut to be retimable.]
561
562 Description [This procedure also labels the nodes reachable from
563 the latches to the cut with fMarkA.]
564
565 SideEffects []
566
567 SeeAlso []
568
569 ***********************************************************************/
Abc_NtkMaxFlowMinCutUpdate(Abc_Ntk_t * pNtk,Vec_Ptr_t * vMinCut,int fForward)570 void 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
616 /**Function*************************************************************
617
618 Synopsis [Verifies the min-cut is indeed a cut.]
619
620 Description []
621
622 SideEffects []
623
624 SeeAlso []
625
626 ***********************************************************************/
Abc_NtkMaxFlowVerifyCut_rec(Abc_Obj_t * pObj,int fForward)627 int 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
657 /**Function*************************************************************
658
659 Synopsis [Verifies the min-cut is indeed a cut.]
660
661 Description []
662
663 SideEffects []
664
665 SeeAlso []
666
667 ***********************************************************************/
Abc_NtkMaxFlowVerifyCut(Abc_Ntk_t * pNtk,Vec_Ptr_t * vMinCut,int fForward)668 int 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
702 /**Function*************************************************************
703
704 Synopsis [Prints the flows.]
705
706 Description []
707
708 SideEffects []
709
710 SeeAlso []
711
712 ***********************************************************************/
Abc_NtkMaxFlowPrintFlow(Abc_Ntk_t * pNtk,int fForward)713 void 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
756 /**Function*************************************************************
757
758 Synopsis [Prints the min-cut.]
759
760 Description []
761
762 SideEffects []
763
764 SeeAlso []
765
766 ***********************************************************************/
Abc_NtkMaxFlowPrintCut(Abc_Ntk_t * pNtk,Vec_Ptr_t * vMinCut)767 void 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
783 ////////////////////////////////////////////////////////////////////////
784 /// END OF FILE ///
785 ////////////////////////////////////////////////////////////////////////
786
787
788 ABC_NAMESPACE_IMPL_END
789
790