← Back to branch summary

~elmer-csc-ubuntu/elmercsc/devel

« back to all changes in this revision

Viewing changes to elmergrid/src/metis/mrefine.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/mrefine.c
1
 
/*
2
 
 * Copyright 1997, Regents of the University of Minnesota
3
 
 *
4
 
 * refine.c
5
 
 *
6
 
 * This file contains the driving routines for multilevel refinement
7
 
 *
8
 
 * Started 7/24/97
9
 
 * George
10
 
 *
11
 
 * $Id: mrefine.c,v 1.1 2005/05/17 10:21:56 vierinen Exp $
12
 
 */
13
 
 
14
 
#include <metis.h>
15
 
 
16
 
 
17
 
/*************************************************************************
18
 
* This function is the entry point of refinement
19
 
**************************************************************************/
20
 
void MocRefine2Way(CtrlType *ctrl, GraphType *orggraph, GraphType *graph, float *tpwgts, float ubfactor)
21
 
{
22
 
  int i;
23
 
  float tubvec[MAXNCON];
24
 
 
25
 
  for (i=0; i<graph->ncon; i++)
26
 
    tubvec[i] = 1.0;
27
 
 
28
 
  IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->UncoarsenTmr));
29
 
 
30
 
  /* Compute the parameters of the coarsest graph */
31
 
  MocCompute2WayPartitionParams(ctrl, graph);
32
 
 
33
 
  for (;;) {
34
 
    ASSERT(CheckBnd(graph));
35
 
 
36
 
    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->RefTmr));
37
 
    switch (ctrl->RType) {
38
 
      case RTYPE_FM:
39
 
        MocBalance2Way(ctrl, graph, tpwgts, 1.03);
40
 
        MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 8); 
41
 
        break;
42
 
      case 2:
43
 
        MocBalance2Way(ctrl, graph, tpwgts, 1.03);
44
 
        MocFM_2WayEdgeRefine2(ctrl, graph, tpwgts, tubvec, 8); 
45
 
        break;
46
 
      default:
47
 
        errexit("Unknown refinement type: %d\n", ctrl->RType);
48
 
    }
49
 
    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->RefTmr));
50
 
 
51
 
    if (graph == orggraph)
52
 
      break;
53
 
 
54
 
    graph = graph->finer;
55
 
    IFSET(ctrl->dbglvl, DBG_TIME, starttimer(ctrl->ProjectTmr));
56
 
    MocProject2WayPartition(ctrl, graph);
57
 
    IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->ProjectTmr));
58
 
  }
59
 
 
60
 
  MocBalance2Way(ctrl, graph, tpwgts, 1.01);
61
 
  MocFM_2WayEdgeRefine(ctrl, graph, tpwgts, 8); 
62
 
 
63
 
  IFSET(ctrl->dbglvl, DBG_TIME, stoptimer(ctrl->UncoarsenTmr));
64
 
}
65
 
 
66
 
 
67
 
/*************************************************************************
68
 
* This function allocates memory for 2-way edge refinement
69
 
**************************************************************************/
70
 
void MocAllocate2WayPartitionMemory(CtrlType *ctrl, GraphType *graph)
71
 
{
72
 
  int nvtxs, ncon;
73
 
 
74
 
  nvtxs = graph->nvtxs;
75
 
  ncon = graph->ncon;
76
 
 
77
 
  graph->rdata = idxmalloc(5*nvtxs, "Allocate2WayPartitionMemory: rdata");
78
 
  graph->where          = graph->rdata;
79
 
  graph->id             = graph->rdata + nvtxs;
80
 
  graph->ed             = graph->rdata + 2*nvtxs;
81
 
  graph->bndptr         = graph->rdata + 3*nvtxs;
82
 
  graph->bndind         = graph->rdata + 4*nvtxs;
83
 
 
84
 
  graph->npwgts         = fmalloc(2*ncon, "npwgts");
85
 
}
86
 
 
87
 
 
88
 
/*************************************************************************
89
 
* This function computes the initial id/ed 
90
 
**************************************************************************/
91
 
void MocCompute2WayPartitionParams(CtrlType *ctrl, GraphType *graph)
92
 
