source: vis_dev/vis-2.3/src/ntk/ntkGraph.c @ 99

/**CFile***********************************************************************

  FileName    [ntkGraph.c]

  PackageName [ntk]

  Synopsis    [Routines related to the abstract graph of a network.]

  Author      [Adnan Aziz, Tom Shiple]

  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, provided that the above copyright notice and
  the following two paragraphs appear in all copies of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

******************************************************************************/

#include "ntkInt.h"

static char rcsid[] UNUSED = "$Id: ntkGraph.c,v 1.11 2005/04/16 04:24:15 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Structure declarations                                                     */
/*---------------------------------------------------------------------------*/

/**Enum************************************************************************

  Synopsis [Used to keep track of the state of a node during depth first
  search.required]

******************************************************************************/
typedef enum {
  dfsWhite_c,   /* unvisited node */
  dfsGrey_c,    /* node on "stack" */
  dfsBlack_c    /* node completely visited */
} DfsColor;


/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void RegionFindNodesRecursively(Ntk_Node_t *node, st_table *leaves, st_table *result);
static boolean NodeTestCannotReachCycle(Ntk_Node_t * node);
static boolean NodeTestCoveredByLeaves(Ntk_Node_t *node, st_table *leaves, st_table *visited);
static DfsColor NodeReadColor(Ntk_Node_t * node);
static void NodeSetColor(Ntk_Node_t * node, DfsColor color);
static void NodeSetTfoLatchList(Ntk_Node_t * node, lsList tfoLatchList);
static lsList NodeReadTfoLatchList(Ntk_Node_t * node);
static void NodeFreeTfoLatchList(Ntk_Node_t * node);
static void ListAppendList(lsList list1, lsList list2);
static lsList NodeComputeTfoLatchList(Ntk_Node_t * node);
static void NodeRecursivelyComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);
static void NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table *leafNodesTable, lsList topologicalNodeList);
static void NodeComputeTransitiveFaninNodes(Ntk_Node_t *node, st_table *resultTable, boolean stopAtLatches);

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis    [Returns array of nodes in transitive fanout of node.]

  Description [Returns array of nodes in transitive fanout of node.  If depth is
  non-zero, then only includes nodes within depth of node.  If depth is zero,
  then includes all nodes up to and including combinational outputs.]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
array_t *
Ntk_NodeComputeTransitiveFanoutNodes(
  array_t * nodeArray,
  int  depth)
{
  fail("not yet implemented");
  return(NIL(array_t));
}

/**Function********************************************************************

  Synopsis    [Returns array of nodes in transitive fanin of node.]

  Description [Returns array of nodes in transitive fanin of node.  If depth is
  non-zero, then only includes nodes within depth of node.  If depth is zero,
  then includes all nodes up to and including combinational inputs.]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
array_t *
Ntk_NodeComputeTransitiveFanInputNodes(
  array_t * nodeArray,
  int  depth)
{
  fail("not yet implemented");
  return(NIL(array_t));
}

/**Function********************************************************************

  Synopsis [Returns array of nodes in transitive fanin of nodeArray.]

  Description [Returns array of nodes in transitive fanin of nodes in
  nodeArray.  If stopAtLatches is TRUE, the search terminates at
  combinational inputs which are latches; otherwise it continues, and
  the search terminates only at primary inputs and pseudo inputs. It
  is an error if this function is called with an empty array.]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
array_t *
Ntk_NodeComputeTransitiveFaninNodes(
  Ntk_Network_t *network,
  array_t * nodeArray,
  boolean stopAtLatches,
  boolean combInputsOnly)
{
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
    NodeComputeTransitiveFaninNodes(node, resultTable, stopAtLatches );
  }
  
  st_foreach_item( resultTable, stGen, &node, NULL ){
    if ( !combInputsOnly || Ntk_NodeTestIsCombInput(node) ) 
      array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );
  
  return resultArray;
}

/**Function********************************************************************

  Synopsis    [Returns array of combinational inputs in transitive fanin
  of nodeArray.]

  Description [Returns array of nodes in transitive fanin of nodes in
  nodeArray.  If stopAtLatches is TRUE, the search terminates at
  combinational inputs which are latches; otherwise it continues, and
  the search terminates only at primary inputs and pseudo inputs. It
  is an error if this function is called with an empty array.]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
array_t *
Ntk_NodeComputeCombinationalSupport(
  Ntk_Network_t *network,
  array_t * nodeArray,
  boolean stopAtLatches )
{
  lsGen gen;
  int i;
  Ntk_Node_t *node;
  st_generator *stGen;
  st_table *resultTable = st_init_table( st_ptrcmp, st_ptrhash );
  array_t *resultArray = array_alloc( Ntk_Node_t *, 0 );

  Ntk_NetworkForEachNode( network, gen, node ) {
        NodeSetColor( node, dfsWhite_c );
  }

  arrayForEachItem( Ntk_Node_t *, nodeArray, i, node ) {
        NodeRecursivelyComputeTransitiveFaninNodes( node, resultTable, stopAtLatches );
  }

  st_foreach_item( resultTable, stGen, &node, NULL ){
        array_insert_last( Ntk_Node_t *, resultArray, node );
  }
  st_free_table( resultTable );

  return resultArray;
}


/**Function********************************************************************

  Synopsis [Return table of all nodes lying in fanin of roots, stopping
  whenever a leaf node is reached. The search also stops on nodes that pass
  the test Ntk_NodeTestIsConstant.  Note that the leaves are also present in
  the returned table.]

  SideEffects []

******************************************************************************/
st_table *
Ntk_RegionFindNodes(
  array_t *roots, 
  st_table *leaves)
{
  int i;
  st_table *result = st_init_table(st_ptrcmp, st_ptrhash);
  for (i = 0; i < array_n(roots); i++) {
    Ntk_Node_t *root = array_fetch(Ntk_Node_t *, roots, i);
    RegionFindNodesRecursively(root, leaves, result);
  }
  return result;
}

