Amesos Package Browser (Single Doxygen Collection)
Development
src
SuiteSparse
CAMD
Source
amesos_camd_l_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
/* This file should make the long int version of CAMD */
15
#define DLONG 1
16
17
#include "
amesos_camd_internal.h
"
18
19
GLOBAL
Int
CAMD_postorder
20
(
21
Int
j,
/* start at node j, a root of the assembly tree */
22
Int
k,
/* on input, next node is the kth node */
23
Int
n,
/* normal nodes 0 to n-1, place-holder node n */
24
Int
head [],
/* head of link list of children of each node */
25
Int
next [],
/* next[i] is the next child after i in link list */
26
Int
post [],
/* postordering, post [k] = p if p is the kth node */
27
Int
stack []
/* recursion stack */
28
)
29
{
30
int
i, p, top = 0 ;
31
stack [0] = j ;
/* place j on the stack, maybe place-holder node n */
32
while
(top >= 0)
/* while (stack is not empty) */
33
{
34
p = stack [top] ;
/* p = top of stack */
35
i = head [p] ;
/* i = youngest child of p */
36
if
(i == -1)
37
{
38
top-- ;
/* p has no unordered children left */
39
if
(p != n)
40
{
41
/* node p is the kth postordered node. Do not postorder the
42
* place-holder node n, which is the root of a subtree
43
* containing all dense and empty nodes. */
44
post [k++] = p ;
45
}
46
}
47
else
48
{
49
head [p] = next [i] ;
/* remove i from children of p */
50
stack [++top] = i ;
/* start dfs on child node i */
51
}
52
}
53
return
(k) ;
54
}
CAMD_postorder
GLOBAL Int CAMD_postorder(Int j, Int k, Int n, Int head [], Int next [], Int post [], Int stack [])
Definition:
amesos_camd_l_postorder.c:20
GLOBAL
#define GLOBAL
Definition:
amesos_amd_internal.h:143
Int
#define Int
Definition:
amesos_amd_internal.h:190
amesos_camd_internal.h
Generated by
1.8.14