Amesos Package Browser (Single Doxygen Collection)
Development
src
SuiteSparse
CAMD
Source
amesos_camd_postorder.c
Go to the documentation of this file.
1
/* ========================================================================= */
2
/* === CAMD_postorder ====================================================== */
3
/* ========================================================================= */
4
5
/* ------------------------------------------------------------------------- */
6
/* CAMD, Copyright (c) Timothy A. Davis, Yanqing Chen, */
7
/* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
8
/* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
9
/* web: http://www.cise.ufl.edu/research/sparse/camd */
10
/* ------------------------------------------------------------------------- */
11
12
/* Perform a postordering (via depth-first search) of an assembly tree. */
13
14
#include "
amesos_camd_internal.h
"
15
16
GLOBAL
Int
CAMD_postorder
17
(
18
Int
j,
/* start at node j, a root of the assembly tree */
19
Int
k,
/* on input, next node is the kth node */
20
Int
n,
/* normal nodes 0 to n-1, place-holder node n */
21
Int
head [],
/* head of link list of children of each node */
22
Int
next [],
/* next[i] is the next child after i in link list */
23
Int
post [],
/* postordering, post [k] = p if p is the kth node */
24
Int
stack []
/* recursion stack */
25
)
26
{
27
int
i, p, top = 0 ;
28
stack [0] = j ;
/* place j on the stack, maybe place-holder node n */
29
while
(top >= 0)
/* while (stack is not empty) */
30
{
31
p = stack [top] ;
/* p = top of stack */
32
i = head [p] ;
/* i = youngest child of p */
33
if
(i == -1)
34
{
35
top-- ;
/* p has no unordered children left */
36
if
(p !=
n
)
37
{
38
/* node p is the kth postordered node. Do not postorder the
39
* place-holder node n, which is the root of a subtree
40
* containing all dense and empty nodes. */
41
post [k++] = p ;
42
}
43
}
44
else
45
{
46
head [p] = next [i] ;
/* remove i from children of p */
47
stack [++top] = i ;
/* start dfs on child node i */
48
}
49
}
50
return
(k) ;
51
}
GLOBAL
#define GLOBAL
Definition:
amesos_amd_internal.h:143
Int
#define Int
Definition:
amesos_amd_internal.h:190
CAMD_postorder
GLOBAL Int CAMD_postorder(Int j, Int k, Int n, Int head [], Int next [], Int post [], Int stack [])
Definition:
amesos_camd_postorder.c:17
amesos_camd_internal.h
n
int n
Generated by
1.8.14