From fefd8b901d89ad0d977db8896c12123cc747e3d7 Mon Sep 17 00:00:00 2001
From: Alan Mishchenko <alanmi@berkeley.edu>
Date: Mon, 30 Jul 2007 08:01:00 -0700
Subject: Version abc70730

---
 src/opt/ret/retFlow.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 47 insertions(+)

(limited to 'src/opt/ret/retFlow.c')

diff --git a/src/opt/ret/retFlow.c b/src/opt/ret/retFlow.c
index 24d7bf57..47ee8516 100644
--- a/src/opt/ret/retFlow.c
+++ b/src/opt/ret/retFlow.c
@@ -75,6 +75,8 @@ static int         Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj );
 static int         Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj );
 static int         Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj );
 static int         Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj );
+//static int         Abc_NtkMaxFlowBwdPath3_rec( Abc_Obj_t * pObj );
+static int         Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin );
 static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward );
 static void        Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
 static int         Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward );
@@ -107,6 +109,7 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
         pObj->fMarkA = 1;
     Abc_NtkForEachLatch( pNtk, pObj, i )
         pObj->fMarkA = Abc_ObjFanin0(pObj)->fMarkA = 1;
+//        Abc_ObjFanin0(pObj)->fMarkA = 1;
     vMinCut = Abc_NtkMaxFlow( pNtk, 1, 1 );
     Vec_PtrFree( vMinCut );
     Abc_NtkCleanMarkA( pNtk );
@@ -116,6 +119,7 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk )
         pObj->fMarkA = 1;
     Abc_NtkForEachLatch( pNtk, pObj, i )
         pObj->fMarkA = Abc_ObjFanout0(pObj)->fMarkA = 1;
+//        Abc_ObjFanout0(pObj)->fMarkA = 1;
     vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 );
     Vec_PtrFree( vMinCut );
     Abc_NtkCleanMarkA( pNtk );
@@ -151,6 +155,7 @@ Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
         {
 //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
             FlowCur  = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
+//            FlowCur  = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
             Flow    += FlowCur;
         }
         else
@@ -195,6 +200,7 @@ Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose )
 //            assert( !Abc_ObjFanout0(pLatch)->fMarkA );
             if ( fUseDirectedFlow )
                 RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) );
+//                RetValue = Abc_NtkMaxFlowFwdPath3_rec( Abc_ObjFanout0(pLatch), pLatch, 1 );
             else
                 RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) );
         }
@@ -333,6 +339,47 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj )
     return 0;
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Tries to find an augmenting path originating in this edge.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NtkMaxFlowFwdPath3_rec( Abc_Obj_t * pObj, Abc_Obj_t * pPrev, int fFanin )
+{
+    Abc_Obj_t * pFanin, * pFanout;
+    int i;
+    // skip visited nodes
+    if ( Abc_NodeIsTravIdCurrent(pObj) )
+        return 0;
+    Abc_NodeSetTravIdCurrent(pObj);
+    // skip the fanin which already has flow
+    if ( fFanin && Abc_ObjGetPath(pPrev) )
+        return 0;
+    // if the node has no flow, try to push through the fanouts
+    if ( !Abc_ObjGetPath(pObj) )
+    {
+        // start the path if we reached a terminal node
+        if ( pObj->fMarkA )
+            return Abc_ObjSetPath( pObj, (void *)1 );
+        // try to push flow through the fanouts
+        Abc_ObjForEachFanout( pObj, pFanout, i )
+            if ( Abc_NtkMaxFlowFwdPath3_rec(pFanout, pObj, 1) )
+                return fFanin? Abc_ObjSetPath(pPrev, pObj) : 1;
+    }
+    // try to push through the fanins
+    Abc_ObjForEachFanin( pObj, pFanin, i )
+        if ( !Abc_ObjIsLatch(pFanin) && Abc_NtkMaxFlowFwdPath3_rec(pFanin, pObj, 0) )
+            return Abc_ObjSetPath( pFanin, NULL );
+    return 0;
+}
+
 /**Function*************************************************************
 
   Synopsis    [Tries to find an augmenting path originating in this node.]
-- 
cgit v1.2.3