1 /* ========================================================================== */
2 /* === CHOLMOD/MATLAB/septree mexFunction =================================== */
3 /* ========================================================================== */
4
5 /* -----------------------------------------------------------------------------
6 * CHOLMOD/MATLAB Module. Copyright (C) 2005-2006, Timothy A. Davis
7 * http://www.suitesparse.com
8 * MATLAB(tm) is a Trademark of The MathWorks, Inc.
9 * METIS is Copyrighted by G. Karypis
10 * -------------------------------------------------------------------------- */
11
12 /* Prune a separator tree.
13 *
14 * Usage:
15 *
16 * [cp_new, cmember_new] = septree (cp, cmember, nd_oksep, nd_small) ;
17 *
18 * cp and cmember are outputs of the nesdis mexFunction.
19 *
20 * cmember(i)=c means that node i is in component
21 * c, where c is in the range of 1 to the number of components. length(cp) is
22 * the number of components found. cp is the separator tree; cp(c) is the
23 * parent of component c, or 0 if c is a root. There can be anywhere from
24 * 1 to n components, where n is the number of rows of A, A*A', or A'*A.
25 *
26 * On output, cp_new and cmember_new are the new tree and graph-to-tree mapping.
27 * A subtree is collapsed into a single node if the number of nodes in the
28 * separator is > nd_oksep times the total size of the subtree, or if the
29 * subtree has fewer than nd_small nodes.
30 *
31 * Requires the CHOLMOD Partition Module.
32 */
33
34 #include "cholmod_matlab.h"
35
mexFunction(int nargout,mxArray * pargout[],int nargin,const mxArray * pargin[])36 void mexFunction
37 (
38 int nargout,
39 mxArray *pargout [ ],
40 int nargin,
41 const mxArray *pargin [ ]
42 )
43 {
44 #ifndef NPARTITION
45 double *p ;
46 Long *Cmember, *CParent ;
47 cholmod_common Common, *cm ;
48 double nd_oksep ;
49 Long nd_small, nc, n, c, j, nc_new ;
50
51 /* ---------------------------------------------------------------------- */
52 /* start CHOLMOD and set defaults */
53 /* ---------------------------------------------------------------------- */
54
55 cm = &Common ;
56 cholmod_l_start (cm) ;
57 sputil_config (SPUMONI, cm) ;
58
59 /* ---------------------------------------------------------------------- */
60 /* get inputs */
61 /* ---------------------------------------------------------------------- */
62
63 if (nargout > 2 || nargin != 4)
64 {
65 mexErrMsgTxt ("Usage: [cp_new, cmember_new] = "
66 "septree (cp, cmember, nd_oksep, nd_small)") ;
67 }
68
69 nc = mxGetNumberOfElements (pargin [0]) ;
70 n = mxGetNumberOfElements (pargin [1]) ;
71 nd_oksep = mxGetScalar (pargin [2]) ;
72 nd_small = mxGetScalar (pargin [3]) ;
73
74 if (n < nc)
75 {
76 mexErrMsgTxt ("invalid inputs") ;
77 }
78
79 CParent = cholmod_l_malloc (nc, sizeof (Long), cm) ;
80 Cmember = cholmod_l_malloc (n, sizeof (Long), cm) ;
81
82 p = mxGetPr (pargin [0]) ;
83 for (c = 0 ; c < nc ; c++)
84 {
85 CParent [c] = p [c] - 1 ;
86 if (CParent [c] < EMPTY || CParent [c] > nc)
87 {
88 mexErrMsgTxt ("cp invalid") ;
89 }
90 }
91
92 p = mxGetPr (pargin [1]) ;
93 for (j = 0 ; j < n ; j++)
94 {
95 Cmember [j] = p [j] - 1 ;
96 if (Cmember [j] < 0 || Cmember [j] > nc)
97 {
98 mexErrMsgTxt ("cmember invalid") ;
99 }
100 }
101
102 /* ---------------------------------------------------------------------- */
103 /* collapse the tree */
104 /* ---------------------------------------------------------------------- */
105
106 nc_new = cholmod_l_collapse_septree (n, nc, nd_oksep, nd_small, CParent,
107 Cmember, cm) ;
108 if (nc_new < 0)
109 {
110 mexErrMsgTxt ("septree failed") ;
111 return ;
112 }
113
114 /* ---------------------------------------------------------------------- */
115 /* return CParent and Cmember */
116 /* ---------------------------------------------------------------------- */
117
118 pargout [0] = sputil_put_int (CParent, nc_new, 1) ;
119 if (nargout > 1)
120 {
121 pargout [1] = sputil_put_int (Cmember, n, 1) ;
122 }
123
124 /* ---------------------------------------------------------------------- */
125 /* free workspace */
126 /* ---------------------------------------------------------------------- */
127
128 cholmod_l_free (nc, sizeof (Long), CParent, cm) ;
129 cholmod_l_free (n, sizeof (Long), Cmember, cm) ;
130 cholmod_l_finish (cm) ;
131 cholmod_l_print_common (" ", cm) ;
132 /*
133 if (cm->malloc_count != 0) mexErrMsgTxt ("!") ;
134 */
135 #else
136 mexErrMsgTxt ("CHOLMOD Partition Module not installed\n") ;
137 #endif
138 }
139