{
93
 
  int i, j, k, l, nvtxs, ncon, nbnd, mincut;
94
 
  idxtype *xadj, *adjncy, *adjwgt;
95
 
  float *nvwgt, *npwgts;
96
 
  idxtype *id, *ed, *where;
97
 
  idxtype *bndptr, *bndind;
98
 
  int me, other;
99
 
 
100
 
  nvtxs = graph->nvtxs;
101
 
  ncon = graph->ncon;
102
 
  xadj = graph->xadj;
103
 
  nvwgt = graph->nvwgt;
104
 
  adjncy = graph->adjncy;
105
 
  adjwgt = graph->adjwgt;
106
 
 
107
 
  where = graph->where;
108
 
  npwgts = sset(2*ncon, 0.0, graph->npwgts);
109
 
  id = idxset(nvtxs, 0, graph->id);
110
 
  ed = idxset(nvtxs, 0, graph->ed);
111
 
  bndptr = idxset(nvtxs, -1, graph->bndptr);
112
 
  bndind = graph->bndind;
113
 
 
114
 
 
115
 
  /*------------------------------------------------------------
116
 
  / Compute now the id/ed degrees
117
 
  /------------------------------------------------------------*/
118
 
  nbnd = mincut = 0;
119
 
  for (i=0; i<nvtxs; i++) {
120
 
    ASSERT(where[i] >= 0 && where[i] <= 1);
121
 
    me = where[i];
122
 
    saxpy(ncon, 1.0, nvwgt+i*ncon, 1, npwgts+me*ncon, 1);
123
 
 
124
 
    for (j=xadj[i]; j<xadj[i+1]; j++) {
125
 
      if (me == where[adjncy[j]])
126
 
        id[i] += adjwgt[j];
127
 
      else
128
 
        ed[i] += adjwgt[j];
129
 
    }
130
 
 
131
 
    if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
132
 
      mincut += ed[i];
133
 
      bndptr[i] = nbnd;
134
 
      bndind[nbnd++] = i;
135
 
    }
136
 
  }
137
 
 
138
 
  graph->mincut = mincut/2;
139
 
  graph->nbnd = nbnd;
140
 
 
141
 
}
142
 
 
143
 
 
144
 
 
145
 
/*************************************************************************
146
 
* This function projects a partition, and at the same time computes the
147
 
* parameters for refinement.
148
 
**************************************************************************/
149
 
void MocProject2WayPartition(CtrlType *ctrl, GraphType *graph)
150
 
{
151
 
  int i, j, k, nvtxs, nbnd, me;
152
 
  idxtype *xadj, *adjncy, *adjwgt, *adjwgtsum;
153
 
  idxtype *cmap, *where, *id, *ed, *bndptr, *bndind;
154
 
  idxtype *cwhere, *cid, *ced, *cbndptr;
155
 
  GraphType *cgraph;
156
 
 
157
 
  cgraph = graph->coarser;
158
 
  cwhere = cgraph->where;
159
 
  cid = cgraph->id;
160
 
  ced = cgraph->ed;
161
 
  cbndptr = cgraph->bndptr;
162
 
 
163
 
  nvtxs = graph->nvtxs;
164
 
  cmap = graph->cmap;
165
 
  xadj = graph->xadj;
166
 
  adjncy = graph->adjncy;
167
 
  adjwgt = graph->adjwgt;
168
 
  adjwgtsum = graph->adjwgtsum;
169
 
 
170
 
  MocAllocate2WayPartitionMemory(ctrl, graph);
171
 
 
172
 
  where = graph->where;
173
 
  id = idxset(nvtxs, 0, graph->id);
174
 
  ed = idxset(nvtxs, 0, graph->ed);
175
 
  bndptr = idxset(nvtxs, -1, graph->bndptr);
176
 
  bndind = graph->bndind;
177
 
 
178
 
 
179
 
  /* Go through and project partition and compute id/ed for the nodes */
180
 
  for (i=0; i<nvtxs; i++) {
181
 
    k = cmap[i];
182
 
    where[i] = cwhere[k];
183
 
    cmap[i] = cbndptr[k];
184
 
  }
185
 
 
186
 
  for (nbnd=0, i=0; i<nvtxs; i++) {
187
 
    me = where[i];
188
 
 
189
 
    id[i] = adjwgtsum[i];
190
 
 
191
 
    if (xadj[i] == xadj[i+1]) {
192
 
      bndptr[i] = nbnd;
193
 
      bndind[nbnd++] = i;
194
 
    }
195
 
    else {
196
 
      if (cmap[i] != -1) { /* If it is an interface node. Note that cmap[i] = cbndptr[cmap[i]] */
197
 
        for (j=xadj[i]; j<xadj[i+1]; j++) {
198
 
          if (me != where[adjncy[j]])
199
 
            ed[i] += adjwgt[j];
200
 
        }
201
 
        id[i] -= ed[i];
202
 
 
203
 
        if (ed[i] > 0 || xadj[i] == xadj[i+1]) {
204
 
          bndptr[i] = nbnd;
205
 
          bndind[nbnd++] = i;
206
 
        }
207
 
      }
208
 
    }
209
 
  }
210
 
 
211
 
  graph->mincut = cgraph->mincut;
212
 
  graph->nbnd = nbnd;
213
 
  scopy(2*graph->ncon, cgraph->npwgts, graph->npwgts);
214
 
 
215
 
  FreeGraph(graph->coarser);
216
 
  graph->coarser = NULL;
217
 
 
218
 
}
219