eg_dptighten.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "dp_config.h"
#include "eg_mempool.h"
#include "eg_dptighten.h"
#include "eg_ugraph.h"
#include "eg_bit.h"
#include "eg_util.h"
#include "eg_bbtree.h"

Include dependency graph for eg_dptighten.c:

Go to the source code of this file.

Data Structures
struct	DPTMove_t
	Structure to hold a movement. More...
struct	DPTFullMove_t
	Dull move structure. More...
struct	DPTGdata_t
	Structure to hold information about the graph. More...
struct	DPTEdata_t
	structure holding information regarding every edge More...
struct	DPTNdata_t
Defines
#define	DPT_ENABLE   1
#define	DPT_MAX_DOM   512U
#define	DPT_MAX_DOM_LOG   9U
#define	DPT_MAX_NODE   131072U
#define	DPT_MAX_NODE_LOG   17U
#define	DPT_MAX_DEPTH   1U
#define	DPTMinImprovement   (-1e-6)
#define	DPTgetEdge(__e_it)   ((EGuGraphEdge_t*)(__e_it->this))
#define	DPTgetOtherEndId(__n_id, __e_it)   (__n_id == DPTgetEdge(__e_it)->head->id ? DPTgetEdge(__e_it)->tail->id : DPTgetEdge(__e_it)->head->id)
#define	DPTgetEdgeId(__e_it)   (DPTgetEdge(__e_it)->id)
#define	DPTNdata(__this)   ((DPTNdata_t*)(__this))
#define	DPTupdateMove(__cmove, __bmove)   __DPTupdateMove(__cmove,__bmove)
	, check if we should update a move, if so, do the update
#define	DPTpriceHcH(__id, __val)   DPTpriceHHc(__id,__val)
	This function prices the move Hc H, assuming the move is feasible.
#define	DPTmakeMoveHcH(__move, __flags)   DPTmakeMoveHHc(__move,__flags)
	Perform a DPT_HcH move.
#define	DPTmakeMove(__move, __flags)   __DPTmakeMove(__move,__flags,__LINE__,__FILE__,__func__)
	given a node, and a move, make it
#define	DPTgoDeeper(__depth)
Typedefs
typedef DPTNdata_t	DPTNdata_t
typedef static DPTNdata_t *	nodeData = 0
typedef static DPTEdata_t *	edgeData = 0
typedef static DPTGdata_t	graphData
typedef static EGuGraph_t *	G = 0
typedef static EGuGraphNode_t **	all_nodes
typedef static EGuGraphEdge_t **	all_edges
typedef static double const *	weight
typedef static EGbbtree_t *	tree
typedef static EGbitset_t	node_update [DPT_MAX_NODE >> __EGBIT_SHIFT__]
Enumerations
enum	move {   DPT_Tc_A, DPT_Tc_B, DPT_Hc_H, DPT_A_B,   DPT_B_A, DPT_B_A_flipH, DPT_A_B_flipH, DPT_A_Tc,   DPT_B_Tc, DPT_H_Hc, DPT_no_move }
Functions
static void	DPTpriceConstraint (double *l_violation)
static int	EGdpTightNdataCompare (const void *N1, const void *N2)
	This function compare two node data information.
static int	__DPTupdateMove (const DPTFullMove_t *const cur_move, DPTFullMove_t *const best_move)
static int	DPTpriceTcA (const DPTMove_t *const cur_move, double *const move_val)
	This function prices the move Tc A, assuming the move is feasible.
static int	DPTpriceTcB (const DPTMove_t *const cur_move, double *const move_val)
	This function prices the move Tc B, assuming the move is feasible.
static int	DPTpriceAB (const DPTMove_t *const cur_move, double *const move_val)
	This function prices the move A B, assuming the move is feasible.
