eg_greedytypes.h

Go to the documentation of this file.

#ifndef _GREEDYTYPES
#define _GREEDYTYPES

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

#include "eg_timer.h"
#include "eg_mempool.h"
#include "eg_list.h"

#include "eg_heap.h"
#include "eg_dgraph.h"
#include "eg_dijkstra.h"
#include "eg_dijkstra_app.h"
#include "eg_ddomino.h"
#include "eg_ddpconstraint.h"

#define KP_DEBUG 0
#define EG_DEBUG_TRACE 0
#define EG_KP_NOST 0xfff
#define EG_KP_MAX_CUTS 250

/* EG_USE_ZERO_DOMINOES. 0 or 1 (DEFAULT 1)

   When set to one, the code will loop through all the 1-dominoes generated 
   by Letchford's algorithm in order to generate 0-dominoes to be used as 
   starting points for the 2P algorithm. */

#define EG_USE_ZERO_DOMINOES 1

/* EG_USE_KARGER. 0 or 1 (DEFAULT 0)

   When set to one, the code will utilize Sanjeeb Dash's karger algorithm
   in order to generate 0-dominoes to be used as starting points for 
   the 2P algorithm. */

#define EG_USE_KARGER 1

/* SAMPLING DEFINITIONS (DEFAULT 1 1 1)

   In order to use sampling, EG_USE_SAMPLING, EG_KP_HEURISTIC and 
   EG_GREEDYKP_FILLTABLE should all be set to one. Otherwise, they
   should be set to zero. */

#define EG_KP_HEURISTIC 1
#define EG_GREEDYKP_FILLTABLE 1
#define EG_USE_SAMPLING 1

/* EG_KP_SAMPLE_TIME (DEFAULT 1.0)

   Thie is the base amount of time which will be to generate cuts from 
   each zero-domino. 

   EG_KP_MAX_SAMPLE (DEFAULT 10)

   The amount of zero-dominoes which will be kept during the cut generation
   process for later use in sampling.

   Hence, if EG_KP_MAX_SAMPLE == 5 and EG_KP_SAMPLE_TIME == 10, then the 
   algorithm will spend a total of 50 seconds sampling. */

#define EG_KP_SAMPLE_TIME 1.0
#define EG_KP_MAX_SAMPLE 10

/* Seed for sampling (DEFAULT 1) */

#define EG_KP_SAMPLE_SEED 1

/* EG_DOMINO_K (DEFAULT 1)

   In theory, for the USE_ZERO_DOMINOES heuristic, the best value for this 
   constant is = to the number of handles. However, for the growth stage it
   suffices to set this value to 1.0. When generating two-pies there are 
   speed-quality tradeoffs between setting it to 1 or 2. */

#define EG_DOMINO_K 2

/* EG_KPC_MAX_HANDLES 1...N (DEFAULT 5)

   For now, this value should be two for the KP algorithm to run. */

#define EG_KPC_MAX_HANDLES 5

/* EG_KARGER_SEED (DEFAULT 1)

   Seed used by srandom() before running the karger algorithm */

#define EG_KARGER_SEED 1

/* EG_KARGER_MAX_ITER (DEFAULT INT_MAX)

   Max number of iterations to be performed by the karger algorithm.
   Note that if we are stopping by time, this should be set to 
   EG_KARGER_MAX_ITER. */

#define EG_KARGER_MAX_ITER INT_MAX

/* EG_KARGER_TIME_PER_NODE (DEFAULT 0.1)

   Amount of time dedicated to generating cuts, as a function of the 
   number of nodes in the original primal graph. */

#define EG_KARGER_MAX_TOT_TIME 15.0
#define EG_KARGER_TIME_PER_NODE 0.3

