← Back to branch summary

~elmer-csc-ubuntu/elmercsc/devel

« back to all changes in this revision

Viewing changes to elmergrid/src/metis-5.1.0/libmetis/mincover.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-5.1.0/libmetis/mincover.c
 
1
/*
 
2
 * Copyright 1997, Regents of the University of Minnesota
 
3
 *
 
4
 * mincover.c
 
5
 *
 
6
 * This file implements the minimum cover algorithm
 
7
 *
 
8
 * Started 8/1/97
 
9
 * George
 
10
 *
 
11
 * $Id: mincover.c 9942 2011-05-17 22:09:52Z karypis $
 
12
 */
 
13
 
 
14
#include "metislib.h"
 
15
 
 
16
/*************************************************************************
 
17
* Constants used by mincover algorithm
 
18
**************************************************************************/
 
19
#define INCOL 10
 
20
#define INROW 20
 
21
#define VC 1
 
22
#define SC 2
 
23
#define HC 3
 
24
#define VR 4
 
25
#define SR 5
 
26
#define HR 6
 
27
 
 
28
 
 
29
/*************************************************************************
 
30
* This function returns the min-cover of a bipartite graph.
 
31
* The algorithm used is due to Hopcroft and Karp as modified by Duff etal
 
32
* adj: the adjacency list of the bipartite graph
 
33
*       asize: the number of vertices in the first part of the bipartite graph
 
34
* bsize-asize: the number of vertices in the second part
 
35
*        0..(asize-1) > A vertices
 
36
*        asize..bsize > B vertices
 
37
*
 
38
* Returns:
 
39
*  cover : the actual cover (array)
 
40
*  csize : the size of the cover
 
41
**************************************************************************/
 
42
void MinCover(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *cover, idx_t *csize)
 
43
{
 
44
  idx_t i, j;
 
45
  idx_t *mate, *queue, *flag, *level, *lst;
 
46
  idx_t fptr, rptr, lstptr;
 
47
  idx_t row, maxlevel, col;
 
48
 
 
49
  mate = ismalloc(bsize, -1, "MinCover: mate");
 
50
  flag = imalloc(bsize, "MinCover: flag");
 
51
  level = imalloc(bsize, "MinCover: level");
 
52
  queue = imalloc(bsize, "MinCover: queue");
 
53
  lst = imalloc(bsize, "MinCover: lst");
 
54
 
 
55
  /* Get a cheap matching */
 
56
  for (i=0; i<asize; i++) {
 
57
    for (j=xadj[i]; j<xadj[i+1]; j++) {
 
58
      if (mate[adjncy[j]] == -1) {
 
59
        mate[i] = adjncy[j];
 
60
        mate[adjncy[j]] = i;
 
61
        break;
 
62
      }
 
63
    }
 
64
  }
 
65
 
 
66
  /* Get into the main loop */
 
67
  while (1) {
 
68
    /* Initialization */
 
69
    fptr = rptr = 0;   /* Empty Queue */
 
70
    lstptr = 0;        /* Empty List */
 
71
    for (i=0; i<bsize; i++) {
 
72
      level[i] = -1;
 
73
      flag[i] = 0;
 
74
    }
 
75
    maxlevel = bsize;
 
76
 
 
77
    /* Insert free nodes into the queue */
 
78
    for (i=0; i<asize; i++) 
 
79
      if (mate[i] == -1) {
 
80
        queue[rptr++] = i;
 
81
        level[i] = 0;
 
82
      }
 
83
 
 
84
    /* Perform the BFS */
 
85
    while (fptr != rptr) {
 
86
      row = queue[fptr++];
 
87
      if (level[row] < maxlevel) {
 
88
        flag[row] = 1;
 
89
        for (j=xadj[row]; j<xadj[row+1]; j++) {
 
90
          col = adjncy[j];
 
91
          if (!flag[col]) {  /* If this column has not been accessed yet */
 
92
            flag[col] = 1;
 
93
            if (mate[col] == -1) { /* Free column node was found */
 
94
              maxlevel = level[row];
 
95
              lst[lstptr++] = col;
 
96
            }
 
97
            else { /* This column node is matched */
 
98
              if (flag[mate[col]]) 
 
99
                printf("\nSomething wrong, flag[%"PRIDX"] is 1",mate[col]);
 
100
              queue[rptr++] = mate[col];
 
101
              level[mate[col]] = level[row] + 1;
 
102
            }
 
103
          }
 
104
        }
 
105
      } 
 
106
    }
 
107
 
 
108
    if (lstptr == 0)
 
109
      break;   /* No free columns can be reached */
 
110
 
 
111
    /* Perform restricted DFS from the free column nodes */
 
112
    for (i=0; i<lstptr; i++)
 
113
      MinCover_Augment(xadj, adjncy, lst[i], mate, flag, level, maxlevel);
 
114
  }
 
115
 
 
116
  MinCover_Decompose(xadj, adjncy, asize, bsize, mate, cover, csize);
 
117
 
 
118
  gk_free((void **)&mate, &flag, &level, &queue, &lst, LTERM);
 
119
 
 
120
}
 
121
 
 
122
 
 
123
/*************************************************************************
 
124
* This function perfoms a restricted DFS and augments matchings
 
125
**************************************************************************/
 
126
idx_t MinCover_Augment(idx_t *xadj, idx_t *adjncy, idx_t col, idx_t *mate, idx_t *flag, idx_t *level, idx_t maxlevel)
 
