/*===========================================================================*/
/*                                                                           */
/* This file is part of a demonstration application for use with the         */
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
/* Capacitated Network Routing Problems.                                     */
/*                                                                           */
/* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved.                  */
/*                                                                           */
/* This application was developed by Ted Ralphs (tkralphs@lehigh.edu)        */
/*                                                                           */
/* This software is licensed under the Common Public License. Please see     */
/* accompanying file for terms.                                              */
/*                                                                           */
/*===========================================================================*/

#ifndef _CUT_GEN_USER_H
#define _CUT_GEN_USER_H

/* system include files */
#include <stdio.h>

/* SYMPHONY include files */
#include "sym_types.h"
#include "sym_proto.h"

/* CNRP include files */
#include "network.h"
#include "cnrp_cg_params.h"

typedef struct CG_CNRP_SPEC{
   cnrp_cg_params par;
   int           dg_id;    /* contains the tid of the graphics window*/
   int           vertnum;  /* the number of nodes in the problem,
			      including the depot                */
   double       *demand;   /* a list of the customer demands*/
   double        capacity; /* the capacity of the trucks*/
   int           numroutes;/* contains the number of routes that the problem
			      is to be solved with. can be prespecified.  */
   int          *edges;    /* contains a list of the edges in the current
			      subproblem*/
   network      *n;
   int           orig_edgenum;
   int          *cost;
   int          *ref;      /* the last five  are for the shrinking routines; */
   char         *in_set;   /* they are here to optimize/speed up things */
   double       *new_demand;
   double       *cut_val;
   char         *cut_list;


#ifdef CHECK_CUT_VALIDITY
   int           feas_sol_size;
   int          *feas_sol;
#endif
}cg_cnrp_spec;

/*===========================================================================*/
/*========================= Other user subroutines =========================*/
/*===========================================================================*/

int check_connectivity PROTO((network *n, double etol, double capacity,
			      int numroutes, char mult, int *num_cuts,
			      int *alloc_cuts, cut_data ***cuts));

int check_flow_connectivity PROTO((network *n, double etol, double capacity,
				   int numroutes, char mult, int *num_cuts,
				   int *alloc_cuts, cut_data ***cuts));

/*===========================================================================*/
/*=============================== shrink.c ==================================*/
/*===========================================================================*/

int reduce_graph PROTO((network *n, double etol, double *demand,
			double capacity, int mult, cut_data *new_cut,
			int *num_cuts, int *alloc_cuts, cut_data ***cuts));
int greedy_shrinking1 PROTO((network *n, double truck_cap, double etol,
			     int max_num_cuts, cut_data *new_cut,
			     int *compnodes, int *compmembers, int compnum,
			     char *in_set, double *cut_val,int *ref,
			     char *cut_list, double *demand, int mult,
			     int *num_cuts, int *alloc_cuts,
			     cut_data ***cuts));
int greedy_shrinking1_dicut PROTO((network *n, double truck_cap, double etol,
			     int max_num_cuts, cut_data *new_cut,
			     int *compnodes, int *compmembers, int compnum,
			     char *in_set, double *cut_val,int *ref,
			     char *cut_list, double *demand, int mult,
			     int *num_cuts, int *alloc_cuts,
			     cut_data ***cuts));
int greedy_shrinking6 PROTO((network *n, double truck_cap,
			     double etol, cut_data *new_cut,
			     int *compnodes,
			     int *compmembers, int compnum, char *in_set,
			     double *cut_val,int *ref, char *cut_list,
			     int max_num_cuts, double *demand, int trial_num,
			     double prob, int mult, int *num_cuts,
			     int *alloc_cuts, cut_data ***cuts));
int greedy_shrinking6_dicut PROTO((network *n, double truck_cap,
			     double etol, cut_data *new_cut,
			     int *compnodes,
			     int *compmembers, int compnum, char *in_set,
			     double *cut_val,int *ref, char *cut_list,
			     int max_num_cuts, double *demand, int trial_num,
			     double prob, int mult, int *num_cuts,
			     int *alloc_cuts, cut_data ***cuts));
int greedy_shrinking1_one PROTO((network *n, double truck_cap,
				 double etol, int max_num_cuts,
				 cut_data *new_cut, char *in_set,
				 double *cut_val, char *cut_list,
				 int num_routes, double *demand,
				 int mult, int *num_cuts,
				 int *alloc_cuts, cut_data ***cuts));
int greedy_shrinking6_one PROTO((network *n, double truck_cap,
				 double etol, cut_data *new_cut,
				 char *in_set, double *cut_val, int num_routes,
				 char *cut_list, int max_num_cuts,
				 double *demand,int trial_num, double prob,
				 int mult, int *num_cuts,
				 int *alloc_cuts, cut_data ***cuts));
int greedy_shrinking2_one PROTO((network *n, double truck_cap,
				 double etol, cut_data *new_cut,
				 char *in_set, double *cut_val, int num_routes,
				 double *demand, int mult, int *num_cuts,
				 int *alloc_cuts, cut_data ***cuts));

/*===========================================================================*/
/*============================ biconnected.c ================================*/
/*===========================================================================*/

void depth_first_search PROTO((vertex *v, int *count1, int *count2));
int biconnected PROTO((network *n, int *compnodes, double *compdemands,
		       double *compcuts));
void compute_comp_nums PROTO((vertex *v, int parent_comp, int *num_comps,
		       char parent_is_art_point));
int tsp_cuts PROTO((network *n, int verbosity, char tsp_prob, int which_cuts,
		    cut_data ***cuts, int *num_cuts, int *alloc_cuts));

#endif
