eg_kpseparator.c

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>

#include "eg_list.h"
#include "eg_mempool.h"
#include "graph_boyer.h"
#include "graphdual.h"

#include "eg_util.h"
#include "eg_dgraph.h"
#include "eg_ddomino.h"
#include "eg_pdp.h"
#include "eg_util.h"
#include "eg_ddpconstraint.h"
#include "bc_spanning.h"
#include "bc_util.h"
#include "cookInterface.h"
#include "eg_1pchecker.h"
#include "eg_emptyhandles.h"
#include "eg_greedykp.h"
#include "eg_kppairs.h"
#include "eg_2pchecker.h"
#include "karger.h"
#include "eg_greedytypes.h"

double DKP_HEURISTIC_MAXTIME = 10.0;

/* Function Definitions */
int KPseparator (int max_handles,
                 int nnodes,
                 int norig_edges,
                 int *const orig_edges,
                 double *const orig_weight,
                 int *nineq,
                 int **nhandles,
                 int ***handle_size,
                 int ****handles,
                 int **nteeth,
                 int ***teeth_size,
                 int ****teeth,
                 int ***teeth_k,
                 int ****teeth_handle,
                 int ****teeth_nhalf,
                 int *****teeth_halves,
                 const char *const boss_name,
                 double percentage) 
{

  /* **************** DECLARE VARIABLES **************** */

  /* auxiliary variables */
  int i,
    rval;
  int is_connected;
  /* flags */
  int eliminated_edges_b = 0,
    is_G_planar_b = 0;
  /* where we will store the edges that are bigger than ZERO_X_EPSILON */
  int *edges = 0,
    nedges = 0,
    nelim_edges = 0;
  double *weight = 0;
  /* for the primal-dual-primal conversions we need an 'applegate' graph */
  graphP primalG = 0;
  /* the bi-directed dual over which we will search for ddominoes */
  EGdGraph_t *biDualG = 0;
  /* the list of ddominoes */
  EGlist_t *dlist = 0;
  EGlist_t **dembed = 0;
  EGlist_t **lembed = 0;
  /* memory pool */
  EGmemPool_t *mem = 0;
  /* used for handling the list of ddominoes */
  EGddomino_t *ddom;
  EGlistNode_t *ddom_it;
#if ELIM_EDGES
  int *planar_edges = 0,
    nplanar_edges = 0,
   *elim_edges = 0;
  double *planar_weight = 0,
    error = 0;
#endif
#if DISPLAY_MODE
  unsigned int distr[10] = {0,0,0,0,0,0,0,0,0,0};
  int nfeasible = 0;
  int ncorrected = 0;
  int nnegative = 0;
  double dual_val,
    prim_val;
#endif
   EGdualCut_t *dcut=0;
   EGdcutIter_t *dcut_it=0;
   EGgreedyData_t *gdata=0;
   EGpkpc_t *pkpc = 0;
   int nadded = 0;
   double minslack;
   unsigned char *pndummy=EGsMalloc(unsigned char,nnodes), 
    *pedummy=EGsMalloc(unsigned char, norig_edges);

  /* ******************* INITIALIZE DATA STRUCTURES ******************* */
  *nineq = 0;
  *nhandles = 0;
  *handle_size = 0;
  *handles = 0;
  *nteeth = 0;
  *teeth_size = 0;
  *teeth = 0;
  *teeth_k = 0;
  *teeth_handle = 0;
  *teeth_nhalf = 0;
  *teeth_halves = 0;
  /* initialize memory pool                                                   */
  mem = EGnewMemPool (512, EGmemPoolNewSize, EGmemPoolNewSize (1));

  /* initialize linked lists                                                  */
  dlist = EGnewList (mem);

  /* ******************* INFORM USER ******************* */

  fprintf (stdout, "KP Version %s\n", DP_VERSION_STRING);
#if DISPLAY_MODE
  if (!boss_name)
    fprintf (stdout, "KP Separator: NO boss.\n");
  else
    fprintf (stdout, "KP Separator: Boss name = %s.\n", boss_name);
  fflush (stdout);
#endif

#if LOG_MODE
  saveBgraph ("graph.b.x", nnodes, norig_edges, orig_edges, orig_weight);
#endif

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Graph G^* has %d nodes, and %d edges.\n", nnodes, norig_edges);
  fflush (stdout);
#endif

  /* ******************* REMOVE SMALL EDGES ******************* */

  /* remove small edges (ie: those smaller than ZERO_X_EPSILON)               */
  rval = removeSmallEdges (ZERO_X_EPSILON, orig_edges, norig_edges, orig_weight,
                           &nedges, &edges, &weight, mem);
  CHECKRVAL (rval);

#if DISPLAY_MODE
  fprintf (stdout,
           "KP Separator: Eliminated %d edges of value less than %lf.\n",
           (norig_edges - nedges), ZERO_X_EPSILON);
  fflush (stdout);
  fprintf (stdout, "KP Separator: Graph G^* now has %d nodes, and %d edges.\n",
           nnodes, nedges);
  fflush (stdout);
#endif

  /* ******************* PLANARIZE GRAPH IF NECESSARY  ******************* */

  /* check if the graph is planar                                             */
  primalG = gp_New ();
  rval = cook2boyerGraph (primalG, nnodes, nedges, edges);
  CHECKRVAL (rval);
  is_G_planar_b = gp_Embed (primalG, EMBEDFLAGS_PLANAR);
  rval = gp_SortVertices (primalG);
  EXITRVAL (rval);

  /* if not planar, run heuristic to planarize                                */
  if (is_G_planar_b != OK)
  {
#if DISPLAY_MODE
    fprintf (stdout, "KP Separator: Graph G^* is not planar.\n");
    fflush (stdout);
#endif
    /* First: Contractions.                                                   */
    /* Second: Eliminate Edges using the Kruskal Heuristic.                   */
#if ELIM_EDGES
#if DISPLAY_MODE
    fprintf (stdout, "KP Separator: Running edge-elimination "
             "heuristic to find planar sub-graph.\n");
    fflush (stdout);
#endif

    /* cuidado! */
    planar_edges = EGmemPoolMalloc (mem, sizeof (int) * 2 * nedges);
    planar_weight = EGmemPoolMalloc (mem, sizeof (double) * nedges);
    elim_edges = EGmemPoolMalloc (mem, sizeof (int) * nedges);
    /* cuidado! */

    rval =
      DPedgeEliminationHeuristic (nnodes, nedges, edges, weight, &nplanar_edges,
                                  planar_edges, planar_weight, &nelim_edges,
                                  elim_edges);

    CHECKRVAL (rval);

#if DISPLAY_MODE
    fprintf (stdout, "KP Separator: Completed edge-elimination.");
    fflush (stdout);
#endif

    eliminated_edges_b = 1;
    TEST (nplanar_edges == nedges, "ERROR: Graph is not planar, yet no edges "
          "were eliminated.");

    for (i = 0; i < nedges - nplanar_edges; i++)
      error += weight[elim_edges[i]];

#if DISPLAY_MODE
    fprintf (stdout, "KP Separator: Found a planar sub-graph with %d edges.\n",
             nplanar_edges);
    fflush (stdout);
    fprintf (stdout, "KP Separator: Total weight of eliminated edges is %lf.\n",
             error);
    fflush (stdout);
#endif
#endif
  }

  /* if graph is planar, we use the original edge set.                        */
  else
  {
#if DISPLAY_MODE
    fprintf (stdout, "KP Separator: Graph G^* is planar.\n");
    fflush (stdout);
#endif
    eliminated_edges_b = 0;
    planar_edges = edges;
    nplanar_edges = nedges;
    planar_weight = weight;
  }

#if LOG_MODE
  saveBgraph ("graph.planar.b.x", nnodes, nplanar_edges, planar_edges,
              planar_weight);
  saveGraph ("graph.planar.x", nnodes, nplanar_edges, planar_edges,
             planar_weight);
#endif

  /* ******************* COMPUTE DUAL GRAPH  ******************* */

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Computing dual of G^*.\n");
  fflush (stdout);
#endif
  is_connected = EGisCookGraphConnected (nnodes, nplanar_edges, planar_edges,
                                         mem);

#if DISPLAY_MODE
  if (is_connected)
    fprintf (stdout, "KP Separator: G^* is connected.\n");
  else
    fprintf (stdout, "KP Separator: G^* is not connected.\n");
#endif

  if (!is_connected)
    goto END_DP;

  /* compute dual of graph                                                    */
  gp_Free (&primalG);
  primalG = gp_New ();
  rval = cook2boyerGraph (primalG, nnodes, nplanar_edges, planar_edges);
  CHECKRVAL (rval);
  biDualG = getDualBoyer (primalG, nnodes, nplanar_edges, planar_weight,
                          &dembed, mem, &lembed);
  if (!biDualG)
    goto END_DP;

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Bi-directed dual graph "
           "has %d nodes and %d edges.\n",
           biDualG->nodes->size, biDualG->nedges);

  /* ******************* COMPUTE AND FIX DUAL 1-DOMINOES  ******************* */

  fprintf (stdout, "KP Separator: Looking for dual dominoes.\n");
  fflush (stdout);
