eg_2pchecker.c

Go to the documentation of this file.

#include "eg_2pchecker.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 EG2pChecker (int const nnodes,
                 int const nedges,
                 int const *const edges,
                 double const *const weight,
                 int const n_ineq,
                 int const *const n2_dom,
                 int **const n_Aset,
                 int **const n_Bset,
                 int **const n_Tset,
                 int const *const n_Ahandle,
                 int const *const n_Bhandle,
                 int ***const Aset,
                 int ***const Bset,
                 int ***const Tset,
                 int **const Ahandle,
                 int **const Bhandle,
                 double *const violation,
                 int **const e_coeff)
{
  /* local variables */
  register int i,
    j;
  int rval = 0,
    cur_const;
  unsigned char *node_marks = 0,
   *edge_parity = 0;
  unsigned int n_adom,
    n_bdom;
  unsigned int values[8];

  /* 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);
    n_bdom = n_adom = 0;
    violation[cur_const] = -2.0;

    /* loop through all 2-dominoes and start setting coefficients of the edges
     * and count n_xdom */
    for (i = n2_dom[cur_const]; i--;)
    {
      memset (node_marks, 0, sizeof (unsigned char) * nnodes);
      /* first set marks of nodes */
      violation[cur_const] -= 2.0;
      TESTG ((rval = (!n_Tset[cur_const][i])), CLEANUP,
             "2-pie %d of constraint %d is empty %d", i, cur_const,
             n_Tset[cur_const][i]);
      TESTG ((rval = (n_Tset[cur_const][i] == nnodes)), CLEANUP,
             "T_%u is not a propper set", i);
      TESTG ((rval = (n_Tset[cur_const][i] <= n_Aset[cur_const][i])),
             CLEANUP, "A_%u is not a propper set of T", i);
      TESTG ((rval = (n_Tset[cur_const][i] <= n_Bset[cur_const][i])),
             CLEANUP, "B_%u is not a propper set of T", i);
      for (j = n_Tset[cur_const][i]; j--;)
        node_marks[Tset[cur_const][i][j]] |= 1U;
      /* now set marks due to A-partition */
      if (n_Aset[cur_const][i])
      {
        n_adom++;
        violation[cur_const] -= 1.0;
        for (j = n_Aset[cur_const][i]; j--;)
        {
          TESTG ((rval = !(node_marks[Aset[cur_const][i][j]] & 1U)), CLEANUP,
                 "Node in Aset not in T");
          node_marks[Aset[cur_const][i][j]] |= 2U;
        }
      }
      /* now set marks due to B-partition */
      if (n_Bset[cur_const][i])
      {
        n_bdom++;
        violation[cur_const] -= 1.0;
        for (j = n_Bset[cur_const][i]; j--;)
        {
          TESTG ((rval = !(node_marks[Bset[cur_const][i][j]] & 1U)), CLEANUP,
                 "Node in Bset not in T");
          node_marks[Bset[cur_const][i][j]] |= 4U;
        }
      }
      /* now we check that if this is a 2-domino, we have a 3-partition */
      if (n_Aset[cur_const][i] && n_Bset[cur_const][i])
      {
        memset (values, 0, sizeof (values));
        for (j = n_Tset[cur_const][i]; j--;)
          values[node_marks[Tset[cur_const][i][j]]]++;
        for (j = 1; j < 8; j++)
          values[0] += values[j] ? 1U : 0U;
        TESTG ((rval = (values[0] < 3)), CLEANUP, "2-domino %u is only a %u"
               " partition", i, values[0]);

      }
      /* 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:T\A) */
        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;
        }
        /* edges in E(B:T\B) */
        if (((node_marks[edges[j << 1]] & 1U)
             && (node_marks[edges[(j << 1) | 1]] & 1U))
            && ((node_marks[edges[j << 1]] & 4U) !=
                (node_marks[edges[(j << 1) | 1]] & 4U)))
        {
          violation[cur_const] += weight[j];
          e_coeff[cur_const][j] += 1;
          edge_parity[j] ^= 2U;
        }
      }                         /* end setting coefficients for this 2-pie */
    }                           /* end for 2pies of the inequalities */

    /* check parity of dominoes for both handles */
    TESTG ((rval = !(n_adom & 1U)), CLEANUP, "A-dominos is even, nadom %u, nbdom %u", n_adom, n_bdom);
    TESTG ((rval = !(n_bdom & 1U)), CLEANUP, "B-dominos is even, nbdom %u, nadom %u", n_bdom, n_adom);
    memset (node_marks, 0, sizeof (unsigned char) * nnodes);

    /* now we set marks for handles in nodes */
    
    WARNING((!n_Ahandle[cur_const] || (n_Ahandle[cur_const]==nnodes)), 
    "Handle A of constraint %d is empty", cur_const);
    for (i = n_Ahandle[cur_const]; i--;)
      node_marks[Ahandle[cur_const][i]] |= 1U;
    WARNING((!n_Bhandle[cur_const] || (n_Bhandle[cur_const]==nnodes)), 
    "Handle B of constraint %d is empty", cur_const);
    for (i = n_Bhandle[cur_const]; i--;)
      node_marks[Bhandle[cur_const][i]] |= 2U;

    /* now check parity of all edges in Delta(Handle_i) and add coefficients
     * accordingly */
    for (i = nedges; i--;)
    {
      /* check if the parity for handle A */
      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;
      }
      /* check if the parity for handle B */
      if (((node_marks[edges[i << 1]] & 2U) !=
           (node_marks[edges[(i << 1) | 1]] & 2U)) && !(edge_parity[i] & 2U))
      {
        violation[cur_const] += weight[i];
        e_coeff[cur_const][i] += 1;
      }
      if (((node_marks[edges[i << 1]] & 2U) ==
           (node_marks[edges[(i << 1) | 1]] & 2U)) && (edge_parity[i] & 2U))
      {
        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;
}

---