SCM

SCM Repository

[matrix] Annotation of /pkg/src/Metis/kvmetis.c
ViewVC logotype

Annotation of /pkg/src/Metis/kvmetis.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 563 - (view) (download) (as text)

1 : bates 10 /*
2 :     * Copyright 1997, Regents of the University of Minnesota
3 :     *
4 :     * kvmetis.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: kvmetis.c,v 1.1 2003/12/31 21:32:30 bates Exp $
13 :     *
14 :     */
15 :    
16 :     #include <metis.h>
17 :    
18 :    
19 :     /*************************************************************************
20 :     * This function is the entry point for KMETIS
21 :     **************************************************************************/
22 :     void METIS_PartGraphVKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
23 :     idxtype *vsize, int *wgtflag, int *numflag, int *nparts,
24 :     int *options, int *volume, idxtype *part)
25 :     {
26 :     int i;
27 :     float *tpwgts;
28 :    
29 :     tpwgts = fmalloc(*nparts, "KMETIS: tpwgts");
30 :     for (i=0; i<*nparts; i++)
31 :     tpwgts[i] = 1.0/(1.0*(*nparts));
32 :    
33 :     METIS_WPartGraphVKway(nvtxs, xadj, adjncy, vwgt, vsize, wgtflag, numflag, nparts,
34 :     tpwgts, options, volume, part);
35 :    
36 :     free(tpwgts);
37 :     }
38 :    
39 :    
40 :     /*************************************************************************
41 :     * This function is the entry point for KWMETIS
42 :     **************************************************************************/
43 :     void METIS_WPartGraphVKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt,
44 :     idxtype *vsize, int *wgtflag, int *numflag, int *nparts,
45 :     float *tpwgts, int *options, int *volume, idxtype *part)
46 :     {
47 : bates 563 /* int i, j; */
48 : bates 10 GraphType graph;
49 :     CtrlType ctrl;
50 :    
51 :     if (*numflag == 1)
52 :     Change2CNumbering(*nvtxs, xadj, adjncy);
53 :    
54 :     VolSetUpGraph(&graph, OP_KVMETIS, *nvtxs, 1, xadj, adjncy, vwgt, vsize, *wgtflag);
55 :    
56 :     if (options[0] == 0) { /* Use the default parameters */
57 :     ctrl.CType = KVMETIS_CTYPE;
58 :     ctrl.IType = KVMETIS_ITYPE;
59 :     ctrl.RType = KVMETIS_RTYPE;
60 :     ctrl.dbglvl = KVMETIS_DBGLVL;
61 :     }
62 :     else {
63 :     ctrl.CType = options[OPTION_CTYPE];
64 :     ctrl.IType = options[OPTION_ITYPE];
65 :     ctrl.RType = options[OPTION_RTYPE];
66 :     ctrl.dbglvl = options[OPTION_DBGLVL];
67 :     }
68 :     ctrl.optype = OP_KVMETIS;
69 :     ctrl.CoarsenTo = amax((*nvtxs)/(40*log2(*nparts)), 20*(*nparts));
70 :     ctrl.maxvwgt = 1.5*((graph.vwgt ? idxsum(*nvtxs, graph.vwgt) : (*nvtxs))/ctrl.CoarsenTo);
71 :    
72 :     InitRandom(-1);
73 :    
74 :     AllocateWorkSpace(&ctrl, &graph, *nparts);
75 :    
76 :     IFSET(ctrl.dbglvl, DBG_TIME, InitTimers(&ctrl));
77 :     IFSET(ctrl.dbglvl, DBG_TIME, starttimer(ctrl.TotalTmr));
78 :    
79 :     *volume = MlevelVolKWayPartitioning(&ctrl, &graph, *nparts, part, tpwgts, 1.03);
80 :    
81 :     IFSET(ctrl.dbglvl, DBG_TIME, stoptimer(ctrl.TotalTmr));
82 :     IFSET(ctrl.dbglvl, DBG_TIME, PrintTimers(&ctrl));
83 :    
84 :     FreeWorkSpace(&ctrl, &graph);
85 :    
86 :     if (*numflag == 1)
87 :     Change2FNumbering(*nvtxs, xadj, adjncy, part);
88 :     }
89 :    
90 :    
91 :     /*************************************************************************
92 :     * This function takes a graph and produces a bisection of it
93 :     **************************************************************************/
94 :     int MlevelVolKWayPartitioning(CtrlType *ctrl, GraphType *graph, int nparts, idxtype *part,
95 :     float *tpwgts, float ubfactor)
96 :     {
97 : bates 563 /* int i, j, nvtxs, tvwgt, tpwgts2[2]; */
98 : bates 10 GraphType *cgraph;
99 :     int wgtflag=3, numflag=0, options[10], edgecut;
100 :    
101 :     cgraph = Coarsen2Way(ctrl, graph);
102 :    
103 :     IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->InitPartTmr));
104 :     AllocateVolKWayPartitionMemory(ctrl, cgraph, nparts);
105 :    
106 :     options[0] = 1;
107 :     options[OPTION_CTYPE] = MATCH_SHEMKWAY;
108 :     options[OPTION_ITYPE] = IPART_GGPKL;
109 :     options[OPTION_RTYPE] = RTYPE_FM;
110 :     options[OPTION_DBGLVL] = 0;
111 :    
112 :     METIS_WPartGraphRecursive(&cgraph->nvtxs, cgraph->xadj, cgraph->adjncy, cgraph->vwgt,
113 :     cgraph->adjwgt, &wgtflag, &numflag, &nparts, tpwgts, options,
114 :     &edgecut, cgraph->where);
115 :    
116 :     IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->InitPartTmr));
117 :     IFSET(ctrl->dbglvl, DBG_IPART, printf("Initial %d-way partitioning cut: %d\n", nparts, edgecut));
118 :    
119 :     IFSET(ctrl->dbglvl, DBG_KWAYPINFO, ComputePartitionInfo(cgraph, nparts, cgraph->where));
120 :    
121 :     RefineVolKWay(ctrl, graph, cgraph, nparts, tpwgts, ubfactor);
122 :    
123 :     idxcopy(graph->nvtxs, graph->where, part);
124 :    
125 :     GKfree(&graph->gdata, &graph->rdata, LTERM);
126 :    
127 :     return graph->minvol;
128 :    
129 :     }
130 :    

root@r-forge.r-project.org
ViewVC Help
Powered by ViewVC 1.0.0  
Thanks to:
Vienna University of Economics and Business Powered By FusionForge