lib

eg_kppairs.c File Reference

#include "eg_kppairs.h"

Include dependency graph for eg_kppairs.c:

Go to the source code of this file.

Defines

#define GETOTHEREND(_cedge)   (G->G[gp_GetTwinArc(G,_cedge - G->G)].v)
#define GETROOTEDGE(curroot)   (G->G + G->G[curroot].link[1])
#define GETNEXTEDGE(curedge, curroot)   ((curedge->link[1] < G->N) ? GETROOTEDGE(curroot) : (G->G + curedge->link[1]))
#define EG_KPPAIRS_VERBOSE   100
#define EG_KPPAIRS_DEBUG   0
#define KP_CHECK_SUM_IS_LESS(a, b, c)   WARNINGL(EG_KPPAIRS_DEBUG, EGdijkstraCostIsLess( EGdijkstraCostAdd((a),(b)), EGdijkstraToCost(c)), "Inequality not satisfied %lf < %lf", EGdijkstraCostToLf(EGdijkstraCostAdd((a), (b))), c)

Functions

static int EGdoPrimalDfs (const unsigned n_marks, size_t *const set_sz, EGlist_t **CUT, unsigned char *const node_mark, unsigned char *const edge_mark, EGgreedyData_t *const data)
 , given a set of marked edges, do DFS, we need as many lists as posible marks, the marks are bynary bits... needs an array of node marks and edge marks (of unsigned chars), previous information will be lost. Node 0 is always in the set 0. nodemarks will be marked as the according set where they bellong.
int EGgenerateInternalPairs (EGgreedyData_t *const data, EGdkdomino_t *const zerodom, const unsigned int orientation, EGlist_t *const pairs, const unsigned max_pairs, double const percentage, unsigned char *const node_mark, unsigned char *const edge_mark, EGdGraphNode_t **const dc_nodes)
 return in a heap, all pairs in the boundary of the zero domino, whose total value (i.e. even path + internal path) is less than two.
void EGinternalPairsClear (void *pair, EGmemPool_t *mem)
 destructor for greedytypes
void EGfreeInternalPairs (void *pair, EGmemPool_t *mem)
 destructor for greedytypes
int EGgetCutNodes (EGgreedyData_t *const data, EGdualCut_t *const dualcut, const unsigned int orientation, int *const cutsz, int **const cutnodes, unsigned char *const node_mark, unsigned char *const edge_mark)
 given a cut and an orientation, return the primal nodes in the cut with that orientation.
int EGgetANodes (EGgreedyData_t *const data, EGdkdomino_t *const kdom, int unsigned const k, int *const cutsz, int **const cutnodes, unsigned char *const node_mark, unsigned char *const edge_mark, EGdGraphEdge_t **const dc_nodes)
 given a k-dom and a path, return the primal nodes in the A halve, the orientation is taken from the k-dom structure.
int EGgetOrientation (EGgreedyData_t *const data, EGdualCut_t *const dualcut, int unsigned const pathsz, EGdGraphEdge_t **const path, unsigned int *const orientation, unsigned char *const node_mark, unsigned char *const edge_mark)
 given a dual cut and an internal path, return the orientation of the path.
int EGgetDualCut (EGgreedyData_t *const data, EGdualCut_t **const dualcut, const int pset_sz, const int *const pset, unsigned char *const node_mark, unsigned char *const edge_mark, EGdGraphEdge_t **const dc_nodes)
 Given a primal cut, return a dual cut.

Variables

static size_t os [EG_MENGER_NUMOS]
static size_t dij_os [6]

Define Documentation

#define EG_KPPAIRS_DEBUG   0
 

Definition at line 9 of file eg_kppairs.c.

#define EG_KPPAIRS_VERBOSE   100
 

Definition at line 8 of file eg_kppairs.c.

#define GETNEXTEDGE (  curedge,
curroot   )     ((curedge->link[1] < G->N) ? GETROOTEDGE(curroot) : (G->G + curedge->link[1]))
 

Definition at line 5 of file eg_kppairs.c.

#define GETOTHEREND (  _cedge   )     (G->G[gp_GetTwinArc(G,_cedge - G->G)].v)
 

Definition at line 3 of file eg_kppairs.c.

#define GETROOTEDGE (  curroot   )     (G->G + G->G[curroot].link[1])
 

Definition at line 4 of file eg_kppairs.c.

