44 #if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER) 61 #define VERBOSE MSG_INFO 70 #define MAX_PATH_LEN PATH_MAX 71 #elif defined(_MAX_PATH) 72 #define MAX_PATH_LEN _MAX_PATH 73 #elif defined(_POSIX_PATH_MAX) 74 #define MAX_PATH_LEN _POSIX_PATH_MAX 76 #define MAX_PATH_LEN 1024 83 #define MAX_LINE_LEN 1024 84 #define MAX_KEYWORD_LEN 64 85 #define MAX_STRING_LEN 256 86 #define MAX_ARGUMENTS 8 95 #define KEY_SECTION 0001 99 #define KEY_COMMENT_NAME 1001 100 #define KEY_COMMENT_DATE 1002 101 #define KEY_COMMENT_CREATOR 1003 102 #define KEY_COMMENT_PROBLEM 1004 103 #define KEY_COMMENT_REMARK 1005 105 #define KEY_GRAPH_NODES 2001 106 #define KEY_GRAPH_EDGES 2002 107 #define KEY_GRAPH_E 2003 108 #define KEY_GRAPH_A 2004 109 #define KEY_GRAPH_AA 2005 110 #define KEY_GRAPH_OBSTACLES 2006 111 #define KEY_GRAPH_HOPLIMIT 2007 113 #define KEY_TERMINALS_END 3001 114 #define KEY_TERMINALS_TERMINALS 3002 115 #define KEY_TERMINALS_T 3003 116 #define KEY_TERMINALS_TP 3004 117 #define KEY_TERMINALS_ROOT 3005 118 #define KEY_TERMINALS_ROOTP 3006 119 #define KEY_TERMINALS_TG 3007 120 #define KEY_TERMINALS_GROUPS 3008 121 #define KEY_TERMINALS_TR 3009 123 #define KEY_COORDINATES_DD 4001 124 #define KEY_COORDINATES_DDD 4002 125 #define KEY_COORDINATES_DDDD 4003 126 #define KEY_COORDINATES_DDDDD 4004 127 #define KEY_COORDINATES_DDDDDD 4005 128 #define KEY_COORDINATES_DDDDDDD 4006 129 #define KEY_COORDINATES_DDDDDDDD 4007 131 #define KEY_COORDINATES_END 4011 132 #define KEY_COORDINATES_GRID 4012 134 #define KEY_SOLUTION_VALUE 4021 135 #define KEY_SOLUTION_DATE 4022 136 #define KEY_SOLUTION_TIME 4023 137 #define KEY_SOLUTION_STEINER 4024 138 #define KEY_SOLUTION_S 4025 140 #define KEY_PRESOLVE_DATE 5001 141 #define KEY_PRESOLVE_FIXED 5002 142 #define KEY_PRESOLVE_LOWER 5003 143 #define KEY_PRESOLVE_UPPER 5004 144 #define KEY_PRESOLVE_TIME 5005 145 #define KEY_PRESOLVE_EA 5006 146 #define KEY_PRESOLVE_EC 5007 147 #define KEY_PRESOLVE_ED 5008 148 #define KEY_PRESOLVE_ES 5009 151 #define KEY_NODEWEIGHTS_NW 6000 152 #define KEY_NODEWEIGHTS_END 6001 154 #define KEY_MAXDEGS_MD 8000 156 #define KEY_OBSTACLES_RR 9000 157 #define KEY_OBSTACLES_END 9001 159 #define KEY_HOPCONS_LIM 10000 160 #define KEY_HOPCONS_FACTOR 10001 162 #define KEY_TREE_S 11000 174 {
"comment.end",
KEY_END, NULL },
193 {
"graph.end",
KEY_END, NULL },
201 {
"maximumdegrees.end",
KEY_END, NULL },
214 {
"presolve.end",
KEY_END, NULL },
218 {
"presolve.orgnodes",
KEY_EOF,
"n" },
223 {
"solution.end",
KEY_END, NULL },
250 #define FLAG_OPTIONAL 1 251 #define FLAG_REQUIRED 2 253 #define SECTION_MISSING 0 254 #define SECTION_EXISTEND 1 304 for( t = s; *s !=
'\0'; s++ )
305 *s = (
char)tolower(*s);
325 const char* intro[] = {
"Fatal Error",
"Error ",
"Warning ",
328 const char* header =
"*** %s File \"%s\" line %05d: ";
330 assert(type <
sizeof(intro) /
sizeof(
char*));
331 assert(curf !=
NULL);
333 assert(curf->
line >= 0);
336 va_start(params, msg);
340 (void)fprintf(stderr, header, intro[type], curf->
filename, curf->
line);
341 (void)vfprintf(stderr, msg, params);
342 (void)fputc(
'\n', stderr);
358 assert(elem !=
NULL);
359 assert(((
const struct key*)elem)->
keyword !=
NULL);
361 return(strcmp((
const char*)key, ((
const struct key*)elem)->
keyword));
375 assert(section !=
NULL);
376 assert(((
const struct section*)section)->name !=
NULL);
378 return(strcmp((
const char*)key, ((
const struct section*)section)->name));
394 const char* err_missmatch_v =
"Wrong Syntax";
395 const char* msg_hello_ss =
"get_arguments(\"%s\", \"%s\")";
397 int missmatch =
FALSE;
401 assert(format !=
NULL);
403 assert(para !=
NULL);
409 while((*s !=
'\0') && (*format !=
'\0') && !missmatch)
418 while((*s !=
'\0') && !isdigit(*s) && (*s !=
'.') && (*s !=
'-') )
426 assert(isdigit(*s) || (*s ==
'.') || (*s ==
'-'));
433 while(isdigit(*s) || (*s ==
'.') || (*s ==
'-'))
439 else if( decimal_spaces != -1 )
440 para->
n = para->
n +
pow(10.0, (
double) -(++decimal_spaces)) * (*s -
'0');
442 para->
n = para->
n * 10 + (*s -
'0');
446 para->
n = (-1) * para->
n;
453 while((*s !=
'\0') && (*s !=
'\"'))
503 unsigned char main_file
506 const char* err_cantopen_s =
"%s.";
507 const char* err_noheader_v =
"Wrong file header.";
508 const char* err_nomagic_d =
"Wrong Magic-Number %d.";
509 const char* err_wrongtype_ss =
"Wrong file type. Found %s, expected %s.";
510 const char* msg_version_dd =
"Format Version %d.%d.";
518 assert(curf !=
NULL);
532 (void)sprintf(fillname_gr,
"%s.%s",
536 if ((curf->
fp = fopen(fillname_gr,
"r")) !=
NULL)
538 (void)sprintf(curf->
filename,
"%s", fillname_gr);
545 (void) sprintf(fillname_stp,
"%s.%s", curf->
filename,
"stp");
547 if ((curf->
fp = fopen(fillname_stp,
"r")) ==
NULL)
552 (void)sprintf(curf->
filename,
"%s", fillname_stp);
559 if (!main_file && (curf->
fp = fopen(curf->
filename,
"r")) ==
NULL)
564 else if (fscanf(curf->
fp,
"%8x %3s File, STP Format Version %2d.%2d \n",
565 &magic, type, &version_major, &version_minor) != 4)
598 const char* pathname,
599 const char* basename,
604 const char* err_missing_v =
"Section name missing";
605 const char* err_badsect_s =
"Unknown section name [%s]";
606 const char* err_required_s =
"Can't access required file [%s]";
615 assert(pathname !=
NULL);
616 assert(basename !=
NULL);
617 assert(curf !=
NULL);
618 assert(save !=
NULL);
626 if( (tokens = sscanf(s,
"%63s %63s %s", sectname, dummy, inclname)) < 1 )
632 if( strcmp(
strlower(sectname),
"comments") == 0 )
646 if( tokens == 1 || (tokens == 2 && strcmp(
strlower(sectname),
"tree") == 0) )
654 (void)sprintf(temp.
filename,
"%s%s%c%s",
656 (*inclname ==
'\0') ? basename : inclname,
659 #if defined(_MSC_VER) 673 temp.
section = §ion_table[0];
699 double*** coordinates,
708 if( *coordinates ==
NULL )
711 assert(termcount !=
NULL);
712 assert(grid_dim !=
NULL);
713 assert(*termcount == 0);
721 for( i = 0; i < dim; i++ )
725 for( i = 0; i < dim; i++ )
726 (*coordinates)[i][*termcount] = (double)para[i + 1].n;
745 length = (int) strlen(str_number);
749 for( i = 0; i < length; i++ )
751 if( str_number[length - i - 1] !=
'0' )
756 for( i = 0; i < length; i++ )
763 order = length - ints - trail_zeroes - 1;
772 double** coordinates,
773 int*** scaled_coords,
785 assert(coordinates !=
NULL);
787 assert(grid_dim > 1);
791 for( i = 0; i < grid_dim; i++ )
792 for( j = 0; j <
nnodes; j++ )
796 if( max_order < tmp )
802 *scale_order = max_order;
803 scale_factor = (int)
pow(10.0, (
double) max_order);
805 for( i = 0; i < grid_dim; i++ )
808 for( j = 0; j <
nnodes; j++ )
810 (*scaled_coords)[i][j] = (int) (coordinates[i][j] * scale_factor);
828 const char* err_unknown_s =
"Unknown keyword [%s]";
829 const char* err_include_v =
"Include in included file";
830 const char* err_missing_s =
"Required section %s missing";
831 const char* msg_newsect_s =
"Processing Section %s";
832 const char* msg_keyword_sd =
"Found Keyword \"%s\", code = %d";
833 const char* err_badedge_ddd =
"Bad edge %d-%d (%d nodes)";
834 const char* err_badroot_dd =
"Bad root %d (%d nodes)";
835 const char* err_baddeg_dd =
"More degree constraints (%d) than nodes (%d)";
836 const char* msg_finish_dddd =
"Nodes: %d Edges: %d Terminals: %d Source=%d\n";
838 const char* endofline =
"#;\n\r";
839 const char* separator =
" \t:=";
852 int stop_input =
FALSE;
857 double** coordinates =
NULL;
873 int obstacle_counter = 0;
874 int** scaled_coordinates =
NULL;
875 int** obstacle_coords =
NULL;
878 assert(file != NULL);
882 for( i = 1; i < (int)(
sizeof(section_table) /
sizeof(section_table[0])); i++ )
887 (void)strcpy(pathname, file);
891 if( (s = strrchr(pathname,
DIRSEP[0])) == NULL )
895 (void)strcpy(basename, pathname);
903 (void)strcpy(basename, s);
909 if ((s = strrchr(basename,
EXTSEP)) != NULL)
914 curf.
section = §ion_table[0];
917 (void)sprintf(curf.
filename,
"%s%s",
927 while((curf.
fp != NULL) && !stop_input)
931 if ((s = fgets(buffer, (
int)
sizeof(buffer), curf.
fp)) == NULL)
935 (void)fclose(curf.
fp);
960 if ((t = strpbrk(s, endofline)) != NULL)
972 i = (int)strlen(keyword);
978 keyword[i] = (
char)tolower(*s);
984 while((*s !=
'\0') && (strchr(separator, *s) != NULL))
987 if( strcmp(keyword,
"comments") == 0 )
988 keyword[i - 1] =
'\0';
992 p = (
struct key*)bsearch(keyword, keyword_table,
993 sizeof(keyword_table) /
sizeof(
struct key),
994 sizeof(struct key), key_cmp);
1000 char newformat[5] =
"";
1008 strcpy(newformat,
"nn");
1010 strcpy(newformat,
"nnnn");
1012 if( p->
format == NULL || !
get_arguments(&curf, (
const char*)( newformat[0] !=
'\0' ? newformat : p->
format ), s, para) )
1019 if (save.
fp == NULL)
1031 curf.
section = §ion_table[0];
1040 for(i = 0; (unsigned)i <
sizeof(section_table) /
sizeof(
struct section); i++)
1054 (void)printf(
"Problem: [%s]\n", para[0].s);
1055 if( strcmp(para[0].s,
"SPG") == 0 )
1057 else if( strcmp(para[0].s,
"PCSPG") == 0
1058 || strcmp(para[0].s,
"Prize-Collecting Steiner Problem in Graphs") == 0 )
1060 else if( strcmp(para[0].s,
"RPCST") == 0
1061 || strcmp(para[0].s,
"Rooted Prize-Collecting Steiner Problem in Graphs") == 0 )
1063 else if( strcmp(para[0].s,
"NWSPG") == 0 )
1065 else if( strcmp(para[0].s,
"DCST") == 0 )
1067 else if( strcmp(para[0].s,
"RSMT") == 0 )
1069 else if( strcmp(para[0].s,
"OARSMT") == 0 )
1071 else if( strcmp(para[0].s,
"Maximum Node Weight Connected Subgraph") == 0
1072 || strcmp(para[0].s,
"MWCS") == 0 )
1074 else if( strcmp(para[0].s,
"Rooted Maximum Node Weight Connected Subgraph") == 0
1075 || strcmp(para[0].s,
"RMWCS") == 0 )
1077 else if( strcmp(para[0].s,
"HCDST") == 0 )
1079 else if( strcmp(para[0].s,
"SAP") == 0 )
1081 else if( strcmp(para[0].s,
"GSTP") == 0 )
1085 (void)printf(
"Comment: [%s]\n", para[0].s);
1086 if( strcmp(para[0].s,
"Transformed") == 0 )
1090 assert(para != NULL);
1091 nodes = (int)para[0].n;
1094 nobstacles = (int)para[0].n;
1095 if( nobstacles > 0 )
1099 hoplimit = (int)para[0].n;
1103 edges = (int)para[0].n;
1108 if( (
int)para[0].
n > nodes || (int)para[1].n > nodes )
1111 (
int)para[0].n, (
int)para[1].n, nodes);
1126 for( i = 0; i < nodes; i++ )
1138 tail = (int)para[0].n - 1;
1139 head = (int)para[1].n - 1;
1142 if( g->
tail[i] == tail )
1147 g->
cost[i] = (double)para[2].n;
1150 else if( stp_type ==
STP_SAP )
1152 graph_edge_add(scip, g, (
int)para[0].n - 1, (
int)para[1].n - 1, (
double)para[2].n, (
double)para[3].n);
1156 graph_edge_add(scip, g, (
int)para[0].n - 1, (
int)para[1].n - 1, 0.0, 0.0);
1164 : (
double)para[3].
n);
1169 assert((
int)para[0].n >= 0);
1171 if( degcount < nodes )
1178 g->
maxdeg[degcount++] = (int)para[0].n;
1188 nodeweight = (double) para[0].n;
1190 assert(presol != NULL);
1196 presol->
fixed += nodeweight;
1200 g->
cost[i] += nodeweight;
1204 curf.
section = §ion_table[0];
1207 assert(nobstacles > 0);
1208 if( obstacle_coords == NULL )
1210 assert(obstacle_counter == 0);
1212 for( i = 0; i < 4; i++ )
1215 for( i = 0; i < 4; i++ )
1216 obstacle_coords[i][obstacle_counter] = (
int)para[i].
n;
1220 curf.
section = §ion_table[0];
1222 if( obstacle_counter != nobstacles )
1224 message(
MSG_FATAL, &curf,
"obstacle number does not match coordinates \n");
1228 if( scaled_coordinates == NULL )
1237 message(
MSG_FATAL, &curf,
"Obstacle avoiding RSMT problems are currently not supported in this format \n");
1241 if( obstacle_coords != NULL )
1242 for( i = 3; i >= 0; i-- )
1247 if( transformed == 0 )
1251 assert(nodes == termcount);
1265 assert(nodes == termcount);
1286 curf.
section = §ion_table[0];
1289 terms = (int)para[0].n;
1294 assert(terms == nodes);
1296 if( g->
prize == NULL )
1302 tgroups = (int)para[0].n;
1303 presol->
fixed -= tgroups * 1e+8;
1304 for( i = 0; i < tgroups; i++ )
1312 if ((
int)para[0].n <= nodes)
1314 g->
source = (int)para[0].n - 1;
1320 (
int)para[0].n, nodes);
1327 g->
source = (int)para[0].n - 1;
1330 if( g->
prize == NULL )
1339 assert(g->
prize != NULL);
1340 g->
prize[(int)para[0].n - 1] = (
double)para[1].
n;
1341 if(
SCIPisGT(scip, (
double)para[1].n, 0.0) )
1342 presol->
fixed -= (
double)para[1].
n;
1350 assert(tgroups > 0);
1351 graph_edge_add(scip, g, (
int)para[0].n - 1, g->
knots - tgroups + (
int)para[1].
n - 1, 1e+8, 1e+8);
1357 if( g->
prize == NULL )
1363 g->
prize[(int)para[0].n - 1] = (
double)para[1].
n;
1369 assert(g->
prize != NULL);
1371 presol->
fixed -= (double)para[1].n;
1405 assert(grid_dim > 1);
1407 curf.
section = §ion_table[0];
1408 if( termcount != nodes )
1418 if( coordinates != NULL )
1419 for( i = 0; i < grid_dim; i++ )
1435 presol->
fixed += (double)para[0].n;
1438 (void)printf(
"Found presolve information %s\n",
1443 presol->
lower = (double)para[0].n;
1447 presol->
upper = (double)para[0].n;
1451 presol->
time = (int)para[0].n;
1473 if( save.
fp != NULL )
1474 (void)fclose(save.
fp);
1479 if( curf.
fp != NULL )
1480 (void)fclose(curf.
fp);
1488 for( i = 0; i < g->
knots; i++ )
1489 if ((g->
term[i] == 0)
1502 (void)printf(msg_finish_dddd,
1510 if( obstacle_coords != NULL )
1512 for( i = 0; i < 4; i++ )
#define KEY_COMMENT_CREATOR
#define KEY_NODEWEIGHTS_NW
SCIP_RETCODE graph_pc_2mw(SCIP *, GRAPH *, SCIP_Real *)
SCIP_RETCODE graph_pc_init(SCIP *, GRAPH *, int, int)
static SCIP_RETCODE scale_coords(double **coordinates, int ***scaled_coords, int *scale_order, int nnodes, int grid_dim)
#define KEY_NODEWEIGHTS_END
#define SCIPfreeMemoryArrayNull(scip, ptr)
static void message(unsigned int type, const CURF *curf, const char *msg,...)
SCIP_RETCODE graph_load(SCIP *scip, GRAPH **graph, const char *file, PRESOL *presol)
SCIP_Bool graph_valid(const GRAPH *)
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
static int sec_cmp(const void *key, const void *section)
#define SCIPallocMemoryArray(scip, ptr, num)
SCIP_RETCODE graph_obstgrid_create(SCIP *, GRAPH **, int **, int **, int, int, int, int)
#define KEY_OBSTACLES_END
#define KEY_COMMENT_REMARK
static SCIP_RETCODE init_coordinates(SCIP *scip, GRAPH *g, PARA *para, double ***coordinates, int *grid_dim, int *termcount, int dim, int nodes)
#define KEY_SOLUTION_DATE
static char * strlower(char *s)
int SCIPsnprintf(char *t, int len, const char *s,...)
enum SCIP_Retcode SCIP_RETCODE
#define KEY_TERMINALS_ROOTP
#define KEY_PRESOLVE_LOWER
char filename[MAX_PATH_LEN]
#define KEY_COORDINATES_END
void graph_knot_chg(GRAPH *, int, int)
static int open_file(CURF *curf, unsigned char main_file)
#define KEY_SOLUTION_VALUE
SCIP_RETCODE graph_pc_2rmw(SCIP *, GRAPH *)
#define KEY_TERMINALS_ROOT
#define KEY_COORDINATES_DD
#define KEY_PRESOLVE_DATE
#define KEY_COORDINATES_DDDDDDDD
SCIP_RETCODE graph_pc_2rpc(SCIP *, GRAPH *)
#define KEY_HOPCONS_FACTOR
#define SCIPfreeBufferArrayNull(scip, ptr)
#define KEY_TERMINALS_TERMINALS
#define KEY_COORDINATES_DDDD
static int get_scale_order(SCIP_Real number)
#define KEY_COORDINATES_DDDDD
#define KEY_PRESOLVE_UPPER
#define SCIPallocBufferArray(scip, ptr, num)
#define KEY_SOLUTION_TIME
#define KEY_COORDINATES_DDDDDD
#define KEY_SOLUTION_STEINER
static const struct key keyword_table[]
static struct section section_table[]
#define KEY_GRAPH_HOPLIMIT
static int get_arguments(const CURF *curf, const char *format, const char *s, PARA *para)
includes various files containing graph methods used for Steiner tree problems
#define KEY_TERMINALS_END
static int start_section(const char *pathname, const char *basename, CURF *curf, CURF *save, const char *s)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define KEY_PRESOLVE_TIME
#define KEY_COMMENT_PROBLEM
#define KEY_PRESOLVE_FIXED
void graph_knot_add(GRAPH *, int)
#define KEY_GRAPH_OBSTACLES
#define KEY_COORDINATES_GRID
#define KEY_COORDINATES_DDDDDDD
SCIP_RETCODE graph_pc_2pc(SCIP *, GRAPH *)
#define KEY_COORDINATES_DDD
#define KEY_TERMINALS_GROUPS
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
static int key_cmp(const void *key, const void *elem)
SCIP_RETCODE graph_grid_create(SCIP *, GRAPH **, int **, int, int, int)
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)