#endif

  /* with dual of planar graph, obtain dual dominoes                          */
  if (boss_name == 0)
    rval = EGddominoComputeAll (mem, biDualG, dlist, EG_DOMINO_K, percentage);
  else
    rval = EGddominoComputeAllRemote (mem, biDualG, dlist, EG_DOMINO_K, boss_name, DKP_HEURISTIC_MAXTIME);

  CHECKRVAL (rval);

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Found %d dual dominoes.\n", dlist->size);
  fflush (stdout);
#endif

  /* now we untengle all the obtained dominoes */
  rval = EGuntangleAllDomino (dlist, biDualG, dembed, mem);
  CHECKRVAL (rval);

  if (!dlist->size)
    goto END_DP;

  /* if using an edge-elimination heuristic, we might want to fix (some? all?) domino values and store this corrected value in primalValue. If there is no edge-elimination we also need to set primalValue, however, in this case there is no need for corrections. Finally, we need to fix numerical errors. Specifically, should we encounter dominoes with slightly negative values, we will round these up to zero (slightly negative == DP_RESET_VALUE. */
  rval =
    EGfixDualDominos (dlist, nnodes, nedges, weight, edges,
                      elim_edges, nelim_edges, primalG, mem);
  CHECKRVAL (rval);


#if DISPLAY_MODE
  if (eliminated_edges_b)
  {

    ncorrected = 0;
    nnegative = 0;
    nfeasible = 0;

    for (ddom_it = dlist->begin; ddom_it; ddom_it = ddom_it->next)
    {

      ddom = (EGddomino_t *) (ddom_it->this);
      dual_val = EGdijkstraCostToLf (ddom->value);
      prim_val = EGdijkstraCostToLf (ddom->primalValue);

      if (fabs (dual_val - prim_val) > 0.0001)
      {
        ncorrected++;
      }
      if (dual_val < 0)
      {
        nnegative++;
      }
      if (prim_val < 1.0000)
        nfeasible++;
    }
    fprintf (stdout,
             "KP Separator: Corrected %d values. %d / %d dominoes remain feasible.\n",
             ncorrected, nfeasible, dlist->size);
    fflush (stdout);
  }
