00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef _SPP_CG_H
00018 #define _SPP_CG_H
00019
00020
00021 #include <stdio.h>
00022 #include <sym_proto.h>
00023
00024
00025 #include "spp_constants.h"
00026 #include "spp_types.h"
00027 #include "spp_cg_params.h"
00028
00029 typedef struct FNODE {
00030 int *nbrs;
00031 double *edgecosts;
00032
00033
00034 int degree;
00035 int ind;
00036
00037
00038 double val;
00039
00040 }fnode;
00041
00042 typedef struct FRAC_GRAPH {
00043
00044
00045 int nodenum;
00046 int edgenum;
00047 double density;
00048 int min_deg_node;
00049 int min_degree;
00050 int max_deg_node;
00051 int max_degree;
00052 fnode *nodes;
00053 int *all_nbr;
00054 double *all_edgecost;
00055 char *node_node;
00056
00057 }frac_graph;
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073 typedef struct LEVEL_GRAPH {
00074 int lnodenum;
00075 int levelnum;
00076 int root;
00077 int *lnodes;
00078 int *lbeg;
00079 int *level_of_node;
00080 }level_graph;
00081
00082 typedef struct CUT_COLLECTION {
00083 int size;
00084 int max_size;
00085 cut_data **cuts;
00086
00087 double *violation;
00088 int *mult;
00089 }cut_collection;
00090
00091 typedef struct SPP_CG_TMP {
00092 int *itmp_m;
00093 int **istartmp_m;
00094
00095 int *itmp_8nodenum;
00096 double *dtmp_2nodenum;
00097 char *ctmp_2nodenum;
00098 cut_data *cuttmp;
00099 }spp_cg_tmp;
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120 typedef struct SPP_CG_PROBLEM {
00121 spp_cg_params *par;
00122 spp_cg_tmp *tmp;
00123 int dg_id;
00124 char wname[MAX_FILE_NAME_LENGTH +1];
00125
00126 char lname[MAX_FILE_NAME_LENGTH +1];
00127
00128 col_ordered *cmatrix;
00129
00130 int max_sol_length;
00131
00132 col_ordered *cm_frac;
00133 row_ordered *rm_frac;
00134 frac_graph *fgraph;
00135 frac_graph *cfgraph;
00136 level_graph *lgraph;
00137 cut_collection *cut_coll;
00138
00139 int *num_cuts;
00140 int *alloc_cuts;
00141 cut_data ***cuts;
00142
00143
00144
00145 }spp_cg_problem;
00146
00147 void allocate_var_length_structures PROTO((spp_cg_problem *spp, int max_ln));
00148 void free_var_length_structures PROTO((spp_cg_problem *spp));
00149 void construct_fractional_graph PROTO((spp_cg_problem *spp, int number,
00150 int *indices, double *values));
00151 void construct_cm_frac PROTO((spp_cg_problem *spp));
00152 void construct_rm_frac PROTO((spp_cg_problem *spp));
00153 void construct_complement_graph PROTO((frac_graph *fgraph,
00154 frac_graph *cfgraph));
00155 void construct_level_graph PROTO((frac_graph *fgraph, int root,
00156 level_graph *lgraph));
00157 int register_and_send_cut PROTO((spp_cg_problem *spp, cut_data *new_cut,
00158 double violation, double etol));
00159
00160 void extend_clique_on_fgraph PROTO((spp_cg_problem *spp, cut_data *new_cut,
00161 double *pviolation));
00162 void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut));
00163 void rotate_odd_hole PROTO((int length, int *indices, int *itmp));
00164
00165 int enumerate_maximal_cliques PROTO((spp_cg_problem *spp, int pos, double etol));
00166 void spp_delete_node PROTO((spp_cg_problem *spp, int del_ind,
00167 int *pcurrent_nodenum, int *current_indices,
00168 int *current_degrees, double *current_values));
00169 int choose_next_node PROTO((spp_cg_problem *spp, int current_nodenum,
00170 int *current_indices, int *current_degrees,
00171 double *current_values));
00172 int find_violated_star_cliques PROTO((spp_cg_problem *spp, double etol));
00173 int find_violated_row_cliques PROTO((spp_cg_problem *spp, double etol));
00174 int greedy_maximal_clique PROTO((spp_cg_problem *spp, cut_data *new_cut,
00175 int length, int *indices, int pos, double etol));
00176 int find_violated_odd_holes PROTO((spp_cg_problem *spp, double etol));
00177 double find_chordless_oh PROTO((spp_cg_problem *spp, frac_graph *fgraph,
00178 int u, int w, int *oh));
00179 void min_path_to_root PROTO((spp_cg_problem *spp, frac_graph *fgraph,
00180 int u, int *path_u, double *pcost));
00181 double lift_nonviolated_odd_hole PROTO((spp_cg_problem *spp, int oh_len,
00182 int *oh, double lhs_oh, int *phub_len,
00183 int *hubs, int *hub_coef));
00184 int max_lhs_of_lifted_odd_hole PROTO((spp_cg_problem *spp, int oh_len,
00185 int *oh, int hub, int hub_len, int *hubs,
00186 int *hub_coef, char *label, int pos));
00187 int find_violated_odd_antiholes PROTO((spp_cg_problem *spp, double etol));
00188 double lift_nonviolated_odd_antihole PROTO((spp_cg_problem *spp, int oah_len,
00189 int *oah, double lhs_oah,
00190 int *phub_len, int *hubs,
00191 int *hub_coef, double etol));
00192 void translate_cut_to_indices PROTO((spp_cg_problem *spp, cut_data *cut));
00193 void rotate_odd_hole PROTO((int length, int *indices, int *itmp));
00194
00195 #endif