eg_ddpconstraint.h

Go to the documentation of this file.

#ifndef _DDPCONSTRAINT
#define _DDPCONSTRAINT

#define DDPCONSTRAINT_MAXVIOL_EPSILON 0.0001
#define EG_DP_SELECT_DEBUG 500

#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 "graph_boyer.h"

typedef struct
{

  EGdijkstraCost_t weight;
  unsigned int pweight;

  EGddomino_t *ddom;
  EGdGraphEdge_t *e;

}
EGcycleData_t;

typedef struct
{

  unsigned int nF,
    ndom;

  /* the slack and the LHS have the dp suffix indicating 
   * that they are dual-primal values. This means that in
   * the case of edge elimination, they use the primalValue
   * entries of the weights for the dual-dominoes, rather
   * than the dual values.                                  */

  double slack_dp;
  EGdijkstraCost_t LHS_dp;

  EGddomino_t **ddom;
  EGdGraphEdge_t **F;
}
EGddpConstraint_t;

typedef const EGdGraphEdge_t *cep_t;
typedef const cep_t *ccep_t;

typedef const EGddomino_t *cddomp_t;
typedef const cddomp_t *ccddomp_t;

void EGfreeCycleDataMP (void *v,
                        EGmemPool_t * mem);

/* EGddpAddHeuristicCuts_3
 marray:  used to mark which nodes have been traversed by the random walk.
 odd_num: used to indicate how many odd edges have been traversed in order 
 to get to each node */
int EGddpAddHeuristicCuts_3 (EGddpConstraint_t ** ddpc_array,
                             double *const ddpc_dist,
                             double *const ddpc_angle_norm,
                             double *const *const ddpc_angle,
                             unsigned int *const ddpc_size,
                             unsigned int const ddpc_max_size,
                             double *const ddpc_best_angle,
                             double *const ddpc_worst_angle,
                             unsigned int *const ddpc_worst_angle_id,
                             int const nedges,
                             EGdGraphNode_t * start_node,
                             EGdGraphEdge_t * start_edge,
                             int k,
                             double ubound,
                             EGdGraph_t * cycleG,
                             EGdGraphEdge_t ** dij_sol,
                             unsigned int *marray,
                             char *sarray,
                             unsigned int *odd_num,
                             unsigned int nddom,
                             int *ddom_markers,
                             size_t * os,
                             double max_node_time,
                             EGmemPool_t * mem);

/* create a new cycle graph. max_val is an upper bouind on 'feasible' edges,
 * then, any edge (real or fake) with value more than max_val will be discarded
 * and not included in the graph */
EGdGraph_t *EGnewCycleGraph (EGmemPool_t * mem,
                             EGlist_t * dlist,
                             EGdGraph_t * bdG,
                             EGdijkstraCost_t max_val);

void EGfreeDDPconstraintMP (void *v,
                            EGmemPool_t * mem);

int EGboyerEdgeNumber (const EGdGraphEdge_t * e);

int EGedgeCompare (const void *p1,
                   const void *p2);

int EGddpcComputeAll (EGmemPool_t * mem,
                      EGdGraph_t * bdG,
                      EGlist_t * dlist,
                      EGlist_t * ddpc_list,
                      int const nedges,
                      int k);

int EGddpSetMaxWeight (EGdGraph_t * cycleG,
                       double *max_weight);

void EGddpcDisplay (EGddpConstraint_t * ddpc,
                    FILE * file);

#endif

---