eg_1pchecker.c

Go to the documentation of this file.

#include "eg_1pchecker.h"
/* this function check a 2-Pie constraint, and return its violation (negative if
 * it is not violated) and the coefficient of each edges in each constraint in
 * the double array e_coeff (that should have been alocated before calling this
 * function */
int EG1pChecker (int const nnodes,
                 int const nedges,
                 int const *const edges,
                 double const *const weight,
                 int const n_ineq,
                 int const *const n_dom,
                 int *const *const n_Aset,
                 int *const *const n_Bset,
                 int const *const n_handle,
                 int **const *const Aset,
                 int **const *const Bset,
                 int *const *const handle,
                 double *const violation,
                 int *const *const e_coeff)
{
  /* local variables */
  register int i,
    j;
  int rval = 0,
    cur_const;
  unsigned char *node_marks = 0,
   *edge_parity = 0;

  /* basic tests */
  TESTG ((rval = !nnodes), CLEANUP, "nnodes is zero");
  TESTG ((rval = !nedges), CLEANUP, "nedges is zero");

  /* looking for memory */
  node_marks = EGsMalloc (unsigned char,
                          nnodes);
  edge_parity = EGsMalloc (unsigned char,
                           nedges);

  /* we loop through all inequalities */
  for (cur_const = n_ineq; cur_const--;)
  {
    /* reset the edges coefficients to zero */
    memset (e_coeff[cur_const], 0, sizeof (int) * nedges);
    memset (edge_parity, 0, sizeof (unsigned char) * nedges);
    violation[cur_const] = -1.0;

    /* loop through all dominoes and start setting coefficients of the edges
     * and count n_xdom */
    for (i = n_dom[cur_const]; i--;)
    {

      /* first set marks of nodes */
      memset (node_marks, 0, sizeof (unsigned char) * nnodes);
      violation[cur_const] -= 3.0;
      TESTG ((rval =
              ((!n_Aset[cur_const][i])
               && (!n_Bset[cur_const][i]))), CLEANUP,
             "domino %d of constraint %d is empty", i, cur_const);

      /* now set marks due to A-partition */
      if (n_Aset[cur_const][i])
      {
        for (j = n_Aset[cur_const][i]; j--;)
        {
          node_marks[Aset[cur_const][i][j]] |= 1U;
          node_marks[Aset[cur_const][i][j]] |= 2U;
        }
      }

      /* now set marks due to B-partition */
      if (n_Bset[cur_const][i])
      {
        for (j = n_Bset[cur_const][i]; j--;)
        {
          TESTG ((rval =
                  node_marks[Bset[cur_const][i][j]]), CLEANUP,
                 "domino %d of constraint %d is such that A and B are non-disjoint",
                 i, cur_const);
          node_marks[Bset[cur_const][i][j]] |= 1U;
          node_marks[Bset[cur_const][i][j]] |= 4U;
        }
      }

      /* now we loop through the edges and set up their coefficients and
       * parities accordingly, also update the violation */
      for (j = nedges; j--;)
      {
        /* edges in Delta(T) */
        if ((node_marks[edges[j << 1]] & 1U) !=
            (node_marks[edges[(j << 1) | 1]] & 1U))
        {
          violation[cur_const] += weight[j];
          e_coeff[cur_const][j] += 1;
        }
        /* edges in E(A:B) */
        if (((node_marks[edges[j << 1]] & 1U)
             && (node_marks[edges[(j << 1) | 1]] & 1U))
            && ((node_marks[edges[j << 1]] & 2U) !=
                (node_marks[edges[(j << 1) | 1]] & 2U)))
        {
          violation[cur_const] += weight[j];
          e_coeff[cur_const][j] += 1;
          edge_parity[j] ^= 1U;
        }
      }                         /* end setting coefficients for this 2-pie */
    }                           /* end for 2pies of the inequalities */

    /* check parity of dominoes for both handles */
    TESTG ((rval =
            !(n_dom[cur_const] & 1U)), CLEANUP, "number of dominoes is even");

    /* now we set marks for handles in nodes */
    memset (node_marks, 0, sizeof (unsigned char) * nnodes);

    /*
     * WARNING((!n_handle[cur_const]), 
     * "Handle of constraint %d is empty", cur_const);
     */

    for (i = n_handle[cur_const]; i--;)
      node_marks[handle[cur_const][i]] |= 1U;

    /* now check parity of all edges in Delta(Handle_i) and add coefficients
     * accordingly */
    for (i = nedges; i--;)
    {
      /* check the parity for the handle */
      if (((node_marks[edges[i << 1]] & 1U) !=
           (node_marks[edges[(i << 1) | 1]] & 1U)) && !(edge_parity[i] & 1U))
      {
        violation[cur_const] += weight[i];
        e_coeff[cur_const][i] += 1;
      }
      if (((node_marks[edges[i << 1]] & 1U) ==
           (node_marks[edges[(i << 1) | 1]] & 1U)) && (edge_parity[i] & 1U))
      {
        violation[cur_const] += weight[i];
        e_coeff[cur_const][i] += 1;
      }
    }                           /* end loop through edges setting up parity for handles */
  }                             /* end loop through all inequalities */

  /* ending */
CLEANUP:
  if (node_marks)
    EGfree (node_marks);
  if (edge_parity)
    EGfree (edge_parity);
  return rval;
}

---