127
{
 
128
  idx_t i;
 
129
  idx_t row = -1;
 
130
  idx_t status;
 
131
 
 
132
  flag[col] = 2;
 
133
  for (i=xadj[col]; i<xadj[col+1]; i++) {
 
134
    row = adjncy[i];
 
135
 
 
136
    if (flag[row] == 1) { /* First time through this row node */
 
137
      if (level[row] == maxlevel) {  /* (col, row) is an edge of the G^T */
 
138
        flag[row] = 2;  /* Mark this node as being visited */
 
139
        if (maxlevel != 0)
 
140
          status = MinCover_Augment(xadj, adjncy, mate[row], mate, flag, level, maxlevel-1);
 
141
        else
 
142
          status = 1;
 
143
 
 
144
        if (status) {
 
145
          mate[col] = row;
 
146
          mate[row] = col;
 
147
          return 1;
 
148
        }
 
149
      }
 
150
    }
 
151
  }
 
152
 
 
153
  return 0;
 
154
}
 
155
 
 
156
 
 
157
 
 
158
/*************************************************************************
 
159
* This function performs a coarse decomposition and determines the 
 
160
* min-cover.
 
161
* REF: Pothen ACMTrans. on Amth Software
 
162
**************************************************************************/
 
163
void MinCover_Decompose(idx_t *xadj, idx_t *adjncy, idx_t asize, idx_t bsize, idx_t *mate, idx_t *cover, idx_t *csize)
 
164
{
 
165
  idx_t i, k;
 
166
  idx_t *where;
 
167
  idx_t card[10];
 
168
 
 
169
  where = imalloc(bsize, "MinCover_Decompose: where");
 
170
  for (i=0; i<10; i++)
 
171
    card[i] = 0;
 
172
 
 
173
  for (i=0; i<asize; i++)
 
174
    where[i] = SC;
 
175
  for (; i<bsize; i++)
 
176
    where[i] = SR;
 
177
 
 
178
  for (i=0; i<asize; i++) 
 
179
    if (mate[i] == -1)  
 
180
      MinCover_ColDFS(xadj, adjncy, i, mate, where, INCOL);
 
181
  for (; i<bsize; i++) 
 
182
    if (mate[i] == -1)  
 
183
      MinCover_RowDFS(xadj, adjncy, i, mate, where, INROW);
 
184
 
 
185
  for (i=0; i<bsize; i++) 
 
186
    card[where[i]]++;
 
187
 
 
188
  k = 0;
 
189
  if (iabs(card[VC]+card[SC]-card[HR]) < iabs(card[VC]-card[SR]-card[HR])) {  /* S = VC+SC+HR */
 
190
    /* printf("%"PRIDX" %"PRIDX" ",vc+sc, hr); */
 
191
    for (i=0; i<bsize; i++) 
 
192
      if (where[i] == VC || where[i] == SC || where[i] == HR)
 
193
        cover[k++] = i;
 
194
  }
 
195
  else {  /* S = VC+SR+HR */
 
196
    /* printf("%"PRIDX" %"PRIDX" ",vc, hr+sr); */
 
197
    for (i=0; i<bsize; i++) 
 
198
      if (where[i] == VC || where[i] == SR || where[i] == HR)
 
199
        cover[k++] = i;
 
200
  }
 
201
 
 
202
  *csize = k;
 
203
  gk_free((void **)&where, LTERM);
 
204
 
 
205
}
 
206
 
 
207
 
 
208
/*************************************************************************
 
209
* This function perfoms a dfs starting from an unmatched col node
 
210
* forming alternate paths
 
211
**************************************************************************/
 
212
void MinCover_ColDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
 
213
{
 
214
  idx_t i;
 
215
 
 
216
  if (flag == INCOL) {
 
217
    if (where[root] == HC)
 
218
      return;
 
219
    where[root] = HC;
 
220
    for (i=xadj[root]; i<xadj[root+1]; i++) 
 
221
      MinCover_ColDFS(xadj, adjncy, adjncy[i], mate, where, INROW);
 
222
  }
 
223
  else {
 
224
    if (where[root] == HR)
 
225
      return;
 
226
    where[root] = HR;
 
227
    if (mate[root] != -1)
 
228
      MinCover_ColDFS(xadj, adjncy, mate[root], mate, where, INCOL);
 
229
  }
 
230
 
 
231
}
 
232
 
 
233
/*************************************************************************
 
234
* This function perfoms a dfs starting from an unmatched col node
 
235
* forming alternate paths
 
236
**************************************************************************/
 
237
void MinCover_RowDFS(idx_t *xadj, idx_t *adjncy, idx_t root, idx_t *mate, idx_t *where, idx_t flag)
 
238
{
 
239
  idx_t i;
 
240
 
 
241
  if (flag == INROW) {
 
242
    if (where[root] == VR)
 
243
      return;
 
244
    where[root] = VR;
 
245
    for (i=xadj[root]; i<xadj[root+1]; i++) 
 
246
      MinCover_RowDFS(xadj, adjncy, adjncy[i], mate, where, INCOL);
 
247
  }
 
248
  else {
 
249
    if (where[root] == VC)
 
250
      return;
 
251
    where[root] = VC;
 
252
    if (mate[root] != -1)
 
253
      MinCover_RowDFS(xadj, adjncy, mate[root], mate, where, INROW);
 
254
  }
 
255
 
 
256
}
 
257
 
 
258
 
 
259