00001 #ifndef _GREEDYKP
00002 #define _GREEDYKP
00003
00004 #include<stdio.h>
00005 #include<stdlib.h>
00006 #include<math.h>
00007
00008 #include "eg_greedytypes.h"
00009 #include "eg_kppairs.h"
00010 #include "karger.h"
00011 #include "eg_greedysample.h"
00012
00013 EGdkdomino_t* EGdcutToDKdom(unsigned int max_k,
00014 EGdualCut_t *dc,
00015 unsigned int orientation,
00016 EGmemPool_t *mem);
00017
00018 EGdkdomino_t *EGddominoToDKdom(EGddomino_t *ddom,
00019 int h,
00020 int max_nh,
00021 EGgreedyData_t *gdata,
00022 EGmemPool_t *mem,
00023 unsigned char *const pndummy,
00024 unsigned char *const pedummy);
00025
00026 void EGfreeDKdomino(void *v, EGmemPool_t *mem);
00027
00028 EGgreedyData_t* EGnewGreedyData(EGmemPool_t *mem);
00029 void EGfreeGreedyData(void *vdata);
00030
00031 int EGfillGreedyData (EGgreedyData_t * data,
00032 EGdGraph_t * bdG,
00033 EGlist_t * ddom_list,
00034 EGlist_t** dembed,
00035 graphP G,
00036 int norig_nodes,
00037 int norig_edges,
00038 int nplanar_edges,
00039 int *orig_edges,
00040 int *planar_edges,
00041 double *orig_weight,
00042 double *planar_weight);
00043
00044 EGdualCut_t* EGnewDualCut(EGmemPool_t *mem,
00045 unsigned int sz);
00046
00047 EGdualCut_t* EGcopyDualCut(EGmemPool_t *mem,
00048 EGdualCut_t *dc_in);
00049
00050 void EGfreeDualCut(void *v,
00051 EGmemPool_t *mem);
00052
00053 EGdcutIter_t* EGnewDcutIter(EGgreedyData_t *gdata);
00054 void EGfreeDcutIter(void *v);
00055
00056 EGdkpc_t* EGdkdomToDKPC(EGdkdomino_t *dkdom,
00057 EGmemPool_t *mem);
00058
00059 EGdkpc_t* EGdcutToDKPC(EGdualCut_t *dc,
00060 unsigned int orientation,
00061 EGmemPool_t *mem);
00062
00063
00064 void EGfreeDKPC(void *v,
00065 EGmemPool_t *mem);
00066
00067 int EGincrementDcutIter(EGdcutIter_t *zit);
00068 EGdualCut_t* EGgetDcut(EGdcutIter_t *zit);
00069
00070 int EGgetEvenPrec (unsigned int s,
00071 unsigned int t,
00072 EGgreedyData_t*data);
00073
00074 int EGgetOddPrec (unsigned int s,
00075 unsigned int t,
00076 EGgreedyData_t*data);
00077
00080 EGdijkstraCost_t EGgetEvenDistance (unsigned s,
00081 unsigned t,
00082 EGgreedyData_t*data);
00083
00084 #if EG_KP_HEURISTIC
00085 EGdijkstraCost_t EGgetOddDistance (unsigned s,
00086 unsigned t,
00087 EGgreedyData_t*data);
00088 #endif
00089
00090 void EGdisplayDualCut(FILE *fout, EGdualCut_t* dc);
00091 void EGdisplayInternalPair(FILE *fout, EGinternalPairs_t *p);
00092 void EGdisplayDKdomino(FILE *fout, EGdkdomino_t *dkdom);
00093 void EGdisplayDKPC(FILE *fout, EGdkpc_t *dkpc);
00094
00095 void EGtraceDistance(unsigned int s,
00096 unsigned int t,
00097 EGgreedyData_t *data);
00098
00099 int EGextractEEpath(unsigned int s,
00100 unsigned int t,
00101 EGgreedyData_t *data,
00102 EGlist_t *path);
00103
00104 EGdualCut_t* EGextractHandleCut(EGdkpc_t *dkpc, unsigned int h);
00105
00106 int EGgrowHandle(EGdkpc_t *dkpc,
00107 EGdkdomino_t *link_dkdom,
00108 EGinternalPairs_t *p,
00109 EGgreedyData_t *data,
00110 EGmemPool_t *mem,
00111 unsigned char *const pndummy,
00112 unsigned char *const pedummy);
00113
00114 int EGremoveHandles(EGdkpc_t *dkpc, EGmemPool_t *mem);
00115
00116 int EGgrowDKdomino(EGdkdomino_t *dkd,
00117 EGinternalPairs_t *p,
00118 int handle_num,
00119 EGmemPool_t *mem);
00120
00121 int EGprimalizeDKPC (EGdkpc_t *dkpc,
00122 EGgreedyData_t *gdata,
00123 EGpkpc_t *pkpc,
00124 unsigned char *const pndummy,
00125 unsigned char *const pedummy);
00126
00127 int EGprimalizeDKPCB(EGdkpc_t *dkpc,
00128 EGgreedyData_t *gdata,
00129 int *nhandles,
00130 int **handle_size,
00131 int ***handles,
00132 int *nteeth,
00133 int **teeth_size,
00134 int ***teeth,
00135 int **teeth_k,
00136 int ***teeth_handle,
00137 int ***teeth_nhalf,
00138 int ****teeth_halves,
00139 unsigned char *const pndummy,
00140 unsigned char *const pedummy);
00141
00142 int EGnewPKPCset(int nineq,
00143 int **nhandles,
00144 int ***handle_size,
00145 int ****handles,
00146 int **nteeth,
00147 int ***teeth_size,
00148 int ****teeth,
00149 int ***teeth_k,
00150 int ****teeth_handle,
00151 int ****teeth_nhalf,
00152 int *****teeth_halves);
00153
00154 void EGfreePKPC(void *v);
00155
00156 int EGfreePKPCB(int nhandles,
00157 int *handle_size,
00158 int **handles,
00159 int nteeth,
00160 int *teeth_size,
00161 int **teeth,
00162 int *teeth_k,
00163 int **teeth_handle,
00164 int **teeth_nhalf,
00165 int ***teeth_halves );
00166
00167 double EGcomputeInterfaceValue(int T_size,
00168 int *T_nodes,
00169 int A_size,
00170 int *A_nodes,
00171 int nnodes,
00172 int nedges,
00173 int *edges,
00174 double *weight,
00175 unsigned char *dummy);
00176
00177 void EGcomputeDualCutValue(EGdualCut_t *dc);
00178
00179 double EGcomputePrimalCutValue(EGgreedyData_t*data,
00180 EGpkpc_t*pkpc,
00181 int set_size,
00182 int *set_nodes,
00183 int nnodes,
00184 int nedges,
00185 int *edges,
00186 double *weight,
00187 unsigned char *dummy);
00188
00189 EGdijkstraCost_t EGcomputeDKPCslack(EGdkpc_t *dkpc);
00190
00191 double EGcomputePKPCslack( EGgreedyData_t*data,
00192 EGpkpc_t *pkpc,
00193 int nnodes,
00194 int nedges,
00195 int *edges,
00196 double *weight);
00197
00198 int EGkpTo2pTooth( int kp_size,
00199 int* kp_nodes,
00200 int kp_k,
00201 int* kp_handles,
00202 int* kp_nhalf,
00203 int** kp_halves,
00204 int *tp_naset,
00205 int *tp_nbset,
00206 int *tp_nmset,
00207 int **tp_aset,
00208 int **tp_bset,
00209 int **tp_mset,
00210 int nnodes,
00211 unsigned char *vdummy );
00212
00213 double EGcomputePKPCBslack(EGgreedyData_t*data,
00214 EGpkpc_t*pkpc,
00215 int nhandles,
00216 int *handle_size,
00217 int **handles,
00218 int nteeth,
00219 int *teeth_size,
00220 int **teeth,
00221 int *teeth_k,
00222 int **teeth_handle,
00223 int **teeth_nhalf,
00224 int ***teeth_halves,
00225 int nnodes,
00226 int nedges,
00227 int *edges,
00228 double *weight);
00229
00230 int KPseparateFromDualCut( EGdualCut_t *dcut,
00231 unsigned int orientation,
00232 EGgreedyData_t *gdata,
00233 int *nadded,
00234 double *minslack,
00235 double sample_time);
00236
00237 void EGdisplayStatus(FILE *fout, EGgreedyData_t *gdata);
00238
00239 int EGaddDualCutToHeap(EGheap_t *h,
00240 EGdualCut_t *dc,
00241 int orientation,
00242 double lfval,
00243 EGmemPool_t *mem);
00244
00245 int KPprocess_cut(int*cutset,int cutsize,double cutweight,void*process_indo,setlist**sets);
00246
00247 int EGareDualCutsEqual(EGdualCut_t *a, EGdualCut_t *b);
00248
00249 #endif
