1 /* ========================================================================== */ 2 /* === Include/cholmod_partition.h ========================================== */ 3 /* ========================================================================== */ 4 5 /* ----------------------------------------------------------------------------- 6 * CHOLMOD/Include/cholmod_partition.h. 7 * Copyright (C) 2005-2013, Univ. of Florida. Author: Timothy A. Davis 8 * CHOLMOD/Include/cholmod_partition.h is licensed under Version 2.1 of the GNU 9 * Lesser General Public License. See lesser.txt for a text of the license. 10 * CHOLMOD is also available under other licenses; contact authors for details. 11 * -------------------------------------------------------------------------- */ 12 13 /* CHOLMOD Partition module. 14 * 15 * Graph partitioning and graph-partition-based orderings. Includes an 16 * interface to CCOLAMD and CSYMAMD, constrained minimum degree ordering 17 * methods which order a matrix following constraints determined via nested 18 * dissection. 19 * 20 * These functions require METIS: 21 * cholmod_nested_dissection CHOLMOD nested dissection ordering 22 * cholmod_metis METIS nested dissection ordering (METIS_NodeND) 23 * cholmod_bisect graph partitioner (currently based on METIS) 24 * cholmod_metis_bisector direct interface to METIS_ComputeVertexSeparator 25 * 26 * Requires the Core and Cholesky modules, and three packages: METIS, CAMD, 27 * and CCOLAMD. Optionally used by the Cholesky module. 28 * 29 * Note that METIS does not have a version that uses SuiteSparse_long integers. 30 * If you try to use cholmod_nested_dissection, cholmod_metis, cholmod_bisect, 31 * or cholmod_metis_bisector on a matrix that is too large, an error code will 32 * be returned. METIS does have an "idxtype", which could be redefined as 33 * SuiteSparse_long, if you wish to edit METIS or use compile-time flags to 34 * redefine idxtype. 35 */ 36 37 #ifndef CHOLMOD_PARTITION_H 38 #define CHOLMOD_PARTITION_H 39 40 #include "cholmod_core.h" 41 #include "cholmod_camd.h" 42 43 /* -------------------------------------------------------------------------- */ 44 /* cholmod_nested_dissection */ 45 /* -------------------------------------------------------------------------- */ 46 47 /* Order A, AA', or A(:,f)*A(:,f)' using CHOLMOD's nested dissection method 48 * (METIS's node bisector applied recursively to compute the separator tree 49 * and constraint sets, followed by CCOLAMD using the constraints). Usually 50 * finds better orderings than METIS_NodeND, but takes longer. 51 */ 52 53 SuiteSparse_long cholmod_nested_dissection /* returns # of components */ 54 ( 55 /* ---- input ---- */ 56 cholmod_sparse *A, /* matrix to order */ 57 int *fset, /* subset of 0:(A->ncol)-1 */ 58 size_t fsize, /* size of fset */ 59 /* ---- output --- */ 60 int *Perm, /* size A->nrow, output permutation */ 61 int *CParent, /* size A->nrow. On output, CParent [c] is the parent 62 * of component c, or EMPTY if c is a root, and where 63 * c is in the range 0 to # of components minus 1 */ 64 int *Cmember, /* size A->nrow. Cmember [j] = c if node j of A is 65 * in component c */ 66 /* --------------- */ 67 cholmod_common *Common 68 ) ; 69 70 SuiteSparse_long cholmod_l_nested_dissection (cholmod_sparse *, 71 SuiteSparse_long *, size_t, SuiteSparse_long *, SuiteSparse_long *, 72 SuiteSparse_long *, cholmod_common *) ; 73 74 /* -------------------------------------------------------------------------- */ 75 /* cholmod_metis */ 76 /* -------------------------------------------------------------------------- */ 77 78 /* Order A, AA', or A(:,f)*A(:,f)' using METIS_NodeND. */ 79 80 int cholmod_metis 81 ( 82 /* ---- input ---- */ 83 cholmod_sparse *A, /* matrix to order */ 84 int *fset, /* subset of 0:(A->ncol)-1 */ 85 size_t fsize, /* size of fset */ 86 int postorder, /* if TRUE, follow with etree or coletree postorder */ 87 /* ---- output --- */ 88 int *Perm, /* size A->nrow, output permutation */ 89 /* --------------- */ 90 cholmod_common *Common 91 ) ; 92 93 int cholmod_l_metis (cholmod_sparse *, SuiteSparse_long *, size_t, int, 94 SuiteSparse_long *, cholmod_common *) ; 95 96 /* -------------------------------------------------------------------------- */ 97 /* cholmod_bisect */ 98 /* -------------------------------------------------------------------------- */ 99 100 /* Finds a node bisector of A, A*A', A(:,f)*A(:,f)'. */ 101 102 SuiteSparse_long cholmod_bisect /* returns # of nodes in separator */ 103 ( 104 /* ---- input ---- */ 105 cholmod_sparse *A, /* matrix to bisect */ 106 int *fset, /* subset of 0:(A->ncol)-1 */ 107 size_t fsize, /* size of fset */ 108 int compress, /* if TRUE, compress the graph first */ 109 /* ---- output --- */ 110 int *Partition, /* size A->nrow. Node i is in the left graph if 111 * Partition [i] = 0, the right graph if 1, and in the 112 * separator if 2. */ 113 /* --------------- */ 114 cholmod_common *Common 115 ) ; 116 117 SuiteSparse_long cholmod_l_bisect (cholmod_sparse *, SuiteSparse_long *, 118 size_t, int, SuiteSparse_long *, cholmod_common *) ; 119 120 /* -------------------------------------------------------------------------- */ 121 /* cholmod_metis_bisector */ 122 /* -------------------------------------------------------------------------- */ 123 124 /* Find a set of nodes that bisects the graph of A or AA' (direct interface 125 * to METIS_ComputeVertexSeperator). */ 126 127 SuiteSparse_long cholmod_metis_bisector /* returns separator size */ 128 ( 129 /* ---- input ---- */ 130 cholmod_sparse *A, /* matrix to bisect */ 131 int *Anw, /* size A->nrow, node weights, can be NULL, */ 132 /* which means the graph is unweighted. */ 133 int *Aew, /* size nz, edge weights (silently ignored). */ 134 /* This option was available with METIS 4, but not */ 135 /* in METIS 5. This argument is now unused, but */ 136 /* it remains for backward compatibilty, so as not */ 137 /* to change the API for cholmod_metis_bisector. */ 138 /* ---- output --- */ 139 int *Partition, /* size A->nrow */ 140 /* --------------- */ 141 cholmod_common *Common 142 ) ; 143 144 SuiteSparse_long cholmod_l_metis_bisector (cholmod_sparse *, 145 SuiteSparse_long *, SuiteSparse_long *, SuiteSparse_long *, 146 cholmod_common *) ; 147 148 /* -------------------------------------------------------------------------- */ 149 /* cholmod_collapse_septree */ 150 /* -------------------------------------------------------------------------- */ 151 152 /* Collapse nodes in a separator tree. */ 153 154 SuiteSparse_long cholmod_collapse_septree 155 ( 156 /* ---- input ---- */ 157 size_t n, /* # of nodes in the graph */ 158 size_t ncomponents, /* # of nodes in the separator tree (must be <= n) */ 159 double nd_oksep, /* collapse if #sep >= nd_oksep * #nodes in subtree */ 160 size_t nd_small, /* collapse if #nodes in subtree < nd_small */ 161 /* ---- in/out --- */ 162 int *CParent, /* size ncomponents; from cholmod_nested_dissection */ 163 int *Cmember, /* size n; from cholmod_nested_dissection */ 164 /* --------------- */ 165 cholmod_common *Common 166 ) ; 167 168 SuiteSparse_long cholmod_l_collapse_septree (size_t, size_t, double, size_t, 169 SuiteSparse_long *, SuiteSparse_long *, cholmod_common *) ; 170 171 #endif 172