#endif

  /* ******************* PREPARE DATA FOR GREEDY ALG **************** */

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Constructing greedy data.\n");
  fflush (stdout);
#endif

  gdata = EGnewGreedyData(mem);
  rval = EGfillGreedyData(gdata, 
                          biDualG, 
                          dlist,
                          lembed,
                          primalG,
                          nnodes,
                          norig_edges,
                          nplanar_edges,
                          orig_edges,
                          planar_edges,
                          orig_weight,
                          planar_weight);
  CHECKRVAL(rval);

 /* allocate memory for one constraint */

  TEST( max_handles != 2, "implementatin only good for max_handles = 2" );

  gdata->max_handles = max_handles;
  gdata->percentage = percentage;
  gdata->cut_heap = EGnewHeap(mem, 2, EG_KP_MAX_CUTS);
  gdata->dc_heap = EGnewHeap(mem, 2, EG_KP_MAX_SAMPLE);
  
  /* ******************* LOOP THROUGH ZERO-DOMINOES ***************** */

  #if EG_USE_ZERO_DOMINOES
  #if DISPLAY_MODE
  fprintf(stdout, "KP: Generating domino-based dual cuts.\n");
  #endif
  dcut_it = EGnewDcutIter(gdata);
  while( dcut_it->ddit )
  {
     dcut = EGgetDcut(dcut_it);
     rval = KPseparateFromDualCut( dcut, 
                                   (unsigned int)dcut_it->current_side, 
                                   gdata,
                                   &nadded,
                                   &minslack,
                                   0.0 );
      CHECKRVAL(rval);

      EGincrementDcutIter(dcut_it);
     
      if (nadded)
        EGaddDualCutToHeap(gdata->dc_heap,
                           dcut,
                           (unsigned int)dcut_it->current_side, 
                           minslack,
                           mem);
      else
        EGfreeDualCut(dcut,mem);
  }
  EGfreeDcutIter(dcut_it);
  #endif

  #if EG_USE_KARGER 
  /* ***************** LOOP WITH KARGER ***************************** */ 

  setlist*sets = 0;
  #if DISPLAY_MODE
  fprintf(stdout, "\nKP: Generating karger-based dual cuts.\n");
  #endif
  max_numiter = EG_KARGER_MAX_ITER;
  double max_time = ((double)gdata->norig_nodes * EG_KARGER_TIME_PER_NODE);
  if (EG_KARGER_MAX_TOT_TIME)
    max_time = EG_KARGER_MAX_TOT_TIME;
  const int seed = EG_KARGER_SEED;
  fprintf(stdout, "KP: Karger sample time = %lf seconds.\n", max_time);
  rval = karger(gdata->norig_nodes, gdata->norig_edges, gdata->orig_edges,
                gdata->orig_weight, 3, 6.0, max_time, seed, &sets, choose_edge1,
                gdata, KPprocess_cut);
  CHECKRVAL(rval);
  #endif

  /* ***************** LOOP WITH SAMPLING *************************** */ 

  #if EG_USE_SAMPLING
  double factor = 1.0;
  srandom(EG_KP_SAMPLE_SEED);
  while(gdata->dc_heap->size)
  {
    EGcutSeed_t *cseed;
    factor += .25;
    cseed = EGheapGetMinThis(gdata->dc_heap);
    dcut = cseed->dc;
    minslack = EGheapCostToLf(EGheapGetMinVal(gdata->dc_heap));
    fprintf(stdout, "\nKP: Sampling. Current cut lower bound = %lf (time = %lf).\n", minslack, EG_KP_SAMPLE_TIME*factor);
    rval = KPseparateFromDualCut( dcut, 
                                  (unsigned int)cseed->orientation, 
                                  gdata,
                                  &nadded,
                                  &minslack,
                                  EG_KP_SAMPLE_TIME*factor );
    EGheapDeleteMin(gdata->dc_heap,mem);
    EGmemPoolSFree(cseed, EGcutSeed_t, 1, mem);
    EGfreeDualCut(dcut,mem);
  }
  #endif

  /* ***************** DISPLAY 0-CUT STATS ************************** */ 
  
  #if DISPLAY_MODE
  fprintf(stdout,"\n0-Cut values:\n");
  for( i = 0 ; i < 7 ; i++)
    if(gdata->delta_distr[i])
      fprintf(stdout,"[%lf,%lf] = %u\n", i*1.0, (i+1)*1.0, 
              gdata->delta_distr[i]);
  fprintf(stdout, "KP: Finished generating dual cuts.\n");
  #endif

  /* ***************** STORE USER ARRAYS *************************** */ 

  if (gdata->cut_heap->size)
  {

     *nineq = gdata->cut_heap->size;
     rval = EGnewPKPCset( *nineq,
                           nhandles,
                           handle_size,
                           handles,
                           nteeth,
                           teeth_size,
                           teeth,
                           teeth_k,
                           teeth_handle,
                           teeth_nhalf,
                           teeth_halves );
     CHECKRVAL(rval);
   
     int tot = gdata->cut_heap->size; 
     for(i=0; gdata->cut_heap->size; i++)
     {

        pkpc = (EGpkpc_t*) EGheapGetMinThis(gdata->cut_heap);
        int w = tot - i - 1;
        //fprintf(stderr, "slack[%d] = %lf\n", w, pkpc->slack);

        #if DISPLAY_MODE
        if(pkpc->slack > -0.1)
          distr[0]++;
        else if(pkpc->slack > -0.2)
          distr[1]++;
        else if(pkpc->slack > -0.3)
          distr[2]++;
        else if(pkpc->slack > -0.4)
          distr[3]++;
        else if(pkpc->slack > -0.5)
          distr[4]++;
        else if(pkpc->slack > -0.6)
          distr[5]++;
        else if(pkpc->slack > -0.7)
          distr[6]++;
        else if(pkpc->slack > -0.8)
          distr[7]++;
        else if(pkpc->slack > -0.9)
          distr[8]++;
        else 
          distr[9]++;
        #endif

        (*nhandles)[w] = pkpc->nhandles;
        (*handle_size)[w] = pkpc->handle_size;
        (*handles)[w] = pkpc->handles;
        (*nteeth)[w] = pkpc->nteeth;
        (*teeth_size)[w] = pkpc->teeth_size;
        (*teeth)[w] = pkpc->teeth;
        (*teeth_k)[w] = pkpc->teeth_k;
        (*teeth_handle)[w] = pkpc->teeth_handle;
        (*teeth_nhalf)[w] = pkpc->teeth_nhalf;
        (*teeth_halves)[w] = pkpc->teeth_halves;

        EGheapDeleteMin(gdata->cut_heap, mem);
        EGfree(pkpc);
     }

    #if DISPLAY_MODE
    fprintf(stdout,"KP: Primal distribution of cuts:\n");
    for( i = 10 ; i-- ;)
      if(distr[i])
        fprintf(stdout,"[%lf,%lf] %u\n", 0.1*i, 0.1*(i+1),distr[i]);
    #endif

  }

  /* ******************* CLEAN UP THE MEMORY ******************* */