#define KP_CHECK_SUM_IS_LESS (  a,
b,
c   )     WARNINGL(EG_KPPAIRS_DEBUG, EGdijkstraCostIsLess( EGdijkstraCostAdd((a),(b)), EGdijkstraToCost(c)), "Inequality not satisfied %lf < %lf", EGdijkstraCostToLf(EGdijkstraCostAdd((a), (b))), c)
 

Definition at line 36 of file eg_kppairs.c.

Function Documentation

static int EGdoPrimalDfs (  const unsigned  n_marks,
size_t *const   set_sz,
EGlist_t **  CUT,
unsigned char *const   node_mark,
unsigned char *const   edge_mark,
EGgreedyData_t *const   data
)  [static]
 

, given a set of marked edges, do DFS, we need as many lists as posible marks, the marks are bynary bits... needs an array of node marks and edge marks (of unsigned chars), previous information will be lost. Node 0 is always in the set 0. nodemarks will be marked as the according set where they bellong.

Parameters:
n_marks posible number of different labels.
CUT array of length n_marks of lists for the DFS, the lists must be empty.
node_mark array initialized as zero, containing where each node bellongs to (marked as mark+1). transitions to use in edges, the marks transitions with logic xor.
set_sz array of length n_marks storing the size of the founded sets.
data greedy KP data.
Returns:
zero on success, non-zero otherwise.
Note:
For this algorithm to work, the set of marks on the edges must define a cut in the normal sense (althought the cut may not be connected). Also, the edge_mark 128 is used to mark an edge as traversed, so it can't be used to denote a set.

Definition at line 58 of file eg_kppairs.c.

void EGfreeInternalPairs (  void *  pair,
EGmemPool_t *  mem
) 
 

destructor for greedytypes

Definition at line 336 of file eg_kppairs.c.

int EGgenerateInternalPairs (  EGgreedyData_t *const   data,
EGdkdomino_t *const   zerodom,
const unsigned int  orientation,
EGlist_t *const   pairs,
const unsigned  max_pairs,
double const   percentage,
unsigned char *const   node_mark,
unsigned char *const   edge_mark,
EGdGraphNode_t **const   dc_nodes
) 
 

return in a heap, all pairs in the boundary of the zero domino, whose total value (i.e. even path + internal path) is less than two.

Parameters:
data information related to the problem.
zerodom zero domino in wich we will look for pairs.
orientation if zero, then compute internal paairs, else, compute external pairs.
pairs sorted list (up to size max_pairs) storing the best pairs. we assume that the best pair is at the beginning of the list, and the worst pair is at the end of the list.
max_pairs maximum elements to be stored in the list.
percentage percentage of the bound of two to use while generating all internal pairs.
node_mark array of length N_PRIMAL_NODES to be used internally.
edge_mark array of length N_PRIMAL_EDGES to be used internally.
dc_nodes array of length N_DUAL_NODES to be used internally.
Returns:
zero on success, non-zero otherwise.

Definition at line 125 of file eg_kppairs.c.

int EGgetANodes (  EGgreedyData_t *const   data,
EGdkdomino_t *const   kdom,
int unsigned const   k,
int *const   cutsz,
int **const   cutnodes,
unsigned char *const   node_mark,
unsigned char *const   edge_mark,
EGdGraphEdge_t **const   dc_nodes
) 
 

given a k-dom and a path, return the primal nodes in the A halve, the orientation is taken from the k-dom structure.

Parameters:
data structure containing all pertinent data to the problem.
kdom k-dom for wich we want the primal A-nodes.
k for wich path we want the A-nodes.
cutsz pointer to an integer where we will return the number of nodes in the cut.
cutnodes pointer to an array, the function will allocate the array if it is NULL, otherwise will use the given array and assume that is large enough.
node_mark array of length N_PRIMAL_NODES to be used internally.
edge_mark array of length N_PRIMAL_EDGES to be used internally.
dc_nodes array of length N_DUAL_NODES to be used internally.
Returns:
zero on success, non-zero otherwise.

Definition at line 395 of file eg_kppairs.c.

int EGgetCutNodes (  EGgreedyData_t *const   data,
EGdualCut_t *const   dualcut,
const unsigned int  orientation,
int *const   cutsz,
int **const   cutnodes,
unsigned char *const   node_mark,
unsigned char *const   edge_mark
) 
 

given a cut and an orientation, return the primal nodes in the cut with that orientation.

Parameters:
data structure containing all pertinent data to the problem.
dualcut cut for wich we want the primal nodes.
orientation wich side of the cut we want.
cutsz pointer to an integer where we will return the number of nodes in the cut.
cutnodes pointer to an array, the function will allocate the array if it is NULL, otherwise will use the given array and assume that is large enough.
node_mark array of length N_PRIMAL_NODES to be used internally.
edge_mark array of length N_PRIMAL_EDGES to be used internally.
Returns:
zero on success, non-zero otherwise.

