abc/src/base/abc/abcDfs.c
/**Function*************************************************************

  Synopsis    [Detects combinational loops.]

  Description [This procedure is based on the idea suggested by Donald Chai. 
  As we traverse the network and visit the nodes, we need to distinquish 
  three types of nodes: (1) those that are visited for the first time, 
  (2) those that have been visited in this traversal but are currently not 
  on the traversal path, (3) those that have been visited and are currently 
  on the travesal path. When the node of type (3) is encountered, it means 
  that there is a combinational loop. To mark the three types of nodes, 
  two new values of the traversal IDs are used.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Function
Synopsis    [Detects combinational loops.]

Description [This procedure is based on the idea suggested by Donald Chai.
As we traverse the network and visit the nodes, we need to distinquish
three types of nodes: (1) those that are visited for the first time,
(2) those that have been visited in this traversal but are currently not
on the traversal path, (3) those that have been visited and are currently
on the travesal path. When the node of type (3) is encountered, it means
that there is a combinational loop. To mark the three types of nodes,
two new values of the traversal IDs are used.]




Function Synopsis [ Detects combinational loops . ] Description [ This procedure is based on the idea suggested by Donald Chai . As we traverse the network and visit the nodes we need to distinquish three types of nodes : ( 1 ) those that are visited for the first time ( 2 ) those that have been visited in this traversal but are currently not on the traversal path ( 3 ) those that have been visited and are currently on the travesal path . When the node of type ( 3 ) is encountered it means that there is a combinational loop . To mark the three types of nodes two new values of the traversal IDs are used . ]
int Abc_NtkIsAcyclic( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode;
    int fAcyclic;
    int i;
    Abc_NtkIncrementTravId( pNtk );   
    Abc_NtkIncrementTravId( pNtk );   
    fAcyclic = 1;
    Abc_NtkForEachCo( pNtk, pNode, i )
    {
        pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode));
        if ( Abc_NodeIsTravIdPrevious(pNode) )
            continue;
        if ( (fAcyclic = Abc_NtkIsAcyclic_rec(pNode)) )
            continue;
        fprintf( stdout, " CO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) );
        break;
    }
    return fAcyclic;
}
int Abc_NtkIsAcyclic ( Abc_Ntk_t * pNtk ) { Abc_Obj_t * pNode ; int fAcyclic ; int i ; Abc_NtkIncrementTravId ( pNtk ) ; Abc_NtkIncrementTravId ( pNtk ) ; fAcyclic = 1 ; Abc_NtkForEachCo ( pNtk , pNode , i ) { pNode = Abc_ObjFanin0Ntk ( Abc_ObjFanin0 ( pNode ) ) ; if ( Abc_NodeIsTravIdPrevious ( pNode ) ) continue ; if ( ( fAcyclic = Abc_NtkIsAcyclic_rec ( pNode ) ) ) continue ; fprintf ( stdout , " \" \" \n " , Abc_ObjName ( Abc_ObjFanout0 ( pNode ) ) ) ; break ; } return fAcyclic ; }
Function
Synopsis    [Detects combinational loops.]
Function Synopsis [ Detects combinational loops . ]
// set the traversal ID for this DFS ordering // pNode->TravId == pNet->nTravIds      means "pNode is on the path" // pNode->TravId == pNet->nTravIds - 1  means "pNode is visited but is not on the path" // pNode->TravId <  pNet->nTravIds - 1  means "pNode is not visited" // traverse the network to detect cycles // traverse the output logic cone // stop as soon as the first loop is detected