File: csrmatch.c

package info (click to toggle)
parmetis 4.0.3-5
  • links: PTS, VCS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 25,384 kB
  • ctags: 3,256
  • sloc: ansic: 41,872; makefile: 298; sh: 190; perl: 25
file content (85 lines) | stat: -rw-r--r-- 1,976 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
 * Copyright 1997, Regents of the University of Minnesota
 *
 * csrmatch.c
 *
 * This file contains the code that computes matchings
 *
 * Started 7/23/97
 * George
 *
 * $Id: csrmatch.c 10057 2011-06-02 13:44:44Z karypis $
 *
 */

#include <parmetislib.h>


/*************************************************************************
* This function finds a matching using the HEM heuristic
**************************************************************************/
void CSR_Match_SHEM(matrix_t *matrix, idx_t *match, idx_t *mlist,
          idx_t *skip, idx_t ncon)
{
  idx_t h, i, ii, j;
  idx_t nrows, edge, maxidx, count;
  real_t maxwgt;
  idx_t *rowptr, *colind;
  real_t *transfer;
  rkv_t *links;

  nrows    = matrix->nrows;
  rowptr   = matrix->rowptr;
  colind   = matrix->colind;
  transfer = matrix->transfer;

  iset(nrows, UNMATCHED, match);

  links = rkvmalloc(nrows, "links");
  for (i=0; i<nrows; i++) {
    links[i].key = 0.0;
    links[i].val = i;
    for (j=rowptr[i]; j<rowptr[i+1]; j++) {
      for (h=0; h<ncon; h++) {
        if (links[i].key < fabs(transfer[j*ncon+h]))
          links[i].key = fabs(transfer[j*ncon+h]);
      }
    }
  }

  rkvsortd(nrows, links);

  for (count=0, ii=0; ii<nrows; ii++) {
    i = links[ii].val;

    if (match[i] == UNMATCHED) {
      maxidx = i;
      maxwgt = 0.0;

      /* Find a heavy-edge matching */
      for (j=rowptr[i]; j<rowptr[i+1]; j++) {
        edge = colind[j];
        if (match[edge] == UNMATCHED && edge != i && skip[j] == 0) {
          for (h=0; h<ncon; h++)
            if (maxwgt < fabs(transfer[j*ncon+h]))
              break;

          if (h != ncon) {
            maxwgt = fabs(transfer[j*ncon+h]);
            maxidx = edge;
          }
        }
      }

      if (maxidx != i) {
        match[i] = maxidx;
        match[maxidx] = i;
        mlist[count++] = gk_max(i, maxidx);
        mlist[count++] = gk_min(i, maxidx);
      }
    }
  }

  gk_free((void **)&links, LTERM);
}