← Back to branch summary

~elmer-csc-ubuntu/elmercsc/devel

« back to all changes in this revision

Viewing changes to elmergrid/src/metis/kvmetis.c

  • Committer: GitHub
  • Author(s): Peter R
  • Date: 2017-10-04 13:47:14 UTC
  • mfrom: (575.1.17)
  • Revision ID: git-v1:91780af69137b74ec539fedc4ad70c9ec52d732a
Merge pull request #115 from ElmerCSC/metis_update

Updated to new Metis API for devel branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
elmergrid/src/metis/kvmetis.c
1
 
/*
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 2005/05/17 10:21:40 vierinen 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
 
  int i, j;
48
 
  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*log2int(*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
 
  int i, j, nvtxs, tvwgt, tpwgts2[2];
98
 
  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