/*
 * 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);
}