/* EGfree up used memory */

END_DP:

#if DISPLAY_MODE
  fprintf (stdout, "KP Separator: Bye.\n");
  fflush (stdout);
#endif

  if (gdata->cut_heap) EGfreeHeap(gdata->cut_heap, mem);
  if (gdata->dc_heap) EGfreeHeap(gdata->dc_heap, mem);
  EGfreeGreedyData(gdata);

  /* EGfree dlist, ddplist, and pdplist */
  if (dlist)
  {
    if (dlist->size)
      EGlistClearMP (dlist, EGfreeDdomino, mem);
    EGfreeList (dlist);
  }

  /* EGfree 'graphdual' objects */
  if (weight)
    EGmemPoolFree (weight, sizeof (double) * nedges, mem);
  if (edges)
    EGmemPoolFree (edges, sizeof (int) * 2 * nedges, mem);

#if ELIM_EDGES
  /* EGfree planar-graph heuristic data structures */
  if (eliminated_edges_b)
  {
    EGmemPoolSFree (planar_edges, int,
                    2 * nedges,
                    mem);
    EGmemPoolSFree (elim_edges, int,
                    nedges,
                    mem);
    EGmemPoolSFree (planar_weight, double,
                    nedges,
                    mem);
  }
#endif

  /* EGfree biDualG: weight, edges, and graph structure. */
  if (biDualG)
  {
    EGdGraphClearMP (biDualG, EGfreeMengerEdgeDataMP, EGfreeMengerNodeDataMP, 0,
                     mem, mem, 0);
    EGfreeDGraph (biDualG);
  }

  if (lembed)
  {
    for (i = nplanar_edges - nnodes + 2; i--;)
      EGfreeList (lembed[i]);
    EGmemPoolSFree (lembed, EGlist_t *, nplanar_edges - nnodes + 2, mem);
  }
  if (dembed)
  {
    for (i = nplanar_edges - nnodes + 2; i--;)
      EGfreeList (dembed[i]);
    EGmemPoolSFree (dembed, EGlist_t *, nplanar_edges - nnodes + 2, mem);
  }
  /* EGfree memory pool */
  EGfreeMemPool (mem);
  gp_Free (&primalG);
  EGfree(pedummy);
  EGfree(pndummy);

  /* return */
  return 0;

}