/**Function********************************************************************

  Synopsis    [Computes the set of latches that each latch transitively
  fanouts to.]

  Description [For each latch, builds a list containing those latches which
  can be transitively reached from the fanout of the latch.  If a latch
  doesn't have any latches in its TFO, then an empty list will be built. The
  dependencies are returned as a hash table mapping each latch (Ntk_Node_t *)
  to a list (lsList). It is the user's responsibility to free the returned
  hash table and the lists stored as values in the table.  NOTE: this function
  name is a misnomer because it does not compute the latches on which a given
  latch depends, but instead computes the latches to which a given latch
  fanouts.]

  SideEffects []

******************************************************************************/
st_table *
Ntk_NetworkComputeLatchDependencies(
  Ntk_Network_t * network)
{
  lsGen       gen;
  Ntk_Node_t *node;
  Ntk_Node_t *latch;
  st_table   *latchDependencies = st_init_table(st_ptrcmp, st_ptrhash);

  /*
   * Initialize the TFO latch list of each node to NULL.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetTfoLatchList(node, (lsList) NULL);
  }

  /*
   * For each latch, compute the set of latches in its TFO (including possibly
   * itself).  Accumulate this set of latches into a list, and when the list
   * is complete, store the latch and list as the key and value in the hash
   * table.
   */
  Ntk_NetworkForEachLatch(network, gen, latch) {
    int         i;
    Ntk_Node_t *fanout;
    lsList      tfoLatchList = lsCreate();  /* allocate a fresh list */

    /*
     * Get the latches in the TFO of each fanout of latch, and accumulate into
     * a list. Note that we can't call NodeComputeTfoLatchList on latch
     * itself, because latches serve as the terminal case of the recursion.
     */
    Ntk_NodeForEachFanout(latch, i, fanout) {
      lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

      ListAppendList(tfoLatchList, fanoutTfoLatchList);
    }

    st_insert(latchDependencies, (char *) latch, (char *) tfoLatchList);
    
  }

  /*
   * Free the tfoLatchList stored at the nodes.  Only nodes in the transitive
   * fanout of latches will have a non-NULL list, but we just call free
   * tfoLatchList function on each node.  Note that the lists being returned
   * in the hash table are distinct from those stored at nodes.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeFreeTfoLatchList(node);
  }

  return (latchDependencies);
}


/**Function********************************************************************

  Synopsis    [Returns 0 if a combinational cycle exists, else returns 1.]

  Description [Returns 0 if a cycle exists in the network, else returns 1.
  Latches are considered to break cycles.  If a cycle is found, then a message
  is written to error_string (see the error package) giving two nodes in the
  cycle.  Use a code fragment like the following to retrieve the error message:
  <pre>
    error_init();
    status = Ntk_NetworkTestIsAcyclic(network);
    if (status == 0) {
      (void) fprintf(fp, "%s", error_string());
    }
  </pre>]
  
  SideEffects []

  Comment     [This function implements the DFS routine outlined in Cormen,
  Leiserson, Rivest, "Introduction to Algorithms", p. 478. It has been
  specialized to just detect cycles.]

******************************************************************************/
boolean
Ntk_NetworkTestIsAcyclic(
  Ntk_Network_t * network)
{
  lsGen       gen;
  Ntk_Node_t *node;
  boolean     status = 1; /* In case network has no vertices. */

  /* The meaning of the colors is:
   *   white: node has not been visited yet
   *   grey:  node is on the "stack"
   *   black: node, and all its descendents, have been visited
   */

  /*
   * Initialize the color of each node to white.
   */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }
  
  /*
   * Recursively visit each unvisited node.  The order in which we visit the
   * nodes is immaterial.  
   */  
  Ntk_NetworkForEachNode(network, gen, node) {
    if (NodeReadColor(node) == dfsWhite_c) {
      status = NodeTestCannotReachCycle(node);
      if (status == 0) {
        /* A cycle has been found. */
        break;
      }
    }
  }

  /*
   * Colors will be left in the undef field of the nodes, but we don't care.
   */
  return (status);
}


