Added generation of MFFC for the network.

3 files changed, 694 insertions, 5 deletions

diff --git a/src/base/abc/abc.h b/src/base/abc/abc.h
index 68a50525..034df03f 100644
--- a/src/base/abc/abc.h
+++ b/src/base/abc/abc.h
@@ -452,6 +452,9 @@ static inline void        Abc_ObjSetMvVar( Abc_Obj_t * pObj, void * pV) { Vec_At
 #define Abc_NtkForEachObj( pNtk, pObj, i )                                                         \
     for ( i = 0; (i < Vec_PtrSize((pNtk)->vObjs)) && (((pObj) = Abc_NtkObj(pNtk, i)), 1); i++ )    \
         if ( (pObj) == NULL ) {} else
+#define Abc_NtkForEachObjVec( pNtk, vIds, pObj, i )                                                \
+    for ( i = 0; i < Vec_IntSize(vIds) && (((pObj) = Abc_NtkObj(pNtk, Vec_IntEntry(vIds,i))), 1); i++ ) \
+        if ( (pObj) == NULL ) {} else
 #define Abc_NtkForEachNet( pNtk, pNet, i )                                                         \
     for ( i = 0; (i < Vec_PtrSize((pNtk)->vObjs)) && (((pNet) = Abc_NtkObj(pNtk, i)), 1); i++ )    \
         if ( (pNet) == NULL || !Abc_ObjIsNet(pNet) ) {} else
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 733e2722..d1e2b0f2 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -8678,7 +8678,7 @@ int Abc_CommandTest( Abc_Frame_t * pAbc, int argc, char ** argv )
 */
 
 //    Abc_NtkHelloWorld( pNtk );
-
+    Abc_NktMffcServerTest( pNtk );
     return 0;
 usage:
     Abc_Print( -2, "usage: test [-h] <file_name>\n" );
diff --git a/src/base/abci/abcMffc.c b/src/base/abci/abcMffc.c
index eb6def53..ec43b71d 100644
--- a/src/base/abci/abcMffc.c
+++ b/src/base/abci/abcMffc.c
@@ -95,11 +95,23 @@ void Abc_MffcRef_rec( Abc_Obj_t * pNode )
 void Abc_MffcCollectNodes( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes )
 {
     int i;
+/*
+    for ( i = 0; i < nNodes; i++ )
+    {
+        pNodes[i]->vFanouts.nSize += 100;
+//Abc_ObjPrint( stdout, pNodes[i] );
+    }
+//printf( "\n" );
+*/
+
     Vec_PtrClear( vNodes );
     for ( i = 0; i < nNodes; i++ )
         Abc_MffcDeref_rec( pNodes[i], vNodes );
     for ( i = 0; i < nNodes; i++ )
         Abc_MffcRef_rec( pNodes[i] );
+
+//    for ( i = 0; i < nNodes; i++ )
+//        pNodes[i]->vFanouts.nSize -= 100;
 }
 
 /**Function*************************************************************
@@ -146,7 +158,7 @@ void Abc_MffcCollectLeaves( Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
   SeeAlso     []
 
 ***********************************************************************/
-Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk )
+Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk, int fSkipPis )
 {
     Vec_Ptr_t * vRoots, * vNodes, * vLeaves;
     Abc_Obj_t * pObj, * pLeaf;
@@ -157,7 +169,7 @@ Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk )
     Abc_NtkForEachCo( pNtk, pObj, i )
     {
         pObj = Abc_ObjFanin0( pObj );
-        if ( Abc_ObjIsCi(pObj) || pObj->fMarkA )
+        if ( Abc_ObjIsCi(pObj) || Abc_ObjFaninNum(pObj) == 0 || pObj->fMarkA )
             continue;
         pObj->fMarkA = 1;
         Vec_PtrPush( vRoots, pObj );
@@ -167,6 +179,8 @@ Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk )
     vLeaves = Vec_PtrAlloc( 100 );
     Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
     {
+        if ( Abc_ObjIsCi(pObj) )
+            continue;
         // collect internal nodes 
         Abc_MffcCollectNodes( &pObj, 1, vNodes );
         // collect leaves
@@ -174,7 +188,7 @@ Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk )
         // add non-PI leaves
         Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, k )
         {
-            if ( Abc_ObjIsCi(pLeaf) || pLeaf->fMarkA )
+            if ( (fSkipPis && Abc_ObjIsCi(pLeaf)) || pLeaf->fMarkA )
                 continue;
             pLeaf->fMarkA = 1;
             Vec_PtrPush( vRoots, pLeaf );
@@ -427,7 +441,7 @@ void Abc_NktMffcTest( Abc_Ntk_t * pNtk )
     Vec_Ptr_t * vRoots, * vRoots1, * vRoots2, * vNodes, * vLeaves;
     Abc_Obj_t * pNodes[3], * pObj;
     int i, nNodes = 0, nNodes2 = 0;
-    vRoots  = Abc_NktMffcMarkRoots( pNtk );
+    vRoots  = Abc_NktMffcMarkRoots( pNtk, 1 );
     vRoots1 = Abc_NktMffcGrowRoots( pNtk, vRoots );
     vRoots2 = Abc_NktMffcGrowRootsAgain( pNtk, vRoots, vRoots1 );
     vNodes  = Vec_PtrAlloc( 100 );
@@ -483,6 +497,678 @@ void Abc_NktMffcTest( Abc_Ntk_t * pNtk )
 }
 
 