int DP2separator(int nnodes,
                 int norig_edges,
                 int *const orig_edges,
                 double *const orig_weight,
                 int *const n2ineq,
                 int **const n2dominoes,
                 int ***const naset,
                 int ***const nbset,
                 int ***const nmset,
                 int **const nahandle,
                 int **const nbhandle,
                 int ****const aset,
                 int ****const bset,
                 int ****const mset,
                 int ***const ahandle,
                 int ***const bhandle,
                 const char *const boss_name,
                 double percentage,
                 double d2p_heuristic_a_maxtime,
                 double d2p_heuristic_b_maxtime,
                 double d2p_heuristic_c_maxtime)
{

  int i, t, rval = 0;
  int nineq = 0,
      *nhandles = 0,
      **handle_size = 0,
      ***handles = 0,
      *nteeth = 0,
      **teeth_size = 0,
      ***teeth = 0,
      **teeth_k = 0,
      ***teeth_handle = 0,
      ***teeth_nhalf = 0,
      ****teeth_halves = 0,
      **ineq_coef = 0;
  double* violation = 0; 

  //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
  rval = KPseparator (2,
                      nnodes, 
                      norig_edges, 
                      orig_edges, 
                      orig_weight, 
                      &nineq,
                      &nhandles,
                      &handle_size,
                      &handles,
                      &nteeth, 
                      &teeth_size,
                      &teeth,
                      &teeth_k,
                      &teeth_handle,
                      &teeth_nhalf,
                      &teeth_halves, 
                      boss_name, 
                      percentage);
  CHECKRVAL(rval);
  //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);

  *n2ineq = nineq;

  *n2dominoes = EGsMalloc(int,nineq);
  for(i=0; i<nineq; i++)
    (*n2dominoes)[i] = nteeth[i];

  //(*n2dominoes) = (nteeth);
  
  unsigned char *vdummy = EGsMalloc(unsigned char,nnodes);

  if(nineq)
  {
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
    *naset = EGsMalloc(int*,nineq);
    *nbset = EGsMalloc(int*,nineq);
    *nmset = EGsMalloc(int*,nineq);
    *nahandle = EGsMalloc(int,nineq);
    *nbhandle = EGsMalloc(int,nineq);
    *aset = EGsMalloc(int**,nineq);
    *bset = EGsMalloc(int**,nineq);
    *mset = EGsMalloc(int**,nineq);
    *ahandle = EGsMalloc(int*,nineq);
    *bhandle = EGsMalloc(int*,nineq);
    for(i=0; i<nineq; i++)
    {
      (*naset)[i] = EGsMalloc(int,nteeth[i]);
      (*nbset)[i] = EGsMalloc(int,nteeth[i]);
      (*nmset)[i] = EGsMalloc(int,nteeth[i]);
      (*aset)[i] = EGsMalloc(int*,nteeth[i]);
      (*bset)[i] = EGsMalloc(int*,nteeth[i]);
      (*mset)[i] = EGsMalloc(int*,nteeth[i]);
      for(t=0; t < nteeth[i]; t++)
      {
        rval = EGkpTo2pTooth( teeth_size[i][t],
                              teeth[i][t],
                              teeth_k[i][t],
                              teeth_handle[i][t],
                              teeth_nhalf[i][t],
                              teeth_halves[i][t],
                              &((*naset)[i][t]),
                              &((*nbset)[i][t]),
                              &((*nmset)[i][t]),
                              &((*aset)[i][t]),
                              &((*bset)[i][t]),
                              &((*mset)[i][t]),
                              nnodes,
                              vdummy );
        CHECKRVAL(rval);
      }
    }
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);

    for(i=0; i<nineq; i++)
    {
      (*nahandle)[i] = handle_size[i][0];
      if (nhandles[i] > 1)
        (*nbhandle)[i] = handle_size[i][1];
      else
        (*nbhandle)[i] = 0;
    }
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);

    ineq_coef = EGsMalloc(int*,nineq);
    violation = EGsMalloc(double,nineq);
    for(i=0; i<nineq; i++)
    {
      ineq_coef[i] = EGsMalloc(int,norig_edges);
      /* a handle */
      (*ahandle)[i] = EGsMalloc(int,(*nahandle)[i]);
      for(t=0; t<((*nahandle)[i]); t++)
         (*ahandle)[i][t] = handles[i][0][t];
     /* bhandle */
      if ( (*nbhandle)[i] )
         (*bhandle)[i] = EGsMalloc(int,(*nbhandle)[i]);
      else
         (*bhandle)[i] = 0;
      for(t=0; t<((*nbhandle)[i]); t++)
         (*bhandle)[i][t] = handles[i][1][t];
    }
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
    /* check the inequality */
    rval = EG2pChecker( nnodes, norig_edges, orig_edges, orig_weight, 
                        *n2ineq, *n2dominoes, *naset, *nbset, *nmset, 
                        *nahandle, *nbhandle, *aset, *bset, *mset, *ahandle,
                        *bhandle, violation, ineq_coef);
    CHECKRVAL(rval);
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
  
    /* free constraints in old form */
    for(i=0; i < nineq; i++)
    {
      EGfree((ineq_coef[i]));
      EGfreePKPCB(nhandles[i],
                  handle_size[i],
                  handles[i],
                  nteeth[i],
                  teeth_size[i],
                  teeth[i],
                  teeth_k[i],
                  teeth_handle[i],
                  teeth_nhalf[i],
                  teeth_halves[i]);
      //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
    }
    //MESSAGE(0,"nhandles %p, nineq %d",(void*)nhandles, nineq);
    free(nhandles);
    free(handle_size);
    free(handles);
    free(nteeth);
    free(teeth_size);
    free(teeth);
    free(teeth_k);
    free(teeth_handle);
    free(teeth_nhalf);
    free(teeth_halves);
    EGfree(ineq_coef);
    EGfree(violation);
  }
  EGfree(vdummy);
  return rval;
}

---