/**Function********************************************************************

  Synopsis [Returns TRUE if leaves cover the support of roots, otherwise
  returns FALSE.]

  Description [The function takes as input a network, a hash table of nodes
  called leaves, and an array of nodes called roots. It returns TRUE if the
  nodes in leaves cover the support of the nodes in roots, otherwise it
  returns FALSE.  In other words, if there exists a combinational input in the
  transitive fanin of a root, which can be reached from the root without
  passing through a leaf, then FALSE is returned.  If FALSE is returned, then
  the message "Node b found in the support of node c" is written to
  error_string, where b is a combinational input not in leaves and c is a
  root. It is allowed that some roots are themselves leaves, and that some
  leaves are in the transitive fanin of other leaves.  Combinational cycles
  within the region defined by roots and leaves have no effect on the result.
  If TRUE is returned, then the runtime of this procedure is proportional to
  the number of nodes in the region defined by roots and leaves; if FALSE is
  returned, then the worst case is proportional to the number of nodes in the
  network.]

  Comment [The undef field is modified of some of the nodes in the network to
  which node belongs.]
  
  SideEffects []

******************************************************************************/
boolean
Ntk_NetworkTestLeavesCoverSupportOfRoots(
  Ntk_Network_t *network,
  array_t       *roots,
  st_table      *leaves)
{
  int         i;
  Ntk_Node_t *root;
  st_table   *visited = st_init_table(st_ptrcmp, st_ptrhash);
  
  /* Perform DFS from the roots.  Return FALSE upon the first failure. */
  arrayForEachItem(Ntk_Node_t *, roots, i, root) {
    boolean status = NodeTestCoveredByLeaves(root, leaves, visited);
    
    if(!status) {
      error_append(Ntk_NodeReadName(root));
      error_append(".\n");
      st_free_table(visited);
      return FALSE; 
    }
  }
  st_free_table(visited);
  return TRUE;
}


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

  Synopsis    [Computes the topological order of nodes in the network
  for a given array of root nodes and the leaf nodes.]

  Description [Depth first traversal is used from each node in the
  root node array. The search is terminated when a node in the leaf
  table is reached. It is necessary that all the root nodes eventually
  depend on the leaf nodes. The returned list contains the nodes in
  the topological order.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
lsList
Ntk_NetworkComputeTopologicalOrder(Ntk_Network_t *network, array_t
                                  *rootNodesArray, st_table
                                  *leafNodesTable) 
{
  int i;
  lsList topologicalNodeList = lsCreate();
  Ntk_Node_t *node;
  lsGen gen;
  
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetColor(node, dfsWhite_c);
  }

  for (i=0; i<array_n(rootNodesArray); i++){
    node = array_fetch(Ntk_Node_t *, rootNodesArray, i);
    NodeComputeTopologicalOrderRecursively(node, leafNodesTable,
                                           topologicalNodeList);
  }
  return topologicalNodeList;
}


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis [Recursively add all fanins of node to result, stopping at leaves
  and constants.]

  SideEffects []

