1 | /* |
---|
2 | * Copyright 1997, Regents of the University of Minnesota |
---|
3 | * |
---|
4 | * mkmetis.c |
---|
5 | * |
---|
6 | * This file contains the top level routines for the multilevel k-way partitioning |
---|
7 | * algorithm KMETIS. |
---|
8 | * |
---|
9 | * Started 7/28/97 |
---|
10 | * George |
---|
11 | * |
---|
12 | * $Id: mkmetis.c,v 1.2 1998/11/27 18:25:09 karypis Exp $ |
---|
13 | * |
---|
14 | */ |
---|
15 | |
---|
16 | #include <metis.h> |
---|
17 | |
---|
18 | |
---|
19 | |
---|
20 | /************************************************************************* |
---|
21 | * This function is the entry point for KWMETIS |
---|
22 | **************************************************************************/ |
---|
23 | void METIS_mCPartGraphKway(int *nvtxs, int *ncon, idxtype *xadj, idxtype *adjncy, |
---|
24 | idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, |
---|
25 | int *nparts, float *rubvec, int *options, int *edgecut, |
---|
26 | idxtype *part) |
---|
27 | { |
---|
28 | int i, j; |
---|
29 | GraphType graph; |
---|
30 | CtrlType ctrl; |
---|
31 | |
---|
32 | if (*numflag == 1) |
---|
33 | Change2CNumbering(*nvtxs, xadj, adjncy); |
---|
34 | |
---|
35 | SetUpGraph(&graph, OP_KMETIS, *nvtxs, *ncon, xadj, adjncy, vwgt, adjwgt, *wgtflag); |
---|
36 | |
---|
37 | if (options[0] == 0) { /* Use the default parameters */ |
---|
38 | ctrl.CType = McKMETIS_CTYPE; |
---|
39 | ctrl.IType = McKMETIS_ITYPE; |
---|
40 | ctrl.RType = McKMETIS_RTYPE; |
---|
41 | ctrl.dbglvl = McKMETIS_DBGLVL; |
---|
42 | } |
---|
43 | else { |
---|
44 | ctrl.CType = options[OPTION_CTYPE]; |
---|
45 | ctrl.IType = options[OPTION_ITYPE]; |
---|
46 | ctrl.RType = options[OPTION_RTYPE]; |
---|
47 | ctrl.dbglvl = options[OPTION_DBGLVL]; |
---|
48 | } |
---|
49 | ctrl.optype = OP_KMETIS; |
---|
50 | ctrl.CoarsenTo = amax((*nvtxs)/(20*log2(*nparts)), 30*(*nparts)); |
---|
51 | |
---|
52 | ctrl.nmaxvwgt = 1.5/(1.0*ctrl.CoarsenTo); |
---|
53 | |
---|
54 | InitRandom(-1); |
---|
55 | |
---|
56 | AllocateWorkSpace(&ctrl, &graph, *nparts); |
---|
57 | |
---|
58 | IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl)); |
---|
59 | IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr)); |
---|
60 | |
---|
61 | *edgecut = MCMlevelKWayPartitioning(&ctrl, &graph, *nparts, part, rubvec); |
---|
62 | |
---|
63 | IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr)); |
---|
64 | IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl)); |
---|
65 | |
---|
66 | FreeWorkSpace(&ctrl, &graph); |
---|
67 | |
---|
68 | if (*numflag == 1) |
---|
69 | Change2FNumbering(*nvtxs, xadj, adjncy, part); |
---|
70 | } |
---|
71 | |
---|
72 | |
---|
73 | /************************************************************************* |
---|
74 | * This function takes a graph and produces a bisection of it |
---|
75 | **************************************************************************/ |
---|
76 | int MCMlevelKWayPartitioning(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part, |
---|
77 | float *rubvec) |
---|
78 | { |
---|
79 | int i, j, nvtxs; |
---|
80 | GraphType *cgraph; |
---|
81 | int options[10], edgecut; |
---|
82 | |
---|
83 | cgraph = MCCoarsen2Way(ctrl, graph); |
---|
84 | |
---|
85 | IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr)); |
---|
86 | MocAllocateKWayPartitionMemory(ctrl, cgraph, nparts); |
---|
87 | |
---|
88 | options[0] = 1; |
---|
89 | options[OPTION_CTYPE] = MATCH_SBHEM_INFNORM; |
---|
90 | options[OPTION_ITYPE] = IPART_RANDOM; |
---|
91 | options[OPTION_RTYPE] = RTYPE_FM; |
---|
92 | options[OPTION_DBGLVL] = 0; |
---|
93 | |
---|
94 | /* Determine what you will use as the initial partitioner, based on tolerances */ |
---|
95 | for (i=0; i<graph->ncon; i++) { |
---|
96 | if (rubvec[i] > 1.2) |
---|
97 | break; |
---|
98 | } |
---|
99 | if (i == graph->ncon) |
---|
100 | METIS_mCPartGraphRecursiveInternal(&cgraph->nvtxs, &cgraph->ncon, |
---|
101 | cgraph->xadj, cgraph->adjncy, cgraph->nvwgt, cgraph->adjwgt, &nparts, |
---|
102 | options, &edgecut, cgraph->where); |
---|
103 | else |
---|
104 | METIS_mCHPartGraphRecursiveInternal(&cgraph->nvtxs, &cgraph->ncon, |
---|
105 | cgraph->xadj, cgraph->adjncy, cgraph->nvwgt, cgraph->adjwgt, &nparts, |
---|
106 | rubvec, options, &edgecut, cgraph->where); |
---|
107 | |
---|
108 | |
---|
109 | IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr)); |
---|
110 | IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial %d-way partitioning cut: %d\n", nparts, edgecut)); |
---|
111 | |
---|
112 | IFSET(ctrl->dbglvl, DBG_KWAYPINFO, ComputePartitionInfo(cgraph, nparts, cgraph->where)); |
---|
113 | |
---|
114 | MocRefineKWayHorizontal(ctrl, graph, cgraph, nparts, rubvec); |
---|
115 | |
---|
116 | idxcopy(graph->nvtxs, graph->where, part); |
---|
117 | |
---|
118 | GKfree(&graph->nvwgt, &graph->npwgts, &graph->gdata, &graph->rdata, LTERM); |
---|
119 | |
---|
120 | return graph->mincut; |
---|
121 | |
---|
122 | } |
---|
123 | |
---|