00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef _CUT_GEN_USER_H
00017 #define _CUT_GEN_USER_H
00018
00019
00020 #include <stdio.h>
00021
00022
00023 #include "sym_types.h"
00024 #include "sym_proto.h"
00025
00026
00027 #include "network.h"
00028 #include "cnrp_cg_params.h"
00029
00030 typedef struct CG_CNRP_SPEC{
00031 cnrp_cg_params par;
00032 int dg_id;
00033 int vertnum;
00034
00035 double *demand;
00036 double capacity;
00037 int numroutes;
00038
00039 int *edges;
00040
00041 network *n;
00042 int orig_edgenum;
00043 int *cost;
00044 int *ref;
00045 char *in_set;
00046 double *new_demand;
00047 double *cut_val;
00048 char *cut_list;
00049
00050
00051 #ifdef CHECK_CUT_VALIDITY
00052 int feas_sol_size;
00053 int *feas_sol;
00054 #endif
00055 }cg_cnrp_spec;
00056
00057
00058
00059
00060
00061 int check_connectivity PROTO((network *n, double etol, double capacity,
00062 int numroutes, char mult, int *num_cuts,
00063 int *alloc_cuts, cut_data ***cuts));
00064
00065 int check_flow_connectivity PROTO((network *n, double etol, double capacity,
00066 int numroutes, char mult, int *num_cuts,
00067 int *alloc_cuts, cut_data ***cuts));
00068
00069
00070
00071
00072
00073 int reduce_graph PROTO((network *n, double etol, double *demand,
00074 double capacity, int mult, cut_data *new_cut,
00075 int *num_cuts, int *alloc_cuts, cut_data ***cuts));
00076 int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
00077 int max_num_cuts, cut_data *new_cut,
00078 int *compnodes, int *compmembers, int compnum,
00079 char *in_set, double *cut_val,int *ref,
00080 char *cut_list, double *demand, int mult,
00081 int *num_cuts, int *alloc_cuts,
00082 cut_data ***cuts));
00083 int greedy_shrinking1_dicut PROTO((network *n, double truck_cap, double etol,
00084 int max_num_cuts, cut_data *new_cut,
00085 int *compnodes, int *compmembers, int compnum,
00086 char *in_set, double *cut_val,int *ref,
00087 char *cut_list, double *demand, int mult,
00088 int *num_cuts, int *alloc_cuts,
00089 cut_data ***cuts));
00090 int greedy_shrinking6 PROTO((network *n, double truck_cap,
00091 double etol, cut_data *new_cut,
00092 int *compnodes,
00093 int *compmembers, int compnum, char *in_set,
00094 double *cut_val,int *ref, char *cut_list,
00095 int max_num_cuts, double *demand, int trial_num,
00096 double prob, int mult, int *num_cuts,
00097 int *alloc_cuts, cut_data ***cuts));
00098 int greedy_shrinking6_dicut PROTO((network *n, double truck_cap,
00099 double etol, cut_data *new_cut,
00100 int *compnodes,
00101 int *compmembers, int compnum, char *in_set,
00102 double *cut_val,int *ref, char *cut_list,
00103 int max_num_cuts, double *demand, int trial_num,
00104 double prob, int mult, int *num_cuts,
00105 int *alloc_cuts, cut_data ***cuts));
00106 int greedy_shrinking1_one PROTO((network *n, double truck_cap,
00107 double etol, int max_num_cuts,
00108 cut_data *new_cut, char *in_set,
00109 double *cut_val, char *cut_list,
00110 int num_routes, double *demand,
00111 int mult, int *num_cuts,
00112 int *alloc_cuts, cut_data ***cuts));
00113 int greedy_shrinking6_one PROTO((network *n, double truck_cap,
00114 double etol, cut_data *new_cut,
00115 char *in_set, double *cut_val, int num_routes,
00116 char *cut_list, int max_num_cuts,
00117 double *demand,int trial_num, double prob,
00118 int mult, int *num_cuts,
00119 int *alloc_cuts, cut_data ***cuts));
00120 int greedy_shrinking2_one PROTO((network *n, double truck_cap,
00121 double etol, cut_data *new_cut,
00122 char *in_set, double *cut_val, int num_routes,
00123 double *demand, int mult, int *num_cuts,
00124 int *alloc_cuts, cut_data ***cuts));
00125
00126
00127
00128
00129
00130 void depth_first_search PROTO((vertex *v, int *count1, int *count2));
00131 int biconnected PROTO((network *n, int *compnodes, double *compdemands,
00132 double *compcuts));
00133 void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
00134 char parent_is_art_point));
00135 int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
00136 cut_data ***cuts, int *num_cuts, int *alloc_cuts));
00137
00138 #endif