******************************************************************************/
static void
RegionFindNodesRecursively(
  Ntk_Node_t *node, 
  st_table *leaves,
  st_table *result)
{
  int i;
  Ntk_Node_t *fanin;

  if (st_is_member(result, (char *) node)) {
    /* already visited this node */
    return;
  }
  else {
    /*
     * Add to table before recursing, to avoid infinite loops in presence of
     * combinational cycles.
     */
    st_insert(result, (char *) node, NIL(char));
  }
  
  
  if (!st_is_member(leaves, (char *) node) && !Ntk_NodeTestIsConstant(node)) {
    /* not a leaf; recurse */
    Ntk_NodeForEachFanin(node, i, fanin) {
      RegionFindNodesRecursively(fanin, leaves, result);
    }
  }

  return;
}

/**Function********************************************************************

  Synopsis    [Returns 1 if node cannot reach a cycle, else returns 0.]

  Description [Visits a node, and recursively all of its children, to
  determine if the node can reach a combinational cycle. If it cannot, the
  function return 1, else it returns 0.  If a cycle is found, then a message
  is written to error_string.]

  SideEffects []

******************************************************************************/
static boolean
NodeTestCannotReachCycle(
  Ntk_Node_t * node)
{
  Ntk_Node_t *fanout;
  int i;

  /*
   * Set the color of node to grey to indicate that it is on the "stack".
   */
  NodeSetColor(node, dfsGrey_c);

  Ntk_NodeForEachFanout(node, i, fanout) {
    /*
     * Traverse fanout if it is *not* a latch; latches break combinational cycles.
     */
    if (Ntk_NodeTestIsLatch(fanout) == 0) {
      DfsColor fanoutColor = NodeReadColor(fanout);

      /* 
       * If fanout is white, it has not been visited yet, so visit it, and 
       * break the search if it can reach a cycle.  Else if fanout is grey, it 
       * means that fanout is also on the stack, so a cycle has been found; 
       * thus break.  Else, the fanout is black, and there is nothing to do.
       */
      if (fanoutColor == dfsWhite_c) {
        if (NodeTestCannotReachCycle(fanout) == 0) {
          return (0);
        }
      }
      else if (fanoutColor == dfsGrey_c) {
        error_append("(");
        error_append(Ntk_NodeReadName(node));
        error_append(", ");
        error_append(Ntk_NodeReadName(fanout));
        error_append(")");
        return (0);
      } 
    }
  }

  /*
   * Set the color of node to black to indicate that it has been visited.
   */
  NodeSetColor(node, dfsBlack_c);
  
  /*
   * No cycles found from node.
   */
  return (1);
}


/**Function********************************************************************

  Synopsis [Returns FALSE if the support of node contains a combinational
  input that is not a leaf, otherwise returns TRUE.]

  Description [The function does a DFS starting from node, never going beyond
  a leaf or a node already visited. If it reaches a combinational input that
  is not a leaf it returns FALSE.  If this doesn't happen for all the fanins
  of the node, then TRUE is returned.]

  SideEffects []

  SeeAlso     [Ntk_NetworkTestLeavesCoverSupportOfRoots]

******************************************************************************/
static boolean
NodeTestCoveredByLeaves(
  Ntk_Node_t *node,
  st_table   *leaves,
  st_table   *visited)
{
  int         i;
  Ntk_Node_t *fanin;

  /*
   * If node has already been visited, just return.  Else, mark it as
   * visited. Note that it is important to mark it as visited BEFORE recursing,
   * in case combinational cycles are present.
   */
  if (st_is_member(visited, (char *) node)) {
    return TRUE;
  }
  else {
    st_insert(visited, (char *) node, NIL(char));
  }

  if (st_is_member(leaves, (char *) node)) {
    /*
     * Positive termination of recursion: if node is a leaf, then everything
     * is fine.
     */ 
    return TRUE;
  }
  else {
    /* Node is not a leaf. */
    if (Ntk_NodeTestIsCombInput(node)) {
      /*
       * Negative termination of recursion: a combinational input was reached
       * without seeing a leaf.
       */ 
      error_append("Node ");
      error_append(Ntk_NodeReadName(node));
      error_append(" found in the support of node ");
      return FALSE;
    }
    else {
      /*
       * Node is not a leaf nor a combinational input.  Recurse over fanins.
       * Return FALSE if any fanins fail the test.
       */
      Ntk_NodeForEachFanin(node, i, fanin) {
        boolean status = NodeTestCoveredByLeaves(fanin, leaves, visited);
        if (!status) {
          return FALSE;
        }
      }
      /*
       * If the loop terminates without the function returning, then each
       * fanin has already been visited and no dfsWhite_c-labelled comb input
       * can be reached from the fanins. Therefore, return TRUE.
       */
      return TRUE;
    }
  }
  
}


