cs_post.c
Go to the documentation of this file.
00001 #include "cs.h"
00002 /* post order a forest */
00003 int *cs_post (const int *parent, int n)
00004 {
00005     int j, k = 0, *post, *w, *head, *next, *stack ;
00006     if (!parent) return (NULL) ;                        /* check inputs */
00007     post = cs_malloc (n, sizeof (int)) ;                /* allocate result */
00008     w = cs_malloc (3*n, sizeof (int)) ;                 /* get workspace */
00009     if (!w || !post) return (cs_idone (post, NULL, w, 0)) ;
00010     head = w ; next = w + n ; stack = w + 2*n ;
00011     for (j = 0 ; j < n ; j++) head [j] = -1 ;           /* empty linked lists */
00012     for (j = n-1 ; j >= 0 ; j--)            /* traverse nodes in reverse order*/
00013     {
00014         if (parent [j] == -1) continue ;    /* j is a root */
00015         next [j] = head [parent [j]] ;      /* add j to list of its parent */
00016         head [parent [j]] = j ;
00017     }
00018     for (j = 0 ; j < n ; j++)
00019     {
00020         if (parent [j] != -1) continue ;    /* skip j if it is not a root */
00021         k = cs_tdfs (j, k, head, next, post, stack) ;
00022     }
00023     return (cs_idone (post, NULL, w, 1)) ;  /* success; free w, return post */
00024 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines


hogman_minimal
Author(s): Maintained by Juergen Sturm
autogenerated on Wed Dec 26 2012 15:36:47