eg_greedykp.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "eg_greedytypes.h"
#include "eg_kppairs.h"
#include "karger.h"
#include "eg_greedysample.h"

Include dependency graph for eg_greedykp.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
EGdkdomino_t *	EGdcutToDKdom (unsigned int max_k, EGdualCut_t *dc, unsigned int orientation, EGmemPool_t *mem)
EGdkdomino_t *	EGddominoToDKdom (EGddomino_t *ddom, int h, int max_nh, EGgreedyData_t *gdata, EGmemPool_t *mem, unsigned char *const pndummy, unsigned char *const pedummy)
void	EGfreeDKdomino (void *v, EGmemPool_t *mem)
EGgreedyData_t *	EGnewGreedyData (EGmemPool_t *mem)
void	EGfreeGreedyData (void *vdata)
int	EGfillGreedyData (EGgreedyData_t *data, EGdGraph_t *bdG, EGlist_t *ddom_list, EGlist_t **dembed, graphP G, int norig_nodes, int norig_edges, int nplanar_edges, int *orig_edges, int *planar_edges, double *orig_weight, double *planar_weight)
EGdualCut_t *	EGnewDualCut (EGmemPool_t *mem, unsigned int sz)
EGdualCut_t *	EGcopyDualCut (EGmemPool_t *mem, EGdualCut_t *dc_in)
void	EGfreeDualCut (void *v, EGmemPool_t *mem)
EGdcutIter_t *	EGnewDcutIter (EGgreedyData_t *gdata)
void	EGfreeDcutIter (void *v)
EGdkpc_t *	EGdkdomToDKPC (EGdkdomino_t *dkdom, EGmemPool_t *mem)
EGdkpc_t *	EGdcutToDKPC (EGdualCut_t *dc, unsigned int orientation, EGmemPool_t *mem)
void	EGfreeDKPC (void *v, EGmemPool_t *mem)
int	EGincrementDcutIter (EGdcutIter_t *zit)
EGdualCut_t *	EGgetDcut (EGdcutIter_t *zit)
int	EGgetEvenPrec (unsigned int s, unsigned int t, EGgreedyData_t *data)
int	EGgetOddPrec (unsigned int s, unsigned int t, EGgreedyData_t *data)
EGdijkstraCost_t	EGgetEvenDistance (unsigned s, unsigned t, EGgreedyData_t *data)
EGdijkstraCost_t	EGgetOddDistance (unsigned s, unsigned t, EGgreedyData_t *data)
void	EGdisplayDualCut (FILE *fout, EGdualCut_t *dc)
void	EGdisplayInternalPair (FILE *fout, EGinternalPairs_t *p)
void	EGdisplayDKdomino (FILE *fout, EGdkdomino_t *dkdom)
void	EGdisplayDKPC (FILE *fout, EGdkpc_t *dkpc)
void	EGtraceDistance (unsigned int s, unsigned int t, EGgreedyData_t *data)
int	EGextractEEpath (unsigned int s, unsigned int t, EGgreedyData_t *data, EGlist_t *path)
EGdualCut_t *	EGextractHandleCut (EGdkpc_t *dkpc, unsigned int h)
int	EGgrowHandle (EGdkpc_t *dkpc, EGdkdomino_t *link_dkdom, EGinternalPairs_t *p, EGgreedyData_t *data, EGmemPool_t *mem, unsigned char *const pndummy, unsigned char *const pedummy)
int	EGremoveHandles (EGdkpc_t *dkpc, EGmemPool_t *mem)
int	EGgrowDKdomino (EGdkdomino_t *dkd, EGinternalPairs_t *p, int handle_num, EGmemPool_t *mem)
int	EGprimalizeDKPC (EGdkpc_t *dkpc, EGgreedyData_t *gdata, EGpkpc_t *pkpc, unsigned char *const pndummy, unsigned char *const pedummy)
int	EGprimalizeDKPCB (EGdkpc_t *dkpc, EGgreedyData_t *gdata, 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, unsigned char *const pndummy, unsigned char *const pedummy)
int	EGnewPKPCset (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)
void	EGfreePKPC (void *v)
int	EGfreePKPCB (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	EGcomputeInterfaceValue (int T_size, int *T_nodes, int A_size, int *A_nodes, int nnodes, int nedges, int *edges, double *weight, unsigned char *dummy)
void	EGcomputeDualCutValue (EGdualCut_t *dc)
double	EGcomputePrimalCutValue (EGgreedyData_t *data, EGpkpc_t *pkpc, int set_size, int *set_nodes, int nnodes, int nedges, int *edges, double *weight, unsigned char *dummy)
EGdijkstraCost_t	EGcomputeDKPCslack (EGdkpc_t *dkpc)
double	EGcomputePKPCslack (EGgreedyData_t *data, EGpkpc_t *pkpc, int nnodes, int nedges, int *edges, double *weight)
int	EGkpTo2pTooth (int kp_size, int *kp_nodes, int kp_k, int *kp_handles, int *kp_nhalf, int **kp_halves, int *tp_naset, int *tp_nbset, int *tp_nmset, int **tp_aset, int **tp_bset, int **tp_mset, int nnodes, unsigned char *vdummy)
double	EGcomputePKPCBslack (EGgreedyData_t *data, EGpkpc_t *pkpc, 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, int nnodes, int nedges, int *edges, double *weight)
int	KPseparateFromDualCut (EGdualCut_t *dcut, unsigned int orientation, EGgreedyData_t *gdata, int *nadded, double *minslack, double sample_time)
void	EGdisplayStatus (FILE *fout, EGgreedyData_t *gdata)
int	EGaddDualCutToHeap (EGheap_t *h, EGdualCut_t *dc, int orientation, double lfval, EGmemPool_t *mem)
int	KPprocess_cut (int *cutset, int cutsize, double cutweight, void *process_indo, setlist **sets)
int	EGareDualCutsEqual (EGdualCut_t *a, EGdualCut_t *b)

---

Function Documentation

int EGaddDualCutToHeap (  EGheap_t *  h, EGdualCut_t *  dc, int  orientation, double  lfval, EGmemPool_t *  mem )

Definition at line 2038 of file eg_greedykp.c.

int EGareDualCutsEqual (  EGdualCut_t *  a, EGdualCut_t *  b )

Definition at line 2095 of file eg_greedykp.c.

EGdijkstraCost_t EGcomputeDKPCslack (  EGdkpc_t *  dkpc  )

Definition at line 732 of file eg_greedykp.c.

void EGcomputeDualCutValue (  EGdualCut_t *  dc  )

Definition at line 1335 of file eg_greedykp.c.

double EGcomputeInterfaceValue (  int  T_size, int *  T_nodes, int  A_size, int *  A_nodes, int  nnodes, int  nedges, int *  edges, double *  weight, unsigned char *  dummy )

Definition at line 1382 of file eg_greedykp.c.

double EGcomputePKPCBslack (  EGgreedyData_t *  data, EGpkpc_t *  pkpc, 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, int  nnodes, int  nedges, int *  edges, double *  weight )

Definition at line 1460 of file eg_greedykp.c.

double EGcomputePKPCslack (  EGgreedyData_t *  data, EGpkpc_t *  pkpc, int  nnodes, int  nedges, int *  edges, double *  weight )

Definition at line 1435 of file eg_greedykp.c.

double EGcomputePrimalCutValue (  EGgreedyData_t *  data, EGpkpc_t *  pkpc, int  set_size, int *  set_nodes, int  nnodes, int  nedges, int *  edges, double *  weight, unsigned char *  dummy )

Definition at line 1353 of file eg_greedykp.c.

EGdualCut_t* EGcopyDualCut (  EGmemPool_t *  mem, EGdualCut_t *  dc_in )

Definition at line 1702 of file eg_greedykp.c.

EGdkdomino_t* EGdcutToDKdom (  unsigned int  max_k, EGdualCut_t *  dc, unsigned int  orientation, EGmemPool_t *  mem )

Definition at line 666 of file eg_greedykp.c.

EGdkpc_t* EGdcutToDKPC (  EGdualCut_t *  dc, unsigned int  orientation, EGmemPool_t *  mem )

Definition at line 635 of file eg_greedykp.c.

EGdkdomino_t* EGddominoToDKdom (  EGddomino_t *  ddom, int  h, int  max_nh, EGgreedyData_t *  gdata, EGmemPool_t *  mem, unsigned char *const   pndummy, unsigned char *const   pedummy )

Definition at line 854 of file eg_greedykp.c.

void EGdisplayDKdomino (  FILE *  fout, EGdkdomino_t *  dkdom )

Definition at line 990 of file eg_greedykp.c.

void EGdisplayDKPC (  FILE *  fout, EGdkpc_t *  dkpc )

Definition at line 1018 of file eg_greedykp.c.

void EGdisplayDualCut (  FILE *  fout, EGdualCut_t *  dc )

Definition at line 947 of file eg_greedykp.c.

void EGdisplayInternalPair (  FILE *  fout, EGinternalPairs_t *  p )

Definition at line 968 of file eg_greedykp.c.

void EGdisplayStatus (  FILE *  fout, EGgreedyData_t *  gdata )

Definition at line 1957 of file eg_greedykp.c.

EGdkpc_t* EGdkdomToDKPC (  EGdkdomino_t *  dkdom, EGmemPool_t *  mem )

Definition at line 612 of file eg_greedykp.c.

int EGextractEEpath (  unsigned int  s, unsigned int  t, EGgreedyData_t *  data, EGlist_t *  path )

Definition at line 523 of file eg_greedykp.c.

EGdualCut_t* EGextractHandleCut (  EGdkpc_t *  dkpc, unsigned int  h )

Definition at line 909 of file eg_greedykp.c.

int EGfillGreedyData (  EGgreedyData_t *  data, EGdGraph_t *  bdG, EGlist_t *  ddom_list, EGlist_t **  dembed, graphP  G, int  norig_nodes, int  norig_edges, int  nplanar_edges, int *  orig_edges, int *  planar_edges, double *  orig_weight, double *  planar_weight )

Definition at line 90 of file eg_greedykp.c.

void EGfreeDcutIter (  void *  v  )

Definition at line 372 of file eg_greedykp.c.

void EGfreeDKdomino (  void *  v, EGmemPool_t *  mem )

Definition at line 687 of file eg_greedykp.c.

void EGfreeDKPC (  void *  v, EGmemPool_t *  mem )

Definition at line 646 of file eg_greedykp.c.

void EGfreeDualCut (  void *  v, EGmemPool_t *  mem )

Definition at line 339 of file eg_greedykp.c.

void EGfreeGreedyData (  void *  vdata  )

Definition at line 22 of file eg_greedykp.c.

void EGfreePKPC (  void *  v  )

Definition at line 1241 of file eg_greedykp.c.

int EGfreePKPCB (  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 )

Definition at line 1263 of file eg_greedykp.c.

EGdualCut_t* EGgetDcut (  EGdcutIter_t *  zit  )

Definition at line 417 of file eg_greedykp.c.

EGdijkstraCost_t EGgetEvenDistance (  unsigned  s, unsigned  t, EGgreedyData_t *  data )

note that s and t are not sorted in any way, the corresnpond to a node ID in the bdG graph Definition at line 494 of file eg_greedykp.c.

int EGgetEvenPrec (  unsigned int  s, unsigned int  t, EGgreedyData_t *  data )

Definition at line 479 of file eg_greedykp.c.

EGdijkstraCost_t EGgetOddDistance (  unsigned  s, unsigned  t, EGgreedyData_t *  data )

Definition at line 512 of file eg_greedykp.c.

int EGgetOddPrec (  unsigned int  s, unsigned int  t, EGgreedyData_t *  data )

Definition at line 469 of file eg_greedykp.c.

int EGgrowDKdomino (  EGdkdomino_t *  dkd, EGinternalPairs_t *  p, int  handle_num, EGmemPool_t *  mem )

Definition at line 827 of file eg_greedykp.c.

int EGgrowHandle (  EGdkpc_t *  dkpc, EGdkdomino_t *  link_dkdom, EGinternalPairs_t *  p, EGgreedyData_t *  data, EGmemPool_t *  mem, unsigned char *const   pndummy, unsigned char *const   pedummy )

Definition at line 769 of file eg_greedykp.c.

int EGincrementDcutIter (  EGdcutIter_t *  zit  )

Definition at line 388 of file eg_greedykp.c.

int EGkpTo2pTooth (  int  kp_size, int *  kp_nodes, int  kp_k, int *  kp_handles, int *  kp_nhalf, int **  kp_halves, int *  tp_naset, int *  tp_nbset, int *  tp_nmset, int **  tp_aset, int **  tp_bset, int **  tp_mset, int  nnodes, unsigned char *  vdummy )

Definition at line 1571 of file eg_greedykp.c.

EGdcutIter_t* EGnewDcutIter (  EGgreedyData_t *  gdata  )

Definition at line 352 of file eg_greedykp.c.

EGdualCut_t* EGnewDualCut (  EGmemPool_t *  mem, unsigned int  sz )

Definition at line 320 of file eg_greedykp.c.

EGgreedyData_t* EGnewGreedyData (  EGmemPool_t *  mem  )

Definition at line 4 of file eg_greedykp.c.

int EGnewPKPCset (  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 )

Definition at line 1305 of file eg_greedykp.c.

int EGprimalizeDKPC (  EGdkpc_t *  dkpc, EGgreedyData_t *  gdata, EGpkpc_t *  pkpc, unsigned char *const   pndummy, unsigned char *const   pedummy )

Definition at line 1072 of file eg_greedykp.c.

int EGprimalizeDKPCB (  EGdkpc_t *  dkpc, EGgreedyData_t *  gdata, 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, unsigned char *const   pndummy, unsigned char *const   pedummy )

Definition at line 1140 of file eg_greedykp.c.

int EGremoveHandles (  EGdkpc_t *  dkpc, EGmemPool_t *  mem )

Definition at line 1656 of file eg_greedykp.c.

void EGtraceDistance (  unsigned int  s, unsigned int  t, EGgreedyData_t *  data )

int KPprocess_cut (  int *  cutset, int  cutsize, double  cutweight, void *  process_indo, setlist **  sets )

Definition at line 1982 of file eg_greedykp.c.

int KPseparateFromDualCut (  EGdualCut_t *  dcut, unsigned int  orientation, EGgreedyData_t *  gdata, int *  nadded, double *  minslack, double  sample_time )

Definition at line 1719 of file eg_greedykp.c.

---