/**Function********************************************************************

  Synopsis    [Gets the color of a node.]

  SideEffects []

  SeeAlso     [NodeSetColor]

******************************************************************************/
static DfsColor
NodeReadColor(
  Ntk_Node_t * node)
{
  return ((DfsColor) (long) Ntk_NodeReadUndef(node));
}


/**Function********************************************************************

  Synopsis    [Sets the color of a node.]

  SideEffects []

  SeeAlso     [NodeReadColor]

******************************************************************************/
static void
NodeSetColor(
  Ntk_Node_t * node,
  DfsColor  color)
{
  Ntk_NodeSetUndef(node, (void *) (long) color);
}


/**Function********************************************************************

  Synopsis    [Sets the tfoLatchList of a node.]

  SideEffects []

  SeeAlso     [NodeReadTfoLatchList NodeFreeTfoLatchList]

******************************************************************************/
static void
NodeSetTfoLatchList(
  Ntk_Node_t * node,
  lsList  tfoLatchList)
{
  Ntk_NodeSetUndef(node, (void *) tfoLatchList);
}


/**Function********************************************************************

  Synopsis    [Gets the TfoLatchList of a node.]

  SideEffects []

  SeeAlso     [NodeSetTfoLatchList NodeFreeTfoLatchList]

******************************************************************************/
static lsList
NodeReadTfoLatchList(
  Ntk_Node_t * node)
{
  return ((lsList) Ntk_NodeReadUndef(node));
}


/**Function********************************************************************

  Synopsis    [Frees the tfoLatchList of a node.]

  Description [If the node has a non-NULL tfoLatchList, then frees the list
  and sets the tfoLatchList of node to NULL; else, does nothing.]
  
  SideEffects []

  SeeAlso     [NodeReadTfoLatchList NodeSetTfoLatchList ]

******************************************************************************/
static void
NodeFreeTfoLatchList(
  Ntk_Node_t * node)
{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  if (tfoLatchList != (lsList) NULL) {
    (void) lsDestroy(tfoLatchList, (void (*) (lsGeneric)) NULL);
    Ntk_NodeSetUndef(node, (void *) NULL);
  }
}

/**Function********************************************************************

  Synopsis    [Appends list2 to list1.]

  Description [Adds the elements of list2 to the end of list1.  The elements
  of list2 are not copied. If an element of list2 already exists in list1,
  then it is not added to the end of list1. List2 is not changed by this
  operation.]

  SideEffects [List1 is modified.]

  SeeAlso     []

******************************************************************************/
static void
ListAppendList(
  lsList  list1,
  lsList  list2)
{
  lsGen      gen;
  lsGeneric  data;
  st_table  *table1 = st_init_table(st_ptrcmp, st_ptrhash);
  
  /*
   * Load a hash table mapping each item in list1 to NULL.
   */
  gen = lsStart(list1);
  while (lsNext(gen, &data, LS_NH) == LS_OK) {
    st_insert(table1, (char *) data, (char *) NULL);
  }
  (void) lsFinish(gen);

  /*
   * For each item in list2, if it's not already present in list1, then add it
   * to the end of list1.
   */
  lsForEachItem(list2, gen, data) {
    if (st_is_member(table1, (char *) data) == 0) {
      lsNewEnd(list1, data, LS_NH);
    }
  }
  st_free_table(table1);
}


