Amesos Package Browser (Single Doxygen Collection) Development
amesos_camd_l_postorder.c
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === CAMD_postorder ====================================================== */
00003 /* ========================================================================= */
00004 
00005 /* ------------------------------------------------------------------------- */
00006 /* CAMD, Copyright (c) Timothy A. Davis, Yanqing Chen,           */
00007 /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
00008 /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
00009 /* web: http://www.cise.ufl.edu/research/sparse/camd                         */
00010 /* ------------------------------------------------------------------------- */
00011 
00012 /* Perform a postordering (via depth-first search) of an assembly tree. */
00013 
00014 /* This file should make the long int version of CAMD */
00015 #define DLONG 1
00016 
00017 #include "amesos_camd_internal.h"
00018 
00019 GLOBAL Int CAMD_postorder
00020 (
00021     Int j,      /* start at node j, a root of the assembly tree */
00022     Int k,      /* on input, next node is the kth node */
00023     Int n,      /* normal nodes 0 to n-1, place-holder node n */
00024     Int head [],    /* head of link list of children of each node */
00025     Int next [],    /* next[i] is the next child after i in link list */
00026     Int post [],    /* postordering, post [k] = p if p is the kth node */
00027     Int stack []    /* recursion stack */
00028 )
00029 {
00030     int i, p, top = 0 ;
00031     stack [0] = j ;   /* place j on the stack, maybe place-holder node n */
00032     while (top >= 0)    /* while (stack is not empty) */
00033     {
00034   p = stack [top] ; /* p = top of stack */
00035   i = head [p] ;    /* i = youngest child of p */
00036   if (i == -1)
00037   {
00038       top-- ;   /* p has no unordered children left */
00039       if (p != n)
00040       {
00041     /* node p is the kth postordered node.  Do not postorder the
00042      * place-holder node n, which is the root of a subtree
00043      * containing all dense and empty nodes. */
00044     post [k++] = p ;
00045       }
00046   }
00047   else
00048   {
00049       head [p] = next [i] ;   /* remove i from children of p */
00050       stack [++top] = i ;     /* start dfs on child node i */
00051   }
00052     }
00053     return (k) ;
00054 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines