1 files changed, 148 insertions, 0 deletions
diff --git a/src/base/abc/abcDfs.c b/src/base/abc/abcDfs.c
index 31a6e8b9..097ee92d 100644
--- a/src/base/abc/abcDfs.c
+++ b/src/base/abc/abcDfs.c
@@ -206,6 +206,37 @@ void Abc_NtkDfsReverse_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
     Vec_PtrPush( vNodes, pNode );
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if the ordering of nodes is DFS.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+bool Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pNode;
+    int i;
+    // set the traversal ID
+    Abc_NtkIncrementTravId( pNtk );
+    // mark the CIs
+    Abc_NtkForEachCi( pNtk, pNode, i )
+        Abc_NodeSetTravIdCurrent( pNode );
+    // go through the nodes
+    Abc_NtkForEachNode( pNtk, pNode, i )
+    {
+        if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pNode)) )
+            return 0;
+        if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pNode)) )
+            return 0;
+        Abc_NodeSetTravIdCurrent( pNode );
+    }
+    return 1;
+}
 
 /**Function*************************************************************
 
@@ -573,6 +604,123 @@ bool Abc_NtkIsAcyclic_rec( Abc_Obj_t * pNode )
     return 1;
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Analyses choice nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NodeSetChoiceLevel_rec( Abc_Obj_t * pNode, int fMaximum )
+{
+    Abc_Obj_t * pTemp;
+    int Level1, Level2, Level, LevelE;
+    // skip the visited node
+    if ( Abc_NodeIsTravIdCurrent( pNode ) )
+        return (int)pNode->pCopy;
+    Abc_NodeSetTravIdCurrent( pNode );
+    // compute levels of the children nodes
+    Level1 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pNode), fMaximum );
+    Level2 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin1(pNode), fMaximum );
+    Level  = 1 + ABC_MAX( Level1, Level2 );
+    if ( pNode->pData )
+    {
+        LevelE = Abc_NodeSetChoiceLevel_rec( pNode->pData, fMaximum );
+        if ( fMaximum )
+            Level = ABC_MAX( Level, LevelE );
+        else
+            Level = ABC_MIN( Level, LevelE );
+        // set the level of all equivalent nodes to be the same minimum
+        for ( pTemp = pNode->pData; pTemp; pTemp = pTemp->pData )
+            pTemp->pCopy = (void *)Level;
+    }
+    pNode->pCopy = (void *)Level;
+    return Level;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Resets the levels of the nodes in the choice graph.]
+
+  Description [Makes the level of the choice nodes to be equal to the
+  maximum of the level of the nodes in the equivalence class. This way
+  sorting by level leads to the reverse topological order, which is
+  needed for the required time computation.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_AigSetChoiceLevels( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pObj;
+    int i, LevelMax, LevelCur;
+    assert( Abc_NtkIsStrash(pNtk) );
+    // set the new travid counter
+    Abc_NtkIncrementTravId( pNtk );
+    // set levels of the CI and constant
+    Abc_NtkForEachCi( pNtk, pObj, i )
+    {
+        Abc_NodeSetTravIdCurrent( pObj );
+        pObj->pCopy = NULL;
+    }
+    pObj = Abc_AigConst1( pNtk->pManFunc );
+    Abc_NodeSetTravIdCurrent( pObj );
+    pObj->pCopy = NULL;
+    // set levels of all other nodes
+    LevelMax = 0;
+    Abc_NtkForEachCo( pNtk, pObj, i )
+    {
+        LevelCur = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pObj), 1 );
+        LevelMax = ABC_MAX( LevelMax, LevelCur );
+    }
+    return LevelMax;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns nodes by level from the smallest to the largest.]
+
+  Description [Correctly handles the case of choice nodes, by first
+  spreading them out across several levels and then collecting.]
+               
+  SideEffects [What happens with dangling nodes???]
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_AigGetLevelizedOrder( Abc_Ntk_t * pNtk, int fCollectCis )
+{
+    Vec_Ptr_t * vNodes, * vLevels;
+    Abc_Obj_t * pNode, ** ppHead;
+    int LevelMax, i;
+    assert( Abc_NtkIsStrash(pNtk) );
+    // set the correct levels
+    Abc_NtkCleanCopy( pNtk );
+    LevelMax = Abc_AigSetChoiceLevels( pNtk );
+    // relink nodes by level
+    vLevels = Vec_PtrStart( LevelMax + 1 );
+    Abc_NtkForEachNode( pNtk, pNode, i )
+    {
+        ppHead = ((Abc_Obj_t **)vLevels->pArray) + (int)pNode->pCopy;
+        pNode->pCopy = *ppHead;
+        *ppHead = pNode;
+    }
+    // recollect nodes
+    vNodes = Vec_PtrStart( Abc_NtkNodeNum(pNtk) );
+    Vec_PtrForEachEntryStart( vLevels, pNode, i, !fCollectCis )
+        for ( ; pNode; pNode = pNode->pCopy )
+            Vec_PtrPush( vNodes, pNode );
+    Vec_PtrFree( vLevels );
+    return vNodes;
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////