1 /* 2 * Copyright 1997, Regents of the University of Minnesota 3 * 4 * proto.h 5 * 6 * This file contains header files 7 * 8 * Started 10/19/95 9 * George 10 * 11 * $Id: proto.h,v 1.1 1998/11/27 17:59:28 karypis Exp $ 12 * 13 */ 14 15 /* balance.c */ 16 void Balance2Way(CtrlType *, GraphType *, int *, float); 17 void Bnd2WayBalance(CtrlType *, GraphType *, int *); 18 void General2WayBalance(CtrlType *, GraphType *, int *); 19 20 /* bucketsort.c */ 21 void BucketSortKeysInc(int, int, idxtype *, idxtype *, idxtype *); 22 23 /* ccgraph.c */ 24 void CreateCoarseGraph(CtrlType *, GraphType *, int, idxtype *, idxtype *); 25 void CreateCoarseGraphNoMask(CtrlType *, GraphType *, int, idxtype *, idxtype *); 26 void CreateCoarseGraph_NVW(CtrlType *, GraphType *, int, idxtype *, idxtype *); 27 GraphType *SetUpCoarseGraph(GraphType *, int, int); 28 void ReAdjustMemory(GraphType *, GraphType *, int); 29 30 /* coarsen.c */ 31 GraphType *Coarsen2Way(CtrlType *, GraphType *); 32 33 /* compress.c */ 34 void CompressGraph(CtrlType *, GraphType *, int, idxtype *, idxtype *, idxtype *, idxtype *); 35 void PruneGraph(CtrlType *, GraphType *, int, idxtype *, idxtype *, idxtype *, float); 36 37 /* debug.c */ 38 int ComputeCut(GraphType *, idxtype *); 39 float ComputeRAsso(GraphType *graph, idxtype *where, int npart); 40 float ComputeNCut(GraphType *, idxtype *, int); 41 int CheckBnd(GraphType *); 42 int CheckBnd2(GraphType *); 43 int CheckNodeBnd(GraphType *, int); 44 int CheckRInfo(RInfoType *); 45 int CheckNodePartitionParams(GraphType *); 46 int IsSeparable(GraphType *); 47 48 /* estmem.c */ 49 void METIS_EstimateMemory(int *, idxtype *, idxtype *, int *, int *, int *); 50 void EstimateCFraction(int, idxtype *, idxtype *, float *, float *); 51 int ComputeCoarseGraphSize(int, idxtype *, idxtype *, int, idxtype *, idxtype *, idxtype *); 52 53 /* fm.c */ 54 void FM_2WayEdgeRefine(CtrlType *, GraphType *, int *, int); 55 56 /* fortran.c */ 57 void Change2CNumbering(int, idxtype *, idxtype *); 58 void Change2FNumbering(int, idxtype *, idxtype *, idxtype *); 59 void Change2FNumbering2(int, idxtype *, idxtype *); 60 void Change2FNumberingOrder(int, idxtype *, idxtype *, idxtype *, idxtype *); 61 void ChangeMesh2CNumbering(int, idxtype *); 62 void ChangeMesh2FNumbering(int, idxtype *, int, idxtype *, idxtype *); 63 void ChangeMesh2FNumbering2(int, idxtype *, int, int, idxtype *, idxtype *); 64 65 /* frename.c */ 66 void METIS_PARTGRAPHRECURSIVE(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 67 void metis_partgraphrecursive(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 68 void metis_partgraphrecursive_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 69 void metis_partgraphrecursive__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 70 void METIS_WPARTGRAPHRECURSIVE(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 71 void metis_wpartgraphrecursive(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 72 void metis_wpartgraphrecursive_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 73 void metis_wpartgraphrecursive__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 74 void METIS_PARTGRAPHKWAY(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 75 void metis_partgraphkway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 76 void metis_partgraphkway_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 77 void metis_partgraphkway__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 78 void METIS_WPARTGRAPHKWAY(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 79 void metis_wpartgraphkway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 80 void metis_wpartgraphkway_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 81 void metis_wpartgraphkway__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 82 void METIS_EDGEND(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 83 void metis_edgend(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 84 void metis_edgend_(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 85 void metis_edgend__(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 86 void METIS_NODEND(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 87 void metis_nodend(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 88 void metis_nodend_(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 89 void metis_nodend__(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 90 void METIS_NODEWND(int *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 91 void metis_nodewnd(int *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 92 void metis_nodewnd_(int *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 93 void metis_nodewnd__(int *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 94 void METIS_PARTMESHNODAL(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 95 void metis_partmeshnodal(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 96 void metis_partmeshnodal_(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 97 void metis_partmeshnodal__(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 98 void METIS_PARTMESHDUAL(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 99 void metis_partmeshdual(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 100 void metis_partmeshdual_(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 101 void metis_partmeshdual__(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 102 void METIS_MESHTONODAL(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 103 void metis_meshtonodal(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 104 void metis_meshtonodal_(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 105 void metis_meshtonodal__(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 106 void METIS_MESHTODUAL(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 107 void metis_meshtodual(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 108 void metis_meshtodual_(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 109 void metis_meshtodual__(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 110 void METIS_ESTIMATEMEMORY(int *, idxtype *, idxtype *, int *, int *, int *); 111 void metis_estimatememory(int *, idxtype *, idxtype *, int *, int *, int *); 112 void metis_estimatememory_(int *, idxtype *, idxtype *, int *, int *, int *); 113 void metis_estimatememory__(int *, idxtype *, idxtype *, int *, int *, int *); 114 void METIS_MCPARTGRAPHRECURSIVE(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 115 void metis_mcpartgraphrecursive(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 116 void metis_mcpartgraphrecursive_(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 117 void metis_mcpartgraphrecursive__(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 118 void METIS_MCPARTGRAPHKWAY(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 119 void metis_mcpartgraphkway(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 120 void metis_mcpartgraphkway_(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 121 void metis_mcpartgraphkway__(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 122 void METIS_PARTGRAPHVKWAY(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 123 void metis_partgraphvkway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 124 void metis_partgraphvkway_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 125 void metis_partgraphvkway__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 126 void METIS_WPARTGRAPHVKWAY(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 127 void metis_wpartgraphvkway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 128 void metis_wpartgraphvkway_(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 129 void metis_wpartgraphvkway__(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 130 131 /* graph.c */ 132 void SetUpGraph(GraphType *, int, int, int, idxtype *, idxtype *, idxtype *, idxtype *, int); 133 void SetUpGraphKway(GraphType *, int, idxtype *, idxtype *); 134 void SetUpGraph2(GraphType *, int, int, idxtype *, idxtype *, float *, idxtype *); 135 void VolSetUpGraph(GraphType *, int, int, int, idxtype *, idxtype *, idxtype *, idxtype *, int); 136 void RandomizeGraph(GraphType *); 137 int IsConnectedSubdomain(CtrlType *, GraphType *, int, int); 138 int IsConnected(CtrlType *, GraphType *, int); 139 int IsConnected2(GraphType *, int); 140 int FindComponents(CtrlType *, GraphType *, idxtype *, idxtype *); 141 142 /* initpart.c */ 143 void Init2WayPartition(CtrlType *, GraphType *, int *, float); 144 void InitSeparator(CtrlType *, GraphType *, float); 145 void GrowBisection(CtrlType *, GraphType *, int *, float); 146 void GrowBisectionNode(CtrlType *, GraphType *, float); 147 void RandomBisection(CtrlType *, GraphType *, int *, float); 148 149 /* mlkkm.c */ 150 /*void spectralInit(CtrlType *, GraphType *, int *);*/ 151 void spectralInit(GraphType *, int, int *, int *); 152 void MLKKM_PartGraphKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, int *, idxtype *, int); 153 void MLKKM_WPartGraphKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, float *, int *, int *, idxtype *, int); 154 int MLKKMPartitioning(CtrlType *, GraphType *, int, int, idxtype *, float *, float); 155 156 /* weighted kernel k-means */ 157 void Compute_Weights(CtrlType *ctrl, GraphType *graph, idxtype *w); 158 void transform_matrix(CtrlType *ctrl, GraphType *graph, idxtype *w, float *adjwgt); 159 void transform_matrix_half(CtrlType *ctrl, GraphType *graph, idxtype *w, float *adjwgt); 160 void pingpong(CtrlType *, GraphType *, int , int , float *, float, int ); 161 void Weighted_kernel_k_means(CtrlType *, GraphType *, int , idxtype *, float *, float ); 162 void remove_empty_clusters_l1(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor); 163 void remove_empty_clusters_l2(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *w, float *tpwgts, float ubfactor); 164 /*void Weighted_kernel_k_means(CtrlType *, GraphType *, int , idxtype *, float *, float *, float ); */ 165 void MLKKMRefine(CtrlType *, GraphType *, GraphType *, int, int, float *, float); 166 float onePoint_move(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int ii); 167 void move1Point2EmptyCluster(GraphType *graph, int nparts, idxtype *sum, idxtype *squared_sum, idxtype *w, idxtype *self_sim, int **linearTerm, int k); 168 int local_search(CtrlType *, GraphType *, int, int, idxtype *, float *, float); 169 /*int local_search(CtrlType *, GraphType *, int, int, idxtype *, float *, float *, float); */ 170 /* kmetis.c */ 171 void METIS_PartGraphKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 172 void METIS_WPartGraphKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 173 int MlevelKWayPartitioning(CtrlType *, GraphType *, int, idxtype *, float *, float); 174 175 /* kvmetis.c */ 176 void METIS_PartGraphVKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 177 void METIS_WPartGraphVKway(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 178 int MlevelVolKWayPartitioning(CtrlType *, GraphType *, int, idxtype *, float *, float); 179 180 /* kwayfm.c */ 181 void Random_KWayEdgeRefine(CtrlType *, GraphType *, int, float *, float, int, int); 182 void Greedy_KWayEdgeRefine(CtrlType *, GraphType *, int, float *, float, int); 183 void Greedy_KWayEdgeBalance(CtrlType *, GraphType *, int, float *, float, int); 184 185 /* kwayrefine.c */ 186 void RefineKWay(CtrlType *, GraphType *, GraphType *, int, float *, float); 187 void AllocateKWayPartitionMemory(CtrlType *, GraphType *, int); 188 void ComputeKWayPartitionParams(CtrlType *, GraphType *, int); 189 void ProjectKWayPartition(CtrlType *, GraphType *, int); 190 int IsBalanced(idxtype *, int, float *, float); 191 void ComputeKWayBoundary(CtrlType *, GraphType *, int); 192 void ComputeKWayBalanceBoundary(CtrlType *, GraphType *, int); 193 194 /* kwayvolfm.c */ 195 void Random_KWayVolRefine(CtrlType *, GraphType *, int, float *, float, int, int); 196 void Random_KWayVolRefineMConn(CtrlType *, GraphType *, int, float *, float, int, int); 197 void Greedy_KWayVolBalance(CtrlType *, GraphType *, int, float *, float, int); 198 void Greedy_KWayVolBalanceMConn(CtrlType *, GraphType *, int, float *, float, int); 199 void KWayVolUpdate(CtrlType *, GraphType *, int, int, int, idxtype *, idxtype *, idxtype *); 200 void ComputeKWayVolume(GraphType *, int, idxtype *, idxtype *, idxtype *); 201 int ComputeVolume(GraphType *, idxtype *); 202 void CheckVolKWayPartitionParams(CtrlType *, GraphType *, int); 203 void ComputeVolSubDomainGraph(GraphType *, int, idxtype *, idxtype *); 204 void EliminateVolSubDomainEdges(CtrlType *, GraphType *, int, float *); 205 void EliminateVolComponents(CtrlType *, GraphType *, int, float *, float); 206 207 /* kwayvolrefine.c */ 208 void RefineVolKWay(CtrlType *, GraphType *, GraphType *, int, float *, float); 209 void AllocateVolKWayPartitionMemory(CtrlType *, GraphType *, int); 210 void ComputeVolKWayPartitionParams(CtrlType *, GraphType *, int); 211 void ComputeKWayVolGains(CtrlType *, GraphType *, int); 212 void ProjectVolKWayPartition(CtrlType *, GraphType *, int); 213 void ComputeVolKWayBoundary(CtrlType *, GraphType *, int); 214 void ComputeVolKWayBalanceBoundary(CtrlType *, GraphType *, int); 215 216 /* match.c */ 217 void Match_HEMN(CtrlType *ctrl, GraphType *graph); 218 void Match_RM(CtrlType *, GraphType *); 219 void Match_RM_NVW(CtrlType *, GraphType *); 220 void Match_HEM(CtrlType *, GraphType *); 221 void Match_SHEM(CtrlType *, GraphType *); 222 void Match_SHEMN(CtrlType *, GraphType *); 223 224 /* mbalance.c */ 225 void MocBalance2Way(CtrlType *, GraphType *, float *, float); 226 void MocGeneral2WayBalance(CtrlType *, GraphType *, float *, float); 227 228 /* mbalance2.c */ 229 void MocBalance2Way2(CtrlType *, GraphType *, float *, float *); 230 void MocGeneral2WayBalance2(CtrlType *, GraphType *, float *, float *); 231 void SelectQueue3(int, float *, float *, int *, int *, PQueueType [MAXNCON][2], float *); 232 233 /* mcoarsen.c */ 234 GraphType *MCCoarsen2Way(CtrlType *, GraphType *); 235 236 /* memory.c */ 237 void AllocateWorkSpace(CtrlType *, GraphType *, int); 238 void FreeWorkSpace(CtrlType *, GraphType *); 239 int WspaceAvail(CtrlType *); 240 idxtype *idxwspacemalloc(CtrlType *, int); 241 void idxwspacefree(CtrlType *, int); 242 float *fwspacemalloc(CtrlType *, int); 243 void fwspacefree(CtrlType *, int); 244 GraphType *CreateGraph(void); 245 void InitGraph(GraphType *); 246 void FreeGraph(GraphType *); 247 248 /* mesh.c */ 249 void METIS_MeshToDual(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 250 void METIS_MeshToNodal(int *, int *, idxtype *, int *, int *, idxtype *, idxtype *); 251 void GENDUALMETIS(int, int, int, idxtype *, idxtype *, idxtype *adjncy); 252 void TRINODALMETIS(int, int, idxtype *, idxtype *, idxtype *adjncy); 253 void TETNODALMETIS(int, int, idxtype *, idxtype *, idxtype *adjncy); 254 void HEXNODALMETIS(int, int, idxtype *, idxtype *, idxtype *adjncy); 255 void QUADNODALMETIS(int, int, idxtype *, idxtype *, idxtype *adjncy); 256 257 /* meshpart.c */ 258 void METIS_PartMeshNodal(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 259 void METIS_PartMeshDual(int *, int *, idxtype *, int *, int *, int *, int *, idxtype *, idxtype *); 260 261 /* mfm.c */ 262 void MocFM_2WayEdgeRefine(CtrlType *, GraphType *, float *, int); 263 void SelectQueue(int, float *, float *, int *, int *, PQueueType [MAXNCON][2]); 264 int BetterBalance(int, float *, float *, float *); 265 float Compute2WayHLoadImbalance(int, float *, float *); 266 void Compute2WayHLoadImbalanceVec(int, float *, float *, float *); 267 268 /* mfm2.c */ 269 void MocFM_2WayEdgeRefine2(CtrlType *, GraphType *, float *, float *, int); 270 void SelectQueue2(int, float *, float *, int *, int *, PQueueType [MAXNCON][2], float *); 271 int IsBetter2wayBalance(int, float *, float *, float *); 272 273 /* mincover.o */ 274 void MinCover(idxtype *, idxtype *, int, int, idxtype *, int *); 275 int MinCover_Augment(idxtype *, idxtype *, int, idxtype *, idxtype *, idxtype *, int); 276 void MinCover_Decompose(idxtype *, idxtype *, int, int, idxtype *, idxtype *, int *); 277 void MinCover_ColDFS(idxtype *, idxtype *, int, idxtype *, idxtype *, int); 278 void MinCover_RowDFS(idxtype *, idxtype *, int, idxtype *, idxtype *, int); 279 280 /* minitpart.c */ 281 void MocInit2WayPartition(CtrlType *, GraphType *, float *, float); 282 void MocGrowBisection(CtrlType *, GraphType *, float *, float); 283 void MocRandomBisection(CtrlType *, GraphType *, float *, float); 284 void MocInit2WayBalance(CtrlType *, GraphType *, float *); 285 int SelectQueueOneWay(int, float *, float *, int, PQueueType [MAXNCON][2]); 286 287 /* minitpart2.c */ 288 void MocInit2WayPartition2(CtrlType *, GraphType *, float *, float *); 289 void MocGrowBisection2(CtrlType *, GraphType *, float *, float *); 290 void MocGrowBisectionNew2(CtrlType *, GraphType *, float *, float *); 291 void MocInit2WayBalance2(CtrlType *, GraphType *, float *, float *); 292 int SelectQueueOneWay2(int, float *, PQueueType [MAXNCON][2], float *); 293 294 /* mkmetis.c */ 295 void METIS_mCPartGraphKway(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 296 int MCMlevelKWayPartitioning(CtrlType *, GraphType *, int, idxtype *, float *); 297 298 /* mkwayfmh.c */ 299 void MCRandom_KWayEdgeRefineHorizontal(CtrlType *, GraphType *, int, float *, int); 300 void MCGreedy_KWayEdgeBalanceHorizontal(CtrlType *, GraphType *, int, float *, int); 301 int AreAllHVwgtsBelow(int, float, float *, float, float *, float *); 302 int AreAllHVwgtsAbove(int, float, float *, float, float *, float *); 303 void ComputeHKWayLoadImbalance(int, int, float *, float *); 304 int MocIsHBalanced(int, int, float *, float *); 305 int IsHBalanceBetterFT(int, int, float *, float *, float *, float *); 306 int IsHBalanceBetterTT(int, int, float *, float *, float *, float *); 307 308 /* mkwayrefine.c */ 309 void MocRefineKWayHorizontal(CtrlType *, GraphType *, GraphType *, int, float *); 310 void MocAllocateKWayPartitionMemory(CtrlType *, GraphType *, int); 311 void MocComputeKWayPartitionParams(CtrlType *, GraphType *, int); 312 void MocProjectKWayPartition(CtrlType *, GraphType *, int); 313 void MocComputeKWayBalanceBoundary(CtrlType *, GraphType *, int); 314 315 /* mmatch.c */ 316 void MCMatch_RM(CtrlType *, GraphType *); 317 void MCMatch_HEM(CtrlType *, GraphType *); 318 void MCMatch_SHEM(CtrlType *, GraphType *); 319 void MCMatch_SHEBM(CtrlType *, GraphType *, int); 320 void MCMatch_SBHEM(CtrlType *, GraphType *, int); 321 float BetterVBalance(int, int, float *, float *, float *); 322 int AreAllVwgtsBelowFast(int, float *, float *, float); 323 324 /* mmd.c */ 325 void genmmd(int, idxtype *, idxtype *, idxtype *, idxtype *, int , idxtype *, idxtype *, idxtype *, idxtype *, int, int *); 326 void mmdelm(int, idxtype *xadj, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, int, int); 327 int mmdint(int, idxtype *xadj, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *); 328 void mmdnum(int, idxtype *, idxtype *, idxtype *); 329 void mmdupd(int, int, idxtype *, idxtype *, int, int *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, int, int *tag); 330 331 /* mpmetis.c */ 332 void METIS_mCPartGraphRecursive(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 333 void METIS_mCHPartGraphRecursive(int *, int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 334 void METIS_mCPartGraphRecursiveInternal(int *, int *, idxtype *, idxtype *, float *, idxtype *, int *, int *, int *, idxtype *); 335 void METIS_mCHPartGraphRecursiveInternal(int *, int *, idxtype *, idxtype *, float *, idxtype *, int *, float *, int *, int *, idxtype *); 336 int MCMlevelRecursiveBisection(CtrlType *, GraphType *, int, idxtype *, float, int); 337 int MCHMlevelRecursiveBisection(CtrlType *, GraphType *, int, idxtype *, float *, int); 338 void MCMlevelEdgeBisection(CtrlType *, GraphType *, float *, float); 339 void MCHMlevelEdgeBisection(CtrlType *, GraphType *, float *, float *); 340 341 /* mrefine.c */ 342 void MocRefine2Way(CtrlType *, GraphType *, GraphType *, float *, float); 343 void MocAllocate2WayPartitionMemory(CtrlType *, GraphType *); 344 void MocCompute2WayPartitionParams(CtrlType *, GraphType *); 345 void MocProject2WayPartition(CtrlType *, GraphType *); 346 347 /* mrefine2.c */ 348 void MocRefine2Way2(CtrlType *, GraphType *, GraphType *, float *, float *); 349 350 /* mutil.c */ 351 int AreAllVwgtsBelow(int, float, float *, float, float *, float); 352 int AreAnyVwgtsBelow(int, float, float *, float, float *, float); 353 int AreAllVwgtsAbove(int, float, float *, float, float *, float); 354 float ComputeLoadImbalance(int, int, float *, float *); 355 int AreAllBelow(int, float *, float *); 356 357 /* myqsort.c */ 358 void iidxsort(int, idxtype *); 359 void iintsort(int, int *); 360 void ikeysort(int, KeyValueType *); 361 void ikeyvalsort(int, KeyValueType *); 362 363 /* ometis.c */ 364 void METIS_EdgeND(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 365 void METIS_NodeND(int *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 366 void METIS_NodeWND(int *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *, idxtype *); 367 void MlevelNestedDissection(CtrlType *, GraphType *, idxtype *, float, int); 368 void MlevelNestedDissectionCC(CtrlType *, GraphType *, idxtype *, float, int); 369 void MlevelNodeBisectionMultiple(CtrlType *, GraphType *, int *, float); 370 void MlevelNodeBisection(CtrlType *, GraphType *, int *, float); 371 void SplitGraphOrder(CtrlType *, GraphType *, GraphType *, GraphType *); 372 void MMDOrder(CtrlType *, GraphType *, idxtype *, int); 373 int SplitGraphOrderCC(CtrlType *, GraphType *, GraphType *, int, idxtype *, idxtype *); 374 375 /* parmetis.c */ 376 void METIS_PartGraphKway2(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 377 void METIS_WPartGraphKway2(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 378 void METIS_NodeNDP(int, idxtype *, idxtype *, int, int *, idxtype *, idxtype *, idxtype *); 379 void MlevelNestedDissectionP(CtrlType *, GraphType *, idxtype *, int, int, int, idxtype *); 380 void METIS_NodeComputeSeparator(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *); 381 void METIS_EdgeComputeSeparator(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, idxtype *); 382 383 /* pmetis.c */ 384 void METIS_PartGraphRecursive(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, int *, int *, idxtype *); 385 void METIS_WPartGraphRecursive(int *, idxtype *, idxtype *, idxtype *, idxtype *, int *, int *, int *, float *, int *, int *, idxtype *); 386 int MlevelRecursiveBisection(CtrlType *, GraphType *, int, idxtype *, float *, float, int); 387 void MlevelEdgeBisection(CtrlType *, GraphType *, int *, float); 388 void SplitGraphPart(CtrlType *, GraphType *, GraphType *, GraphType *); 389 void SetUpSplitGraph(GraphType *, GraphType *, int, int); 390 391 /* pqueue.c */ 392 void PQueueInit(CtrlType *ctrl, PQueueType *, int, int); 393 void PQueueReset(PQueueType *); 394 void PQueueFree(CtrlType *ctrl, PQueueType *); 395 int PQueueGetSize(PQueueType *); 396 int PQueueInsert(PQueueType *, int, int); 397 int PQueueDelete(PQueueType *, int, int); 398 int PQueueUpdate(PQueueType *, int, int, int); 399 void PQueueUpdateUp(PQueueType *, int, int, int); 400 int PQueueGetMax(PQueueType *); 401 int PQueueSeeMax(PQueueType *); 402 int PQueueGetKey(PQueueType *); 403 int CheckHeap(PQueueType *); 404 405 /* refine.c */ 406 void Refine2Way(CtrlType *, GraphType *, GraphType *, int *, float ubfactor); 407 void Allocate2WayPartitionMemory(CtrlType *, GraphType *); 408 void Compute2WayPartitionParams(CtrlType *, GraphType *); 409 void Project2WayPartition(CtrlType *, GraphType *); 410 411 /* separator.c */ 412 void ConstructSeparator(CtrlType *, GraphType *, float); 413 void ConstructMinCoverSeparator0(CtrlType *, GraphType *, float); 414 void ConstructMinCoverSeparator(CtrlType *, GraphType *, float); 415 416 /* sfm.c */ 417 void FM_2WayNodeRefine(CtrlType *, GraphType *, float, int); 418 void FM_2WayNodeRefineEqWgt(CtrlType *, GraphType *, int); 419 void FM_2WayNodeRefine_OneSided(CtrlType *, GraphType *, float, int); 420 void FM_2WayNodeBalance(CtrlType *, GraphType *, float); 421 int ComputeMaxNodeGain(int, idxtype *, idxtype *, idxtype *); 422 423 /* srefine.c */ 424 void Refine2WayNode(CtrlType *, GraphType *, GraphType *, float); 425 void Allocate2WayNodePartitionMemory(CtrlType *, GraphType *); 426 void Compute2WayNodePartitionParams(CtrlType *, GraphType *); 427 void Project2WayNodePartition(CtrlType *, GraphType *); 428 429 /* stat.c */ 430 void ComputePartitionInfo(GraphType *, int, idxtype *); 431 void ComputePartitionInfoBipartite(GraphType *, int, idxtype *); 432 void ComputePartitionBalance(GraphType *, int, idxtype *, float *); 433 float ComputeElementBalance(int, int, idxtype *); 434 435 /* subdomains.c */ 436 void Random_KWayEdgeRefineMConn(CtrlType *, GraphType *, int, float *, float, int, int); 437 void Greedy_KWayEdgeBalanceMConn(CtrlType *, GraphType *, int, float *, float, int); 438 void PrintSubDomainGraph(GraphType *, int, idxtype *); 439 void ComputeSubDomainGraph(GraphType *, int, idxtype *, idxtype *); 440 void EliminateSubDomainEdges(CtrlType *, GraphType *, int, float *); 441 void MoveGroupMConn(CtrlType *, GraphType *, idxtype *, idxtype *, int, int, int, idxtype *); 442 void EliminateComponents(CtrlType *, GraphType *, int, float *, float); 443 void MoveGroup(CtrlType *, GraphType *, int, int, int, idxtype *, idxtype *); 444 445 /* timing.c */ 446 void InitTimers(CtrlType *); 447 void PrintTimers(CtrlType *); 448 double seconds(void); 449 450 /* util.c */ 451 void print_help(char *program_name); 452 void clusterSize(GraphType * graph, int *clustersize); 453 void sparse2dense(GraphType * graph, double * dense, float *); 454 void extractfilename(char *path, char *name); 455 void graclus_errexit(char *,...); 456 #ifndef DMALLOC 457 Chains *chainmalloc(int n, char *msg); 458 float **f2malloc(int n, int m, char *msg); 459 int **i2malloc(int, int, char *); 460 int *imalloc(int, char *); 461 idxtype *idxmalloc(int, char *); 462 float *fmalloc(int, char *); 463 int *ismalloc(int, int, char *); 464 idxtype *idxsmalloc(int, idxtype, char *); 465 void *GKmalloc(int, char *); 466 #endif 467 void GKfree(void **,...); 468 int *iset(int n, int val, int *x); 469 idxtype *idxset(int n, idxtype val, idxtype *x); 470 float *sset(int n, float val, float *x); 471 int iamax(int, int *); 472 int idxamax(int, idxtype *); 473 int idxamax_strd(int, idxtype *, int); 474 int samax(int, float *); 475 int samax2(int, float *); 476 int idxamin(int, idxtype *); 477 int samin(int, float *); 478 int idxsum(int, idxtype *); 479 int idxsum_strd(int, idxtype *, int); 480 void idxadd(int, idxtype *, idxtype *); 481 int charsum(int, char *); 482 int isum(int, int *); 483 float ssum(int, float *); 484 float ssum_strd(int n, float *x, int); 485 void sscale(int n, float, float *x); 486 float snorm2(int, float *); 487 float sdot(int n, float *, float *); 488 void saxpy(int, float, float *, int, float *, int); 489 void RandomPermute(int, idxtype *, int); 490 void RandomInit(int n, int k, idxtype *label); 491 int ispow2(int); 492 void InitRandom(int); 493 int log2_metis(int); 494 495 496 497 498 499 500 501 502 503 504 /*************************************************************** 505 * Programs Directory 506 ****************************************************************/ 507 508 /* io.c */ 509 void ReadCoarsestInit(GraphType *graph, char *filename, int *wgtflag); 510 void WriteCoarsestGraph(GraphType *graph, char *filename, int *wgtflag); 511 void CreateGraph_Matlab(GraphType *graph, double* idata, double* jdata, double* edgeval, int vtx, int edges, int *wgtflag); 512 void ReadGraph(GraphType *, char *, int *); 513 void WritePartition(char *, idxtype *, int, int); 514 void WriteMeshPartition(char *, int, int, idxtype *, int, idxtype *); 515 void WritePermutation(char *, idxtype *, int); 516 int CheckGraph(GraphType *); 517 idxtype *ReadMesh(char *, int *, int *, int *); 518 void WriteGraph(char *, int, idxtype *, idxtype *); 519 520 /* smbfactor.c */ 521 void ComputeFillIn(GraphType *, idxtype *); 522 idxtype ComputeFillIn2(GraphType *, idxtype *); 523 int smbfct(int, idxtype *, idxtype *, idxtype *, idxtype *, idxtype *, int *, idxtype *, idxtype *, int *); 524 525 526 /*************************************************************** 527 * Test Directory 528 ****************************************************************/ 529 void Test_PartGraph(int, idxtype *, idxtype *); 530 int VerifyPart(int, idxtype *, idxtype *, idxtype *, idxtype *, int, int, idxtype *); 531 int VerifyWPart(int, idxtype *, idxtype *, idxtype *, idxtype *, int, float *, int, idxtype *); 532 void Test_PartGraphV(int, idxtype *, idxtype *); 533 int VerifyPartV(int, idxtype *, idxtype *, idxtype *, idxtype *, int, int, idxtype *); 534 int VerifyWPartV(int, idxtype *, idxtype *, idxtype *, idxtype *, int, float *, int, idxtype *); 535 void Test_PartGraphmC(int, idxtype *, idxtype *); 536 int VerifyPartmC(int, int, idxtype *, idxtype *, idxtype *, idxtype *, int, float *, int, idxtype *); 537 void Test_ND(int, idxtype *, idxtype *); 538 int VerifyND(int, idxtype *, idxtype *); 539 540