/**Function********************************************************************

  Synopsis    [Computes the set of latches in the TFO of a node.]

  Description [Computes the set of latches in the TFO of a node.  If there are
  no latches in the TFO, then an empty list is returned.  In the special case
  where the node is itself a latch, then a list containing just the node is
  returned; this is one of the terminal cases of the recursion. The other
  terminal case is a node with no immediate fanouts.]

  SideEffects []

******************************************************************************/
static lsList
NodeComputeTfoLatchList(
  Ntk_Node_t * node)
{
  lsList tfoLatchList = NodeReadTfoLatchList(node);

  /*
   * If node already has a non-NULL tfoLatchList, then just return it (this
   * can happen if the node was already visited via one of its other
   * fanins). Otherwise, create an empty list and fill it appropriately.
   */
  if (tfoLatchList != (lsList) NULL) {
    return (tfoLatchList);
  }
  else {
    tfoLatchList = lsCreate();

    if (Ntk_NodeTestIsLatch(node)) {
      /*
       * Special case; terminal condition.
       */
      lsNewEnd(tfoLatchList, (lsGeneric) node, LS_NH);
    }
    else {
      int         i;
      Ntk_Node_t *fanout;
      
      /*
       * Get the latches in the TFO of each fanout of node, and accumulate into
       * a list.
       */
      Ntk_NodeForEachFanout(node, i, fanout) {
        lsList fanoutTfoLatchList = NodeComputeTfoLatchList(fanout);

        ListAppendList(tfoLatchList, fanoutTfoLatchList);
      }
    }

    /*
     * Store the list with the node, then return the list.
     */
    NodeSetTfoLatchList(node, tfoLatchList);
    return (tfoLatchList);    
  }
}



/**Function********************************************************************

  Synopsis    [Computes the set of combinational inputs in the TFI of the node.]

  Description [Computes the set of combinational inputs in the TFI of the node.
  If stopAtLatches is TRUE, the search terminates at combinational inputs which
  are latches; otherwise it continues, and the search terminates only at primary 
  inputs and pseudo inputs.]

  SideEffects []

******************************************************************************/
static void
NodeRecursivelyComputeTransitiveFaninNodes( 
  Ntk_Node_t *node, 
  st_table *resultTable,
  boolean stopAtLatches) 
{
  int i;
  Ntk_Node_t * fanin;

  /* test if we have already started processing this node */
  if ( NodeReadColor( node ) == dfsBlack_c ) {
        return;
  }
  NodeSetColor( node, dfsBlack_c );

  if ( Ntk_NodeTestIsCombInput( node ) ) {
        st_insert( resultTable, (char *) node, (char *) 0 );
  }

  if ( Ntk_NodeTestIsInput(node) || ((stopAtLatches == TRUE)&&(Ntk_NodeTestIsLatch(node))) ) {
        return;
  }

  Ntk_NodeForEachFanin( node, i, fanin ) {
        NodeRecursivelyComputeTransitiveFaninNodes( fanin, resultTable, stopAtLatches );
  }
}



/**Function********************************************************************

  Synopsis    [Recursively performs the depth-first traversal of the
  network starting at the given node.]

  Description [Recursively performs the depth-first traversal of the
  network starting at the given node.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
static void
NodeComputeTopologicalOrderRecursively(Ntk_Node_t *node, st_table
                                       *leafNodesTable, lsList
                                       topologicalNodeList) 
{
  int i;
  Ntk_Node_t *fanin;
  
  if (NodeReadColor(node) == dfsBlack_c){
    /* Has already been put in the list. */
    return;
  }
  if (NodeReadColor(node) == dfsGrey_c){
    /* Indicates that this node is currently being processed (possibly a
       combinational loop). */
    return;
  }
  if (st_is_member(leafNodesTable, (char *)node)== 0){
    NodeSetColor(node, dfsGrey_c);
    Ntk_NodeForEachFanin(node, i, fanin){
      NodeComputeTopologicalOrderRecursively(fanin, leafNodesTable,
                                             topologicalNodeList);
    }
  }
  NodeSetColor(node, dfsBlack_c);
  lsNewEnd(topologicalNodeList, (lsGeneric)node, LS_NH);
  return;
}

/**Function********************************************************************

  Synopsis [Computes the set of nodes in the TFI of the node.]

  Description [Computes the set of nodes in the TFI of the node.  If
  stopAtLatches is TRUE, the search terminates at combinational inputs
  which are latches; otherwise it continues, and the search terminates
  only at primary inputs and pseudo inputs.]

  SideEffects []

******************************************************************************/
static void
NodeComputeTransitiveFaninNodes( 
  Ntk_Node_t *node, 
  st_table *resultTable,
  boolean stopAtLatches) 
{
  int i;
  Ntk_Node_t * fanin;
  
  /* test if we have already started processing this node */
  if (st_is_member(resultTable, node))
    return;

  st_insert(resultTable, node, (char *)(long)2);

  if (Ntk_NodeTestIsInput(node) || (stopAtLatches && Ntk_NodeTestIsLatch(node)))
    return;

  Ntk_NodeForEachFanin(node, i, fanin) {
    NodeComputeTransitiveFaninNodes(fanin, resultTable, stopAtLatches);
  }
}