static int	DPTpriceABflipH (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move A to B, and flip the node in H, assuming the move is feasible.
static int	DPTpriceBA (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move B A, assuming the move is feasible.
static int	DPTpriceBAflipH (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move B to A, and flip the node in H, assuming the move is feasible.
static int	DPTpriceHHc (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move H Hc, assuming the move is feasible.
static int	DPTpriceBTc (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move B Tc, assuming the move is feasible.
static int	DPTpriceATc (DPTMove_t const *const cur_move, double *const move_val)
	This function prices the move A Tc, assuming the move is feasible.
static int	DPTmakeMoveTcA (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_TcA move.
static int	DPTmakeMoveTcB (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_TcB move.
static int	DPTmakeMoveAB (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_AB move.
static int	DPTmakeMoveBA (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_BA move.
static int	DPTmakeMoveBAflipH (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_BA_flipH move.
static int	DPTmakeMoveABflipH (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_AB_flipH move.
static int	DPTmakeMoveHHc (DPTMove_t const *const move, const unsigned int update_flags)
	Perform a DPT_HHc move.
static int	DPTmakeMoveBTc (DPTMove_t const *const move)
	Perform a DPT_BTc move.
static int	DPTTestEdges (void)
	This function check that the edges got the wright values in hteir data.
static int	DPTmakeMoveATc (DPTMove_t const *const move)
	Perform a DPT_ATc move.
static int	__DPTmakeMove (DPTMove_t const *const move, const unsigned int update_flags, const int line, const char *file, const char *function)
static int	DPTmakeInvMove (DPTMove_t const *const move, const unsigned int update_flags)
	given a node, and a move, make the inverse move
static int	DPTmakeFullMove (DPTFullMove_t const *const full_move)
	Make a full move (in his whole depth ).
static int	DPTSetBestMove (const unsigned int nc_id, DPTFullMove_t *const best_move, DPTFullMove_t *const base_move, const unsigned int depth)
	, given a node, compute the best possible move for it, taking into acount if the node has been added to the T set before or not, remember that the priority is to add, and then to substract, note that this change is not reflected in the tree of best moves, you have to do it outside this function. the best move and value is stored in the given field, the actual best move stored inside the node data is not changed.
static int	DPTisMoveFeasible (DPTMove_t const *const move, const unsigned int update_flags)
	given a node, and a move, check if it is feasible, if update_flags is set to one, then it will check the constrains imposed by them.
static int	DPTisFullMoveFeasible (DPTFullMove_t const *const full_move)
	check if a full move is feasible
static int	DPTresetFlags (void)
	This function reset all flags to zero, we do this every time that we make a substancial improvement.
static int	DPTStoreFullMove (const unsigned int nc_id, DPTFullMove_t const *const full_move)
	This function stores a move in a node.
static int	DPTResetMove (DPTFullMove_t *move)
	reset a full move to all no-move
static int	DPTupdateNeighMove (DPTFullMove_t *full_move)
	This function update the moves of all neighbours in a full move.
int	DPtighten (int n_nodes, int n_edges, int *edges, double const *const external_weight, int n_dominos, int *n_aset, int *n_bset, int n_handle, int **aset, int **bset, int *handle, int **new_n_aset, int **new_n_bset, int *new_n_handle, int ***new_aset, int ***new_bset, int **new_handle, double *violation)
Variables
static const char	move_name [11][20]
static unsigned char	DPT_inv_move [11]

---

Define Documentation

#define DPT_ENABLE   1

Definition at line 6 of file eg_dptighten.c.

#define DPT_MAX_DEPTH   1U

Definition at line 18 of file eg_dptighten.c.

#define DPT_MAX_DOM   512U

Definition at line 14 of file eg_dptighten.c.

#define DPT_MAX_DOM_LOG   9U

Definition at line 15 of file eg_dptighten.c.

#define DPT_MAX_NODE   131072U

Definition at line 16 of file eg_dptighten.c.

#define DPT_MAX_NODE_LOG   17U

Definition at line 17 of file eg_dptighten.c.

#define DPTgetEdge (  __e_it   )     ((EGuGraphEdge_t*)(__e_it->this))

Definition at line 174 of file eg_dptighten.c.

#define DPTgetEdgeId (  __e_it   )     (DPTgetEdge(__e_it)->id)

Definition at line 176 of file eg_dptighten.c.

#define DPTgetOtherEndId (  __n_id, __e_it   )     (__n_id == DPTgetEdge(__e_it)->head->id ? DPTgetEdge(__e_it)->tail->id : DPTgetEdge(__e_it)->head->id)

Definition at line 175 of file eg_dptighten.c.

#define DPTgoDeeper (  __depth   )

Value: if(__depth+1<DPT_MAX_DEPTH){\ /* now we call for deeper moves */\ DPTmakeMove(base_move->move+__depth,0);\ for( e_it = all_nodes[nc_id]->edges->begin; e_it ; e_it=e_it->next){\ /*if(DPTgetOtherEndId(nc_id,e_it)<nc_id)*/\ DPTSetBestMove( DPTgetOtherEndId( nc_id, e_it), best_move, \ base_move, __depth + 1);}\ /* undo the last move */\ DPTmakeInvMove(base_move->move+__depth,0);\ } @ brief, call the best move on a deeper base Definition at line 1425 of file eg_dptighten.c.

#define DPTmakeMove (  __move, __flags   )     __DPTmakeMove(__move,__flags,__LINE__,__FILE__,__func__)

given a node, and a move, make it Definition at line 1304 of file eg_dptighten.c.

#define DPTmakeMoveHcH (  __move, __flags   )     DPTmakeMoveHHc(__move,__flags)

Perform a DPT_HcH move. Definition at line 1153 of file eg_dptighten.c.

#define DPTMinImprovement   (-1e-6)

Definition at line 127 of file eg_dptighten.c.

#define DPTNdata (  __this   )     ((DPTNdata_t*)(__this))

Definition at line 177 of file eg_dptighten.c.

#define DPTpriceHcH (  __id, __val   )     DPTpriceHHc(__id,__val)

This function prices the move Hc H, assuming the move is feasible. Definition at line 719 of file eg_dptighten.c.

#define DPTupdateMove (  __cmove, __bmove   )     __DPTupdateMove(__cmove,__bmove)

, check if we should update a move, if so, do the update Definition at line 395 of file eg_dptighten.c.

---

Typedef Documentation

typedef static EGuGraphEdge_t** all_edges [static]

Definition at line 117 of file eg_dptighten.c.

typedef static EGuGraphNode_t** all_nodes [static]

Definition at line 116 of file eg_dptighten.c.

typedef struct DPTNdata_t DPTNdata_t

Definition at line 107 of file eg_dptighten.c.

typedef static DPTEdata_t* edgeData = 0 [static]

Definition at line 113 of file eg_dptighten.c.

typedef static EGuGraph_t* G = 0 [static]

Definition at line 115 of file eg_dptighten.c.

typedef static DPTGdata_t graphData [static]

Definition at line 114 of file eg_dptighten.c.

typedef static EGbitset_t node_update[DPT_MAX_NODE >> __EGBIT_SHIFT__] [static]

Definition at line 120 of file eg_dptighten.c.

typedef static DPTNdata_t* nodeData = 0 [static]

Definition at line 112 of file eg_dptighten.c.

typedef static EGbbtree_t* tree [static]

Definition at line 119 of file eg_dptighten.c.

typedef static double const* weight [static]

Definition at line 118 of file eg_dptighten.c.

---

Enumeration Type Documentation

enum move

Enumerator: DPT_Tc_A  DPT_Tc_B  DPT_Hc_H  DPT_A_B  DPT_B_A  DPT_B_A_flipH  DPT_A_B_flipH  DPT_A_Tc  DPT_B_Tc  DPT_H_Hc  DPT_no_move  Definition at line 130 of file eg_dptighten.c.

---

Function Documentation

static int __DPTmakeMove (  DPTMove_t const *const   move, const unsigned int  update_flags, const int  line, const char *  file, const char *  function )  [static]

Definition at line 1305 of file eg_dptighten.c.

static int __DPTupdateMove (  const DPTFullMove_t *const   cur_move, DPTFullMove_t *const   best_move )  [inline, static]

Definition at line 397 of file eg_dptighten.c.

int DPtighten (  int  n_nodes, int  n_edges, int *  edges, double const *const   external_weight, int  n_dominos, int *  n_aset, int *  n_bset, int  n_handle, int **  aset, int **  bset, int *  handle, int **  new_n_aset, int **  new_n_bset, int *  new_n_handle, int ***  new_aset, int ***  new_bset, int **  new_handle, double *  violation )

Definition at line 1847 of file eg_dptighten.c.

static int DPTisFullMoveFeasible (  DPTFullMove_t const *const   full_move  )  [inline, static]

check if a full move is feasible Definition at line 1692 of file eg_dptighten.c.

static int DPTisMoveFeasible (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

given a node, and a move, check if it is feasible, if update_flags is set to one, then it will check the constrains imposed by them. Definition at line 1618 of file eg_dptighten.c.

static int DPTmakeFullMove (  DPTFullMove_t const *const   full_move  )  [inline, static]

Make a full move (in his whole depth ). Definition at line 1414 of file eg_dptighten.c.

static int DPTmakeInvMove (  DPTMove_t const *const   move, const unsigned int  update_flags )  [static]

given a node, and a move, make the inverse move Definition at line 1361 of file eg_dptighten.c.

static int DPTmakeMoveAB (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_AB move. Definition at line 916 of file eg_dptighten.c.

static int DPTmakeMoveABflipH (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_AB_flipH move. Definition at line 1073 of file eg_dptighten.c.

static int DPTmakeMoveATc (  DPTMove_t const *const   move  )  [inline, static]

Perform a DPT_ATc move. Definition at line 1256 of file eg_dptighten.c.

static int DPTmakeMoveBA (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_BA move. Definition at line 966 of file eg_dptighten.c.

static int DPTmakeMoveBAflipH (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_BA_flipH move. Definition at line 1016 of file eg_dptighten.c.

static int DPTmakeMoveBTc (  DPTMove_t const *const   move  )  [inline, static]

Perform a DPT_BTc move. Definition at line 1158 of file eg_dptighten.c.

static int DPTmakeMoveHHc (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_HHc move. Definition at line 1129 of file eg_dptighten.c.

static int DPTmakeMoveTcA (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_TcA move. Definition at line 810 of file eg_dptighten.c.

static int DPTmakeMoveTcB (  DPTMove_t const *const   move, const unsigned int  update_flags )  [inline, static]

Perform a DPT_TcB move. Definition at line 864 of file eg_dptighten.c.

static int DPTpriceAB (  const DPTMove_t *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move A B, assuming the move is feasible. Definition at line 527 of file eg_dptighten.c.

static int DPTpriceABflipH (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move A to B, and flip the node in H, assuming the move is feasible. Definition at line 569 of file eg_dptighten.c.

static int DPTpriceATc (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move A Tc, assuming the move is feasible. Definition at line 767 of file eg_dptighten.c.

static int DPTpriceBA (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move B A, assuming the move is feasible. Definition at line 612 of file eg_dptighten.c.

static int DPTpriceBAflipH (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move B to A, and flip the node in H, assuming the move is feasible. Definition at line 654 of file eg_dptighten.c.

static int DPTpriceBTc (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move B Tc, assuming the move is feasible. Definition at line 724 of file eg_dptighten.c.

static void DPTpriceConstraint (  double *  l_violation  )  [inline, static]

Definition at line 295 of file eg_dptighten.c.

static int DPTpriceHHc (  DPTMove_t const *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move H Hc, assuming the move is feasible. Definition at line 697 of file eg_dptighten.c.

static int DPTpriceTcA (  const DPTMove_t *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move Tc A, assuming the move is feasible. Definition at line 437 of file eg_dptighten.c.

static int DPTpriceTcB (  const DPTMove_t *const   cur_move, double *const   move_val )  [inline, static]

This function prices the move Tc B, assuming the move is feasible. Definition at line 482 of file eg_dptighten.c.

static int DPTresetFlags (  void   )  [inline, static]

This function reset all flags to zero, we do this every time that we make a substancial improvement. Definition at line 1718 of file eg_dptighten.c.

static int DPTResetMove (  DPTFullMove_t *  move  )  [inline, static]

reset a full move to all no-move Definition at line 1756 of file eg_dptighten.c.

static int DPTSetBestMove (  const unsigned int  nc_id, DPTFullMove_t *const   best_move, DPTFullMove_t *const   base_move, const unsigned int  depth )  [static]

, given a node, compute the best possible move for it, taking into acount if the node has been added to the T set before or not, remember that the priority is to add, and then to substract, note that this change is not reflected in the tree of best moves, you have to do it outside this function. the best move and value is stored in the given field, the actual best move stored inside the node data is not changed. Definition at line 1445 of file eg_dptighten.c.

static int DPTStoreFullMove (  const unsigned int  nc_id, DPTFullMove_t const *const   full_move )  [inline, static]

This function stores a move in a node. Definition at line 1736 of file eg_dptighten.c.

static int DPTTestEdges (  void   )  [inline, static]

This function check that the edges got the wright values in hteir data. Definition at line 1206 of file eg_dptighten.c.

static int DPTupdateNeighMove (  DPTFullMove_t *  full_move  )  [inline, static]

This function update the moves of all neighbours in a full move. Definition at line 1765 of file eg_dptighten.c.

static int EGdpTightNdataCompare (  const void *  N1, const void *  N2 )  [static]

This function compare two node data information. Definition at line 349 of file eg_dptighten.c.

---

Variable Documentation

unsigned char DPT_inv_move[11] [static]

Initial value: {[DPT_no_move] = DPT_no_move, [DPT_A_Tc] = DPT_Tc_A, [DPT_B_Tc] = DPT_Tc_B, [DPT_A_B] = DPT_B_A, [DPT_H_Hc] = DPT_Hc_H, [DPT_Tc_A] = DPT_A_Tc, [DPT_Tc_B] = DPT_B_Tc, [DPT_B_A] = DPT_A_B, [DPT_Hc_H] = DPT_H_Hc, [DPT_A_B_flipH] = DPT_B_A_flipH, [DPT_B_A_flipH] = DPT_A_B_flipH } Definition at line 159 of file eg_dptighten.c.

const char move_name[11][20] [static]

Initial value: {[DPT_no_move] = "DPT_no_move", [DPT_A_Tc] = "DPT_A_Tc", [DPT_B_Tc] = "DPT_B_Tc", [DPT_A_B] = "DPT_A_B", [DPT_H_Hc] = "DPT_H_Hc", [DPT_Tc_A] = "DPT_Tc_A", [DPT_Tc_B] = "DPT_Tc_B", [DPT_B_A] = "DPT_B_A", [DPT_Hc_H] = "DPT_Hc_H", [DPT_A_B_flipH] = "DPT_A_B_flipH", [DPT_B_A_flipH] = "DPT_B_A_flipH" } Definition at line 146 of file eg_dptighten.c.

---