Definition at line 344 of file eg_kppairs.c.

int EGgetDualCut (  EGgreedyData_t *const   data,
EGdualCut_t **const   dualcut,
const int  pset_sz,
const int *const   pset,
unsigned char *const   node_mark,
unsigned char *const   edge_mark,
EGdGraphEdge_t **const   dc_edges
) 
 

Given a primal cut, return a dual cut.

Parameters:
data structure containing all pertinent data to the problem.
node_mark array of length N_PRIMAL_NODES to be used internally.
dc_edges array of length N_PRIMAL_EDGES to be used internally.
pset_sz size of the primal set (number of nodes)
pset array of length pset_sz containing all nodes in the primal set
edge_mark array of length N_PRIMAL_EDGES to be used internally.
dualcut pointer to where to retunr the new dualcut.
Returns:
zero on success, non-zero otherwise.

Definition at line 548 of file eg_kppairs.c.

int EGgetOrientation (  EGgreedyData_t *const   data,
EGdualCut_t *const   dualcut,
int unsigned const   pathsz,
EGdGraphEdge_t **const   path,
unsigned int *const   orientation,
unsigned char *const   node_mark,
unsigned char *const   edge_mark
) 
 

given a dual cut and an internal path, return the orientation of the path.

Parameters:
data structure containing all pertinent data to the problem.
dualcut cut where we are working.
pathsz number of edges in the internal path.
path array of pointer of edges in the internal path.
orientation pointer where we will retunr the orientation.
node_mark array of length N_PRIMAL_NODES to be used internally.
edge_mark array of length N_PRIMAL_EDGES to be used internally.
Returns:
zero on success, non-zero otherwise.

Definition at line 496 of file eg_kppairs.c.

void EGinternalPairsClear (  void *  pair,
EGmemPool_t *  mem
) 
 

destructor for greedytypes

Definition at line 319 of file eg_kppairs.c.

Variable Documentation

size_t dij_os[6] [static]
 

Initial value:

 { 
    [EG_DIJ_DIST] = offsetof (EGmengerNodeData_t, orig_dist),
    [EG_DIJ_NDIST] = offsetof (EGmengerNodeData_t, orig_ndist),
    [EG_DIJ_FATHER] = offsetof (EGmengerNodeData_t, orig_father),
    [EG_DIJ_MARKER] = offsetof (EGmengerNodeData_t, orig_marker),
    [EG_DIJ_HCONNECTOR] = offsetof (EGmengerNodeData_t, hc),
    [EG_DIJ_ELENGTH] = offsetof (EGmengerEdgeData_t, cost)
  }

Definition at line 27 of file eg_kppairs.c.

size_t os[EG_MENGER_NUMOS] [static]
 

Initial value:

 {
    [EG_MENGER_PI] = offsetof (EGmengerNodeData_t, pi),
    [EG_MENGER_DIST] = offsetof (EGmengerNodeData_t, dist),
    [EG_MENGER_ORIG_DIST] = offsetof (EGmengerNodeData_t, orig_dist),
    [EG_MENGER_NDIST] = offsetof (EGmengerNodeData_t, ndist),
    [EG_MENGER_ORIG_NDIST] = offsetof (EGmengerNodeData_t, orig_ndist),
    [EG_MENGER_MARK] = offsetof (EGmengerNodeData_t, marker),
    [EG_MENGER_ORIG_MARK] = offsetof (EGmengerNodeData_t, orig_marker),
    [EG_MENGER_FATHER] = offsetof (EGmengerNodeData_t, father),
    [EG_MENGER_ORIG_FATHER] = offsetof (EGmengerNodeData_t, orig_father),
    [EG_MENGER_HEAP_CONNECTOR] = offsetof (EGmengerNodeData_t, hc),
    [EG_MENGER_ECOST] = offsetof (EGmengerEdgeData_t, cost),
    [EG_MENGER_REDUCED_ECOST] = offsetof (EGmengerEdgeData_t, reduced_cost),
    [EG_MENGER_IS_IN_SOL] = offsetof (EGmengerEdgeData_t, is_in_solution),
    [EG_MENGER_EDATA] = offsetof (EGmengerEdgeData_t, data)
  }

Definition at line 11 of file eg_kppairs.c.

Generated on Thu Oct 20 14:58:59 2005 for DominoParitySeparator by  doxygen 1.4.5