+
+/**Function*************************************************************
+
+  Synopsis    [Create the network of supernodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcTestSuper( Abc_Ntk_t * pNtk )
+{
+    Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vNodes, * vLeaves;
+    Abc_Obj_t * pObj, * pFanin; 
+    Vec_Int_t * vCounts, * vNumbers, * vSizes, * vMarks;
+    Vec_Int_t * vNode1, * vNode2;
+    int i, k, Entry, nSizes, clk = clock();
+    vRoots   = Abc_NktMffcMarkRoots( pNtk, 1 );
+    vFanins  = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
+    vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
+    vCounts  = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+    vNode1   = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+    vNode2   = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+    vSizes   = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+    vMarks   = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+
+    // create fanins/fanouts
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Vec_PtrWriteEntry( vFanins,  Abc_ObjId(pObj), Vec_IntAlloc(8) );
+        Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) );
+    }
+    // add fanins/fanouts
+    vNodes   = Vec_PtrAlloc( 100 );
+    vLeaves  = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Abc_MffcCollectNodes( &pObj, 1, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
+        {
+            if ( !Abc_ObjIsNode(pFanin) )
+                continue;
+            Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins,  Abc_ObjId(pObj)),   Abc_ObjId(pFanin) );
+            Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) );
+            // count how many times each object is a fanin
+            Vec_IntAddToEntry( vCounts, Abc_ObjId(pFanin), 1 );
+        }
+        Vec_IntWriteEntry( vSizes, Abc_ObjId(pObj), Vec_PtrSize(vNodes) );
+    }
+
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Abc_MffcCollectNodes( &pObj, 1, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
+        {
+            if ( !Abc_ObjIsNode(pFanin) )
+                continue;
+            if ( Vec_IntEntry(vCounts, Abc_ObjId(pFanin)) != 2 )
+                continue;
+            if ( Vec_IntEntry(vNode1, Abc_ObjId(pFanin)) == 0 )
+                Vec_IntWriteEntry( vNode1, Abc_ObjId(pFanin), Abc_ObjId(pObj) );
+            else //if ( Vec_IntEntry(vNode2, Abc_ObjId(pFanin)) == 0 )
+                Vec_IntWriteEntry( vNode2, Abc_ObjId(pFanin), Abc_ObjId(pObj) );
+
+            Vec_IntWriteEntry( vMarks, Abc_ObjId(pFanin), 1 );
+            Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj),   1 );
+        }
+    }
+
+    // count sizes
+    nSizes = 0;
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        if ( Vec_IntEntry( vMarks, Abc_ObjId(pObj) ) )
+            nSizes += Vec_IntEntry( vSizes, Abc_ObjId(pObj) );
+    }
+    printf( "Included = %6d.  Total = %6d. (%6.2f %%)\n", 
+        nSizes, Abc_NtkNodeNum(pNtk), 100.0 * nSizes / Abc_NtkNodeNum(pNtk) );
+
+
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        if ( Vec_IntEntry(vCounts, Abc_ObjId(pObj)) != 2 )
+            continue;
+        printf( "%d ", Vec_IntEntry( vSizes, Abc_ObjId(pObj) ) + 
+                       Vec_IntEntry( vSizes, Vec_IntEntry(vNode1, Abc_ObjId(pObj)) ) + 
+                       Vec_IntEntry( vSizes, Vec_IntEntry(vNode2, Abc_ObjId(pObj)) ) );
+    }
+    printf( "\n" );
+
+    // print how many times they appear
+    vNumbers = Vec_IntStart( 32 );
+    Vec_IntForEachEntry( vCounts, Entry, i )
+    {
+/*
+if ( Entry == 2 )
+{
+    pObj = Abc_NtkObj( pNtk, i );
+    Abc_MffcCollectNodes( &pObj, 1, vNodes );
+    Abc_MffcCollectLeaves( vNodes, vLeaves );
+    printf( "%d(%d) ", Vec_PtrSize(vNodes), Vec_PtrSize(vLeaves) );
+}
+*/
+        if ( Entry == 0 )
+            continue;
+        if ( Entry <= 10 )
+            Vec_IntAddToEntry( vNumbers, Entry, 1 );
+        else if ( Entry <= 100 )
+            Vec_IntAddToEntry( vNumbers, 10 + Entry/10, 1 );
+        else if ( Entry < 1000 )
+            Vec_IntAddToEntry( vNumbers, 20 + Entry/100, 1 );
+        else
+            Vec_IntAddToEntry( vNumbers, 30, 1 );
+    }
+    for ( i = 1; i <= 10; i++ )
+        if ( Vec_IntEntry(vNumbers,i) )
+            printf( "       n =  %4d   %6d\n", i, Vec_IntEntry(vNumbers,i) );
+    for ( i = 11; i <= 20; i++ )
+        if ( Vec_IntEntry(vNumbers,i) )
+            printf( "%4d < n <= %4d   %6d\n", 10*(i-10),  10*(i-9),  Vec_IntEntry(vNumbers,i) );
+    for ( i = 21; i < 30; i++ )
+        if ( Vec_IntEntry(vNumbers,i) )
+            printf( "%4d < n <= %4d   %6d\n", 100*(i-20), 100*(i-19), Vec_IntEntry(vNumbers,i) );
+    if ( Vec_IntEntry(vNumbers,31) )
+    printf( "       n >  1000   %6d\n", Vec_IntEntry(vNumbers,30) );
+    printf( "Total MFFCs = %d. ", Vec_PtrSize(vRoots) );
+    Abc_PrintTime( 1, "Time", clock() - clk );
+    Vec_IntFree( vNumbers );
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+
+    // delete fanins/fanouts
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins,  Abc_ObjId(pObj)) );
+        Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) );
+    }
+
+    Vec_IntFree( vCounts );
+    Vec_PtrFree( vFanouts );
+    Vec_PtrFree( vFanins );
+    Vec_PtrFree( vRoots );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Collects the leaves and the roots of the window.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffCollectLeafRoot( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots )
+{
+    Abc_Obj_t * pObj, * pNext;
+    int i, k;
+    // mark
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+        pObj->fMarkA = 1;
+    // collect leaves
+    Vec_PtrClear( vLeaves );
+    Abc_NtkIncrementTravId( pNtk );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+        Abc_ObjForEachFanin( pObj, pNext, k )
+        {
+            if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) )
+                continue;
+            Abc_NodeSetTravIdCurrent(pNext);
+            Vec_PtrPush( vLeaves, pNext );
+        }
+    // collect roots
+    Vec_PtrClear( vRoots );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+    {
+        Abc_ObjForEachFanout( pObj, pNext, k )
+            if ( !pNext->fMarkA )
+            {
+                Vec_PtrPush( vRoots, pObj );
+                break;
+            }
+    }
+    // unmark
+    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+        pObj->fMarkA = 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects the leaves and the roots of the window.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffCollectLeafRootInt( Abc_Ntk_t * pNtk, Vec_Int_t * vNodes, Vec_Int_t * vLeaves, Vec_Int_t * vRoots )
+{
+    Abc_Obj_t * pObj, * pNext;
+    int i, k;
+    // mark
+    Abc_NtkForEachObjVec( pNtk, vNodes, pObj, i )
+        pObj->fMarkA = 1;
+    // collect leaves
+    Vec_IntClear( vLeaves );
+    Abc_NtkIncrementTravId( pNtk );
+    Abc_NtkForEachObjVec( pNtk, vNodes, pObj, i )
+        Abc_ObjForEachFanin( pObj, pNext, k )
+        {
+            if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) )
+                continue;
+            Abc_NodeSetTravIdCurrent(pNext);
+            Vec_IntPush( vLeaves, Abc_ObjId(pNext) );
+        }
+    // collect roots
+    if ( vRoots )
+    {
+        Vec_IntClear( vRoots );
+        Abc_NtkForEachObjVec( pNtk, vNodes, pObj, i )
+        {
+            Abc_ObjForEachFanout( pObj, pNext, k )
+                if ( !pNext->fMarkA )
+                {
+                    Vec_IntPush( vRoots, Abc_ObjId(pObj) );
+                    break;
+                }
+        }
+    }
+    // unmark
+    Abc_NtkForEachObjVec( pNtk, vNodes, pObj, i )
+        pObj->fMarkA = 0;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Create the network of supernodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcTestIdeaOne( Abc_Ntk_t * pNtk, Abc_Obj_t * pObj )
+{
+    Vec_Ptr_t * vNodes, * vLeaves, * vRoots, * vVolume;
+    Vec_Ptr_t * vLeaves2, * vRoots2, * vVolume2;
+    Abc_Obj_t * pNode, * pNodeBest = pObj;
+    double Cost, CostBest = 0.0;
+    int i, k;
+    vNodes   = Vec_PtrAlloc( 100 );
+    vLeaves  = Vec_PtrAlloc( 100 );
+    vRoots   = Vec_PtrAlloc( 100 );
+    vVolume  = Vec_PtrAlloc( 100 );
+    vLeaves2 = Vec_PtrAlloc( 100 );
+    vRoots2  = Vec_PtrAlloc( 100 );
+    vVolume2 = Vec_PtrAlloc( 100 );
+printf( "\n" );
+    for ( i = 1; i <= 16; i++ )
+    {
+        Vec_PtrPush( vNodes, pNodeBest );
+        Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves, vRoots );
+        Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots), Vec_PtrSize(vRoots), vVolume );
+
+        printf( "%2d : Node =%6d (%2d%3d)  Cost =%6.2f   ", i, Abc_ObjId(pNodeBest), 
+            Abc_ObjFaninNum(pNodeBest), Abc_ObjFanoutNum(pNodeBest), CostBest );
+        printf( "Leaf =%2d  Root =%2d  Vol =%2d\n", Vec_PtrSize(vLeaves), Vec_PtrSize(vRoots), Vec_PtrSize(vVolume) );
+
+        // try including different nodes
+        pNodeBest = NULL;
+        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, k )
+        {
+            if ( !Abc_ObjIsNode(pNode) )
+                continue;
+            Vec_PtrPush( vNodes, pNode );
+            Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 );
+            Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 );
+            Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2));
+            if ( pNodeBest == NULL || CostBest < Cost )
+            {
+                pNodeBest = pNode;
+                CostBest  = Cost;
+            }
+            Vec_PtrPop( vNodes );
+        }
+        Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, k )
+        {
+            if ( Vec_PtrFind(vNodes, pNode) >= 0 )
+                continue;
+            if ( !Abc_ObjIsNode(pNode) )
+                continue;
+            Vec_PtrPush( vNodes, pNode );
+            Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 );
+            Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 );
+            Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2));
+            if ( pNodeBest == NULL || CostBest < Cost )
+            {
+                pNodeBest = pNode;
+                CostBest  = Cost;
+            }
+            Vec_PtrPop( vNodes );
+        }
+        if ( pNodeBest == NULL )
+            break;
+    }
+
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+    Vec_PtrFree( vRoots );
+    Vec_PtrFree( vVolume );
+    Vec_PtrFree( vLeaves2 );
+    Vec_PtrFree( vRoots2 );
+    Vec_PtrFree( vVolume2 );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Create the network of supernodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcTestIdea( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pObj; 
+    int i;
+    Abc_NtkForEachNode( pNtk, pObj, i )
+        if ( Abc_ObjIsNode(pObj) && Abc_ObjId(pObj) % 100 == 0 )
+            Abc_NktMffcTestIdeaOne( pNtk, pObj );
+}
+
+
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Creates MFFCs and their fanins/fanouts/volumes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NktMffcDerive( Abc_Ntk_t * pNtk, Vec_Ptr_t ** pvFanins, Vec_Ptr_t ** pvFanouts, Vec_Ptr_t ** pvVolumes )
+{
+    Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vVolumes, * vNodes, * vLeaves;
+    Abc_Obj_t * pObj, * pFanin; 
+    int i, k, clk = clock();
+    // create roots
+    vRoots   = Abc_NktMffcMarkRoots( pNtk, 0 );
+    // create fanins/fanouts/volumes
+    vFanins  = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
+    vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
+    vVolumes = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Vec_PtrWriteEntry( vFanins,  Abc_ObjId(pObj), Vec_IntAlloc(8) );
+        Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) );
+        Vec_PtrWriteEntry( vVolumes, Abc_ObjId(pObj), Vec_IntAlloc(8) );
+    }
+    // add fanins/fanouts
+    vNodes   = Vec_PtrAlloc( 100 );
+    vLeaves  = Vec_PtrAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        if ( Abc_ObjIsCi(pObj) )
+            continue;
+        Abc_MffcCollectNodes( &pObj, 1, vNodes );
+        Abc_MffcCollectLeaves( vNodes, vLeaves );
+        Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
+        {
+            Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins,  Abc_ObjId(pObj)),   Abc_ObjId(pFanin) );
+            Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) );
+        }
+        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pFanin, k )
+            Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)),   Abc_ObjId(pFanin) );
+    }
+
+    Vec_PtrFree( vNodes );
+    Vec_PtrFree( vLeaves );
+    // sort
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanins,  Abc_ObjId(pObj)), 0 );
+        Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)), 0 );
+    }
+    // return
+    *pvFanins  = vFanins;
+    *pvFanouts = vFanouts;
+    *pvVolumes = vVolumes;
+    return vRoots;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Frees MFFCs and their fanins/fanouts.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcFree( Vec_Ptr_t * vRoots, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes )
+{
+    Abc_Obj_t * pObj; 
+    int i;
+    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
+    {
+        Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins,  Abc_ObjId(pObj)) );
+        Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) );
+        Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)) );
+    }
+    Vec_PtrFree( vVolumes );
+    Vec_PtrFree( vFanouts );
+    Vec_PtrFree( vFanins );
+    Vec_PtrFree( vRoots );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the cost of two supports.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NktMffcCostTwo( Vec_Int_t * vSupp1, Vec_Int_t * vSupp2, int Limit )
+{
+    int nCommon = Vec_IntTwoCountCommon( vSupp1, vSupp2 );
+    if ( Vec_IntSize(vSupp1) + Vec_IntSize(vSupp2) - nCommon > Limit )
+        return -ABC_INFINITY;
+    return 3 * nCommon - Vec_IntSize(vSupp1) - Vec_IntSize(vSupp2);
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns support of the group.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins )
+{
+    Vec_Int_t * vIns, * vIns2, * vTemp;
+    Abc_Obj_t * pObj;
+    int i;
+//    int Entry;
+    vIns = Vec_IntAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i )
+    {
+        vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) );
+        vIns  = Vec_IntTwoMerge( vTemp = vIns, vIns2 );
+        Vec_IntFree( vTemp );
+    }
+//Vec_IntForEachEntry( vIns, Entry, i )
+//printf( "%d ", Entry );
+//printf( "\n" );
+    return vIns;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the best merger for the cluster of given node (pPivot).]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t * vIns, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, int Limit )
+{
+    Vec_Int_t * vIns2, * vOuts, * vOuts2, * vTemp;
+    Abc_Obj_t * pPivot2, * pObj, * pObjBest = NULL;
+    int i, Cost, CostBest = -ABC_INFINITY;
+    // collect the fanouts of the fanins
+    vOuts = Vec_IntAlloc( 100 );
+    Abc_NtkForEachObjVec( pNtk, vIns, pObj, i )
+    {
+        vOuts2 = (Vec_Int_t *)Vec_PtrEntry( vFanouts, Abc_ObjId(pObj) );
+        if ( Vec_IntSize(vOuts2) > 16 )
+            continue;
+        vOuts  = Vec_IntTwoMerge( vTemp = vOuts, vOuts2 );
+        Vec_IntFree( vTemp );
+    }
+    // check the pairs
+    Abc_NtkForEachObjVec( pNtk, vOuts, pPivot2, i )
+    {       
+        if ( Vec_IntEntry(vMarks, Abc_ObjId(pPivot2)) == 0 )
+            continue;
+        vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pPivot2) );
+        Cost  = Abc_NktMffcCostTwo( vIns, vIns2, Limit );
+        if ( Cost == -ABC_INFINITY )
+            continue;
+        if ( pObjBest == NULL || CostBest < Cost )
+        {
+            pObjBest = pPivot2;
+            CostBest = Cost;
+        }
+    }    
+    Vec_IntFree( vOuts );
+    return pObjBest;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Processes one cluster.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Abc_NktMffcSaveOne( Vec_Ptr_t * vThis, Vec_Ptr_t * vVolumes )
+{
+    Vec_Int_t * vVolume, * vResult;
+    Abc_Obj_t * pObj;
+    int i, k, Entry;
+    vResult = Vec_IntAlloc( 100 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i )
+    {
+        vVolume = (Vec_Int_t *)Vec_PtrEntry( vVolumes, Abc_ObjId(pObj) );
+        Vec_IntForEachEntry( vVolume, Entry, k )
+        {
+            Vec_IntPush( vResult, Entry );
+//printf( "%d ", Entry );
+        }
+    }
+//printf( "\n" );
+    return vResult;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Create the network of supernodes.]
+
+  Description [Returns array of interger arrays of IDs of nodes
+  included in a disjoint structural decomposition of the network.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
+{
+    Vec_Ptr_t * vResult, * vThis;
+    Vec_Ptr_t * vPivots, * vFanins, * vFanouts, * vVolumes;
+    Vec_Int_t * vLeaves, * vMarks;
+    Abc_Obj_t * pObj, * pObj2;
+    int i, k;
+    assert( nOutMax >= 1 && nOutMax <= 32 );
+    vResult = Vec_PtrAlloc( 100 );
+    // create fanins/fanouts
+    vPivots = Abc_NktMffcDerive( pNtk, &vFanins, &vFanouts, &vVolumes );
+    // create marks
+    vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
+        if ( Abc_ObjIsNode(pObj) )
+            Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 );
+    // consider nodes in the order of the marks
+    vThis = Vec_PtrAlloc( 10 );
+    Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
+    {
+        if ( Vec_IntEntry(vMarks, Abc_ObjId(pObj)) == 0 )
+            continue;
+        // start the set
+        Vec_PtrClear( vThis );        
+        Vec_PtrPush( vThis, pObj );
+        Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 0 );
+        // quit if exceeded the limit
+        vLeaves = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) );
+        if ( Vec_IntSize(vLeaves) > nInMax )
+        {
+            Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) );
+            continue;
+        }
+        // try adding one node at a time
+        for ( k = 1; k < nOutMax; k++ )
+        {
+            // quit if exceeded the limit
+            vLeaves = Abc_NktMffcSupport( vThis, vFanins );
+            assert( Vec_IntSize(vLeaves) <= nInMax );
+            pObj2 = Abc_NktMffcFindBest( pNtk, vMarks, vLeaves, vFanins, vFanouts, nInMax );
+            Vec_IntFree( vLeaves );
+            // quit if there is no extension
+            if ( pObj2 == NULL )
+                break;
+            Vec_PtrPush( vThis, pObj2 );
+            Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj2), 0 );
+        }
+        Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) );
+    }
+    Vec_PtrFree( vThis );
+    Vec_IntFree( vMarks );
+    // delele fanins/outputs
+    Abc_NktMffcFree( vPivots, vFanins, vFanouts, vVolumes );
+    return vResult;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Testbench.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk )
+{
+    Vec_Ptr_t * vGlobs;
+    Vec_Int_t * vGlob, * vLeaves, * vRoots;
+    double Cost;
+    int i, nNodes = 0, clk = clock();
+    vGlobs  = Abc_NktMffcServer( pNtk, 18, 3 );
+    vLeaves = Vec_IntAlloc( 100 );
+    vRoots  = Vec_IntAlloc( 100 );
+    Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i )
+    {
+        nNodes += Vec_IntSize(vGlob);
+        Abc_NktMffCollectLeafRootInt( pNtk, vGlob, vLeaves, vRoots );
+        Cost = 1.0 * Vec_IntSize(vGlob)/(Vec_IntSize(vLeaves) + Vec_IntSize(vRoots));
+        if ( Cost < 0.3 || Vec_IntSize(vGlob) < 5 )
+            continue;
+        printf( "%4d : Root =%3d. Leaf =%3d. Node =%4d. ", 
+            i, Vec_IntSize(vRoots), Vec_IntSize(vLeaves), Vec_IntSize(vGlob) );
+        printf( "Cost =%6.2f\n", Cost );
+    }
+    Vec_IntFree( vLeaves );
+    Vec_IntFree( vRoots );
+    Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i )
+        Vec_IntFree( vGlob );
+    Vec_PtrFree( vGlobs );
+    printf( "Total = %6d.  Nodes = %6d.  ", Abc_NtkNodeNum(pNtk), nNodes );
+    Abc_PrintTime( 1, "Time", clock() - clk );
+}
+
+
 ABC_NAMESPACE_IMPL_END
 
 ////////////////////////////////////////////////////////////////////////