/* EGgreedyData
 *
 * The idea is as follows: Nodes in cycleG are either even or odd.
 * Even nodes are those on the 'left' hand side. That is, nodes whose
 * node id is even. Odd nodes are those on the 'right' hand side. That
 * is, nodes whose node id is odd. 
 *
 * ee_dist : distance between pairs (s,t) of even nodes, such that s < t.
 * ee_prec : father (in tree) of node t in shortest path between pairs 
 *           (s,t) of even nodes, such that s < t.
 * eo_prec : father (in tree) of node t of shortest path between pairs 
 *           (s,t) where s is even, t is odd, and s < t.
 * bdGnodeMap : element i is a pointer to the i-th node of the list
 *              bdG->nodes (with regard to the actual list ordering)
 * cycleEdgeMap : element i points to the edge whose id is i in cycleG 
 * bdGtoCycleGmap : consider a node in bdG with id i. Element i of
                    this array corresponds to the even copy of this 
                    node in graph cycleG.
*/

typedef struct
{
  int norig_nodes, norig_edges, nplanar_edges;
  int *orig_edges, *planar_edges;
  double *orig_weight, *planar_weight;
  EGlist_t** dembed;
  EGdGraph_t *bdG;
  EGdGraph_t *cycleG;
  graphP G;                          
  EGdGraphNode_t **bdGnodeMap;
  EGdGraphEdge_t **cycleEdgeMap;
  EGlist_t *ddom_list;
  EGdijkstraCost_t **ee_dist;
  #if EG_KP_HEURISTIC
  EGdijkstraCost_t **eo_dist;
  EGdGraphNode_t **bdGtoCycleGmap;
  #endif
  int **ee_prec, **eo_prec;
  unsigned int* randa;        
  unsigned int* randb;        
  EGheap_t *cut_heap;
  EGheap_t *dc_heap;
  int max_handles;
  double percentage;

  unsigned int nviolated;
  double min_violated;
  double max_violated;
  unsigned delta_distr[7];
  unsigned char *pndummy;   
  unsigned char *pedummy;   
  EGdGraphNode_t **bdnodes; 
  EGdGraphEdge_t **pedges;  
  double *pedgevals;        
} EGgreedyData_t;

/* ========================================================================= */
typedef struct EGdualCut_t
{
  unsigned int sz;        
  EGdGraphEdge_t **edges; 
  EGdijkstraCost_t value; 
} EGdualCut_t;

/* ========================================================================= */
struct EGdkdomino_t;
typedef struct EGinternalPairs_t
{
  EGdGraphNode_t *s;           
  EGdGraphNode_t *t;           
  EGdijkstraCost_t value;      
  EGdijkstraCost_t ivalue;     
  EGdijkstraCost_t evalue;     
  unsigned int npath;          
  EGdGraphEdge_t **stpath;     
  EGlist_t *extpath;           
} EGinternalPairs_t;

/* ========================================================================= */
void EGfreeInternalPairs(void*pair,EGmemPool_t*mem);

/* ========================================================================= */
typedef struct EGdkdomino_t
{
  unsigned int k;           
  unsigned int max_k;       
  unsigned int orientation;  
  EGinternalPairs_t* pairs;   
  unsigned int * handleid;   
  EGdualCut_t *cut;           
} EGdkdomino_t;

typedef struct
{
  unsigned int nhandles;
  EGlist_t* FH[EG_KPC_MAX_HANDLES];
  EGlist_t* dkdom;
  EGdijkstraCost_t slack;
} EGdkpc_t;

/* given a list of ddominos, keeps track of the zdom we are currently
 * analyzing. For this, it takes a ddom, removes a path (which one 
 * is determined by current_middle) and considers the side given
 * by current_side. current_side \in {0,1}. current_middle \in {0,1,2}. 
*/

typedef struct
{
  int num_it;
  EGlistNode_t *ddit;
  int current_side;
  int current_middle;
  EGgreedyData_t *gdata;
} EGdcutIter_t;

typedef struct
{
  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;
  double slack;
  
  unsigned int randa;
  unsigned int randb;

} EGpkpc_t;

typedef struct
{

  EGdualCut_t *dc;
  int orientation;

} EGcutSeed_t;

void EGdisplayDualCut(FILE *fout, 
                      EGdualCut_t* dc);

int EGincreaseDKdomino(EGdkdomino_t *dkd, 
                       EGinternalPairs_t *p);

#endif

---