Version abc80706

1 files changed, 763 insertions, 0 deletions

diff --git a/src/aig/nwk/nwkMerge.c b/src/aig/nwk/nwkMerge.c
new file mode 100644
index 00000000..57de7f04
--- /dev/null
+++ b/src/aig/nwk/nwkMerge.c
@@ -0,0 +1,763 @@
+/**CFile****************************************************************
+
+  FileName    [nwkMerge.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Netlist representation.]
+
+  Synopsis    [LUT merging algorithm.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "nwk.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Marks the fanins of the node with the current trav ID.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManMarkFanins_rec( Nwk_Obj_t * pLut, int nLevMin )
+{
+    Nwk_Obj_t * pNext;
+    int i;
+    if ( !Nwk_ObjIsNode(pLut) )
+        return;
+    if ( Nwk_ObjIsTravIdCurrent( pLut ) )
+        return;
+    Nwk_ObjSetTravIdCurrent( pLut );
+    if ( Nwk_ObjLevel(pLut) < nLevMin )
+        return;
+    Nwk_ObjForEachFanin( pLut, pNext, i )
+        Nwk_ManMarkFanins_rec( pNext, nLevMin );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Marks the fanouts of the node with the current trav ID.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManMarkFanouts_rec( Nwk_Obj_t * pLut, int nLevMax, int nFanMax )
+{
+    Nwk_Obj_t * pNext;
+    int i;
+    if ( !Nwk_ObjIsNode(pLut) )
+        return;
+    if ( Nwk_ObjIsTravIdCurrent( pLut ) )
+        return;
+    Nwk_ObjSetTravIdCurrent( pLut );
+    if ( Nwk_ObjLevel(pLut) > nLevMax )
+        return;
+    if ( Nwk_ObjFanoutNum(pLut) > nFanMax )
+        return;
+    Nwk_ObjForEachFanout( pLut, pNext, i )
+        Nwk_ManMarkFanouts_rec( pNext, nLevMax, nFanMax );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects the circle of nodes around the given set.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax )
+{
+    Nwk_Obj_t * pObj, * pNext;
+    int i, k;
+    Vec_PtrClear( vNext );
+    Vec_PtrForEachEntry( vStart, pObj, i )
+    {
+        Nwk_ObjForEachFanin( pObj, pNext, k )
+        {
+            if ( !Nwk_ObjIsNode(pNext) )
+                continue;
+            if ( Nwk_ObjIsTravIdCurrent( pNext ) )
+                continue;
+            Nwk_ObjSetTravIdCurrent( pNext );
+            Vec_PtrPush( vNext, pNext );
+        }
+        Nwk_ObjForEachFanout( pObj, pNext, k )
+        {
+            if ( !Nwk_ObjIsNode(pNext) )
+                continue;
+            if ( Nwk_ObjIsTravIdCurrent( pNext ) )
+                continue;
+            Nwk_ObjSetTravIdCurrent( pNext );
+            if ( Nwk_ObjFanoutNum(pNext) > nFanMax )
+                continue;
+            Vec_PtrPush( vNext, pNext );
+        }
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects the circle of nodes removes from the given one.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManCollectNonOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
+{
+    Vec_Ptr_t * vTemp;
+    Nwk_Obj_t * pObj;
+    int i, k;
+    Vec_PtrClear( vCands );
+    if ( pPars->nMaxSuppSize - Nwk_ObjFaninNum(pLut) <= 1 )
+        return;
+
+    // collect nodes removed by this distance
+    assert( pPars->nMaxDistance > 0 );
+    Vec_PtrClear( vStart );
+    Vec_PtrPush( vStart, pLut );
+    Nwk_ManIncrementTravId( pLut->pMan );
+    Nwk_ObjSetTravIdCurrent( pLut );
+    for ( i = 1; i < pPars->nMaxDistance; i++ )
+    {
+        Nwk_ManCollectCircle( vStart, vNext, pPars->nMaxFanout );
+        vTemp = vStart;
+        vStart = vNext;
+        vNext = vTemp;
+        // collect the nodes in vStart
+        Vec_PtrForEachEntry( vStart, pObj, k )
+            Vec_PtrPush( vCands, pObj );
+    }
+
+    // mark the TFI/TFO nodes
+    Nwk_ManIncrementTravId( pLut->pMan );
+    if ( pPars->fUseTfiTfo )
+        Nwk_ObjSetTravIdCurrent( pLut );
+    else
+    {
+        Nwk_ObjSetTravIdPrevious( pLut );
+        Nwk_ManMarkFanins_rec( pLut, Nwk_ObjLevel(pLut) - pPars->nMaxDistance );
+        Nwk_ObjSetTravIdPrevious( pLut );
+        Nwk_ManMarkFanouts_rec( pLut, Nwk_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout );
+    }
+
+    // collect nodes satisfying the following conditions:
+    // - they are close enough in terms of distance
+    // - they are not in the TFI/TFO of the LUT
+    // - they have no more than the given number of fanins
+    // - they have no more than the given diff in delay
+    k = 0;
+    Vec_PtrForEachEntry( vCands, pObj, i )
+    {
+        if ( Nwk_ObjIsTravIdCurrent(pObj) )
+            continue;
+        if ( Nwk_ObjFaninNum(pLut) + Nwk_ObjFaninNum(pObj) > pPars->nMaxSuppSize )
+            continue;
+        if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff || 
+             Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
+             continue;
+        Vec_PtrWriteEntry( vCands, k++, pObj );
+    }
+    Vec_PtrShrink( vCands, k );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Count the total number of fanins.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Nwk_ManCountTotalFanins( Nwk_Obj_t * pLut, Nwk_Obj_t * pCand )
+{
+    Nwk_Obj_t * pFanin;
+    int i, nCounter = Nwk_ObjFaninNum(pLut);
+    Nwk_ObjForEachFanin( pCand, pFanin, i )
+        nCounter += !pFanin->MarkC;
+    return nCounter;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Collects overlapping candidates.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwl_ManCollectOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
+{
+    Nwk_Obj_t * pFanin, * pObj;
+    int i, k;
+    // mark fanins of pLut
+    Nwk_ObjForEachFanin( pLut, pFanin, i )
+        pFanin->MarkC = 1;
+    // collect the matching fanouts of each fanin of the node
+    Vec_PtrClear( vCands );
+    Nwk_ManIncrementTravId( pLut->pMan );
+    Nwk_ObjSetTravIdCurrent( pLut );
+    Nwk_ObjForEachFanin( pLut, pFanin, i )
+    {
+        if ( !Nwk_ObjIsNode(pFanin) )
+            continue;
+        if ( Nwk_ObjFanoutNum(pFanin) > pPars->nMaxFanout )
+            continue;
+        Nwk_ObjForEachFanout( pFanin, pObj, k )
+        {
+            if ( !Nwk_ObjIsNode(pObj) )
+                continue;
+            if ( Nwk_ObjIsTravIdCurrent( pObj ) )
+                continue;
+            Nwk_ObjSetTravIdCurrent( pObj );
+            // check the difference in delay
+            if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff || 
+                 Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
+                 continue;
+            // check the total number of fanins of the node
+            if ( Nwk_ManCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize )
+                continue;
+            Vec_PtrPush( vCands, pObj );
+        }
+    }
+    // unmark fanins of pLut
+    Nwk_ObjForEachFanin( pLut, pFanin, i )
+        pFanin->MarkC = 0;
+}
+
+
+
+#define MAX_LIST  16
+
+// edge of the graph
+typedef struct Nwk_Edg_t_  Nwk_Edg_t;
+struct Nwk_Edg_t_
+{
+    int             iNode1;      // the first node
+    int             iNode2;      // the second node
+    Nwk_Edg_t *     pNext;       // the next edge
+};
+
+// vertex of the graph
+typedef struct Nwk_Vrt_t_  Nwk_Vrt_t;
+struct Nwk_Vrt_t_
+{
+    int             Id;          // the vertex number
+    int             iPrev;       // the previous vertex in the list
+    int             iNext;       // the next vertex in the list
+    int             nEdges;      // the number of edges
+    int             pEdges[0];   // the array of edges
+};
+
+// the connectivity graph
+typedef struct Nwk_Grf_t_  Nwk_Grf_t;
+struct Nwk_Grf_t_
+{
+    // preliminary graph representation
+    int             nObjs;       // the number of objects
+    int             nVertsPre;   // the upper bound on the number of vertices
+    int             nEdgeHash;   // approximate number of edges
+    Nwk_Edg_t **    pEdgeHash;   // hash table for edges
+    Aig_MmFixed_t * pMemEdges;   // memory for edges
+    // graph representation
+    int             nEdges;      // the number of edges
+    int             nVerts;      // the number of vertices
+    Nwk_Vrt_t **    pVerts;      // the array of vertices
+    Aig_MmFlex_t *  pMemVerts;   // memory for vertices
+    // intermediate data
+    int             pLists1[MAX_LIST+1];
+    int             pLists2[MAX_LIST+1];
+    // the results of matching
+    Vec_Int_t *     vPairs;
+    // mappings graph into LUTs and back
+    int *           pMapLut2Id;
+    int *           pMapId2Lut;
+};
+
+/**Function*************************************************************
+
+  Synopsis    [Deallocates the graph.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManGraphFree( Nwk_Grf_t * p )
+{
+    if ( p->vPairs )    Vec_IntFree( p->vPairs );
+    if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 );
+    if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 );
+    FREE( p->pEdgeHash );
+    FREE( p->pVerts );
+    FREE( p->pMapLut2Id );
+    FREE( p->pMapId2Lut );
+    free( p );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Allocates the graph.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Nwk_Grf_t * Nwk_ManGraphAlloc( int nObjs, int nVertsPre )
+{
+    Nwk_Grf_t * p;
+    p = ALLOC( Nwk_Grf_t, 1 );
+    memset( p, 0, sizeof(Nwk_Grf_t) );
+    p->nObjs      = nObjs;
+    p->nVertsPre  = nVertsPre;
+    p->nEdgeHash  = Aig_PrimeCudd(10 * nVertsPre);
+    p->pEdgeHash  = CALLOC( Nwk_Edg_t *, p->nEdgeHash );
+    p->pMemEdges  = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash );
+    p->pMapLut2Id = ALLOC( int, nObjs );
+    p->pMapId2Lut = ALLOC( int, nVertsPre );
+    p->vPairs     = Vec_IntAlloc( 1000 );
+    memset( p->pMapLut2Id, 0xff, sizeof(int) * nObjs );
+    memset( p->pMapId2Lut, 0xff, sizeof(int) * nVertsPre );
+    return p;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Finds or adds the edge to the graph.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphSetMapping( Nwk_Grf_t * p, int iLut )
+{
+    p->nVerts++;
+    p->pMapId2Lut[p->nVerts] = iLut;
+    p->pMapLut2Id[iLut] = p->nVerts;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Finds or adds the edge to the graph.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 )
+{
+    Nwk_Edg_t * pEntry;
+    int Key;
+    if ( iLut1 == iLut2 )
+        return;
+    if ( iLut1 > iLut2 )
+    {
+        Key = iLut1;
+        iLut1 = iLut2;
+        iLut2 = Key;
+    }
+    assert( iLut1 < iLut2 );
+    Key = (741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash;
+    for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
+        if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 )
+            return;
+    pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges );
+    pEntry->iNode1 = iLut1;
+    pEntry->iNode2 = iLut2;
+    pEntry->pNext = p->pEdgeHash[Key];
+    p->pEdgeHash[Key] = pEntry;
+    p->nEdges++;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Prepares the graph for solving the problem.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListAdd( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
+{
+    if ( *pList )
+    {
+        Nwk_Vrt_t * pHead;
+        pHead = p->pVerts[*pList];
+        pVertex->iPrev = 0;
+        pVertex->iNext = pHead->Id;
+        pHead->iPrev = pVertex->Id;
+    }
+    *pList = pVertex->Id;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Prepares the graph for solving the problem.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListDelete( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
+{
+    assert( *pList );
+    if ( pVertex->iPrev )
+        p->pVerts[pVertex->iPrev]->iNext = pVertex->iNext;
+    if ( pVertex->iNext )
+        p->pVerts[pVertex->iNext]->iNext = pVertex->iPrev;
+    if ( *pList == pVertex->Id )
+        *pList = pVertex->iNext;
+    pVertex->iPrev = pVertex->iNext = 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Inserts the edge into one of the linked lists.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListInsert( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
+{
+    Nwk_Vrt_t * pNext;
+    assert( pVertex->nEdges > 0 );
+    if ( pVertex->nEdges == 1 )
+    {
+        pNext = p->pVerts[ pVertex->pEdges[0] ];
+        if ( pNext->nEdges >= MAX_LIST )
+            Nwk_ManGraphListAdd( p, p->pLists1 + MAX_LIST, pVertex );
+        else
+            Nwk_ManGraphListAdd( p, p->pLists1 + pNext->nEdges, pVertex );
+    }
+    else
+    {
+        if ( pVertex->nEdges >= MAX_LIST )
+            Nwk_ManGraphListAdd( p, p->pLists1 + MAX_LIST, pVertex );
+        else
+            Nwk_ManGraphListAdd( p, p->pLists1 + pVertex->nEdges, pVertex );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Extracts the edge from one of the linked lists.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Nwk_ManGraphListExtract( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
+{
+    Nwk_Vrt_t * pNext;
+    assert( pVertex->nEdges > 0 );
+    if ( pVertex->nEdges == 1 )
+    {
+        pNext = p->pVerts[ pVertex->pEdges[0] ];
+        if ( pNext->nEdges >= MAX_LIST )
+            Nwk_ManGraphListDelete( p, p->pLists1 + MAX_LIST, pVertex );
+        else
+            Nwk_ManGraphListDelete( p, p->pLists1 + pNext->nEdges, pVertex );
+    }
+    else
+    {
+        if ( pVertex->nEdges >= MAX_LIST )
+            Nwk_ManGraphListDelete( p, p->pLists1 + MAX_LIST, pVertex );
+        else
+            Nwk_ManGraphListDelete( p, p->pLists1 + pVertex->nEdges, pVertex );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Prepares the graph for solving the problem.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManGraphPrepare( Nwk_Grf_t * p )
+{
+    Nwk_Edg_t * pEntry;
+    Nwk_Vrt_t * pVertex;
+    int * pnEdges, Key, nBytes, i;
+    // count the edges
+    pnEdges = CALLOC( int, p->nVerts );
+    for ( Key = 0; Key < p->nEdgeHash; Key++ )
+        for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
+        {
+            // translate into vertices
+            assert( pEntry->iNode1 < p->nObjs );
+            assert( pEntry->iNode2 < p->nObjs );
+            pEntry->iNode1 = p->pMapLut2Id[pEntry->iNode1];
+            pEntry->iNode2 = p->pMapLut2Id[pEntry->iNode2];
+            // count the edges
+            assert( pEntry->iNode1 < p->nVerts );
+            assert( pEntry->iNode2 < p->nVerts );
+            pnEdges[pEntry->iNode1]++;
+            pnEdges[pEntry->iNode2]++;
+        }
+    // allocate the real graph
+    p->pMemVerts  = Aig_MmFlexStart();
+    p->pVerts = ALLOC( Nwk_Vrt_t *, p->nVerts + 1 );
+    p->pVerts[0] = NULL;
+    for ( i = 1; i <= p->nVerts; i++ )
+    {
+        assert( pnEdges[i] > 0 );
+        nBytes = sizeof(Nwk_Vrt_t) + sizeof(int) * pnEdges[i];
+        p->pVerts[i] = (Nwk_Vrt_t *)Aig_MmFlexEntryFetch( p->pMemVerts, nBytes );
+        memset( p->pVerts[i], 0, nBytes );
+        p->pVerts[i]->Id = i;
+    }
+    // add edges to the real graph
+    for ( Key = 0; Key < p->nEdgeHash; Key++ )
+        for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
+        {
+            pVertex = p->pVerts[pEntry->iNode1];
+            pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode2;
+            pVertex = p->pVerts[pEntry->iNode2];
+            pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode1;
+        }
+    // put vertices into the data structure
+    for ( i = 1; i <= p->nVerts; i++ )
+    {
+        assert( p->pVerts[i]->nEdges == pnEdges[i] );
+        Nwk_ManGraphListInsert( p, p->pVerts[i] );
+    }
+    // clean up
+    Aig_MmFixedStop( p->pMemEdges, 0 ); p->pMemEdges = NULL;
+    FREE( p->pEdgeHash );
+    p->nEdgeHash = 0;
+    free( pnEdges );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Updates the problem after pulling out one edge.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManGraphUpdate( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex, Nwk_Vrt_t * pNext )
+{
+    Nwk_Vrt_t * pChanged;
+    int i, k;
+    // update neibors of pVertex
+    for ( i = 0; i < pVertex->nEdges; i++ )
+    {
+        pChanged = p->pVerts[ pVertex->pEdges[i] ];
+        Nwk_ManGraphListExtract( p, pChanged );
+        for ( k = 0; k < pChanged->nEdges; k++ )
+            if ( pChanged->pEdges[k] == pVertex->Id )
+                break;
+        assert( k < pChanged->nEdges );
+        pChanged->nEdges--;
+        for ( ; k < pChanged->nEdges; k++ )
+            pChanged->pEdges[k] = pChanged->pEdges[k+1];
+        if ( pChanged->nEdges > 0 )
+            Nwk_ManGraphListInsert( p, pChanged );
+    }
+    // update neibors of pNext
+    for ( i = 0; i < pNext->nEdges; i++ )
+    {
+        pChanged = p->pVerts[ pNext->pEdges[i] ];
+        Nwk_ManGraphListExtract( p, pChanged );
+        for ( k = 0; k < pChanged->nEdges; k++ )
+            if ( pChanged->pEdges[k] == pNext->Id )
+                break;
+        assert( k < pChanged->nEdges );
+        pChanged->nEdges--;
+        for ( ; k < pChanged->nEdges; k++ )
+            pChanged->pEdges[k] = pChanged->pEdges[k+1];
+        if ( pChanged->nEdges > 0 )
+            Nwk_ManGraphListInsert( p, pChanged );
+    }
+    // add to the result
+    if ( pVertex->Id < pNext->Id )
+    {
+        Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] ); 
+        Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] ); 
+    }
+    else
+    {
+        Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] ); 
+        Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] ); 
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Solves the problem.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Nwk_ManGraphSolve( Nwk_Grf_t * p )
+{
+    Nwk_Vrt_t * pVertex, * pNext;
+    int i, j;
+    while ( 1 )
+    {
+        // find the next vertext to extract
+        for ( i = 1; i <= MAX_LIST; i++ )
+            if ( p->pLists1[i] )
+            {
+                pVertex = p->pVerts[ p->pLists1[i] ];
+                assert( pVertex->nEdges == 1 );
+                pNext = p->pVerts[ pVertex->pEdges[0] ];
+                // update the data-structures
+                Nwk_ManGraphUpdate( p, pVertex, pNext );
+                break;
+            }
+        // find the next vertext to extract
+        for ( j = 2; j <= MAX_LIST; j++ )
+            if ( p->pLists2[j] )
+            {
+                pVertex = p->pVerts[ p->pLists2[j] ];
+                assert( pVertex->nEdges == j || j == MAX_LIST );
+                // update the data-structures
+                Nwk_ManGraphUpdate( p, pVertex, pNext );
+                break;
+            }
+        if ( i == MAX_LIST + 1 && j == MAX_LIST + 1 )
+            break;
+    }
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Performs LUT merging with parameters.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * pNtk, Nwk_LMPars_t * pPars )
+{
+    Nwk_Grf_t * p;
+    Vec_Int_t * vResult;
+    Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2;
+    Nwk_Obj_t * pLut, * pCand;
+    int i, k, nVertsPre;
+    // count the number of vertices
+    nVertsPre = 0;
+    Nwk_ManForEachNode( pNtk, pLut, i )
+        nVertsPre += (int)(Nwk_ObjFaninNum(pLut) <= pPars->nMaxLutSize);
+    p = Nwk_ManGraphAlloc( Nwk_ManObjNumMax(pNtk), nVertsPre );
+    // create graph
+    vStart  = Vec_PtrAlloc( 1000 );
+    vNext   = Vec_PtrAlloc( 1000 );
+    vCands1 = Vec_PtrAlloc( 1000 );
+    vCands2 = Vec_PtrAlloc( 1000 );
+    Nwk_ManForEachNode( pNtk, pLut, i )
+    {
+        if ( Nwk_ObjFaninNum(pLut) > pPars->nMaxLutSize )
+            continue;
+        Nwl_ManCollectOverlapCands( pLut, vCands1, pPars );
+        Nwk_ManCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars );
+        if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 )
+            continue;
+        // save candidates
+        Nwk_ManGraphSetMapping( p, Nwk_ObjId(pLut) );
+        Vec_PtrForEachEntry( vCands1, pCand, k )
+            Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
+        Vec_PtrForEachEntry( vCands2, pCand, k )
+            Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
+        // print statistics about this node
+        printf( "Node %6d : Fanins = %d. Fanouts = %3d.  Cand1 = %3d. Cand2 = %3d.\n",
+            Nwk_ObjId(pLut), Nwk_ObjFaninNum(pLut), Nwk_ObjFaninNum(pLut), 
+            Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) );
+    }
+    Vec_PtrFree( vStart );
+    Vec_PtrFree( vNext );
+    Vec_PtrFree( vCands1 );
+    Vec_PtrFree( vCands2 );
+    // solve the graph problem
+    Nwk_ManGraphPrepare( p );
+    Nwk_ManGraphSolve( p );
+    vResult = p->vPairs; p->vPairs = NULL;
+    Nwk_ManGraphFree( p );
+    return vResult;
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+